dollop, a Python Lisp interpreter

June 15, 2009 at 09:00 AM | categories: Uncategorized | View Comments

Via 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 instruction or an x86 jmp opcode.

blog comments powered by Disqus