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
 3     
 4     attr_accessor :parent
 5     
 6     def initialize(parent = nil)
 7       @parent = parent
 8       @table = {}
 9     end
10     
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
16     
17     def define(name, value)
18       @table[name] = value
19     end
20     
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:

If it has been passed a Symbol then it calls find on the current environment using the symbol as the key and returns the value it finds.
If it is anything other than an Array at this point then we are looking at a literal (be it a String, Integer, or Float), and we need to return the literal untouched.
If it is an array then we are evaluating a function call. The first item in the array is evaluated to get the Ruby Proc object that should be associated with it, and then the Proc is called with the rest of the array as arguments.

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

 1 module MiniLisp
 2   class Interpreter
 3    
 4    attr_accessor :base_environment, 
 5                  :current_environment
 6    
 7     def initialize
 8       @base_environment = @current_environment = MiniLisp::Environment.new
 9     end
10     
11     def run(program)
12       expressions = Sexpistol.new.parse(program)
13       result = nil
14       expressions.each do |expression|
15         result = evaluate(expression)
16       end
17       return result
18     end
19     
20     def evaluate(expression)
21       return @current_environment.find(expression) if expression.is_a? Symbol
22       return expression unless expression.is_a? Array
23       
24       if expression[0] == :define
25         return @current_environment.define expression[1], evaluate(expression[2])
26         
27       elsif expression[0] == :native_function
28         return eval expression[1]
29         
30       else # function call
31         function = evaluate(expression[0])
32         arguments = expression.slice(1, expression.length)
33         return function.call(arguments, self)
34       end
35     end
36     
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     Proc.new() do |arguments, interpreter|
4       argments.inject(0) {|sum, x| sum += interpreter.evaludate(x) }
5     end
6   "))
7   
8 (add 1 2 3 4 5)
9 # => 15

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

1 interpreter = MiniLisp::Interpreter.new
2 result = interpreter.run("(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!