AST Transformations

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-student

2Edit 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/ast-transformations

6. Exercise 4: AST Transformations (30 tests)

Goal: Implement three pure AST-to-AST transformation passes: constant folding, variable renaming, and dead-code elimination.

Time: ~30 minutes

File to edit: exercises/ast-transformations/starter/transformations.ml

Dependencies: shared_ast

Also provided: exercises/ast-transformations/starter/build_sample_ast.ml -- small AST fragments used by the tests

What to implement

#	Function	What it does
1	`constant_fold expr`	Bottom-up: fold sub-expressions first, then if a `BinOp` has two `IntLit` (or `BoolLit`) children, compute the result. Handle arithmetic, comparison, logical, and unary operators
2	`rename_variable old_name new_name stmts`	Replace every `Var old_name` with `Var new_name` and every `Assign(old_name, ...)` with `Assign(new_name, ...)`. Recurse into all nested structures
3	`eliminate_dead_code stmts`	Two rules: (a) remove all statements after a `Return` in the same list; (b) replace `If(BoolLit true, then_b, _)` with `Block then_b` and `If(BoolLit false, _, else_b)` with `Block else_b`. Apply recursively into nested blocks

Constant folding examples

BinOp(Add, IntLit 2, IntLit 3)                     -->  IntLit 5
BinOp(Mul, IntLit 2, BinOp(Add, IntLit 1, IntLit 3))  -->  IntLit 8
BinOp(Add, Var "x", BinOp(Add, IntLit 2, IntLit 3))   -->  BinOp(Add, Var "x", IntLit 5)
BinOp(Lt, IntLit 3, IntLit 5)                      -->  BoolLit true
UnaryOp(Neg, IntLit 5)                              -->  IntLit (-5)
UnaryOp(Not, BoolLit true)                          -->  BoolLit false

Dead-code elimination examples

[Return (Some (IntLit 42)); Print [Var "x"]]
  -->  [Return (Some (IntLit 42))]

[If (BoolLit true, [Assign("x", IntLit 1)], [Assign("x", IntLit 2)])]
  -->  [Block [Assign("x", IntLit 1)]]

Run tests

dune runtest modules/module2-ast/exercises/ast-transformations/

Starter output: EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE (30 errors -- all TODOs, displayed as 28 due to terminal line truncation)

Hints

Constant folding: This is a bottom-up transformation. First recursively fold both operands, then check whether the result is two literals. Write a helper eval_binop : op -> expr -> expr -> expr that handles all operator cases (Add, Sub, Mul, Div, Lt, Gt, Eq, etc.). Return a BoolLit for comparison/logical operators and an IntLit for arithmetic. For logical operators (And, Or), also handle BoolLit operands.
Variable renaming: Write a helper rename_expr for expressions and rename_stmt for statements. Pattern match each constructor and rebuild it with the renamed parts. Remember to rename both the LHS of Assign and Var nodes inside expressions.
Dead-code elimination: Process the statement list left-to-right. If you encounter a Return, keep it and discard everything after it. For If nodes, check the condition -- if it is BoolLit true or BoolLit false, replace the whole If with a Block of the live branch. Recurse into If branches, While bodies, and Block contents.

Starter Files

starter

Test Files

tests

starter/build_sample_ast.ml

Read-only

Loading editor...

Work on this exercise locally

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit 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/ast-transformations