Just for fun I wondered if I could write one in C++. My goals would be
1. A Lisp interpreter that would complete Peter's Lis.py test cases correctly...
2. ...in no more than 90 lines of C++.
Although I've been thinking about this for a few weeks, as I write this I have not written a line of the code. I'm pretty sure I will achieve 1, and 2 will be... a piece of cake!
In one short line of Python Mr. Norvig implements Lisp functions car, cdr and append. Another line and we've done the four basic mathematical operators on bignums. Gulp.
To give myself any sort of chance I don't intend to support bignums, garbage collection or error handling and I'm only going to implement the bare minimum to pass the test cases.
. . .
OK, I've done it. Here it is:
With Lis.py to guide me writing this was fairly straight-forward, with two exceptions. The first point I had to stop and think was in
eval()when the symbol to be evaluated was "
lambda", i.e. at the point of definition of the lambda. In Peter's code he returns a Python lambda; not something available to me. Then I realised that I didn't have to actually do anything with the lambda body, just keep it around until it needs to be executed. That's why I can just change the cell type from Symbol to Lambda and return it as-is.
The second pause for thought was much longer; this time it was at the point of execution of the lambda. Partly because I don't know Python (or Scheme) it wasn't clear to me what was going on with the environment. The problem was that lambdas that returned lambdas didn't work: variables that were defined at the time the lambda was returned were not defined at the time that returned lambda was executed.
It took a little while to work through the problem, but eventually I did. It helped to look at some simple examples to see where things went wrong. Here is my program executing some sample code adapted from an article that appeared in February 1988 Byte magazine:
doubleris not only associated with the procedure
(lambda (y) (* y n))but it must also have access to an environment where the value of
I added some code to the start of the
evalfunction to dump out the value of the paramaters
enveach time it is called. Here is the output while executing some of the above sample code.
[global]" means the global environment where "
*" maps to the built-in
[y->4 [n->2 [global]]]" means an innermost environment where
4, that environment's outer environment where
2and that environemt's outer environment, which is the global environment.
When looking up the value of a variable the code starts with the innermost environment and if the variable is not defined there it tries the next outer environment and so on.
I don't know whether I've explained that clearly enough to make sense. The important bit I realised is that a new environment must be created when a lambda is evaluated containing (a) all the paramater->argument associations, and (b) this new environment's outer environment must be the reference to the environment that existed at the time the lambda was defined. I believe this is called a lexical closure.
Here's my program executing a another example I like, this time adapted from that Wikipedia article on lexical closures. It just underlines that the closure captures the variable, not just the value of the variable, and that the captured variable may be changed.
Here is another example, again adapted from the Wikipedia article on closures. This demonstrates that not only can the closure capture existing variables, it also captures variables created inside the closure (the variable
hiddenin this case). Also in this example, two procedures are created that share the same closure. (I spread some of the code over several lines to make it more readable; it has to be entered all on one line for my primitive program.)
Here are the 29 tests for Lis.py. The
main()function in the code above is replaced by all this code to run the tests.
All 29 tests pass. Goal 1 achieved.
Goal 2: I'm not counting blank lines or comment-only lines, and I'm not counting lines that contain only an opening or closing curly brace, because I'm just not counting them.
Not quite 90. But south of 200 isn't bad, is it? (Just to be clear: I'm not claiming I've produced the equivalent of Lis.py in under 200 lines of C++.)
Compared with Lis.py my effort is incomplete, inefficient and leaks memory. Unlike some of the code I've presented in other blog posts the end result here is not useful in itself; it was the process of developing it that was useful, if only for me.
Nevertheless, I get a little thrill out of having made something that allows me to type
(define cube (lambda (n) (* n n n)))and then
(cube 3). It's like magic.
EDIT June 2013: Since I published this post it has been viewed 37,561 times, which is a big deal for me. Occasionally someone will ask me if I'll allow the code to be used for their project and I always say yes. To make it simpler I've removed the copyright and placed it in the public domain.