Chapters 14, 16, 17 & 19

Functions and Recursion

Run-time Stack

Why Run-time Stack?

There are two options to store the local variables and relevant information of each function (called activation record):

1. Systematically assign spots in memory for each function to place its activation record. This has serious limitation when a program calls itself—the activation records of the two calls will overlap.
2. Each invocation of a function gets its own place in memory for its locals. Because the calling pattern of functions (LIFO) resembles the property of a stack, we use a stack to implement this.

The Organisation of Run-time Stacks

int main() {
    int a, b;
    b = Watt(a);
    return 0;
}

int Watt(int a) {
    int w;
    w = Volta(w, 10);
    return w;
}

int Volta(int q, int r) {d
    int k, m;
    ...
    return k;
}

The run-time stack before returning from Volta is:

↑
m	Local variables of Volta
k
Watt's frame pointer (dynamic link)	Bookkeeping info of Volta
return address for Watt
return value to Watt
q (value of w)	Parameters
r (10)
w	Local variables of Watt
main's frame pointer (dynamic link)	Bookkeeping info of Watt
return address for main
return value to main
a	Parameters
...	Activation Record of main
↓

The frame pointer (R5) of an invocation points to the base of the local variables in its activation record. The stack pointer (R6) points to the top of the run-time stack.

When calling a subroutine, the caller needs to:

• push parameters for the callee. The parameters are pushed from right to left.

Then, the callee should:

1. Save space on the stack for the return value. The saved space is immediately on top of the parameters for the callee.
2. Push a copy of the return address in R7. (The return address in R7 is written during the JSR instruction.)
3. Push a copy of the dynamic link (caller’s frame pointer) in R5 onto the stack.
4. Allcate enough space on the stack for its local variables, and adjust R5 to point to the base of the local variables and R6 to point to the top of stack.

Before ending the subroutine, the callee should:

1. Write the return value into the reserved space, if there is one.
2. Pop the local variables.
3. Pop and restore the dynamic link to R5.
4. Pop and restore the return address to R7.
5. Execute the RET instruction and return control to the caller program.

Then, the caller can access the return value on top of the run-time stack.

Recursion

A function that calls itself is a recursive function. Recursion can be done directly or indirectly. (fun1() → fun2() → fun(1) → …) With the help of the run-time stack, it is possible to implement recursion.

All recursive functions can be written using iteration. Sometimes recursion is simpler and more elegant, but it often costs more time and space beause of the stack operations.

Linked List

When dealing with linked lists in LC-3 Assembly Language, if the address of the current node is stored in, say, R2, then LDR R2, R2, #? will load R2 with the address of the next node. ? is the offset from start of node to the pointer that points to the next node.