Scheme from Scratch - Bootstrap v0.7 - Symbols
Symbols and symbol manipulation were and still are one of the features that distinguishes Lisp from many other languages. Most languages use symbols but they don’t let you pass them around as values.
The REPL sample session:
$ ./scheme Welcome to Bootstrap Scheme. Use ctrl-c to exit. > asdf asdf
In Scheme, symbols are not self-evaluating so the REPL is still working like a pretty printer. Today is the last day that will be true.
The simple REPL example for symbols betrays the interesting implementation of symbols and symbol tables.
The symbol table I’ve implemented reuses pairs to make a linked list which means
O(n) lookup time. That isn’t a good choice for a production Scheme interpreter implemented in C. The justification for my choice is that I’m trying to make it as easy as possible to read the source code for the C interpreter. Part of that means keeping the implementation small.
A hash table approach could mean much improved lookup times. I think it would be a great exercise to use a hash table for the symbol table implementation. K&R 2e shows a simple hash table implementation in section 6.6 Table Lookup on page 143. I encourage you to try adapting that example to fit into your interpreter.
After one week of work, this version with symbols more-or-less completes work on the read and print layers of the REPL. Most Scheme in Scheme interpreters, like the meta-circular interpreters in SICP, punt on the work that we’ve done. Those interpreters can just use
read in the implementation language because they don’t change the syntax but rather are interested in illustrating varying semantics. By implementing in C, we needed to implement our own parser. I think writing a parser by hand, rather than using tools like lex and yacc, is a good exercise to see that hand parsing a simple syntax is quite possible.
So far we’ve been thinking almost exclusively about source program syntax. With the read layer complete, from now on we can focus on the model and evaluate layers and switch our thinking to program semantics and model manipulation. It will be even more exciting to see the evaluator start to live and breath.
There is a v0.7 branch on github for this version.
Have something to write? Comment on this article.