Scheme from Scratch - Bootstrap v0.6 - Pairs
Pairs.
After today’s additions, our pretty printing REPL will echo any dotted pairs, proper lists and improper lists we enter. For example:
$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (0 . 1)
(0 . 1)
> (0 1)
(0 1)
> (0 . (1 . ()))
(0 1)
> (0 . (1 . 2))
(0 1 . 2)
The reader has to grow by a reasonable amount to make all these pair and list variations possible. The interesting part is that the reader functions read
and read_pair
become mutually recursive. Together they form a recursive-descent parser. I thought it was pretty neat to implement a recursive-descent parser, type arbitrarily nested data structures, and imagine the parser traversing the structure to build the internal model. (Another example of a recursive-descent parser is found in section 5.12 Complicated Declarations on page 122 of K&R 2e.)
The print layer also must be able to print arbitrarily nested data structures. The functions write
and write_pair
are mutually recursive and mirror the relationship of the reader code.
There is a v0.6 branch on github for this version.
Previous article: The Empty List
Next article: Symbols
Comments
Have something to write? Comment on this article.
Björn,
Your suggestion is a good one. I considered using C’s assert
for this purpose as it can be turned off during compilation. Another goal is to keep the source code as small and readable as possible and adding a lot of guard code would obscure the process of what is happening a bit. The good news is it seems like quite a few readers are really building their own Scheme interpreters and so they are free to choose if they include such guard code or not.
Jumping ahead a little bit, what are you thinking about tail recursion? Is that something you can leave out of this bootstrap system?
kbob,
Perhaps it could be left out but tail recursion will definitely be included in this bootstrap system. How could we pass up that much fun?! :-)
Since you aren't doing error checking, why not implement car
and cdr
as a C macro and avoid the need for set_ . . . .
#define CAR(obj) obj->data.pair.car
Or does that break something you plan to do in garbage collection?
Chris,
Chibi Scheme uses a lot of macros like you are suggesting which makes it possible to use car(obj)
as an lvalue which is quite nice. You could definitely do the same here.
Just wanted to let you know how much I’m enjoying this series. I’ve been eagerly reading each article and the additions to the code as you publish each entry. Keep up the interesting writing!
Have something to write? Comment on this article.
I have one suggestion to make. Since speed is not a primary concern with the bootstrap interpreter, I would change the
car(object*)
andcdr(object*)
accessor functions to check the object type before dereferencing the fields inobject::data.pair
. For example, I thinkwould do the job. This could simplify debugging later on a lot as it avoids triggering random crashes and gives you a source line for a break point). From my experience, double checking like that pays off, especially with accessor macros like
cddddr()
defined.Similarly, I'd add such guards also to
set_cdr()
andset_car()
.Very nice series, keep going!