Types of Recursion

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Types of Recursion

Beitrag 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.

JanPM
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 105
Registriert: 20. Mär 2009 14:25
Wohnort: Darmstadt

Re: Types of Recursion

Beitrag 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)

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Re: Types of Recursion

Beitrag 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?

JanPM
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 105
Registriert: 20. Mär 2009 14:25
Wohnort: Darmstadt

Re: Types of Recursion

Beitrag 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

keksberg
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 4. Okt 2010 15:55

Re: Types of Recursion

Beitrag 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]

Antworten

Zurück zu „Archiv“