Types of Recursion

[Kineese]

In the sample-exam of the lecture SS11 (find it here) on page 3 Ex. 3.1 there is a question about 4 different kinds of recursion-implementation.

Well at the moment I just figured out two types:

1. Usage the base languages recursion pattern --> Meta Interpreter
2. Usage of FixPoints

Heres the first type:

Code: Alles auswählen

 def interp(...) : ...{
   ...
   case Rec(...) =>  interp(boundBody, cycBindAndInterp(boundId, namedExpr, env))
   ...
 }
 def cycBindAndInterp(...) = {
   lazy val recEnv: Env = (id: Symbol) => {
     if (id == boundId) interp(namedExpr, recEnv)
     else env(id)
   }
   recEnv
 }

The second type (fixpoint) is to difficult to write it down here

But what are the other two types of recursion?

Greets

K.

[JanPM]

Hi, we asked the tutor today and agreed that the other two are:

-using state of the interpreted language (boxes)
-using state of the interpreting language (var)

[Kineese]

Hi, we asked the tutor today and agreed that the other two are:

-using state of the interpreted language (boxes)
-using state of the interpreting language (var)

Thanks for the response!
Is this mentioned somewhere in the slides or can you give a rough description how the recursion should looks like when using these styles?
I think that the usage of boxes is to store the variables for recursive calls, am I right?

[JanPM]

Hi, there is an example in the GC_SRCFWAEInterp:

This is an example of using state of the INTERPRETED language. They first put a dummy value in the store. Then the namedExpr evaluates to a closure and the environment of that closure contains a pointer to the dummy. Afterwards the dummy gets replaced by the closure. So the env in the closure has a pointer to the closure itself.

Code: Alles auswählen

    /**
     * In our stateful language, we do not require mutation from the
     * host language to implement cyclic environments.
     */
    case Rec(boundId, namedExpr, boundBody) => {
      val (newLoc,s2) = store.malloc(stack, NumV(0))
      val extStack = Map(boundId -> newLoc) :: stack
      val (namedVal, bodyStore) = interp(namedExpr, extStack, store)
      interp(boundBody, extStack, bodyStore.update(newLoc, namedVal))
    }

Edit: I mean interpreted language

[keksberg]

Explain the strategy of implementing recursion by means of [global function
declarations/lazy evaluation/immediate substitution/dynamic scoping/cyclic
environments/meta-interpretation]