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,
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
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
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
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.
Have something to write? Comment on this article.