Taming the stack
summary
Shows how any first-order non-tail recursion becomes a tail-recursive loop by applying a worker‑wrapper, CPS to named continuations, turning closures into an explicit continuation data type and a single eval loop, producing a constant‑stack implementation. Presents alternatives: a tail-recursive loop using explicit constructors (about 6–8× slower than naive recursion) and a trampoline monad that handles higher‑order recursion but runs ~25–50× slower. Derives the same result via least/greatest fixed points and a free monad‑style trampoline; all approaches are stack‑safe and practical tradeoffs.
AI-written summary · about
chapters (7)
- 0:00Start
- 0:15STACK SAFETY
- 5:43AN EXAMPLE
- 6:53A TRANSFORMATION
- 13:19TAILREC
- 14:46GREATEST FIXPOINT
- 18:25LEAST FIXPOINT
related talks
59mAn introduction to Continuation Passing Style (CPS)
37mY: Recursion The Hard Way
56mAn introduction to recursion schemes
36mWorking Hard to Keep Things Lazy
27mMonad Stacks or: How I Learned to Stop Worrying and Love the Free Monad
47mHands on With Recursion Schemes - Part 1 of 2
29mIntroduction to Recursion Schemes
46mWriting and improving tail recursive functions