Scheme from Scratch - Bootstrap v0.15 - Cond

The only remaining part of the first meta-circular interpreter of SICP still to port to our interpreter is the cond form.

Sample REPL session:

$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (cond (#f          1)
        ((eq? 'a 'a) 2)
        (else        3))
2

The cond form is “library syntax” and so the implementation of cond is an abstract syntax tree manipulation to convert the form to a series of nested if forms. The conversion algorithm is spelled out for us in SICP.

SICP notes and discusses how inefficient the implementation is. Every time a single cond form is evaluated it is (re)converted to nested if forms. This is inefficient and the second meta-circular interpreter addresses this issue; however, for the purpose of a bootstrap intereter, simple is more important than efficient.

We’ve reached an important milestone along our path. The port from SICP is complete. Any extra functionality we need for our interpreter to be a useful bootstrap interpreter we will need to figure out how to implement on our own.

There is a v0.15 branch on github for this version.

Previous article: Begin
Next article: Let

Comments

Have something to write? Comment on this article.

Jim Ingram January 19, 2010

bs went from zero to lambda in 10 days and about 65 commits. If anyone is following along with the articles, but not writing their own interpreter, they’re missing out.

Peter Michaux January 19, 2010

Jim,

Nice work and good recommendation. Actually writing the code is important.

Chris January 20, 2010

After Lambda and getting environments working right cond and begin were a breeze! I've noticed that some things evaluate their arguments and others don't. For instance, cond does not evaluate its arguments in the normal manner while cons, car, and cdr appear to evaluate every argument before binding them. Is there a normal way to set this behavior on a normal scheme procedure or is it a characteristic of primitives and language constructs?

Peter Michaux January 20, 2010

Chris,

Forms like cond are called “special forms” because they do not evaluate all the arguments like a procedure application does. In many Scheme implementations you can create new special forms using macros.

You may be interested to look at The Kernel Programming Language and its vau expressions for an alternative to macros.

Nick Fitzgerald January 20, 2010

Jim, I'm jealous!

I have been a little strapped for time between school, work, and my other projects! Fear not though, guys, Ada-Scheme will come catching up soon! I just need a little bit of quality time to focus.

Have something to write? Comment on this article.