Scheme from Scratch - Bootstrap v0.6 - Pairs

Published January 10, 2010 in Scheme

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 January 10, 2010

I have one suggestion to make. Since speed is not a primary concern with the bootstrap interpreter, I would change the car(object*) and cdr(object*) accessor functions to check the object type before dereferencing the fields in object::data.pair. For example, I think

if (!is_pair(pair)) {
    fprintf(stderr, "%p (type: %d) is not a pair\n", pair, pair->type);
    exit(1);
}

would 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() and set_car().

Very nice series, keep going!

Peter Michaux January 10, 2010

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.

kbob January 10, 2010

Jumping ahead a little bit, what are you thinking about tail recursion? Is that something you can leave out of this bootstrap system?

Peter Michaux January 10, 2010

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?! :-)

Chris January 10, 2010

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?

Peter Michaux January 10, 2010

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.

Zellyn Hunter January 11, 2010

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.