Lambda Calculus Interpreter (Ruby)

From LiteratePrograms

The following is an implementation of a simple interpreter in Ruby. The language that the interpreter will evaluate is a simple version of the Lambda Calculus, consisting of function abstractions, function application, let expressions that bind values to variables, if expressions, and binary and unary operators. This provides an example that demonstrates how to implement programming language interpreters.

First we will start by defining the syntax of our Lambda Calculus.

var ::= <sequence of letters>
int ::= <sequence of digits>
bool ::= 'true'
       | 'false'
unary_op ::= '-' 
           | 'not'
binary_op ::= '+' 
            | '*' 
            | 'and' 
            | 'or'
term ::= var 
       | int 
       | bool 
       | 'Apply' term term 
       | 'Abs' var term 
       | 'let' var '=' term 'in' term 
       | unary_op term 
       | binary_op term term 
       | 'if' term 'then' term 'else' term

Next we provide classes that represent the abstract syntax defined by the above grammar. Objects of these classes will be linked together to create an Abstract Syntax Tree or AST.

We wish to be able to "run" our Lambda Calculus programs. We will do this by giving each class in the AST an eval method. Each eval method will recursively call eval on the node's children, then process those results and return a result. So, to "run" a Lambda Calculus program we simply call eval on the root node of the AST.

The AST nodes that represent terms will have an eval method that takes an optional Hash as an argument. This Hash is an environment, used to map variable names to their values.

Since ruby is dynamically typed there is no need to use something like a Term superclass or interface for our abstract syntax tree nodes.

First the AST node for variables is defined. A variable has a name. Evaluating a variable simply involves using its name to look up its value in the environment.

<<lambda.rb>>=
class Var 
  def initialize(name)
    @name = name
  end
  def eval(env=Hash.new)
    # lookup the value of the variable in the environment
    env[@name] 
  end
  def to_s
    @name
  end
end

Next the AST nodes for unary and binary operators are defined. The different operators will be specified using strings. The eval method is called recursively on the operands.

<<lambda.rb>>=
class BinaryOp
  def initialize(op, t1, t2)
    @op, @t1, @t2 = op, t1, t2
  end
  def eval(env=Hash.new)
    case @op
      when "+"   
        @t1.eval(env) + @t2.eval(env)
      when "*"   
        @t1.eval(env) * @t2.eval(env)
      when "and" 
        @t1.eval(env) and @t2.eval(env)
      when "or"  
        @t1.eval(env) or @t2.eval(env)
      else 
        raise "Unknown binary operation"
    end
  end
  def to_s
    "#{@t1} #{@op} #{@t2}"
  end
end

<<lambda.rb>>=
class UnaryOp 
  def initialize(op, t)
    @op, @t = op, t
  end
  def eval(env=Hash.new)
    case @op
      when "-"
        -(@t.eval(env))
      when "not"
        !(@t.eval(env))
      else 
        raise "Unknown unary operation"
      end
  end
  def to_s
    "#{@op} #{@t}"
  end
end

The AST node for let expressions is used to bind a variable to a value. This creates a new variable name in the environment and maps it to the value. Then the second term is evaluated in this new environment. If a variable with the same name already existed in the environment it is overwritten, or "shadowed".

<<lambda.rb>>=
class Let
  def initialize(var, t1, t2)
    @var, @t1, @t2 = var, t1, t2
  end
  def eval(env=Hash.new)
    env[@var] = @t1.eval(env)
    @t2.eval(env) 
  end
  def to_s
    "let (#{@var} = #{@t1}) in (#{@t2})"
  end
end

The AST nodes for functions and function applications are a bit more interesting. In Lambda Calculus, like in functional programming languages, a function is a first class value. The Ruby language actually contains this very concept, the Proc object. Therefore we will model function abstractions as Proc objects.

Evaluating a function abstraction, also called a "lambda", results in a Proc object.

<<lambda.rb>>=
class Lambda
  def initialize(var, term)
    @var, @term = var, term
  end
  def eval(env=Hash.new)
    var, term = @var, @term
    # returns a procedure that will perform
    # the body of the lambda function
    proc = Proc.new { |t| 
      env[var] = t    # substitution into body of function
      term.eval(env)
    }
    # add a to_s method to the newly created Proc
    def proc.to_s 
      "lambda"
    end
    proc
  end
  def to_s
    "\\#{@var}.#{@term}"
  end
end

When the Proc is called it must be given a value that represents the argument passed to the lambda term. This value will be bound to the name of the lambda's argument (similar to let expressions) and then the body of the lambda is evaluated.

A function application, when called, will evaluate the first term which must result in a Proc object. The Proc is then called by passing it the value of the lambda term's argument.

<<lambda.rb>>=
class Apply
  def initialize(t1, t2)
    @t1, @t2 = t1, t2
  end
  def eval(env=Hash.new)
    # the first term must evaluate to a ruby Proc
    @t1.eval(env).call(@t2.eval(env))
  end
  def to_s
    "(#{@t1}) #{@t2}"
  end
end

An if-then-else expression is straightforward.

<<lambda.rb>>=
class If
  def initialize(t1, t2, t3)
    @t1, @t2, @t3 = t1, t2, t3
  end
  def eval(env=Hash.new)
    if @t1.eval(env)
      @t2.eval(env)
    else
      @t3.eval(env)
    end
  end
  def to_s
    "if (#{@t1}) then #{@t2} else #{@t3}"
  end
end

We still need AST nodes for simple numbers and booleans. This will be done in a way that minimizes the number of lines of code that are needed for this.

Ruby has the concept of "open classes", meaning that a class definition may be reopened so that new methods and fields may be added. Instead of defining our own AST nodes for numbers and booleans, we will add an eval method to the corresponding Ruby library classes.

First a mixin module that contains an eval method that just returns self is defined.

<<lambda.rb>>=
module Eval
  def eval(env=Nil)
    self
  end
end

Then four classes from the Ruby library are "opened" and the mixin is added. We can now call eval on number and boolean literals.

<<lambda.rb>>=
class Fixnum
  include Eval
end
class Bignum
  include Eval
end
class TrueClass
  include Eval
end
class FalseClass
  include Eval
end

Some lambda terms for testing are defined. We are not concerned with scanning and parsing lambda terms from a file for this example so they will simply be hard-coded.

<<lambda.rb>>=
term1 = BinaryOp.new("*", 99, 100)
# the else clause contains a type error but won't be executed
term2 = If.new(BinaryOp.new("or", true, false), -10, UnaryOp.new("not", 99))
term3 = Let.new("x", 25, BinaryOp.new("+", Var.new("x"), 50))
double = Lambda.new("n", BinaryOp.new("+", Var.new("n"), Var.new("n")))
term4 = Apply.new(double, 12)
# \x.\y. x + y
add = Lambda.new("x", Lambda.new("y", BinaryOp.new("+", Var.new("x"), Var.new("y"))))
term5 = Let.new("a", add, Apply.new(Apply.new(Var.new("a"), 10), 9))
badterm = BinaryOp.new("+", 50, false)
wierdterm = BinaryOp.new("+", Object.new, Object.new)

Some testing.

def test(t)
  print t, "\n", t.eval, "\n\n"
end
test term1
test term2
test term3
test double
test term4
test add
test term5
begin
  print badterm, "\n"
  test badterm
rescue
  print "type error\n\n"
end
begin
  print wierdterm, "\n"
  wierdterm.eval
rescue
  print "what?\n"
end