FibonacciElement, recursion and pushing variables

[rodrigomlp]

Hi everyone!

So I pass every single test except Fibonacci element. From my searches through the forum it seems the issue arises from the fact that FibonacciElement is recursive so there is some sort of overwrite happening to the varisbles LCL, ARGs, etc if we don't make them static.

However I'm having a hard time visualizing why that is the case and what would be the solution. In another thread it was suggested that we should push the variables in writeCall as if they were static. Why?

[WBahn]

I would expect the opposite to happen. If you use static variables then each instance of the Fibonacci function call will overwrite the values still in use by the prior invocations.

I would really need to see your code to better answer your question.

[AlexShroyer]

I am having the same issue. All the tests in the 08/ folder pass for me, except FibonacciElement. Here's my FibonacciElement.out:

| RAM[0] |RAM[261]|
|    274 |      4 |

[WBahn]

As before, I can't do much without seeing the code, or at least decent pseudocode.

The key with recursion is that when Fred() calls Fred(), it is treated EXACTLY the same as when Fred() calls Sue(). In either case, all of the information the the called function needs has to be placed on the stack and the state registers (LCL, ARG, THIS, and THAT) updated as necessary for the called function. These then have to be restored when the called function returns, leaving the SP one location higher than it was before the call to reflect the single return value that is left on the stack by the called function.

When you don't have recursion, you can get incorrect code to pass the tests. But then actually making a recursive call puts enough additional stress to break the code.
 

[AlexShroyer]

Thanks for the reply! As I was drafting a response I seem to have fixed my bug. Part of my previous python3 pseudocode for 'call functionName nargs':

retAddrLabel = "@ret_{functionName}_{callCount}"
callCount += 1 # incremented when translating 'call' instruction only

Changed as follows, all tests pass:

retAddrLabel = "@ret_{functionName}_{globalCount}"
globalCount += 1 # incremented when translating any instruction, not just 'call'

It seems that it's not sufficient to simply increment a count for each time a function call occurs in the vm code.