# 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>>=classVardef initialize(name)@name = nameenddef eval(env=Hash.new)# lookup the value of the variable in the environment env[@name]enddef to_s@nameendend

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>>=classBinaryOpdef initialize(op, t1, t2)@op, @t1, @t2 = op, t1, t2enddef eval(env=Hash.new)case@opwhen"+" @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)elseraise"Unknown binary operation"endenddef to_s"#{@t1} #{@op} #{@t2}"endend

<<lambda.rb>>=classUnaryOpdef initialize(op, t)@op, @t = op, tenddef eval(env=Hash.new)case@opwhen"-" -(@t.eval(env))when"not" !(@t.eval(env))elseraise"Unknown unary operation"endenddef to_s"#{@op} #{@t}"endend

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>>=classLetdef initialize(var, t1, t2)@var, @t1, @t2 = var, t1, t2enddef eval(env=Hash.new)env[@var]= @t1.eval(env)@t2.eval(env)enddef to_s"let (#{@var} = #{@t1}) in (#{@t2})"endend

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>>=classLambdadef initialize(var, term)@var, @term = var, termenddef eval(env=Hash.new)var, term = @var, @term # returns a procedure that will perform # the body of the lambda functionproc= Proc.new{|t| env[var]= t # substitution into body of function term.eval(env)}# add a to_s method to the newly created Procdef proc.to_s"lambda"endprocenddef to_s"\\#{@var}.#{@term}"endend

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>>=classApplydef initialize(t1, t2)@t1, @t2 = t1, t2enddef eval(env=Hash.new)# the first term must evaluate to a ruby Proc @t1.eval(env).call(@t2.eval(env))enddef to_s"(#{@t1}) #{@t2}"endend

An if-then-else expression is straightforward.

<<lambda.rb>>=classIfdef initialize(t1, t2, t3)@t1, @t2, @t3 = t1, t2, t3enddef eval(env=Hash.new)if@t1.eval(env)@t2.eval(env)else@t3.eval(env)endenddef to_s"if (#{@t1}) then #{@t2} else #{@t3}"endend

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>>=moduleEvaldef eval(env=Nil)selfendend

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>>=classinclude EvalFixnumendclassinclude EvalBignumendclassinclude EvalTrueClassendclassinclude EvalFalseClassend

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)eval, "\n\n"endtestterm1testterm2testterm3testdoubletestterm4testaddtestterm5begintestbadtermrescueendbeginevalrescueend

Download code |