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