Rethinking Lisp/Scheme in Erlang and Java

 I wrote these old blog entries a while back.  Now rethinking them.

https://www.myberlinaustin-atl.com/2008/07/simple-lisp-implementation-in-java-ode.html

https://www.myberlinaustin-atl.com/2008/07/neophyte-schemelisp-interpreter-in.html

Lisp can look strange if you come from Java, C, C++, or another procedural language. There are parentheses everywhere, functions seem to be mixed with data, and even a simple expression like (+ 1 2 3 4) does not look like the code most programmers are used to reading. Instead of starting with Lisp theory, I think it is easier to start with something every computer science student has probably implemented at some point: a linked list. A linked list has a node containing some data and a reference to the next node. You can walk through the nodes, print them, add their values, or perform some other operation on each element. Keep that basic data structure in mind because it gets us surprisingly close to understanding Lisp.

Consider the Lisp expression (+ 1 2 3 4). We can represent that expression as a list where the first element is + and the remaining elements are 1, 2, 3, and 4. In Java we could build essentially the same thing using a chain of Pair objects. Each Pair contains a first value and a rest value pointing to another Pair. Lisp calls the basic operations on these structures cons, car, and cdr. There is nothing particularly magical happening here. cons constructs a Pair, car retrieves the first value, and cdr retrieves the rest. Once you see the Lisp expression as a data structure sitting in memory, the syntax starts to become much less mysterious.

Of course, we still have to get from a string such as "(+ 1 2 3 4)" to that structure. This is where the input reader comes in. The reader moves through the characters, ignores whitespace, recognizes parentheses, numbers, and symbols, and builds tokens. When it encounters an opening parenthesis, it knows that it is beginning a list and recursively builds a chain of Pair objects until it encounters the closing parenthesis. At the end of this process we no longer have a string of Lisp source code. We have a Java object representing the expression. For (+ 1 2 3 4), the first value is the symbol +, and the rest of the list contains the arguments. At this point we have parsed Lisp, but we still have not actually executed anything.

Execution happens in eval. If the value is a number, there is not much to do; return the number. If it is a symbol, look up that symbol in the environment. If it is a Pair, then we probably have a procedure call. Take the first element, determine what procedure it represents, evaluate the remaining arguments, and apply the procedure to those arguments. The environment itself does not have to be complicated. In my implementation it is basically a Java HashMap associating names such as +, -, *, /, cons, car, and cdr with Java implementations of those operations. So when the evaluator encounters (+ 1 2 3 4), it finds the implementation of +, walks through the remaining list, adds the numbers together, and returns 10. That is a very small Lisp interpreter.

This implementation is based on Peter Norvig's JScheme and intentionally leaves out a lot of Scheme. The point was not to build the world's best Scheme implementation. I wanted to strip the interpreter down enough that I could see how the pieces worked. Start with a linked list. Turn Lisp text into tokens. Turn those tokens into Pair objects. Look up the first element as a function and apply that function to the remaining elements. Once I worked through those steps, Lisp stopped looking nearly as mysterious. That is generally how I prefer to learn these kinds of systems: take away some of the abstraction, build a small working version, and follow the data from the beginning to the end. There is plenty more that could be added—more Scheme functionality, better I/O, a compiler, or even another small language such as Forth—but the small implementation is enough to expose the basic machinery.