Due Monday, November 2 at 11:59:59 PM
By the time you have completed this work, you should be able to:
There are two sizable tasks that you need to complete for this week, some with multiple steps. You may complete them in any order, though it is recommended to start with Task 1 as Task 2 reuses components from Task 1. The tasks are listed below:
The initial step below describes how to get the files you will need into the appropriate place. These files are used for all the different tasks.
After you log in, go into your cs64 directory that you created last time:
cd cs64
Then create a new directory for this lab: lab5:
mkdir lab5
Then go into that directory.
Now copy over all of the files necessary for this week's tasks:
cp ~kyledewey/public_html/cs64/labs/5/iterative_max.asm ~kyledewey/public_html/cs64/labs/5/recursive_max.asm ~kyledewey/public_html/cs64/labs/5/partner.txt .
Note the use of the trailing . in the above command, which stipulates that the specified files should be copied into the current directory.
In this task, you will implement the IterativeMax function in iterative_max.asm using the MIPS calling convention.
IterativeMax take two arguments:
$a0.$a1.The main purpose of the function is to determine which element of the provided array is the largest (i.e., the maximum element in the array). This is achieved by going through the array one element at a time. On each element, the function should do the following, in order:
5 and 7 was just observed in the array, then the maximum should be set to 7.
ConventionCheck function, to help make sure the proper MIPS calling convention is being followed
Do not implement ConventionCheck youself, or modify it in any way.
On our end, we are going to use our own version of ConventionCheck while grading, so the only assumptions you can make about ConventionCheck are that it will follow the MIPS calling convention.
While we provide an array in the file, your code should work on any arbitrary array. On our end, for testing purposes we will use different arrays, so your code should work with any other valid (non-empty) array.
The main function provided in iterative_max.asm calls IterativeMax on your behalf, and it will display the contents of the array in non-reversed order before and after calling IterativeMax.
Your output should have the format shown below.
The first two lines and the last line are generated by the main function, so you do not have to implement anything to print those portions out.
The lines containing the words “Convention Check” are produced by the ConventionCheck function you must call after printing each input.
To help clarify which output you need to produce and which output is produced for you, output you must produce is marked in bold.
Current Array: 0 1 -1 5 32 6 -66 33 12 58 -4 64 0 0 Convention Check 1 1 Convention Check -1 1 Convention Check 5 5 Convention Check 32 32 Convention Check 6 32 Convention Check -66 32 Convention Check 33 33 Convention Check 12 33 Convention Check 58 58 Convention Check -4 58 Convention Check 64 64 Convention Check 0 1 -1 5 32 6 -66 33 12 58 -4 64
Remember to follow the MIPS calling convention while implementing your IterativeMax function.
Otherwise, the program may crash hard.
You may assume that the provided array will always be non-empty. That is, it is guaranteed that the provided array will always contain at least one element.
Some hints follow, which you may or may not find useful:
Use “jal label” to call other functions, replacing label with the name of the function you want to call.
For example, if you want to call the ConventionCheck function, then you ultimately need to use the following code snippet:
jal ConventionCheck
In this task, you will implement two functions in recursive_max.asm, using the MIPS calling convention.
These functions are described in the table below.
| Function Name | Parameter 1 Description (in $a0) |
Parameter 2 Description (in $a1) |
Parameter 3 Description (in $a2) |
|---|---|---|---|
RecursiveMax |
The address of an array of word-long (four byte) signed integers | The length of the array as an unsigned integer | N/A (does not take a third parameter) |
TailRecursiveMax |
The address of an array of word-long (four byte) signed integers | The length of the array as an unsigned integer | The running maximum element in the array, as a signed integer |
The combination of these two functions behave just as in Task 1. That is, running Task 2 should produce exactly the same output as Task 1.
The difference from Task 1 is that your function will be implemented this time in a tail-recursive style.
In order to do this, initially main will call RecursiveMax.
RecursiveMax will set up the arguments properly for a call to TailRecursiveMax, and subsequently call TailRecursiveMax.
In TailRecursiveMax, on each recursive call the length of the array is decremented, and we concurrently more forward one element in the array.
The end result is that the array “shrinks” by one element at a time from the left, until the length is 0, at which point we are done.
To illustrate how this should work, below is some C-like code which mostly accomplishes what you will write:
void RecursiveMax(int* array, unsigned int length) {
TailRecursiveMax(array, length, INT_MIN);
}
void TailRecursiveMax(int* array, unsigned int length, int max) {
if (length != 0) {
print_int(*array);
if (*array > max) {
max = *array;
}
print_int(max);
ConventionCheck();
TailRecursiveMax(array + 1, length - 1, max);
}
}
The reason why the above code only mostly does what you want is because of the recurisve call to TailRecursiveMax within the TailRecursiveMax function.
Going off of C semantics, the compiler may treat this as an ordinary call and push things onto the stack.
However, this is wasteful, as no work is done after the recursive call to TailRecursiveMax.
This means that there is no need to save anything, as it is guaranteed that TailRecursiveMax will never use it again.
An optimization that can be performed here is to not save anything on recursively calling TailRecursiveMax, and treat it more like a loop than a function call.
In MIPS, this typically means the use of the jump (j) instruction on recursive calls, as opposed to the jump-and-link (jal) instruction.
For full credit, your code must perform this optimization.
To see how this can be coded up, you may want to consult this factorial implementation which has been written tail-recursively with the optimization.
turnin
If you partnered with someone, record the email address they are using for the class in partner.txt.
For example, if your partner had the email address foo@bar.com, then the contents of partner.txt should be the following (and only the following):
Partner: foo@bar.com
If you did not partner with anyone, you do not need to (and should not) edit partner.txt.
Assuming you are in the cs64/lab5 directory you created at the beginning, you can send in your answers via the following command:
turnin lab5@cs64 iterative_max.asm recursive_max.asm partner.txt
You may turn in the same assignment up to 100 times, which is useful if you are working on it incrementally. Note that only the last version you submitted will be graded.
Even if you did not partner with anyone, you should still turn in partner.txt, which should not have been modified.
Prepared for Computer Science 64 by Diana Franklin, with slight adaptation by Kyle Dewey.