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/module0-warmup/exercises/types-and-recursionTypes and Recursion
4. Exercise 2: Types and Recursion (~25 min)
File: exercises/types-and-recursion/starter/main.ml
Run:
dune exec modules/module0-warmup/exercises/types-and-recursion/starter/main.exe
What You'll Implement
This exercise defines a tiny expression tree -- a miniature version of the AST you will work with in Modules 2-6:
type op = Add | Sub | Mul
type expr =
| Num of int
| Var of string
| BinOp of op * expr * expr
| Function | What It Does | Concept |
|---|---|---|
string_of_op | Converts op to "+", "-", "*" | Pattern matching |
string_of_expr | Pretty-prints expression tree | Recursive pattern matching |
count_nodes | Counts nodes in tree | Tree recursion |
depth | Computes tree depth | Tree recursion with max |
eval | Evaluates expr, returns int option | Option type |
substitute | Replaces Var with Num | Tree transformation |
vars_in | Collects variable names | List.sort_uniq |
is_constant | Checks if expr has no Vars | Using vars_in |
simplify | Constant folding optimization | Bottom-up transformation |
Hints
- When a function needs recursion, the stub says "add
[rec]when ready". Just changelettolet rec. - For
eval, match on(eval left, eval right)to handle theoptionpairs:match eval left, eval right with | Some l, Some r -> Some (... compute ...) | _ -> None - For
simplify, simplify children first, then check if both areNum.
Expected Output
=== Exercise 2: Types and Recursion ===
string_of_expr e1 = (2 + 3)
string_of_expr e2 = (x * (1 + y))
string_of_expr e3 = ((10 + 20) - 5)
count_nodes e1 = 3
count_nodes e2 = 5
depth e1 = 2
depth e2 = 3
eval e1 = Some 5
eval e2 = None
eval e3 = Some 25
substitute "x" 3 e2 = (3 * (1 + y))
eval (substitute "x" 3 e2) = None
vars_in e2 = [x; y]
is_constant e1 = true
is_constant e2 = false
simplify e3 = 25
simplify e2 = (x * (1 + y))
Done!
Starter Files
starter
starter/main.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/module0-warmup/exercises/types-and-recursionTypes and Recursion
4. Exercise 2: Types and Recursion (~25 min)
File: exercises/types-and-recursion/starter/main.ml
Run:
dune exec modules/module0-warmup/exercises/types-and-recursion/starter/main.exe
What You'll Implement
This exercise defines a tiny expression tree -- a miniature version of the AST you will work with in Modules 2-6:
type op = Add | Sub | Mul
type expr =
| Num of int
| Var of string
| BinOp of op * expr * expr
| Function | What It Does | Concept |
|---|---|---|
string_of_op | Converts op to "+", "-", "*" | Pattern matching |
string_of_expr | Pretty-prints expression tree | Recursive pattern matching |
count_nodes | Counts nodes in tree | Tree recursion |
depth | Computes tree depth | Tree recursion with max |
eval | Evaluates expr, returns int option | Option type |
substitute | Replaces Var with Num | Tree transformation |
vars_in | Collects variable names | List.sort_uniq |
is_constant | Checks if expr has no Vars | Using vars_in |
simplify | Constant folding optimization | Bottom-up transformation |
Hints
- When a function needs recursion, the stub says "add
[rec]when ready". Just changelettolet rec. - For
eval, match on(eval left, eval right)to handle theoptionpairs:match eval left, eval right with | Some l, Some r -> Some (... compute ...) | _ -> None - For
simplify, simplify children first, then check if both areNum.
Expected Output
=== Exercise 2: Types and Recursion ===
string_of_expr e1 = (2 + 3)
string_of_expr e2 = (x * (1 + y))
string_of_expr e3 = ((10 + 20) - 5)
count_nodes e1 = 3
count_nodes e2 = 5
depth e1 = 2
depth e2 = 3
eval e1 = Some 5
eval e2 = None
eval e3 = Some 25
substitute "x" 3 e2 = (3 * (1 + y))
eval (substitute "x" 3 e2) = None
vars_in e2 = [x; y]
is_constant e1 = true
is_constant e2 = false
simplify e3 = 25
simplify e2 = (x * (1 + y))
Done!