Test-Driven Tail Recursion

Today's goal: Implement tail call optimization in Mesche to enable loops!


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)
	(display "Still not there yet: ")
	(display i)
	(count-loop (+ i 1)))
      (display "Done!\n")))

(let list-loop ((vals '(1 2 3 4 5)))
  (if (pair? vals)
	(display "Still not there yet: ")
	(display (car vals))
	(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)
  (infinite-loop (+ i 1)))


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


  • 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?

Next Steps

TODO Finish writing let/lambda parsing

TODO Finish call offset patching after lambda is created

TODO Set function name based on let name (will also work for declared functions)