Seite 1 von 1

Types of Recursion

Verfasst: 19. Jul 2013 15:49
von 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 :P

But what are the other two types of recursion?

Greets

K.

Re: Types of Recursion

Verfasst: 19. Jul 2013 16:31
von 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)

Re: Types of Recursion

Verfasst: 19. Jul 2013 16:42
von Kineese
JanPM hat geschrieben: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?

Re: Types of Recursion

Verfasst: 19. Jul 2013 17:10
von 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

Re: Types of Recursion

Verfasst: 21. Jul 2013 10:36
von keksberg
https://repository.st.informatik.tu-darmstadt.de/2012/copl/public/exam/check-list.pdf hat geschrieben:Explain the strategy of implementing recursion by means of [global function
declarations/lazy evaluation/immediate substitution/dynamic scoping/cyclic
environments/meta-interpretation]