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)
ok
> a
0
> (set! a 1)
ok
> a
1
> (define a 2)
ok
> a
2
> (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