Be sure to also check "(How to Write a ((Better) Lisp) Interpreter (in Python))": <a href="http://norvig.com/lispy2.html" rel="nofollow">http://norvig.com/lispy2.html</a>
For those interested in a more in-depth treatment of Lisp interpreters: "Lisp in Small Pieces", by Christian Queinnec is one of the canonical references in that area. (<a href="http://www.amazon.com/exec/obidos/ASIN/0521562473" rel="nofollow">http://www.amazon.com/exec/obidos/ASIN/0521562473</a>)<p>At university we had a copy on implementation of functional programming languages following "The Architecture of Symbolic Computers" by Peter Kogge, which is very good, too. (<a href="http://www.amazon.com/exec/obidos/ASIN/0070355967" rel="nofollow">http://www.amazon.com/exec/obidos/ASIN/0070355967</a>)
I like the quote that a powerful language should fit a page of code:<p>"I asserted that you could define the "most powerful language in the world" in "a page of code." I had orignally made the boast because McCarthy's self-describing LISP interpreter was written in itself. It was about "a page", and as far as power goes, LISP was the whole nine-yards for functional languages." --- Alan Kay in <a href="http://gagne.homedns.org/~tgagne/contrib/EarlyHistoryST.html" rel="nofollow">http://gagne.homedns.org/~tgagne/contrib/EarlyHistoryST.html</a>
I love how short and simple the tokeniser is:<p><pre><code> def tokenize(s):
"Convert a string into a list of tokens."
return s.replace('(',' ( ').replace(')',' ) ').split()</code></pre>
Kind of an unrelated question. But the phrase without the text inside the parentheses would be "How to write a Interpreter". Wouldn't "An" be a better choice?<p>In this case, what is the best option? to be faithful to the original sentence, or to stick to what sounds best with the parentheses inserted?
Norvig's interpreter is pretty solid, but another fellow did it recently as well: <a href="http://fogus.me/fun/lithp/" rel="nofollow">http://fogus.me/fun/lithp/</a>
Python's a great language for teaching this. In my an undergrad CS languages course we wrote both an interpreter and compiler (to MIPS assembly) for Lisp in Python in just a couple weeks. I'd written an interpreter for another language in C++ once and spent 3/4 of my time getting pointers and other language constructs right.
glad to see this up here.<p>this is a pretty standard exercise in university programming language theory courses. last year when i took the course, we had to write an oCaml interpreter in oCaml, and had about a week to do it (complete with environments, bindings, expressions, custom operators, higher-order functions, etc...). it was challenging, but paid off as far as contributing to my understanding about how a) functional languages work and b) how interpreters work. an interesting follow up would be to write a compiler for the language as well.<p>if writing an interpreter is something you've never done before then this is, by all means, a worthwhile activity. it would have been nice had it been structured as a series of descriptions and exercises rather than with the answers posted along with it. so easy to look :)
Oh, for crying out loud! Have you no sense of history? The whole <i>point</i> of Lisp and Scheme is that you can write the interpreter <i>in</i> Lisp or Scheme! It's a sad day when you have to write a Lisp interpreter in Python, which is itself an interpreter written in C.<p>God has killed so many kittens because of you. ;-)