Scheme in as little Ruby and as much Scheme as possible. Supports macros, continuations, tail recursion and lazy evaluation.
Scheme in as little Ruby and as much Scheme as possible. Supports macros, continuations, tail recursion and lazy evaluation.
= Heist
http://github.com/jcoglan/heist
Heist is a Scheme interpreter written in Ruby. It provides an executable for running Scheme code directly, and also allows the interpreter to be easily embedded in, and extended using, Ruby applications. It nominally targets R5RS, though is likely to be more liberal than other implementations.
== What is Scheme?
Scheme is a dialect of Lisp, one of the oldest programming languages still in use today. Lisp was the first language to implement conditionals, first class functions (lambdas), closures and recursion. Some Lisp features, such as closures and macros, have yet to penetrate mainstream languages and it has been observed that mainstream languages are slowly converging on the feature set of Lisp.
Scheme in particular is important for its influence on current languages, in particular JavaScript and Ruby (JavaScript is remarkably similar to Scheme if you ignore the syntactic differences). It is also used in the much-praised book "Structure and Interpretation of Computer Programs", wherein it is used to explore some of the theory surrounding interpreters.
It is a functional language, in that it supports first-class functions and many constructs that would be syntax in other languages resemble function calls in Scheme. However it is not purely functional as it allows side effects, and is more procedural in nature than Haskell and its ilk. Like other Lisps, its lack of predefined syntax and its support for macros (functions that rewrite source code) make it ideal for creating new syntactic forms and embedded languages.
== Features
Heist nominally targets R5RS (http://www.schemers.org/Documents/Standards/R5RS/HTML). It has good support for many Scheme runtime features such as tail call optimisation, macros and first-class continuations, as well as reasonably complete libraries for all the Scheme data types.
Currently implemented R5RS features include:
In addition to the above R5RS features, the following are provided. Heist allows the behaviour of some of these features to be configured on a per-runtime-environment basis.
== Installation and Usage
gem install heist
Heist can be run from the command line or embedded in Ruby applications. To run a Scheme file:
heist path/to/file.scm
To start a REPL session:
heist -i
Both these commands accept a number of runtime configuration options; run heist -h for more information.
=== Embed in your Ruby app
To embed Heist in a Ruby application, you need to create an instance of the runtime:
require 'heist' scheme = Heist::Runtime.new(options)
options is an optional argument and is a hash that specifies the behaviour of optional parts of the runtime. For example, to enable lazy evaluation:
scheme = Heist::Runtime.new(:lazy => true)
The full list of options is:
Bear in mind that continuations and lazy evaluation are not currently compatible; enabling continuations forces eager evaluation. Also note that lazy evaluation has a slightly unpredictable effect on the use of macros.
To run a Scheme file using the runtime, just call:
scheme.run("path/to/file.scm")
=== Create Scheme functions using Ruby
Every runtime gets its own copy of all the built-in functions. You can add your own functions written in Ruby and Heist will make them available as Scheme procedures. For example, for running tests I do this in my +setup+ method:
@runtime = Heist::Runtime.new @runtime.define 'assert-equal' do |expected, actual| actual.should == expected end
This lets me write, for example, (assert-equal 7 (+ 3 4)) in my tests. You can place arbitrary Ruby code in your functions, so this is an easy way to expose Ruby functionality to the Scheme environment.
=== Run Ruby data as Scheme code
Heist can interpret Scheme code provided as Ruby data, allowing you to write and manipulate Lisp-style expressions inline with Ruby code. For example, using our Heist::Runtime instance from above:
scheme.exec [:define, [:square, :x], [:*, :x, :x]]
scheme.exec [:square, 9] #=> 81
Arrays map directly to Scheme lists, symbols map to identifiers, strings, numbers and booleans are treated as literals, and any other data is interpreted verbatim. So, you can use any piece of Ruby data in these expressions as long as the functions you're calling can operate on it.
Due to syntactic limitations, some Scheme constructs cannot be used in this interface. Quoting syntax is out, so the expression '(1 2 3) would need to be written [:quote, [1, 2, 3]]. Dotted pairs and improper lists are also not available, though you can work around this to some extent using :cons. Vectors should be written as [:vector, 1, 2, 3] for example. Characters can be generated using the char procedure with a unit-length string, for example [:char, "Z"] produces the character #\Z.
== Notes
This is alpha-quality software. While every attempt has been made to run valid Scheme code, error handling is at present very weak. Anything explicitly documented in this file can be assumed to work according to the Scheme standard, or according to the information presented here, and can be assumed to be reasonably stable.
=== Ruby-based syntax
I have not documented how to write your own syntax using Ruby because it requires far too much knowledge of Heist's plumbing at present (I suspect this may be unavoidable). Besides, we have macros so if you want new syntax we've got you covered. In fact, writing syntax using macros makes sure that new syntactic forms support continuations correctly, and Heist itself eschews Ruby-based syntax where possible.
=== Valid symbols
Heist is extremely liberal as regards symbols. Any sequence of characters that does not contain any spaces or parentheses and that is not a boolean literal, a number, a character literal or a string is considered a valid symbol.
=== Vectors and quoting
Vectors do not need to be quoted, for example the expression #(1 2 3) evaluates to itself. If a vector is quoted, it is made immutable and a quoted vector expression returns the same in-memory object every time it is evaluated. In contrast, an unquoted vector returns a new vector object every time it is evaluated. Unquoted vectors are not frozen as this makes macro transformations hard to implement, and because we cannot let the vector-set! procedure modify the parse tree each unquoted vector is copied on evaluation.
=== Macros
Macros are slightly more liberal than R5RS, in that this is a valid macro:
(define-syntax my-let (syntax-rules () [(my-let (name value) ... body ...) (let [(name value) ...] body ...)]))
You are allowed to use ellipses in infix positions, as long as the pattern that follows the ellipsis matches input that the preceeding pattern would fail to match. This is, the ellipsis acts as a greedy star operator in regular expressions. In the above, (name value) ... body ... matches zero or more two-element lists followed by zero or more expressions of any type. The following expression evaluates to 3 using this macro:
(my-let (x 2) (y 3) y)
Speaking of macros, there is no distinct macro expansion stage in Heist. Macros are expanded as they are encountered at runtime, and their expansions are inlined into the AST to improve performance: the same macro use is never expanded more than once. Macros (and native syntactic forms) are first-class, so they can be easily aliased and used anonymously:
(define when if)
((syntax-rules () [(_ expr) expr]) (+ 3 4)) ; => 7
It's not clear whether it would be useful to choose syntactic forms conditionally, certainly this will not work with macros as the inlining process will overwrite conditional code using the first expansion generated.
=== Laziness
Lazy evaluation mode is mainly useful for doing lambda calculus without being concerned about the difference between normal and applicative order, which for example affects the expression for the Y combinator. It displays some interesting properties, such as the fact that this is a perfectly reasonable definition for Y:
(define (Y f) (f (Y f))) ; => #
(define fact (Y (lambda (rec) (lambda (x) (if (zero? x) 1 (* x (rec (- x 1)))))))) ; => #
(fact 6) ; => 720
== License
(The MIT License)
Copyright (c) 2009-2011 James Coglan
No open issues yet, or sync has not completed.