Scheme from Scratch - Royal Scheme Planning
The Scheme from Scratch introduction included a list of several possible Scheme implementations. Bootstrap Scheme covered one of those possibilities: a quick and dirty C implementation of a Scheme interpreter. Folks reported that they enjoy the Bootstrap Scheme series and the way the interpreter was developed incrementally. I really enjoyed the feedback and that others were actually following along, coding their own interpreters, and experiencing the excitement when they saw their REPL’s running. I’m excited to continue the Scheme from Scratch series but which implementation next?
The next implementation I will attack is a bytecode interpreting virtual machine which I’m calling Royal Scheme. This kind of implementation is actually both a compiler and an interpreter. The source code is read and converted to an abstract syntax tree. The AST is then compiled to bytecode. Finally the bytecode is interpreted by the virtual machine. The fact that the compiler and virtual machine can both be written in ANSI C means that the implementation can be portable and there is no need to learn hardware-specific machine code.
I want Royal Scheme to be a good-enough Scheme implementation. A Scheme implementation that can actually be used for real programming. An engine that can be embedded in other C programs. Real garbage collection. Real error handling. A foreign-function interface. Even with these features, I’m hoping Royal Scheme won’t top 8000 lines of code. It will still be a simple version of the Scheme family of languages. It won’t be R6RS. It might be R4RS. It doesn’t need to be the world’s fastest Scheme. I’ll trade some speed for source code readability. It does need to be fast enough for some real world applications like writing a blog web application or writing a simple vim/emacs-like text editor.
Implementing a bytecode interpreting Scheme has been written about. You may already have the books. Chapter 5 of Structure and Interpretation of Computer Programs and chapter 7 of Lisp in Small Pieces both present byte-code interpreting virtual machines for Scheme that are implemented in Scheme. I’ve spent a lot of time reading these chapters and thinking about how they might port to C.
Chibi Scheme is a small byte-code interpreting virtual machine for Scheme that is implemented in C. Chibi is an admirable implementation and I think will influence certain parts of Royal Scheme. I’ve talked with Alex Shinn, author of Chibi, about this and he is ok with such influence.
One thing I am sure about is that the pace of the project will be slower than Bootstrap Scheme. Readers kept me excited and moving faster than I thought I would but the coding plus a blog post per day was tall order. Once the Royal Scheme project is genuinely under way, I’m thinking something along the lines of a post per week would be better this time around.
A major detail still up in the air is how to document the project. Bootstrap Scheme was small and simple. The incremental development seemed to work well. I’m not sure that the same will work well for a fully fledged Royal Scheme. Perhaps something along the lines of Knuth’s literate programming style would be better. After all, the interpreters in chapters 5 of SICP and 7 of LiSP are presented much like the woven output of the literate programming style. I haven’t programmed in the literate style before but have thought an interpreter would be an ideal subject for such a style. Any thoughts on documenting the project? What would you like to see in your feed reader?
If you are interested in watching when things start moving, I have made a place holder project on Github. There is not much there for now. I was impressed that fitzgen already found the new repository and is following it.
Next article: Integers
Have something to write? Comment on this article.