Bob: a Scheme interpreter, compiler, and VM in Python
November 6th, 2010 at 2:55 pmBob is my latest hobby project. It’s a suite of implementations of the Scheme language in Python. It currently includes:
- A Scheme interpreter
- An implementation of a stack-based virtual machine called the "Bob VM"
- A compiler from Scheme to Bob VM bytecode
- A serializer and deserializer for Bob VM bytecode
Here’s a schematic description of these parts:
Bob is a self-educational project. I find that the best way to understand complex concepts and mechanisms is implementing them from scratch. Working on Bob helped me understand the following concepts much better:
- How to write an interpreter for a complete programming-language. This was the easy part, because I’ve written a few interepreters before. However, it’s important in order to provide a base-line implementation with which the other implementations can be compared.
- How to implement a stack-based virtual machine with its own bytecode. The Bob VM is not much different in its core from "real" VMs, like the one Python itself (to be more exact, the official CPython implementation) runs on. It’s just much simpler.
- How to compile a high-level programming language into much lower-level VM bytecode.
I learned a lot by working on Bob, and I release its code with the hope that it can help educate other people. Bob is written in Python, which is the closest to executable pseudo-code one can get. The code is relatively compact, clean and well documented. Many such hobby projects exist, but I believe Bob is particularly clean, self-contained and easy to understand.
Bob implements a representative subset of the standard R5RS Scheme. The initial aim was to allow implementing all the code from SICP. For an example of what Bob supports, here is the Y combinator, and an invocation of the factorial function defined by using it:
(define Y
(lambda (X)
((lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg))))
(lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg)))))))
(define F*
(lambda (func-arg)
(lambda (n)
(if (zero? n)
1
(* n (func-arg (- n 1)))))))
(define fact (Y F*))
(write (fact 8))
So, if this topic interests you, please download Bob, play with it and let me know what you think.
Related posts:
November 6th, 2010 at 16:02
Hi! Thanks for your work. In near future I’m planning to write a compiler or interpreter for similar language for the same educational purposes.
Btw, if you have something interesting about writing ur own compiler, please, give me links
Thanks again
November 6th, 2010 at 16:12
Btw, I’ve bookmarked your Blog. GREAT work!
November 6th, 2010 at 19:43
Great work!
I also started, some time ago, a similar project http://bitbucket.org/alefnula/panda but much less ambitious, and it only directly interprets the scheme code, doesn’t have a virtual machine so it suffers from “RuntimeError: maximum recursion depth exceeded while calling a Python object” :-S I’ll definitely spend some time learning from bob
November 9th, 2010 at 05:06
What lexer/parser generator library do you prefer for Python? ANTLR looks nice, but it requires purchase of a book to know how to use it.
November 9th, 2010 at 07:07
@José,
My favorite parsing lib for Python is PLY (I use it heavily in pycparser). However, in Bob I parse Scheme which is so simple I decided not to bother. I use my own very simple regex-based Lexer (you can download it as part of Bob), and the parser for Bob is a rudimentary recursive-descent one.
November 18th, 2010 at 04:19
Hi Eliben
Have you ever used the Spirit library in the Boost? How to do you think about that library?
November 18th, 2010 at 07:19
@jdxyw,
No, I have never used Spirit (or Boost, for that matter).
December 16th, 2010 at 14:00
Hi Eli,
Thanks for making your code open source.
I’ve recently released my own version of Scheme interpreter named Serval:
http://ruslanspivak.com/2010/12/12/serval-simple-scheme-interpreter-in-python/
Cheers,
Ruslan
January 14th, 2011 at 18:31
Thanks for sharing! What references (textbooks/articles/etc.) did you use as you worked through this project?
January 14th, 2011 at 19:52
@Nadeem,
Mostly the books SICP and PAIP (Paradigms of Artificial Intelligence Programming, by Peter Norvig) as well as a bunch of articles – I don’t recall them all
April 26th, 2012 at 10:50
@eliben: I just recently came across your set of posts on Bob (your toy language) and would like to ask your permission if I may borrow your ideas (and maybe some code) from your Python/C++ implementations? I’m working on a toy language myself (for educational purposes for now) based on Io. See: http://bitbucket.org/prologic/mio/ Hope you’re okay with this
I’m mainly interested in your bytecode and vm stuff…
cheers
James
April 26th, 2012 at 11:46
James,
Sure, no problem at all. The code is in the public domain for this very reason. I’d be happy for it to be useful to someone else.