![]() |
Previous | Table Of Contents | Next | ![]() |
Subroutines
A subroutine is a specially packaged section of your program that holds code that you wish employ at many different times while your program is running. That is, if after writing a program you notice that you are doing something over and over again then repackage that repeated code into a subroutine. The code will then exist at only one location in your program which makes your program smaller. The rest of the program can call (enter) the subroutine whenever you want that code executed.
The use of subroutines improves your program. Back when you had the code repeated at different places in your program you might have made a typing error and not really had the exact same code in all those places. But after you have repackaged the code as a subroutine you are guaranteed that the code that executes at those different times is identical since it now only exists in one location. The other reason that using subroutines improves your programs becomes apparent the day you discover you need to make a change in that section. If the code is repeated then you must find all those locations and make the change in each one of them. But if the code is packaged as a subroutine then there is only one place you must make the change. So the use of subroutines improves the quality and reliability of your code.
So how do you package code as a subroutine? It's simple: precede the code with an unused LBL n statement and end it with a RTN statement.
We have already seen the GTO n statement which allows you to jump around in your program. The statement that is used to enter a subroutine is the GSB n statement. Yes, we have seen the GSB n statement too but up until now we have only executed it from the calculator's keyboard and never placed it inside a program. The difference between the GTO n and GSB n statements is that the latter has an automatic mechanism to return to the original location in the program. This is the critical feature of a subroutine: it can be called from anywhere in your program and will return back to the original location once it completes (that is, once the RTN statement is encountered).
So how is this magic accomplished? Well, let's try to invent the mechanism ourselves. We have already seen how register 0 is used as the indirect register, to hold addresses that are employed with the STO i, RCL i, etc. instructions. Let's imagine that in a similar spirit we claim register 1 as the return register. Anytime we enter a subroutine via a GSB n statement we will populate register 1 with the program step (PC value or program memory address) we need to return to once the subroutine completes. This would work as illustrated below:
We are executing the program at statement 26 when we discover a GSB n statement. Hence we need to branch to the LBL 7 statement but we also need to remember how to get back to statement 27. To accomplish this we populate register 1 with the value 27. We then begin executing at statement 54 (just as if a GTO statement had brought us there). When we get to the RTN instruction at statement 56 we need to return to wherever the subroutine had been called from. So we look in register 1 and discover that we need to return to statement 27, where we continue executing the program.
This design works, but only in the case of non-nested subroutines. A nested subroutine is the situation where the code in one subroutine calls another subroutine. We want this to be legal, but it means that register 1 will already be populated at a time when we need to preserve a return address. While we are executing within the nested subroutine we need to preserve two return addresses which we obviously can't do using only register 1.
Okay, you say. So use both register 1 and register 2 and subsequent registers to hold return addresses, the number of registers depending upon how deep you want to be able to nest subroutines. Sorry, this design offers sufficient storage space but no means for the RTN address to know which of these registers holds the program memory address it should return to. You see, every one of the nested subroutines ends with a RTN statement and these RTN statements are all identical.
The solution to this predicament is the return address stack. See, I told you stacks were important. All computers use a return address stack to allow subroutines to nest (that is, to allow subroutines to call other subroutines). This structure is called a stack because, just like the RPN calculator's operand stack, it displays a last in, first out nature. Consider the following code that employs a nested subroutine:
When we are operating at statement 25 the return address stack is empty. Statement 26 not only transfers execution to statement 54 but also pushes (adds) the program memory address 27 onto the return address stack. The top of the return address stack always holds the program memory address where we must return when we next hit a RTN statement. At the moment the return address stack has only a single entry. Statement 26 causes execution to enter subroutine #7 which immediately calls another subroutine. So after we execute statement 55 we enter subroutine #8 and the return address stack gets two entries: program memory addresses 27 (the statement after the GSB 7 statement) and program memory address 56 (the statement after the GSB 8 statement).
Subroutine #8 squares a number and then returns. Execution of a RTN statement causes the calculator to pop (remove) a program memory address from the top of the stack and then continue executing at that location. So the RTN instruction at statement 83 pops the program memory address 56 off the top of the stack and goes there. Execution continues at statement 56 which is another RTN statement. This RTN statement pops the program memory address 27 off the top of the stack and goes there. The return address stack is then empty. This is all illustrated in the following table:
In this example the return address stack grew to a maximum depth of 2. Most computers give the stack sufficient memory that it can grow large enough to allow deeply nested subroutines. But the RPN calculator has a fixed return address stack depth of 3, which means that a subroutine can call a subroutine which can call a subroutine but then no additional subroutines can be called until you exit from (at least) that last subroutine.
So the stack cleverly solves the problem of getting a bunch of identical RTN statements to do different things. Each RTN statement pops the return address stack, thus providing unique program memory locations where execution should continue.
The only place where you can see the RPN calculator's return address stack is in a trace file. A trace file is a plain-text (.TXT) file which logs every instruction executed by a running program. Generating a trace file is the second most common debugging technique after single-stepping. Since the generation of this .TXT file does slow the calculator somewhat the operator must specifically request the trace file when he wants it. This is accomplished via the Tracing option found on the dialog box that displays when you select View/Options from the menu bar. This option is further discussed in the section on simulator options.
We will generate a trace file when we run our next example program in order to illustrate how subroutines work. So we need to find some code that cries out for restructuring as a subroutine. The code I have selected is found in a program that computes the mathematical operation known as combination.
Mathematical combination is a simple concept. Imagine that you have a collection of 4 distinct items, such as the letters A, B, C, and D. How many ways can you select 2 of these 4 letters? Well, you can select AB, AC, AD, BC, BD, or CD. Hence there are 6 ways of selecting 2 out of 4 items. Note that we consider AB to be the same combination as BA (there is a mathematical operation called permutation where these are considered to be different). A mathematician would write:
4C2 = 6
to say that there are 6 ways of taking 2 of 4 items. The number of possible combinations, each containing n objects, that can be formed from a collection of m distinct objects is given by:
where m and n are positive integers and 0 <= n <= m. The value mCn is also called the binomial coefficient (you may have seen Pascal's triangle which describes the symmetry seen in a table of binomial coefficients).
We see that we need to compute 3 factorials in order to solve for mCn. Since we need to keep employing the code that computes the factorial we will repackage it as a subroutine. Conceptually, this only involves sticking a LBL n statement at the top and a RTN statement at the bottom but we will discover some complications.
Notice that this program requires two passed parameters: m and n. The obvious thing to do is to require the operator to populate both the X and Y stack locations before initiating the program via a GSB 0 keystroke. So to compute mCn you will need to use the keystroke sequence m, ENTER, n, GSB 0.
We will look at this program in two pieces. Shown below is all of the program except for the subroutine that computes the factorial. This subroutine has been given the label 5 and hence you will observe three GSB 5 statements. These are the three calls to the factorial subroutine that compute the three factorials needed for eq. [1] above. Notice also that the first thing the program does is preserve the n passed parameter in register 2 and the m passed parameter in register 3.
; file BadCombination.txt LBL 0 ; at start of program X = n, Y = m STO 2 ; Reg[2] = n x<>y ; exchange X and Y STO 3 ; Reg[3] = m GSB 5 ; compute m! RCL 2 ; recall n, pushes m! to Y stack position GSB 5 ; compute n!, upon return Y still holds m! / ; X = m!/n! RCL 3 ; X = m, Y = m!/n! RCL 2 ; X = n, Y = m, Z = m!/n! - ; X = m-n, Y = m!/n! GSB 5 ; compute (m-n)!, upon return Y still holds m!/n! / ; m!/[(m-n)!n!] RTN ; we're done
Now let's look at the subroutine. You should be able to easily see that this is just the same code from our previous Factorial.txt example program repackaged as a subroutine.
This is how I originally wrote the factorial subroutine and I was sure surprised when my combination program gave the wrong answers (such as saying that 4C2 = .5). You can still observe my original attempt in the file BadCombination.txt.
When life serves you lemons, make lemonade. So let's take this opportunity to learn about debugging.
![]() |
Previous | Table Of Contents | Next | ![]() |