dollop, a Python Lisp interpreter
June 15, 2009 at 09:00 AM | categories: Uncategorized | View CommentsVia Hacker News, Hans Nowak's proof of concept:
The proof-of-concept implementation that uses this concept is called dollop and is available at github. (Requires Python 3.0.) The name is because it's only a "dollop of Lisp" (or rather, Scheme); it only supports a few special forms (begin, define, if, lambda), and a few functions for example programs (+, -, *, =, list). It cuts corners in other ways as well, as my goal was to get a working proof-of-concept out, not to write a complete Scheme interpreter.
Hans explains how he avoids stack overflow, due to tail recursion, by replacing the machine call stack with an explicit stack data structure in his interpreter. A tail call replaces the token at the end of this stack, instead of pushing a new one.
This is a technique you can apply in an interpreter based around an eval-apply cycle: with a full compiler, the principle is the same, but you have to detect tail calls in advance and generate the correct bytecode -- say, a .NET tail.call instruction or an x86 jmp opcode.