This fold(node) is supposed to fold every constant subexpression in an AST -- (2 * 3) + 4 should become ("num", 10), not stay as a tree with an unfolded 2 * 3 inside it. It works fine on the simple, one-level cases. It's silently wrong the moment a foldable subexpression is nested inside a larger one.

Your task: find the bug and fix it. Don't rewrite fold from scratch -- the overall approach is right, one specific thing about it is wrong.

fold(node) operates on the same two AST node shapes as the Parser exercise -- ("num", value) and ("binop", op, left, right) -- plus possibly other leaf shapes (e.g. ("var", name)) that aren't foldable and should come back unchanged.

Example that currently fails

fold(("binop", "+", ("binop", "*", ("num", 2), ("num", 3)), ("num", 4)))
# should be: ("num", 10)
# currently: ("binop", "+", ("binop", "*", ("num", 2), ("num", 3)), ("num", 4))
#            -- completely unchanged! the inner (2*3) never got a chance to fold.

Real-world grounding

• LLVM's constant folding: llvm/lib/Analysis/ConstantFolding.cpp

Real compilers fold constants at every stage of optimization, not just once -- an earlier pass might turn a non-constant expression into a constant one, so folding often runs repeatedly until nothing changes. This exercise is the single core operation that machinery is built on.