Scheme from Scratch - Bootstrap v0.9 - Environments

If you’ve been hoping for a day with a bit more meat to implement then today is your day. Environments, variables, define and set! form a group of features that can be implemented together in one swoop.

A sample REPL session:

$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (define a 0)
> a
> (set! a 1)
> a
> (define a 2)
> a
> (set! b 3)
unbound variable

The implementation in C is a reasonably straightforward port of Operations on Environments in SICP. Please (re)read that section if any of the C implementation needs clarification.

Since we don’t have procedures quite yet, the second form of define to define procedures, (define (identity x) x), has been left out of this version.

I’ve long thought that the return value of define and set! as shown in SICP are not the best choices. By these forms returning the symbol ok, it is not possible to meaningfully nest definitions or use a set! in a conditional which I’ve found handy when reading input in a loop or working with regular expressions. Anyway I’m resisting the urge to “improve” on SICP’s meta-circular interpreter and just port it to C faithfully.

You will likely notice that the_global_environment is a global variable in the C code. Global variables make me wretch. Again, I’m trying to be faithful to the SICP implementation. It would be better to have a struct vm to collect together all of a virtual machine’s data, like a global environment. All that data could be passed around together. A notable place we will need access to the global environment is in the implementation of a load form.

Any readers who are true test-driven developers may be uncomfortable with this version. The idea of chained environments and walking up that chain looking for a variable and its value is clearly not needed to implement define and set! until we can create new scopes with lambda. Well, all I can say about that is after 30 years of Scheme, we know we will need chained environments very soon and so I implemented them at this stage.

We are only days away from having a basic, complete Scheme interpreter. Turing complete is just around the corner.

Thanks to vthacker03 for posting this series to Reddit. It was on the front page last night and this morning and quite a few more people have been reading the posts and hopefully starting their own interpreter implementations.

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

Previous article: Quote
Next article: If


Have something to write? Comment on this article.

Nada Amin January 13, 2010

I am enjoying your series so far.

Shouldn't you return after the set_car of line 310? Though it doesn't hurt, you're changing the binding and adding a new binding, which is a bit unnecessary. What do you think?

Philipp January 13, 2010

Can you please explain what you do in the function define_variable? First you change the binding in the current environment and then you append a new environment with this binding. Are you missing a return-statement?

The way I understand this (my read of SICP was quite a while ago) we should try to change the binding in the current environment and when that fails to create a new binding.

Anyway, thanks for this series!


Peter Michaux January 13, 2010

Nada and Philipp,

Thank you both for reading the code so carefully and reporting the omission. I've added the needed return and updated the code on github.

Stu January 13, 2010

I will post a link to my code tomorrow night (left my usb stick at work). My version has a context thats passed around with all global data, so you can have multiple contexts without stomping each other, good for embedding. Accepts hex numbers (I added that to test myself), strings are one time allocated (like symbols, there are no dupes). all objects are in a linked list so I can track every allocation (poor mans GC without the GC.. just means I don’t loose any memory when a context is shutdown).

I don’t know scheme at all, so I’m having trouble following along on that side of things, the C is a cakewalk tho.

Jim Ingram January 14, 2010

I’ve gotten up to pairs in my interpreter last night, and was going to start on symbols, but I got sidetracked into making this while working on some hash-table test code:

I’m slightly ashamed.

Have something to write? Comment on this article.