Work on this exercise locally
This web app is a reference guide — you can read instructions, browse starter code, and view tests here. To actually complete the exercise, you need to work in your local development environment.
1Clone the repo:
git clone https://github.com/weihaoqu/program-analysis-bootcamp-student2Edit the starter file in your editor (VS Code, Vim, etc.) — replace
failwith "TODO" with your implementation.3Run the tests:
dune runtest modules/module2-ast/exercises/traversal-algorithmsTraversal Algorithms
4. Exercise 2: Traversal Algorithms (27 tests)
Goal: Implement three classic tree traversal strategies and two visitor-style operations on the AST.
Time: ~30 minutes
Files to edit:
exercises/traversal-algorithms/starter/traversals.ml-- pre-order, post-order, and BFS traversalsexercises/traversal-algorithms/starter/visitor.ml--count_nodesandevaluate
Dependencies: shared_ast
The three traversals
Each traversal walks a stmt list and collects a string label for every node
visited. Labels look like:
- Statements:
"Assign","If","While","Return","Print","Block" - Expressions:
"IntLit(3)","BoolLit(true)","Var(x)","BinOp(+)","UnaryOp(-)","Call(f)"
Example: Assign("x", BinOp(Add, IntLit 1, IntLit 2))
Pre-order: ["Assign"; "BinOp(+)"; "IntLit(1)"; "IntLit(2)"]
Visit node FIRST, then children left-to-right.
Post-order: ["IntLit(1)"; "IntLit(2)"; "BinOp(+)"; "Assign"]
Visit children FIRST, then the node itself.
BFS: ["Assign"; "BinOp(+)"; "IntLit(1)"; "IntLit(2)"]
All nodes at depth d before any at depth d+1.
What to implement
In traversals.ml:
| # | Function | Hint |
|---|---|---|
| 1 | label_of_expr e | Pattern match on expr and return the label string, e.g., IntLit n returns "IntLit(" ^ string_of_int n ^ ")" |
| 2 | label_of_stmt s | Pattern match on stmt and return just the constructor name, e.g., Assign _ returns "Assign" |
| 3 | pre_order stmts | Emit current node label, then recurse into children. Use mutual recursion with helpers for expr and stmt |
| 4 | post_order stmts | Recurse into children first, then emit the current node label |
| 5 | bfs stmts | Use the OCaml Queue module. You need a sum type to handle both stmt and expr nodes in the same queue |
In visitor.ml:
| # | Function | Hint |
|---|---|---|
| 6 | count_nodes stmts | Walk the AST and count each constructor name (without parameters). Return an association list like [("Assign", 2); ("BinOp", 3); ...] |
| 7 | evaluate e | Evaluate constant integer expressions. Return Some int for pure arithmetic, None if variables/booleans/calls/comparisons appear. Division by zero returns None |
Run tests
dune runtest modules/module2-ast/exercises/traversal-algorithms/
Starter output: EEEEEEEEEEEEEEEEEEEEEEEEEEE (27 errors -- all TODOs)
Hints
- Pre-order/Post-order: Write mutually recursive helpers
pre_order_expr,pre_order_stmt,pre_order_stmts(and likewise for post-order). For pre-order, cons the label before the recursive results; for post-order, append the label after. - BFS: Define a sum type like
type node = Stmt_node of stmt | Expr_node of expr. Seed the queue with all top-level statements, then dequeue a node, emit its label, and enqueue its children. Repeat until empty. evaluate: UseOption.bindto chain recursive calls. If either operand of aBinOpreturnsNone, the whole expression isNone.
Starter Files
starter
Test Files
tests
starter/traversals.ml
Read-only
Loading editor...
Work on this exercise locally
This web app is a reference guide — you can read instructions, browse starter code, and view tests here. To actually complete the exercise, you need to work in your local development environment.
1Clone the repo:
git clone https://github.com/weihaoqu/program-analysis-bootcamp-student2Edit the starter file in your editor (VS Code, Vim, etc.) — replace
failwith "TODO" with your implementation.3Run the tests:
dune runtest modules/module2-ast/exercises/traversal-algorithmsTraversal Algorithms
4. Exercise 2: Traversal Algorithms (27 tests)
Goal: Implement three classic tree traversal strategies and two visitor-style operations on the AST.
Time: ~30 minutes
Files to edit:
exercises/traversal-algorithms/starter/traversals.ml-- pre-order, post-order, and BFS traversalsexercises/traversal-algorithms/starter/visitor.ml--count_nodesandevaluate
Dependencies: shared_ast
The three traversals
Each traversal walks a stmt list and collects a string label for every node
visited. Labels look like:
- Statements:
"Assign","If","While","Return","Print","Block" - Expressions:
"IntLit(3)","BoolLit(true)","Var(x)","BinOp(+)","UnaryOp(-)","Call(f)"
Example: Assign("x", BinOp(Add, IntLit 1, IntLit 2))
Pre-order: ["Assign"; "BinOp(+)"; "IntLit(1)"; "IntLit(2)"]
Visit node FIRST, then children left-to-right.
Post-order: ["IntLit(1)"; "IntLit(2)"; "BinOp(+)"; "Assign"]
Visit children FIRST, then the node itself.
BFS: ["Assign"; "BinOp(+)"; "IntLit(1)"; "IntLit(2)"]
All nodes at depth d before any at depth d+1.
What to implement
In traversals.ml:
| # | Function | Hint |
|---|---|---|
| 1 | label_of_expr e | Pattern match on expr and return the label string, e.g., IntLit n returns "IntLit(" ^ string_of_int n ^ ")" |
| 2 | label_of_stmt s | Pattern match on stmt and return just the constructor name, e.g., Assign _ returns "Assign" |
| 3 | pre_order stmts | Emit current node label, then recurse into children. Use mutual recursion with helpers for expr and stmt |
| 4 | post_order stmts | Recurse into children first, then emit the current node label |
| 5 | bfs stmts | Use the OCaml Queue module. You need a sum type to handle both stmt and expr nodes in the same queue |
In visitor.ml:
| # | Function | Hint |
|---|---|---|
| 6 | count_nodes stmts | Walk the AST and count each constructor name (without parameters). Return an association list like [("Assign", 2); ("BinOp", 3); ...] |
| 7 | evaluate e | Evaluate constant integer expressions. Return Some int for pure arithmetic, None if variables/booleans/calls/comparisons appear. Division by zero returns None |
Run tests
dune runtest modules/module2-ast/exercises/traversal-algorithms/
Starter output: EEEEEEEEEEEEEEEEEEEEEEEEEEE (27 errors -- all TODOs)
Hints
- Pre-order/Post-order: Write mutually recursive helpers
pre_order_expr,pre_order_stmt,pre_order_stmts(and likewise for post-order). For pre-order, cons the label before the recursive results; for post-order, append the label after. - BFS: Define a sum type like
type node = Stmt_node of stmt | Expr_node of expr. Seed the queue with all top-level statements, then dequeue a node, emit its label, and enqueue its children. Repeat until empty. evaluate: UseOption.bindto chain recursive calls. If either operand of aBinOpreturnsNone, the whole expression isNone.