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:
- Usage the base languages recursion pattern --> Meta Interpreter
- 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.
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