(How to Write a (Lisp) Interpreter (in Python))
October 3, 2010 at 11:25 am 1 comment
It’s not really computing education, but it’s totally geeky fun and could make for a cool project to dissect for a student in a programming language’s class.
This page has two purposes: to describe how to implement computer language interpreters in general, and in particular to show how to implement a subset of the Scheme dialect of Lisp using Python. I call my interpreter Lispy (lis.py). Years ago, I showed how to write a Scheme interpreter in Java as well as one in Common Lisp. This time around the goal is to demonstrate, as concisely and accessibly as possible, what Alan Kay called “Maxwell’s Equations of Software.”
via (How to Write a (Lisp) Interpreter (in Python)).
Entry filed under: Uncategorized. Tags: programming, programming languages.
1.
Alan Kay | October 3, 2010 at 12:23 pm
Hi Mark,
To me this is very much a part of “computer education” — especially since Peter did such a clean job of both programming and explanation (Peter and I have been exchanging emails about this).
He also did a nice follow on to this one which adds a few more features:
http://norvig.com/lispy2.html
Our correspondence was about even more compact and more readily understandable ways to do this.
For example, both McCarthy’s original version, and Peter’s (and most others), use an already recursive language to implement this recursive language, so much of the significance (and joys) of bootstrapping to a higher level are missed.
So an exercise like this should be done with a subset of the parent language that is like simple hardware (just assignments and loops).
Another is that quite a bit of space in Lisp interpreters written this way is needlessly devoted to dealing with “special forms” (those things that are not simple functions, such as quote, lambda, cond, etc.).
However, real Lisps have the idea of FEXPR, which is to pass the arguments unevaluated, and let the interior of the procedure decide to evaluate them or not.
This means that an “FEXPR” eval-apply can be much simpler. I used this idea to do the original Smalltalk interpreter in 1972.
This can be taken further by using Shorre’s ideas for Meta II, to let the new FEXPR actually parse, eval, and bind its argument stream. This makes “lisp” into a syntactically extensible language with much more readable and distributed syntax. I did this also for the first Smalltalk.
Finally, there are several ways in real lisps (property lists, closures) to associate meanings in strong ways. For example, closures can be used as “instances” of functions to make a useful kind of “object”.
If the Meta II interface recognizer is implemented as a kind of conditional that maps inputs to their meanings, then you get a very powerful and simple object system in “less than a page of code”.
This is why I called what John did “The Maxwell’s Equations of Software” — because it provides enormous power via enormous simplicity via a very different perspective on computer languages and programming.
Once you understand this, you are a very different kind of “computer thinker”.
This is why I think this is one of the most vital parts of any “computer education”.
Best wishes,
Alan