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
asdfIn 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.
Comments
Have something to write? Comment on this article.
Jim’s suggestion is a great one. For everyone who is coding along, please add a comment with a link to your code. I know Jim’s is on github.
I’m not exactly following along. I started my own interpreter 16 months ago, and worked through all these issues on my own and came up with different solutions. In general, mine is more “production-like” than Peter’s. So far, mine is a superset of everything Peter’s shown us.
But anyone here is welcome to glean what they can.
Source: git://github.com/kbob/kbscheme.git
A variety of ’blog posts: http://kernelbob.wordpress.com/tag/scheme
My ongoing stream-of-consciousness notes as the project went on. (Not nearly as nicely organized as Peter’s series)
I’ve been following Peter’s progression if not his style. You can find my code at http://git.kc5vzm.com/?p=scheme;a=summary I prefer flex/bison to hand building a parser.
Have something to write? Comment on this article.
I’m hoping to get caught up with your interpreter by tomorrow. I decided to have a separate lexer that reads and tokenizes an entire line at once, and to write read() in terms of tokens rather than characters. I'm happy with the resulting code, but is definitely time to move on to semantics though.
If there’s anyone else following along and writing their own interpreter, post a link to your code!