FoP Exercises 4 11-May-2002 School of Computer and Communication Sciences Programming Methods Laboratory (LAMP)

 Home Staff Research Publications Events Teaching   FoP     Overview     Schedule     Slides     Tutorial     Contact     Links Jobs

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 beta-reduction rule and an evaluation strategy (call-by-name, call-by-value, call-by-need). We start with implementing a call-by-name 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 lambda-abstractions have unique argument names.
```def subst(s, y, t) = s.match {
...
}
```
Finally, you are able to implement beta-reduction with a call-by-name 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 call-by-value evaluation strategy is used? Implement a call-by-value interpreter:
```def eval_cbv(t) = t.match {
...
}
```
Initially we restricted ourselves only to lambda terms where every lambda-abstraction used an unique argument name. What do you have to change if we remove this restriction? For implementing alpha-conversion you can use the following function that creates unique names:
```var nameCounter := 0
def newName = {
nameCounter := nameCounter + 1
"A" + nameCounter
}
```
Instead of alpha-conversion you could also think about modifying function `subst`.

 [an error occurred while processing this directive]