convert a simple program into a simple leaf procedure leaf means it doesn’t call anything else

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Objective: You are going to convert a simple program (on the next page, you can copy paste) into a simple leaf procedure (leaf means it doesn’t call anything else).

You can achieve this with labels – label your program above something useful (say, multiply), read in two integers from the user, and “jal multiply”.
In a real program you may have numerous procedures (functions or methods) being called, sometimes many layers deep, these are called nested procedures and we’re getting there. The goal here is to think from the perspective of the method being called (that is the ‘callee’)– you want to provide a service to a caller without mucking up its data.

So what we need to do is to push the caller data onto a stack (and keep track of what is on the stack) execute our procedure, and then restore the stack.

Conceptually think of a fairly simple problem
So what happens to “a” and “b” in the previous example? Broadly speaking this is also the problem of scope, and differently languages behave differently in terms of how nested functions can see caller variables and so on (and if it can see them, how you access them).

We are working closer to the “metal” than that. We have a piece of data in a specific memory location, but what if some called function wants to use the same memory location but to store something else, after all, if I’m the callee I can’t account for all possible memory states when I get called.

The convention for MIPS $s registers are caller saved, $t registers are callee saved.

some Background Terminology:

 
program counter: the memory location of the instruction being executed. After executing an instruction you go to current program counter + 4 since instructions are 4 bytes long. (You never work with the PC number directly, but it is stored in the return address).

$ra : is the return address. It’s where you jump to, to return to a previous state (e.g. when you are done your procedure you jr $ra and you are back at the calling function). You need to keep track of what is in the $ra if you want to have many procedures chained together though. Technically jal to a label saves the current program counter (the location of the instruction being executed)

$sp : the stack pointer. When you push things (whatever they are) onto the stack you need to pop them back off when you are done and put them back where they belong.

How do we do this? We want to Push variables onto the stack to save them, and then pop them off when we’re done.

$sp is the stack pointer, it’s supposed to be the memory address that is the top of the stack. The custom is to push onto the stack from larger memory addresses to smaller. You do this by copying something to the next available memory address, and then adjusting the stack pointer.

So to push something onto the stack you save it at memory location $sp-4, then you set

$sp=$sp-4

To Pop something off the top of the stack is $sp (the top element) and then $sp=$sp+4




Simple Example:

Push the contents of register 15 (r15) into the stack

The reason there aren’t ‘push’ and ‘pop’ instructions is because this is a RISC architecture (Reduced Instruction Set) not a CISC (Complex Instruction Set) architecture like your modern computers.

Or perhaps usefully, and this is what allows us to make a nested procedure

Make sure you do not copy and paste the code above you could run into encoding issues because of word.




Combine that program with a labelled procedure that will store a value $s0 into the stack, and that puts in a new line (that’s the program below)

Pay attention to what this does, inside the procedure we save any $s register we want to use by pushing it onto the stack, then we can do whatever we want with that register, and when we finish we pop them back to where they were.

Using what you just learned from saving one variable convert the following program into a called leaf procedure. This program reads two numbers and adds them together.


Notice that this program uses 3 $s variables, you need to make sure each one is preserved, to test that set them to something unique like $s0 =1, $s1 = 2 $s2 =3, call the procedure, the procedure should push the old values on to the stack, run, then pop the values back off. The calling main procedure should receive a value back which it should print to the consoe.

Recursion:

Now we’re going to make a recursive procedure (a procedure that calls itself). This is conceptually very similar to the previous example except the program can have a fairly large stack.
Let’s say we have 3 programs. A calls B, B calls C, C calls D.
A{ B()}; B{C()}; C{D()}; D{something}. The way this actually works is D finishes first, gets popped off the execution stack then C gets the result of D, finishes what it was doing, gets popped off, B gets the result of C, finishes, pops off the stack, then A gets the result of B and finishes.

Recursion is essentially the same, except it’s the same function, just with different parameters at each step.  Well, hopefully.  If you keep giving it the same parameters, you’ll get an infinite loop.

We will make a simple recursive function, given two integers (s and f) we will have a recursive function that adds all of the integers from s to f







Example in C#:

int mySum (int s, int f){ if (s==f){

return f;

}

else{

return s+mySum(s+1, f);

}

}

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of