There seems to be a tradition of some two years’ standing that dictates I must release some piece of open source software on or around my birthday. A couple of years ago it was Flagger, a Rails plugin for doing useful things with boolean ‘flag’ columns in your database, and last year it was (with the support of theOTHERmedia), the Ojay JavaScript library. The former has faded into obscurity, while the latter continues to be used day-in day-out by myself and various people I work with.

So, at the risk of solidifying this tradition with a third iteration that may very well prove to be hard to top next year, I’m announcing my latest bit of spare-time hackery: Heist. Heist is an interpreter for the Scheme programming language, written in Ruby, that can run Scheme programs in standalone fashion and can be embedded in, and extended using, Ruby applications. Scheme is a dialect of Lisp that was invented in the 1970s and is used in the book Structure and Interpretation of Computer Programs, which I’m currently working my way through. Scheme is also very influential in the design of JavaScript (which is basically Scheme semantics with Java syntax), and Ruby, so it’s also an accessible avenue for me to explore functional programming.

Installation is a snap, assuming the gem has been mirrored to the gem repos by the time you read this:

sudo gem install hoe
sudo gem install heist

Heist runs on Ruby 1.8 and seems fine on 1.9, and partly works on Rubinius.

You may be asking yourself why I did this, and this a perfectly good question. Essentially I just wanted to see if I could, and writing Consent last month got me far along enough with writing an interpreter for a simple language that I thought a real programming language shouldn’t be too hard. Scheme is a perfect language for a beginner as it’s small and has almost no syntax (making it very easy to parse), and it’s perfect for me because its semantics are very close to languages I already know. I managed to get a first pass that could define functions, perform arithmetic and supported closures written on my lunch hour one day last month.

Six weeks later and I’ve got a reasonably ambitious Scheme on my hands. The first goal was to have something capable of tackling chapter 1 of SICP, but as I learned more about the language I set my sights on getting as solid and complete a runtime written as I could. So, while Heist’s function library is fairly small right now, it has runtime support for tail recursion, macros (with optional hygiene), first-class continuations and lazy evaluation. The only other Ruby Schemes I’ve found so far support none of these in any current release.

The astonishing thing is how small this is. The runtime (that’s the engine that executes code after it’s been parsed and on top of which the built-in functions are implemented) is, according to Rails’ stat counter, 672 lines of Ruby, and you can throw most of that away if you don’t want the advanced features. Macros are 214 lines, continuation support about 160, and if you throw out tail calls you’re down to about 260 lines. The parser is a dozen or so Treetop rules, and the built-in functions are a few hundred lines of Ruby and Scheme macros. All very small and relatively digestible for someone wanting to get into language implementations.

I won’t go on much further here since there is much more information on GitHub on Heist’s features and how to use it. You may notice that there are currently no list manipulation functions; this is because I did not do my research and implemented lists using arrays when really you’re supposed to use binary trees. I’m working on fixing this, and list support is a high priority for the next release. However, I’ve found that you can get along without them in some places using macros. For example, here’s an implementation of (case) that does not use any list functions:

(define-syntax case (syntax-rules (else)
  [(case key) #f]
  [(case key (else expr1 expr2 ...))
    (begin expr1 expr2 ...)]
  [(case key (() expr ...) clause ...)
    (case key clause ...)]
  [(case key
         ((datum1 datum2 ...) expr1 expr2 ...)
         clause ...)
    (let ([temp key])
      (if (eqv? temp 'datum1)
          (begin expr1 expr2 ...)
          (case temp
                ((datum2 ...) expr1 expr2 ...)
                clause ...)))]))

Yes this is probably excessively recursive and inefficient, but the point is it’s possible. I’ll mention one final curiosity I’ve discovered while writing this: in lazy evaluation mode, the following is a perfectly fine definition for the Y combinator:

(define (Y f)
  (f (Y f)))

It’s an odd feeling having written something only to discover that you don’t really understand what it is you’ve produced.