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

November 6th, 2010 at 2:55 pm

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:

http://eli.thegreenplace.net/wp-content/uploads/2010/11/bob_toplevel.png

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:

  1. Giving PLT Scheme a try
  2. Common Lisp vs. Scheme macros
  3. lambda²
  4. short article on lambda
  5. C -> Parrot compiler

12 Responses to “Bob: a Scheme interpreter, compiler, and VM in Python”

  1. AdilNo Gravatar Says:

    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

  2. AdilNo Gravatar Says:

    Btw, I’ve bookmarked your Blog. GREAT work!

  3. ViktorNo Gravatar Says:

    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 :)

  4. José HernándezNo Gravatar Says:

    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.

  5. elibenNo Gravatar Says:

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

  6. jdxywNo Gravatar Says:

    Hi Eliben

    Have you ever used the Spirit library in the Boost? How to do you think about that library?

  7. elibenNo Gravatar Says:

    @jdxyw,

    No, I have never used Spirit (or Boost, for that matter).

  8. Ruslan SpivakNo Gravatar Says:

    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

  9. NadeemNo Gravatar Says:

    Thanks for sharing! What references (textbooks/articles/etc.) did you use as you worked through this project?

  10. elibenNo Gravatar Says:

    @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 :)

  11. James MillsNo Gravatar Says:

    @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

  12. elibenNo Gravatar Says:

    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.

Leave a Reply

To post code with preserved formatting, enclose it in `backticks` (even multiple lines)