⇒ Bring up the "K Sub-MIPS Simulator referred to in these instructions in a separate, side-by-side browser window, if you haven't already.
In the first exercise, you will be writing a "leaf" function (a function that does not call any other function) and a Main procedure that calls it. The "leaf" function does not need to save anything to the Stack, so long as it only uses $t registers. The Main procedure saves $ra to the Stack.
In the second and third exercises, you will be writing a recursive version and a non-recursive version of the Triangular Numbers function, to further explore use of the Stack.
Download this Markdown template to record your program and submit it to Kit.
Look over the "Simple Non-Leaf Example" in the K Sub-MIPS Simulator. It implements the same functionality as the "Main as Leaf" example, calculating the midpoint between two values, but this Main calls a sub-function, Midpt, to do the actual midpoint calculation. The Main function loads two memory values into registers, calls Midpt, and stores the returned result out to memory.
This example illustrates passing arguments and passing back a return value,
as well as using the jal and jr instructions.
It also provides a simple-case use of the Stack. The Main function pushes
the $ra register, which says where to return to in the operating system
(address 008), to the Stack before calling Midpt, since the call to Midpt
will replace the value in $ra with the instruction in Main that Midpt
should return to (address 036).
Here is C code that corresponds to the assembly language program:
int main()
{
int x = 4; /* Or other value in M100 */
int y = 10; /* Or other value in M104 */
int mid = midpt(x, y); /* Stored in M108 */
return;
}
int midpt(int a, int b)
{
int temp = a;
if ( a != b )
temp = (a + b)/2;
return temp;
}
The assembly language program assumes that the values for x and y (stored in the argument registers $a0 and $a1) come from memory locations M100 and M104. The Main procedure stores the computed midpoint (coming back in register $v0) out to M108.
Manually run the sample code to be sure you understand what it does.
⇒ Analysis Question: Why does this program use registers $a0, $a1, and $v0 instead of $t1, $t2, and $t3, as the "Main as Leaf" example did?
Program 1:
Modify the program you used for the "Leaf Procedure" assignment
(or one of the other previous programs, if you would rather), pulling
the key functionality out into a procedure. The goal is to have our little
simulated OS call Main, which should put appropriate values in the
argument registers and then call a function to do the bulk of the work for
the program, returning a value to the Main. The Main program should store
the return value to a memory location and then return to the OS.
If you are careful about which registers you use in your sub-function (for example, use $t registers rather than $s registers), then your sub-function, as a leaf function, will not have to use the Stack. Your Main, on the other hand, will have to at least push $ra to the Stack before calling the sub-function, and pop it before returning to the OS, just as in the Simulator sample program. If you are careful with your use of registers, you might not need to store anything else to the Stack.
Test your program, then "Save" and copy it into the Markdown file.
Program 2:
You may recognize the Triangular Numbers function,
1 + 2 + 3 + ... + N.
Write an assembly language version of the following recursive
implementation of the Triangular Numbers function.
(This is similar to the Factorial function, but using addition instead of
multiplication.) In this case, you will need to push more than just $ra to
the Stack in rec_tri before it calls itself recursively.
The pre-condition for the Triangular Number function is N >= 1.
int main()
{
int n = 6;
int result = rec_tri(n); /* Stored in M100 */
return;
}
int rec_tri(int n) /* Recursive triangular number function */
{
if ( n == 1 )
return 1;
return n + rec_tri(n-1);
}
Test your program, then "Save" and copy it into the Markdown file.
Program 3:
Some recursive functions can be written just as easily with a non-recursive
algorithm, and Triangular Number and Factorial are two of these.
Write an assembly language version of the following non-recursive
implementation of the Triangular Numbers function. Note that the
non-recursive function is a leaf function, so if you are careful about your
choice of registers your nr_tri code
should not require using the Stack (although your main, of
course, will).
int main()
{
int n = 6;
int result = nr_tri(n); /* Stored in M100 */
return;
}
int nr_tri(int n) /* Non-recursive triangular number */
{
int i;
int result = 0;
for (i = 1; i <= n; i++ )
result += i;
return result;
}
Test your program, then "Save" and copy it into the Markdown file.
⇒ Analysis Question: What do these two programs tell you about the compiled machine code of recursive vs. non-recursive functions?
⇒ Note:
If you have taken Discrete Math, you should recognize the function
1 + 2 + 3 + ... + N as having the closed form
N(N+1)/2.
We're not making use of the closed form in these exercises, though, both
because our focus is on the use of the Stack in procedure calls and because
multiplication in MIPS introduces extra complexity.
Optional Tail-Recursive Program:
The Triangular and Factorial Numbers functions can also be written as
"tail-recursive" functions. A tail-recursive function is one where all of
the work is done on the way "down" and the only thing the function
does after the recursive call is to pass the return value back "up."
(Which, at the assembly language level, just means to leave $v0 where it is
and to return.) Tail-recursive functions are frequently implemented with a
"helper function," like the one below.
Implement the tail-recursive algorithm in assembly language. Note that there are no leaf functions here, so you will always need to save $ra to the Stack. If you are careful in your choice of registers, though, you should not need to save anything else to the Stack.
The pre-condition for tr_tri_helper, like tr_tri,
is N >= 1.
int main()
{
int n = 6;
int result = tr_tri(n); /* Stored in M100 */
return;
}
int tr_tri(int n) /* Triangular number using tail recursion */
{
return tr_tri_helper(n, 0);
}
int tr_tri_helper(int n, int intermed) /* Tail-rec helper function */
{
int new_intermed = intermed + n;
if ( n == 1 )
return new_intermed;
return tr_tri_helper(n - 1, new_intermed);
}
Test your program, then "Save" and copy it into the Markdown file.
⇒ Note: The main advantage of tail-recursion is that an optimizing compiler can compile a tail-recursive function as a non-recursive procedure. For this reason, programmers writing in functional languages (where recursion is ubiquitous) learn to write tail-recursive algorithms wherever they can. Some problems, such as the Fibonacci sequence, for example, cannot be written using tail-recursive algorithms.