Fibonacci and functions with more than one return

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Fibonacci and functions with more than one return

nandona
I'm really stuck with the Fibonacci, and figuring out how to handle recursive in asm which is linear. I'm using python. So basically everytime my program see a call function it open the file that has this function, find it and translates it until the return value and I cant seem to figure out what to do with for instance if I have a jump in the code and how to use it twice
Reply | Threaded
Open this post in threaded view
|

Re: Fibonacci and functions with more than one return

WBahn
Administrator
It sounds like you don't understand how the stack works.

You only want function code to exist in the ROM in one place. Everytime the function is called, you want to transfer control to that location in ROM in order to execute that function and then return to the point in ROM immediately after the place it was called from.

But since that function might be called from many different places, you need a means of letting the function know where it needs to return to when it finished this time. That is one of the purposes served by the stack.

We place the return address on the stack in such a way that the called function knows how to find it. But we can do so much more. We can also take a small part of the RAM contents that every function might need to use and place a copy of that contents onto the stack for safe keeping. That way the function can freely use those RAM cells for its own purposes and, provided it restores the saved information back into those RAM cells before it returns, the calling function will be none the wiser and can continue on as if it had had possession of those RAM cells all along. Furthermore, we can pass information (arguments) to the function we are calling via the stack and also reserve some memory on the stack for the function's local variables.

All of these things sit inside a block of memory on the stack known as a Stack Frame and each call to any function creates a new stack frame specific to that call. The function code itself merely interacts with the current stack frame. So Sys.init() has a stack frame and when it calls Main.main() a new stack frame is created on top of it and when Main.main() calls Fred.doSomething() a new stack frame is created on top of that. When Fred.doSomething() finishes, that stack frame is destroyed and the stack frame for Main.main() is restored before control is returned to Main.main().

The exact same process happens with recursive calls -- they are NO different in ANY way from the normal function calling process. If MyMath.factorial() is running it has a stack frame. If it calls the function MyMath.factorial() then a new stack frame is created and control is transferred to that function. If MyMath.factorial() is called again, then a new stack frame is created. If MyMath.factorial() is called twenty times, then there are twenty stack frames on the stack. Eventually (we hope) we get to a call to MyMath.factorial() that does NOT call MyMath.factorial(), but rather returns a value to whoever called it (it has NO idea who called it). That results in that last stack frame disappearing and control being returned to the function that owns the prior stack frame (by way of the return address stored within the exiting function's stack frame). The unwinds all the way back to the initial call to MyMath.factorial() which eventually does the same thing and returns a value to whatever function called it in exactly the same fashion.

Reply | Threaded
Open this post in threaded view
|

Re: Fibonacci and functions with more than one return

nandona
How can I jump to a row in the rom that is located in the value of the stack though?
Reply | Threaded
Open this post in threaded view
|

Re: Fibonacci and functions with more than one return

WBahn
Administrator
nandona wrote
How can I jump to a row in the rom that is located in the value of the
stack though?
Simple, you get the value located in RAM (which is where the stack lives) into the A register and then perform an unconditional jump.

For the sake of argument, let's assume that the return address is located at the RAM location pointed to by the stack pointer (i.e., stored in RAM[0]). Then all you would need to do is

@ SP  // Set A to address of stack pointer
A = M // load the stack pointer value into A (i.e., the address in RAM pointed to)
A = M // load the value stored at the RAM cell pointed to by the stack pointer into A
0; JMP // perform an unconditional jump to the ROM address currently stored in A

The actual location of the return address is fixed relative to the current stack frame's ARG pointer, so the current function knows where to find it.

The calling function is responsible for placing the return address onto the stack, which it does by using the value of a label located just before the point in the code where execution should continue.


Reply | Threaded
Open this post in threaded view
|

Re: Fibonacci and functions with more than one return

nandona
Oh yeah sorry this part is easy I forgot what my goal was. What I wanted to ask is how can I store a ROM line num, but I just set a label where I wanted to come back to and the did like @thatlabel and then D=A ans then stored it so the compile can later to that for me