Implement an interpreter for the lambda calculus in Funnel.
An interpreter for a language is a function that, when applied
to a term, performs the actions required to evaluate the
expression:
interpreter: Term > Value
For the lambda calculus, an interpreter is described by the
betareduction rule and an evaluation strategy
(callbyname, callbyvalue, callbyneed).
We start with implementing a callbyname interpreter.
Terms should be implemented using the Visitor design
pattern, names are simply strings. Here is a framework for the
definition of Term s:
val Term = {
def Name(s) = { ... }
def Lambda(x, t) = { ... }
def Apply(t, u) = { ... }
}
Write a function toString that transforms a term
into readable form:
def toString(t) = t.match {
...
}
Now implement a visitor for doing substitutions on lambda terms.
For simplicity you can assume that lambdaabstractions have unique
argument names.
def subst(s, y, t) = s.match {
...
}
Finally, you are able to implement betareduction with a callbyname
evaluation strategy. The following function eval is supposed
to reduce a term as much as possible:
def eval(t) = t.match {
...
}
How do you have to modify eval so that a callbyvalue
evaluation strategy is used? Implement a callbyvalue interpreter:
def eval_cbv(t) = t.match {
...
}
Initially we restricted ourselves only to lambda terms where every
lambdaabstraction used an unique argument name. What do you
have to change if we remove this restriction? For implementing
alphaconversion you can use the following function that
creates unique names:
var nameCounter := 0
def newName = {
nameCounter := nameCounter + 1
"A" + nameCounter
}
Instead of alphaconversion you could also think about modifying
function subst .
