dollop, a Python Lisp interpreter

| No Comments | No TrackBacks

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

No TrackBacks

TrackBack URL: http://mt.partario.com/mt-tb.cgi/62

Leave a comment

About this Entry

This page contains a single entry by Tim Robinson published on June 15, 2009 9:00 AM.

Lisp compiler in F#: What's next? was the previous entry in this blog.

What's a control flow graph? is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.