Scheme from Scratch - Bootstrap v0.5 - The Empty List
So far we have a nice REPL that echos integers, booleans, characters and strings but LisP is supposed to be all about List Processing. Today we embark on a weekend adventure to implement lists. After a week of hard work and obligatory side hacking, everyone is a bit tired on Saturdays. We’ll start our list adventure with the slightly odd object called “the empty list” which is a breeze to implement.
In Scheme, this thing called “the empty list” is typed (). The reason I’ve been writing its name in quotations is because it is not a list at all. It is just a single object with a confusing name. Even worse, given that it is typed like a list, some people also refer to this object as “null” and/or “nil”. Just think of the empty list as a singleton object that is used as the terminator of actual lists: like NULL is used at the end of a C linked list, or '\0' at the end of a C string.
It is important to reemphasize that right now the REPL is really just a pretty printer. The REPL reads your input and creates an s-expression. The eval layer just echos that s-expression. That eval behavior has been fine so far because integers, booleans, characters and strings are “self-evaluating” or “auto-quoting”. The print layer then prints out the s-expression in a regular format (e.g. your excess input whitespace is omitted etc). The whole thing works like a pretty printer. Beauty is in the eye of the beholder.
The empty list is not self-evaluating. If the empty list is sent to eval then an error should be signaled...and in a couple more days it will be. For today, we will continue with the pretty printer idea and just echo the empty list to the output. Today’s example REPL sessions:
$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> ()
()The implementation of the empty list singleton is virtually identical to the implementation of the boolean true singleton, for example.
For those anxious to have the REPL do something exciting, like add two numbers, we are only a few days away. It’s Saturday and we should be doing something like enjoying the outdoors.
There is a v0.5 branch on github for this version.
Thanks to all those who commented yesterday that they are reading and running the code or even programming their own REPL in a slightly different way. It is great to know people are really doing it!
Comments
Have something to write? Comment on this article.
kbob,
Wow, you’re serious about taking baby steps.
I had a choice. I could either implement the empty list, pairs, symbols and the (quote) form all in one day or spread that content over four days. I thought all of that in one day was too much. I want to limit each day to an atomic change so that it is as easy as possible to see what needs to change at each step. I really did implement these four steps in the order I will present them. Even with such small steps, a basic interpreter will take less than a couple weeks.
I think your approach is great. Having implemented (poorly) a Scheme myself using R5RS and being confused at various points, I am enjoying this series and am looking forward to each post.
I’ve been interested in writing an interpreter for a while now, and reading this series of articles motivated me to finally start one. The code is at http://github.com/ingramj/bs.
Looking forward to reading more!
The empty list is not self-evaluating.
Why it should be like this? I couldn’t find exact clarification about this in R5RS or here.
Also in mit-scheme implementation () evaluates to (), but in scheme48 implementation () results in syntax error.
Valentin,
Good questions. I don’t know the answers for sure.
In JavaScript, null is self-evaluating. In Ruby, nil is self-evaluating. In Python, None is self-evaluating.
Why do you need an actual object for () rather than just null pointer or the like?
Chris,
I think having an actual object for the empty object helps at least in the implementation. It is nice to be able to distinguish if a C function is returning C’ NULL or returning Scheme’s the empty list.
I think it isn’t self-evaluating because in Scheme an unquoted list is evaluated as a function application. The empty list has no function to apply, so it is an error.
To enter a literal empty list is most Schemes, quote it just like any other list: '() => (), '(a b c) => (a b c), etc.
Have something to write? Comment on this article.
Wow, you’re serious about taking baby steps.
As for going outside, it’s cold and rainy out there. I’d rather sit by the warmth of my PC tower, gazing into the cheery flickering lights of my monitor.