TCO
summary
A source-to-source compiler named ctco transforms Clojure on the JVM by applying CPS, thunkification and trampolining so mutual tail calls execute without growing the JVM stack; factorial and mutually recursive even/odd examples run to large depths without stack overflow. Implementation tags thunks with metadata, auto-inserts recur for simple self-recursion, and trades stack use for heap-allocated continuations so performance is slightly worse and long non-tail recursion can cause heap growth. Work is usable, mostly correct, and being optimized and ported to ClojureScript.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:09Outline
- 4:17Current Year: 1977
- 4:48A Sinister Debate
- 5:37Setting the Record Straight (Still 1977)
- 6:13Tail Calls Are Special
- 8:55Tail Calls Are Awesome
- 10:09Built-In TCO
- 11:29Build It Better
- 13:27Big Claim
- 17:29Part II: Thunkification
- 23:15Part III: Trampolining
- 25:41CTCO In Summary
- 30:08Costs of CTCO
- 31:44Optimizations
- 34:22Future Work
- 35:50Thank You
related talks
20mA Tail of TwoTails: The Second Act
14mOn-Stack Replacement for Program Generators and Source-to-Source Compilers
59mAn introduction to Continuation Passing Style (CPS)
39mCrawling Inside the Tauntaun
40mJoy of Meta-Tracing Just-in-Time Compilation: More Than Just a VM Generator
15m(TOPLAS) Type-Safe Compilation of Dynamic Inheritance via Merging
42mClojure Futures
31mAn Exceptionally Janky Tale