Martin Karlsson / prog.re

Notes to self


Make A Lisp (Step 5)

Continued from step 4. Step 5 introduces Tail Call Optimization. In practice, this means that any recursive calls in the evaluation function is eliminated, and instead a the whole body of the evaluation is wrapped in a while(true){...}. The parts that had a recursive call to the same evaluation function (return evaluate(...);) instead reassigns the AST to the new AST to evaluate (and updates the environment), ant then lets the while do it's thing.

For the lambda functions this means that the apply part is replaced by a preparation of the environment (just binding the arguments) and then the body of the lambda becomes the new AST. This also eliminates the dependency between the types module and the eval, which is nice.

The test for this step is incomplete, the test runner even spits out a "TODO" note about adding tests for let*,do and if. Only the lambda is actually tested and the test passes even without modifications to the code. However, removing the recursive calls makes them run a whole lot faster.

Previous posts


Get in touch: martin [at] prog.re