Labs for The Most Complex Machine

xComputerLab 3: Subroutines

A SUBROUTINE IS A SET OF INSTRUCTIONS for performing some task, chunked together and thought of as a unit. Like loops and decisions, subroutines are useful in the construction of complex programs. The machine language for xComputer does not provide direct support for subroutines. But then again, it doesn't really provide direct support for loops and decisions, which must be implemented by the programmer with jump and conditional jump instructions. Similarly, it is possible to implement subroutines using jump instructions. They are not as easy, as neat, or as safe as subroutines in a high-level language, but they can still be a useful tool. Furthermore, by working with subroutines on xComputer, you'll get to see some of the details of how subroutines can be implemented on a very low level. (You should understand, though, that the machine languages of real computers do provide more support for subroutines than what is covered here.)

Before doing this lab, you should be very familiar with the xComputer applet and with assembly language programming for xComputer, as covered in xComputerLab 1 and xComputer Lab 2. The material in this lab is not covered in The Most Complex Machine.

This lab includes the following sections:

Start by clicking this button to launch the xComputer applet in its own window:

(Sorry, your browser doesn't do Java!)

(For a full list of labs and applets, see the index page.)

There and Back Again

The idea of subroutines is simple enough. A subroutine is just a sequence of instructions that performs some specific task. Whenever a program needs to perform that task, it can call the subroutine to do so. The subroutine only has to be written once, and once it is written, you can forget about the details of how it works. If the same task needs to be performed in another program, then it can simply be copied from one program to another using cut-and-paste . So the work done on writing the subroutine doesn't have to be repeated over and over. The subroutine can be reused. In fact, real computers have large libraries of subroutines that are available for use by programs. The complex programs that are used on modern computers would be extremely difficult to write, if these libraries of pre-written subroutines were not available.

In xComputer's assembly language, "calling" a subroutine means jumping to the first instruction in the subroutine, using a JMP instruction. The execution of the subroutine will end with a jump back to the same point in the program from which the subroutine was called, so that the program can pick up where it left off before calling the subroutine. This is known as returning from the subroutine. (Other computers provide special commands for calling and returning from subroutines.)

There is more to it than a few jump instructions, though. For one thing, if the subroutine is to be reusable in a meaningful sense, it must be possible to call the subroutine from many different places in a program. If this is the case, how does the computer know what point in the program to return to when the subroutine ends? The answer is that the return point has to be recorded somewhere before the subroutine is called. The address in memory to which the computer is supposed to return after the subroutine ends is called the return address. Before jumping to the start of the subroutine, the program must store the return address in a place where the subroutine can find it. When the subroutine has finished performing its assigned task, it ends with a jump back to the return address. If, for example, the return address has been stored in a memory location labeled "RetAddr", then the subroutine can finish with the statement:

                  JMP-I  RetAddr

In the language of xComputer, JMP-I is an indirect jump instruction, which uses indirect addressing. It tells the computer to jump to the location whose address is stored in RetAddr. In this case, that will be the return address for the subroutine.

All of the subroutines that you will work with in this lab use return addresses in the same way. A memory location in the subroutine is reserved for holding the return address. Before jumping to the beginning of the subroutine, the program will save the appropriate address in that memory location. The subroutine ends with an indirect jump instruction to the return address.

As a first example, look at the sample program "MultiplyBySeven.txt" This program uses a very simple subroutine whose task is to multiply a number by seven. The subroutine, which is named Times7, is at the end of the program. It begins with the lines:

        RetAddr:  data          ; The return address for the subroutine must
                                ;    be stored in this location before the
                                ;    subroutine is called.

        Times7:   STO num_t     ; STARTING POINT OF SUBROUTINE.

The first line reserves a memory location to hold the return address. The "main program," which uses the subroutine, stores the return address in this memory location. It then jumps to the location "Times7", which is where the instructions for the subroutine begin. The last instruction in the subroutine is "JMP-I RetAddr" which returns control back to the main program.

The return address is not the only item of information that the program has to send to the subroutine. The task of the subroutine is to multiply a number by seven. The main program has to tell the subroutine which number to multiply by seven. This information is said to be a parameter of the subroutine. Similarly, the subroutine has to get its answer -- the result of multiplying the parameter value by seven -- back to the main program. This answer is called the return value of the subroutine. In "MultiplyBySeven.txt," the program puts the parameter value in the accumulator before calling the subroutine. The subroutine knows to look for it there. Before it jumps back to the main program, the subroutine puts its return value in the accumulator. The main program knows to look for it there. Passing parameter values and return values back and forth in a register, such as the accumulator, is a very simple and efficient method of communication between a subroutine and the rest of a program. In the next section, we'll look at other methods of communication.

You should read the "MultiplyBySeven.txt" sample program and be sure you understand it. Load it into memory with the "Translate" button and execute it. You might want to execute it by hand with the "Cycle" button so that you can follow in detail how it works. Modify the program so that it computes 103*7 instead of 34*7. (Would you have thought of multiplying a number by seven using the method in this subroutine? Of course, a major point about subroutines is that when you are using a subroutine that someone else has written for you, you don't really care so much how it performs its task, as long as it does it correctly. You use the subroutine as a "black box.")

Parameters and Local Names

It is not always possible to pass parameter values in registers. In xComputer, for example, there is only register (the accumulator) that can be used for parameter-passing. But some subroutines require two or more parameters. The solution is to use reserved memory locations for the parameter values, just as is done for the subroutine's return address. Similarly, a return value from a subroutine can be placed in a reserved memory location rather than in a register. This method is a little more difficult than using registers, but it is also more flexible.

Look at the sample program "MultiplyTwoNumbers.txt." This sample program includes a subroutine that can multiply any two numbers. The numbers that are to be multiplied are parameters to the subroutine, and the product of the two numbers is its return value. The memory locations labeled N1, N2, and Answer are used to hold the two parameter values and the return value. These locations can be found at the beginning of the subroutine, along with a memory location to hold the return address. Before it calls the subroutine, the main program must load the two numbers that it wants to multiply into N1 and N2. When the subroutine ends, the main program can get the answer by loading the contents of memory location Answer You should read the program, try it out, and make sure that you understand all this. The program contains a list of detailed instructions for using the subroutine. (Note that you don't have to understand the method that the subroutine uses for multiplying the numbers. In fact, it's a fairly complex procedure.)

By the way, when you read the "Multiply" subroutine, you'll notice that it uses nine different labeled memory locations. Five of these -- ret_addr, N1, N2, Answer, and Multiply -- are used for communication with the main program. The other four are part of the internal working of the subroutine. Ideally, the main program wouldn't have to know about them at all, because the main program is only interested in the task performed by the subroutine, not in its internal workings. These labels are called local names, since they are meant to be used only "locally" inside the subroutine. Unfortunately, in the simple assembly language of xComputer, it is not possible to actually "hide" these names from the main program, and you have to be careful not to use the same name for a different purpose in the main program. In my sample subroutines, I have tried to use local names that are not likely to occur elsewhere in the program, such as loop_m and done_m. In real programming languages, local names are actually invisible to the rest of the program, so there is no possibility of a conflict.

Passing Pointers

The final sample program, "ListSumSubroutine.txt," illustrates one more aspect of parameter passing. The subroutine in this example is meant to add up an entire list of numbers. There is no limit placed on the number of items in the list. How is it possible to pass a potentially limitless number of parameters to the subroutine?

The solution is that the numbers in the list are not passed to the subroutine at all! Instead, the main program tells the subroutine where in memory to look for the list. There is only one parameter: the address of the starting location of the list. This address is said to be a pointer to the list.

In the "ListSumSubroutine.txt" example, the main program stores a pointer to the list in the memory location labeled "ListStart." The subroutine then accesses the numbers in the list using indirect addressing (in a LOD-I instruction). This is a nice example that demonstrates once again the usefulness of pointers and indirect addressing.

Reality Check

It's actually kind of crazy to try to write subroutines for xComputer. The limited variety of machine language instructions for xComputer makes it very hard to express the idea of a subroutine in that language. Not surprisingly, real computers have special-purpose machine language instructions for working with subroutines.

The first thing that a machine language needs is a pair of instructions for calling a subroutine and for returning from a subroutine. These instructions might be called jump-to-subroutine and return-from-subroutine. The jump-to-subroutine instruction would automatically save a return address and then jump to the starting point of the subroutine. The computer could figure out the return address on its own -- instead of leaving it up to the programmer -- by looking at the value in the Program Counter register. (The Program Counter holds the address of the next instruction after the one that is currently being executed, and that's exactly the point that the subroutine should jump back to.) The return-from-subroutine instruction would get the return address that was previously saved by jump-to-subroutine and jump back to that address. These two instructions would make it unnecessary for a programmer to even think about return addresses.

Real computers also have a more systematic way of dealing with parameters. An area of memory called the stack is used to hold the parameters for all subroutines. In fact, the stack also holds return addresses and data values used internally by subroutines. The stack is just a list of values. When a subroutine is called, the parameters and return address for the subroutine are added to the end of the list. When the subroutine ends, the return address and parameters are removed from the stack. The jump-to-subroutine instruction stores the return address on the stack, and return-from-subroutine removes it from the stack when it's time for the subroutine to end. Typically, a computer has a register called the Stack Pointer to keep track of how big the stack currently is. And machine language typically includes instructions called push and pop to add items from the stack and to remove items from the end of the stack.

When one subroutine calls another, all the data for the second subroutine is simply added to the stack, on "top" of the data that is already there. When the second subroutine ends, its data is removed from the stack, but the data for the first subroutine is still there so that the first subroutine can simply pick up where it left off. The whole system is really rather elegant.

Maybe it's not so crazy to write a few subroutines for xComputer after all, since doing everything by hand can help you understand what really goes on when a subroutine is called. And it can also help you appreciate the elegance of more sophisticated computers and programming languages.

Exercises

Exercise 1: The main program in the "MultiplyTwoNumbers.txt" sample program is as follows: 

           lod-c 13         ; Set up to call the subroutine with
           sto N1           ;   N1 = 13, N2 = 56, and ret_addr = back.
           lod-c 56
           sto N2
           lod-c back
           sto ret_addr
           jmp Multiply     ; Call the subroutine.
      
     back: lod Answer       ; When the subroutine ends, it returns
                            ;    control to this location, and the
                            ;    product of N1 and N2 is in Answer.
                            ;    This LOD instruction puts the answer
                            ;    in the accumulator.

           hlt              ; Terminate the program by halting the computer.

Carefully explain each instruction in this program. Explain exactly what each of the first 8 instructions has to do with calling the subroutine.

Exercise 2: Write a main program that uses the Multiply subroutine in "MultiplyTwoNumbers.txt" to compute the product 5 * 23 * 17. Do not modify the subroutine. The main program should call the subroutine twice.

Exercise 3: Write a subroutine to add three numbers. (This is a pretty silly thing to do, but the point is to demonstrate that you understand the basic concepts involved.) Your subroutine should have three parameters and a return value (the three numbers to be added and their sum). Write a main program that uses your subroutine to add 17, 42, and 105. Your program will be very similar to the sample program "MultiplyTwoNumbers.txt." Make sure to include comments in your program!

Exercise 4: Read the Reality Check section above. Why can't you express the jump-to-subroutine and return-from-subroutine operations in the language of xComputer? What do these instructions need to do that can't be expressed in that language? What sort of modifications would have to be made to xComputer to add them to xComputer's machine language?

Exercise 5: The sample program "ListSumSubroutine.txt" uses a subroutine to add up a list of numbers. Suppose you would like to multiply the numbers instead. To do this, copy the multiplication subroutine from the "MultiplyTwoNumbers.txt" sample program, and paste it onto the end of "ListSumSubroutine.txt." Modify the ListSum subroutine so that instead of adding two numbers, it uses the Multiply subroutine to multiply. You have to replace the instruction "add Sum" with several instructions that set up a call to the Multiply subroutine. And you'll need to make up a return address label for the subroutine to jump back to. Once you've made this modification, the program will compute the product 1*2*3*4*5*6*7 instead of the sum 1+2+3+4+5+6+7. (You might want to change the name of the subroutine from ListSum to ListMul, and change the name of the memory location Sum to Product. This will require that you also change the names in the main program.)

Exercise 6: The sample file "PrimesAndRemainders.txt" defines two subroutines. One of the subroutines can be used to find the remainder when one integer is divided into another. The other subroutine can be used to determine whether a number is prime. The file does not contain a main program. If you want to use one or both of the subroutines, you can add a main program at the beginning of the file.

You should read the comments on the two subroutines to find out how to use them. Then write two programs that use the subroutines. The first program should use the "Remainder" subroutine to compute the remainder when 609 is divided by 81. The second program should use the "PrimeTest" subroutine to determine whether or not 51 is prime. Note that you do not have to understand how the subroutines work. You just need to know how to call them and pass the proper parameters to them.

Exercise 7: This exercise, like the previous one, involves writing a main program for the "PrimesAndRemainders.txt" example. However, this exercise is much more challenging. Write a main program that makes a list of prime numbers. The program should use the "PrimeTest" subroutine to test whether each of the numbers 2, 3, 4, 5, 6, and so on, is prime. Each number that is found to be prime should be added to a list. You can write a program that runs in an infinite loop.

Use a location named "p" to store the number that you are checking. Start by storing a 2 in p. In a loop, you should call PrimeTest to see whether p is prime. If p is prime, then add it to the list. In any case, you should then add 1 to p and jump back to the start of the loop to test the next value of p.

Making a list of primes means storing primes in consecutive memory locations. Use a location named "list" to point to the end of the list. That is, the value of list is the location where you want to store the next prime that you find. Let's say that you want the list of primes to begin at location 50. At the beginning of the program, you should store a 50 in list. When you find a prime number, you can add it to the end of the list with a STO-I list command. Then you should add 1 to the value of list to get ready for the next number.

If you run your program at high speed, you can watch it store the numbers 2, 3, 5, 7, 11, 13, and so on in memory. You might want to watch the program in graphics mode so that you can watch the activity in the main program and in the two subroutines.

Exercise 8: Write a short essay discussing how subroutines can make it easier to design and write complex programs. (Your answer should show that you understand that they can do more than save you typing!) In your essay, use some of the work you did in this lab for examples.

This is one of a series of labs written to be used with The Most Complex Machine: A Survey of Computers and Computing, an introductory computer science textbook by David Eck. For the most part, the labs are also useful on their own, and they can be freely used and distributed for private, non-commercial purposes. However, they should not be used as a formal part of a course unless The Most Complex Machine is also adopted for use in that course.

--David Eck (eck@hws.edu), Summer 1998