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.
http://github.com/petermichaux/royal-scheme
Next article: Integers
Comments
Have something to write? Comment on this article.
Great news! I can’t wait.
I agree wholeheartedly about the timing. Bootstrap scheme went faster than I could follow, given all my other commitments.
I think you can develop it incrementally, but there’s going to have to be some design up front. The memory manager, in particular, and the general architecture of your VM (data types, registers vs. stack, how continuations are implemented, etc.)
In any case, it’ll be a lot of fun.
If you are going to be mixing C with scheme in your literate programming, you may wish to try nuweb. It is a simple language-agnostic variant of CWEB that has worked very well for me. It neither typesets your source code nor automatically indexes terms, but those limitations are precisely what enables it to work seamlessly with multiple languages. That said, CWEB output is gorgeous.
Excited to start up again!
Not sure if I want to try and follow along with Ada again or just buckle down and learn me some C this time around.
Another +1 for a slower pace. It was really and fun and exciting writing Bootstrap Scheme, but it really did move faster than my other commitments would allow me to keep up with. I think it would be nice to have a post about the design and architecture of an upcoming piece of Royal Scheme before releasing your code. That way we can all try and implement it on our own and compare implementations.
I haven’t made it to chapter 7 of LiSP yet, but I suppose I can read ahead and figure out what I have in store for myself ;) Ditto for chapter 5 of SICP. (I have this tendency to buy and read too many books at a time and leave a lot of them half-finished)...
Good to see Jim and kbob are still around as well! Hey guys! We need to make sure that we can all follow each others’ progress on GitHub again, as well. It was a lot of fun watching everyone’s Schemes come together commit by commit.
Awesome! I had given up on this being continued (i even removed you from my rss feeds :( ). I second the motion to slow it down this time around. I really enjoyed it the first time around though i quickly fell behind. Playing catch up was frustrating because i saw all the cool things that were coming (and it felt like cheating to peek ahead)
Can’t wait!-
Great to read that others are interested in the next round of the project! It is way more fun with everyone along for the ride.
It seems unanimous on the slower pace front. Good news for everyone. :-)
I’ve decided to continue with the incremental approach. The difference compared with Bootstrap Scheme will be that the increments will be larger grained this time around. For example, the first version will be a pretty printer which will be more or less equivalent to Bootstrap Scheme v0.8 but more professional and geared to being used as a library in larger programs. The second version will add a basic garbage collector. The versions introducing source code analysis, compilation to bytecode, and execution of byte code will likely be more finer-grained as there are a couple thousand lines of code to write there. Some optimizations might follow along with the foreign function interface.
Nick, I like your suggestion about posting about what is next before showing the code. I will try that approach. The outline I've just given will be expanded as time unfolds. (I also think it would be well worth your while to learn more C. I am very happy I learned it early on in my programming education.)
I’ve been waiting for something else one this one :) YAY!
Have something to write? Comment on this article.
Excellent! I’ve been looking forward to more Scheme from Scratch posts. I’ve written a couple of toy bytecode VMs for Forth-like languages, but they’ve never gotten very far. Seeing a useful Scheme virtual machine being designed and implemented will be pretty interesting. I might even take a stab at writing one myself. Writing BS while following along with your previous articles was a lot of fun.