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.
git clone https://github.com/weihaoqu/program-analysis-bootcamp-studentfailwith "TODO" with your implementation.dune runtest modules/module3-static-analysis/exercises/interprocedural-analysisInterprocedural Analysis
7. Exercise 5: Interprocedural Analysis (18 tests)
Goal: Build a call graph from a multi-function program and use it to answer questions about function reachability and recursion detection.
Time: ~30 minutes
Files to edit:
exercises/interprocedural-analysis/starter/call_graph.ml-- call graph construction + queries
Also provided (read-only):
exercises/interprocedural-analysis/starter/example_program.ml-- the test programexercises/interprocedural-analysis/starter/context_analysis.md-- background reading
The example program
def helper(param): Call graph:
return param + 1
main
def process_data(x, y): |
temp = x * 2 v
result1 = helper(temp) process_data
result2 = helper(y) |
return result1 + result2 v
helper
def main():
a = 5
b = 10
output = process_data(a, b)
print(output)
What to implement (in order)
| # | Function | Hint |
|---|---|---|
| 1 | calls_in_expr expr | Recursively walk the expression tree; collect function names from Call(name, args) nodes; do not forget to recurse into args |
| 2 | calls_in_stmts stmts | Walk each statement; recurse into Assign, If (cond + both branches), While (cond + body), Return, Print, Block. Use let rec ... and ... for mutual recursion |
| 3 | build_call_graph program | For each func_def, add its name to nodes and record calls_in_stmts func.body as its edge set in a StringMap |
| 4 | reachable_from cg start | BFS or DFS from start following call graph edges; return all reachable functions (not including start unless it is in a cycle) |
| 5 | find_recursive cg | A function f is recursive if f is in reachable_from cg f. Check every node and return a sorted list |
Run tests
dune runtest modules/module3-static-analysis/exercises/interprocedural-analysis/
Starter output:
Fatal error: exception Failure("TODO: Build call graph from a program")
This fatal error occurs because the test file builds a call graph at the top
level (module load time) using build_call_graph. Since that function is
still a TODO, the test runner crashes immediately before showing per-test
results. You need to implement calls_in_expr, calls_in_stmts, and
build_call_graph first. Once those three are done, the test runner will
be able to start and you will see per-test output for the remaining functions.
Hint for calls_in_expr: You need let rec because Call arguments are
themselves expressions that may contain nested calls. Pattern match on each
expression variant:
IntLit,BoolLit,Var-- return[]Call(name, args)--name :: List.concat_map calls_in_expr argsBinOp(_, e1, e2)-- recurse into both sub-expressionsUnaryOp(_, e)-- recurse into the sub-expression
Hint for reachable_from: Use a StringSet as a "visited" set. Start with
the callees of start, add them to the visited set, and continue BFS/DFS
until the frontier is empty. Do not add start to the initial visited set --
it should only appear in the result if a cycle leads back to it.
Starter Files
Test Files
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.
git clone https://github.com/weihaoqu/program-analysis-bootcamp-studentfailwith "TODO" with your implementation.dune runtest modules/module3-static-analysis/exercises/interprocedural-analysisInterprocedural Analysis
7. Exercise 5: Interprocedural Analysis (18 tests)
Goal: Build a call graph from a multi-function program and use it to answer questions about function reachability and recursion detection.
Time: ~30 minutes
Files to edit:
exercises/interprocedural-analysis/starter/call_graph.ml-- call graph construction + queries
Also provided (read-only):
exercises/interprocedural-analysis/starter/example_program.ml-- the test programexercises/interprocedural-analysis/starter/context_analysis.md-- background reading
The example program
def helper(param): Call graph:
return param + 1
main
def process_data(x, y): |
temp = x * 2 v
result1 = helper(temp) process_data
result2 = helper(y) |
return result1 + result2 v
helper
def main():
a = 5
b = 10
output = process_data(a, b)
print(output)
What to implement (in order)
| # | Function | Hint |
|---|---|---|
| 1 | calls_in_expr expr | Recursively walk the expression tree; collect function names from Call(name, args) nodes; do not forget to recurse into args |
| 2 | calls_in_stmts stmts | Walk each statement; recurse into Assign, If (cond + both branches), While (cond + body), Return, Print, Block. Use let rec ... and ... for mutual recursion |
| 3 | build_call_graph program | For each func_def, add its name to nodes and record calls_in_stmts func.body as its edge set in a StringMap |
| 4 | reachable_from cg start | BFS or DFS from start following call graph edges; return all reachable functions (not including start unless it is in a cycle) |
| 5 | find_recursive cg | A function f is recursive if f is in reachable_from cg f. Check every node and return a sorted list |
Run tests
dune runtest modules/module3-static-analysis/exercises/interprocedural-analysis/
Starter output:
Fatal error: exception Failure("TODO: Build call graph from a program")
This fatal error occurs because the test file builds a call graph at the top
level (module load time) using build_call_graph. Since that function is
still a TODO, the test runner crashes immediately before showing per-test
results. You need to implement calls_in_expr, calls_in_stmts, and
build_call_graph first. Once those three are done, the test runner will
be able to start and you will see per-test output for the remaining functions.
Hint for calls_in_expr: You need let rec because Call arguments are
themselves expressions that may contain nested calls. Pattern match on each
expression variant:
IntLit,BoolLit,Var-- return[]Call(name, args)--name :: List.concat_map calls_in_expr argsBinOp(_, e1, e2)-- recurse into both sub-expressionsUnaryOp(_, e)-- recurse into the sub-expression
Hint for reachable_from: Use a StringSet as a "visited" set. Start with
the callees of start, add them to the visited set, and continue BFS/DFS
until the frontier is empty. Do not add start to the initial visited set --
it should only appear in the result if a cycle leads back to it.