## Recursion in SRCFWAE

lkbaerenfaenger
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

### Recursion in SRCFWAE

Hey all,

I am wondering why the 'namedExpr' in 'Rec' is being interpreted with a new stack frame 'extStack'. This new stack frame only contains the self-binding (boundId -> ...). Therefore, assuming that 'namedExpr' will turn out to be a closure, this closure will close over nothing but that self-binding. That's not the way it should be, is it? Here's the code:

Code: Alles auswählen

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))
}
Btw, what's 'ext' stand for anyways?

Best
Lucas

Toa
BASIC-Programmierer
Beiträge: 121
Registriert: 16. Feb 2011 23:58

### Re: Recursion in SRCFWAE

This new stack frame only contains the self-binding (boundId -> ...)

Code: Alles auswählen

val extStack = Map(boundId -> newLoc) :: stack
No.
Btw, what's 'ext' stand for anyways?
I assume 'ext' stands for 'extendedStack'

lkbaerenfaenger
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

### Re: Recursion in SRCFWAE

Hi Toa,

actually, the new stack frame only contains the self-binding. This is true despite the fact that all other stack frames are appended. And, if you take a look at how function definitions are being interpreted, only this very stack frame is taken from the top ('stack.head') and included in the closure:

Code: Alles auswählen

case Fun(arg, body) => (Closure(arg, body, stack.head), store)
As a consequence, like I said, the resulting closure will only close over its own self-binding -- and nothing else. It is my understanding that this shouldn't be the case: With static scoping, a function body should be able to access all names that were in scope at definition-time, right? And this is not possible if only the self-binding is being closed over...

Best
Lucas

lkbaerenfaenger
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

### Re: Recursion in SRCFWAE

Hey,

I hate to be annoying but is there anything new on this? I do still believe there is an error in the interpreter. Thanks in advance!

Best
Lucas

Toa
BASIC-Programmierer
Beiträge: 121
Registriert: 16. Feb 2011 23:58

### Re: Recursion in SRCFWAE

Hi,
in my opinion there is nothing wrong. Compare the implementation with the "RCFWAEInterp" interpreter. The extended environment is a recursive environment binding the recursive identifier in the namedExpr and the boundBody as well. The behavior/idea is described in V3-2.pdf. With state we do not require a mutual env to implement this behavior.

Code: Alles auswählen

val extStack = Map(boundId -> newLoc) :: stack
val (namedVal, bodyStore) = interp(namedExpr, extStack, store)

We bind the recursive identifier e.g 'fact and evaluate the namedExpr to a closure storing this binding. This means, the closure has a binding for 'fact in the namedExpr. This is actually, why we introduced the additional Rec case and haven't just used the Let. Because the Let just binds the boundId in the boundBody. Later we put the result (the closure) on the store:

Code: Alles auswählen

interp(boundBody, extStack, bodyStore.update(newLoc, namedVal))

and evaluate the boundBody with a binding for the 'fact function. Once we refer to the 'fact function in the boundBody with an App, we will look it up on the store and execute it. The nice thing is, that we bound a definition for 'fact at compile time to the closure. This means we actually have a binding for 'fact and can execute the recursive call once again

Btw, a lot of people are on vacation. Maybe this is also true for the course organizer. Or they simply don't care

Toa
BASIC-Programmierer
Beiträge: 121
Registriert: 16. Feb 2011 23:58

### Re: Recursion in SRCFWAE

Haha, I finally understood the problem you were talking about Your point is, that the Rec case should actually look like:

Code: Alles auswählen

case Rec(boundId, namedExpr, boundBody) => {
val (newLoc,s2) = store.malloc(stack, NumV(0))
val extStack = stack.head + (boundId -> newLoc) :: stack
val (namedVal, bodyStore) = interp(namedExpr, extStack, store)
interp(boundBody, extStack, bodyStore.update(newLoc, namedVal))
}

Am I right? Well, I think so too. Any official approval would be nice. One could also argue, if the namedExpr should be evaluated with the store "s2". In this case it doesn't matter because we don't need the NumV(0) binding.

Talaron
Mausschubser
Beiträge: 85
Registriert: 26. Apr 2012 11:34

### Re: Recursion in SRCFWAE

You're right! I've checked the code and Toa's solution should be the correct one.