Bob: a Scheme interpreter, compiler, and VM in Python

Bob 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.

For comments, please send me an email.