Scheme from Scratch - Bootstrap v0.16 - Let

We could have lived our lives without adding cond. It is a convenience form and there are a few others that are handy to have around: let is one of them.

Sample REPL session:

$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (let ((x (+ 1 1))
        (y (- 5 2)))
    (+ x y))
5

The let form is also “library syntax” and so the implementation is another abstract syntax tree manipulation. This time it is a manipulation that converts the let form to a procedure application with a lambda form.

At this point you may be thinking these abstract syntax tree manipulations could become tedious to implement. Macros exist for this reason and so that the programmer can invent his own new library syntax. We only need a few bits of library syntax for a bootstrap interpreter and it is easier to implement directly in C than to implement macros in C and then the library syntax in Scheme.

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

Previous article: Cond
Next article: And and Or

Comments

Have something to write? Comment on this article.

Chris January 20, 2010

When did you add list and eq? I don’t remember those being in Primitive Procedures Part 2 when I went through your list...

Peter Michaux January 20, 2010

Chris,

I think I added them the day after. I will be going back to that article and adding as necessary.

Stu January 20, 2010

Yay, lambda’s are in, the Y combinator examples are working fine. I did indeed have an issue in my environments, and lambdas were complicated by my using linked lists rather than PAIR objects for passing args/params in, but once I realised what it was doing it was cake. I was fighting some bugs because I did things differently in my primitive proc implementations. most of them can take entire lists eg:

(int->char (char->int (int->char 99 100 101 102)))

rather than just a single parameter (at the time I did not realise about map/iterate and how I could rewrite this in scheme rather than C.

One thing that nagged me was that symbols are not scoped like variables that they are entirely global no matter what scope (I guess your using the word environment for scope) your in... I’m like 50/50 on this, I’m sure it lets you do cool things but I want to change it ;) I guess real scheme people are screaming right now and pointing fingers so enough of scoped symbols. maybe it just does not matter.

now for begin/cond/let!

Stu January 20, 2010

whoo hit cond/begin/let.. wow that was so much easier than lambda!

Peter Michaux January 20, 2010

Stu,

Nice work. cond/begin/let in less than an hour. Seems like you are doing some interesting variations too.

Symbols are values and values are not scoped. It is variables that are scoped. If you had scoped symbols then 'a from one scope might not equal 'a from another scope? That would be like the integers 21 from one scope not equalling 21 from another scope. I don’t know if that would be useful.

Nick Fitzgerald January 21, 2010

Just finished pairs/lists and symbols and it is time to call it a night. So far this has been way more fun and educational than any of the classes I am taking right now! Thanks again, Peter.

Sometimes I wish I just implemented getc/ungetc variants for Ada before starting (Ada’s text io abstracts them away, and I’m not finding that helpful). Most of my debug time is spent making sure I am manually moving my index var to the right place on the string. There is probably a better way, that an actual Ada user could point me towards. Oh well.

Another crunch session and lambdas should be mine!

Stu January 21, 2010

Peter, having your working implementation helps a lot. Once I understood what each was trying to do, implementation was pretty straightforward. I think tonight I’ll replace all the single function calls that do nothing but a car/cdr into defines and some more error checking. Its too easy to break ;) my implementation.

Peter Michaux January 21, 2010

Nick,

Perhaps building your own version of a stream (i.e. C’s FILE *) would be the best way to abstract away your read buffer issues. Then just pass that stream around. I’d hope something like that already exists for Ada.

Nick Fitzgerald January 21, 2010

Peter,

pmarin suggested the same thing and I actually talked to one of my profs about it as well. I wish I had done that from the start but I feel that I have too much sunk cost in my current stab at things to refactor all of that.

All in all I feel pretty good about my code, though parts are duct taped together, because all that is left of the reader is quote, so I can put this behind me very soon.

Charles Lloyd March 20, 2010

I am working on a Java implementation of Scheme and have two versions of let. One is based on lambda (ie creates a new Closure each time) per all the texts. The other simply binds the args of let into a new Environment (whose parent is the environment where let is being evaluated) and evaluates the body of the let using a begin construct. This second form generates a whole lot less garbage but I fear I have over simplified yet I have not been able to come up with a test case that breaks it.

Can anyone show me a test case for let where you MUST have the closure feature of lambda/procedures for it to work? For example, the following does work:

> (define double (lambda (x) (* 2 x)))
> (let ((double "foobar") 
           (triple (lambda (x) (+ x (double x)))))
                 (triple 7))

Ans: 21

But I doubt I have really tested what I need to test with this. Any ideas, however convoluted, would be appreciated.

Have something to write? Comment on this article.