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!
Have something to write? Comment on this article.