Test-Driven Tail Recursion
Today's goal: Implement tail call optimization in Mesche to enable loops!
Updates
- Mesche now lives in its own repo(s):
- Added basic record type support to Mesche
- Improved the module system
- Created
projectrecord type for defining Mesche projects - Created basic CLI interface for Mesche, the first Mesche program!
- Added basic unit tests for scanner, compiler, and VM
Implementing tail recursion
Mesche currently doesn't have a looping construct.
To write a game loop (and other non-trivial code) we'll need one!
Today we're going to attempt an implementation of tail call optimization (tail recursion) in Mesche, first by adding functionality to the compiler in a test-driven way and then by testing it with real code!
Scheme-style "named let" is a very versatile pattern for writing loops. This is effectively a specialization for normal tail-recursive function definitions (and is probably implemented as such in many Scheme implementations).
(let count-loop ((i 1))
(if (<= i 5)
(begin
(display "Still not there yet: ")
(display i)
(newline)
(count-loop (+ i 1)))
(display "Done!\n")))
(let list-loop ((vals '(1 2 3 4 5)))
(if (pair? vals)
(begin
(display "Still not there yet: ")
(display (car vals))
(newline)
(list-loop (cdr vals)))
(display "Done!\n")))
;; Because it's tail-recursive, you can loop infinitely...
(let infinite-loop ((i 1))
(display "Current value: ")
(display i)
(newline)
(infinite-loop (+ i 1)))
Tasks
DONE Write up notes for what we think the design should be
DONE Add compiler support for "named let" expressions
DONE Add a unit test for checking named let compilation
TODO Implement tail call checks in the compiler
TODO Update tests to verify that tail call checks are being compiled correctly
TODO Generalize tail recursion implementation for all function definitions
Notes
- A named let should create an entry in the locals for the function
- Are we checking the symbol or the value? The symbol…
- Have a heuristic for whether the block is tail recursive…
- Mark the current closure with the closest function/let local slot?
- At the location where the function/let name is called, we have to decide how to emit the bytecode. Is it a jump or a function call?