Tutorial on Program Transformations
summary
Step-by-step recipe that turns a small Scheme interpreter into C: the session shows exact transforms — CPS conversion, lifting and replacing higher-order closures/environments with tagged data, defunctionalization of continuations, registerizing names into globals and trampolined goto-style control, then a tiny transpiler to emit C. The demonstration actually compiles and runs: factorial and Fibonacci examples produce the expected results (factorial 5 → 120; fib 5 → 5) with warnings but a working C binary.
AI-written summary · about
chapters (12)
- 0:00Program transformations tutorial
- 2:05Course context and goals
- 7:54Minimal interpreter with lambdas
- 16:09Environments and closures as data
- 23:30Higher-order to first-order
- 31:09Rewriting in continuation-passing style
- 42:26Continuations for control flow
- 53:59Throw and continuation handling
- 1:05:13Defunctionalizing continuations
- 1:17:04Tail calls to gotos
- 1:23:46Final C transformation and demo
- 1:27:49Q&A
related talks
59mAn introduction to Continuation Passing Style (CPS)
44mLet's Lisp like it's 1959
37mTCO
46mInventing a language (placeholder title)
33mA Historical Perspective on Program Transformation and Recent Developments (Invi...
44mImplementing Software Machines in Go and C
59mCoq to C Translation with Partial Evaluation + Counterexample Generation
16mTranspiling Slang Methods to C Functions: An Example of Static Polymorphism for S...