Image of Aaron Gough, Software Developer

Cheating your way to Lisp with Ruby

The main purpose of this post is to illustrate how simple it can be to bootstrap a small programming language using a high level language. The core of the language we’ll create is well under 100 lines, and is so extensible that it would be a relatively simple task to turn it into a full-blown Scheme implementation.

The code examples in this post are stripped down versions of code found in my miniature Lisp implementation, Flea.

Let’s dive right in and have a look at the core code for our mini-lisp! First let’s have a look at MiniLisp::Environment. This class is responsible for defining and finding variables, each environment can optionally have a parent which gets included in the variable lookup chain, this allows us to implement lexical scoping.

 1 module MiniLisp
 2   class Environment
 4     attr_accessor :parent
 6     def initialize(parent = nil)
 7       @parent = parent
 8       @table = {}
 9     end
11     def find(name)
12       return @table[name] if @table.has_key?(name)
13       return nil if @parent.nil?
14       return @parent.find(name)
15     end
17     def define(name, value)
18       @table[name] = value
19     end
21   end
22 end

Next is MiniLisp::Interpreter, this class has two main methods: run and evaluate. The run method simply steps through an array of expressions and passes them individually to the evaluate method. The evaluate method then does several checks:

evaluate is often called recursively to allow variable lookups within expressions and function calls.

 1 module MiniLisp
 2   class Interpreter
 4    attr_accessor :base_environment, 
 5                  :current_environment
 7     def initialize
 8       @base_environment = @current_environment =
 9     end
11     def run(program)
12       expressions =
13       result = nil
14       expressions.each do |expression|
15         result = evaluate(expression)
16       end
17       return result
18     end
20     def evaluate(expression)
21       return @current_environment.find(expression) if expression.is_a? Symbol
22       return expression unless expression.is_a? Array
24       if expression[0] == :define
25         return @current_environment.define expression[1], evaluate(expression[2])
27       elsif expression[0] == :native_function
28         return eval expression[1]
30       else # function call
31         function = evaluate(expression[0])
32         arguments = expression.slice(1, expression.length)
33         return, self)
34       end
35     end
37   end
38 end

The interpreter comes with 2 small functions baked-in: native_function and define. Without these functions none of the rest of the language would work, so we have to bake them in from the start. define allows us to set a variable in the current environment, while native_function allows us to pass a string through to Ruby for evaluation. This allows us to bootstrap the language by writing the initial functions using Ruby.

Before we can run a program we need to convert the S-Expressions that make up the program into native Ruby data-structures. To do this we’re using the Sexpistol S-Expression parser gem. This takes a S-Expression like this:

1 (define test 1)

And turns it into a native Ruby data-structure like so:

1 [[:define, :test, 1]]

Once we have those parts in place we can set about writing code using our new mini language!

1 (define add
2   (native_function "
3 do |arguments, interpreter|
4       argments.inject(0) {|sum, x| sum += interpreter.evaludate(x) }
5     end
6   "))
8 (add 1 2 3 4 5)
9 # => 15

To run a program simply pass the program text to the method like so:

1 interpreter =
2 result ="(define test 1)")

At this point the next step is to start writing the Standard Library for our little language using what we have implemented so far, however that process is a little long for this blog post, so I will refer you instead to the Flea repository for a simple example in an existing implementation!