![]() |
Previous | Table Of Contents | Next | ![]() |
Debugging
In the last section we wrote a program (in the BadCombination.txt file) that DIDN'T manage to correctly compute the mathematical combination mCn which is given by:
Since this equation requires three factorials we decided to repackage the code from the Factorial.txt example program as a subroutine. But the program is giving wrong answers.
We need to debug the program and we will do this by single-stepping the program until we can observe the problem. When you are searching for a bug you want to first locate a simple test case that displays the bug. Our test case will be 4C2 which should give the answer 6 but is currently giving the answer .5 . You then execute the test case a single program statement at a time.
Go ahead and load BadCombination.txt into the calculator and then, in Run mode, issue the following keystrokes: GTO .00, 4, ENTER, 2, SST. At this point all the program windows will be displayed and you will have already executed the first instruction in the program. The "02 STO 2" statement will be highlighted indicating that it is the next statement to be executed. Click on SST four more times and you will find yourself within the LBL 5 subroutine which is where we compute all the factorials. We called this subroutine to compute 4! and after 24 more SST keystrokes you will find yourself at the RTN statement at the end of this subroutine with the value 24 in the X stack location. Since 4! = 24 everything has gone fine thus far. Did you notice that during those 24 SST keystrokes you repeated a loop inside the LBL 5 subroutine 4 times? These 4 loop iterations were required to compute 4! .
The next SST brings you back to the statement immediately following the GSB 5 statement that entered the factorial subroutine. The calculator knew where to return to following the RTN statement thanks to a program memory address that was found on the return address stack. We will be able to see this stack in the trace file we will generate shortly. Two more SST keystrokes take you back into the factorial subroutine to compute 2! . Fourteen more SST keystrokes again bring you to the RTN statement and since the X stack location holds 2 which is 2! we are again happy with our subroutine. Click SST one more time to return to the code that called the factorial subroutine (this is called the calling code). You are about to execute statement 08 which is a divide operation. The Y and X stack locations are supposed to hold m! and n! respectively which we already saw being computed as 24 and 2 respectively.
But wait a minute! The Y stack location holds 1 instead of 24. This means the divide operation in statement 08 will not give the correct answer. So at this point we can see that our program has gone off track. We can see there is a problem but we don't know how it happened. The customary thing to do is to restart the program and again watch the events that led up to this situation.
To restart the program we only need to repeat the keystroke sequence: GTO .00, 4, ENTER, 2, SST. Click SST 28 more times and you will be at the RTN statement with the X stack location holding the value 24. Click SST once more and you will be back at the RCL 2 statement in line 06. Click SST once more and you will have executed the RCL 2 statement that populates the X stack location with n = 2. At this time everything is perfect: m! = 24 is in the Y stack location and n = 2 is in the X stack location and we are about to call the LBL 5 subroutine which is supposed to replace the contents of the X stack location with its factorial. If this really would happen then upon the return from the subroutine the Y stack location would still hold m! = 24 and the X stack location would then hold n! = 2 and we would be ready for the divide operation in statement 08.
But this won't happen and the fault lies in the factorial subroutine. Click on SST and you will enter the factorial subroutine. Slowly keep clicking SST while you watch the value 24 in the stack. You will observe that the operation of the factorial subroutine causes the value 24 to keep climbing up through the stack until it disappears from the top of the stack. Bummer! So we conclude that although the factorial subroutine computes the factorial of the X stack value correctly, it also perturbs other numbers left in the stack by the calling code.
High-level languages such as C, C++, and Java have a mechanism that prevents subroutines from interfering with the operation of the calling code. But in the RPN calculator (and in the 8051 microprocessor we will study next) there is no such protection. Both the subroutine and the calling code want to employ the stack and they are currently getting in each other's way.
There are two ways we could solve this problem. We could place the burden upon the calling code by insisting that it leave nothing important lying around in the stack. That is, before it calls into the factorial subroutine it will have to copy all its intermediate results into data memory locations for safekeeping. This approach requires us to add a bunch of code at every place where the factorial subroutine is called. The second approach is to improve the factorial subroutine so that it does as little damage as possible to the stack. This would make the subroutine a "good neighbor" for whatever code calls it. Since the subroutine code exists only once in the program while the calling code exists 3 times, it's obvious that it would be easier to make the changes in the subroutine.
A subroutine that is created using a high-level language begins with statements that preserve the state of the computer and ends with statements that restore the state of the computer. In between is the body of the subroutine which is now free to do whatever it wants. When the subroutine returns the calling code won't be able to tell that anyone else has been messing with the computer since everything is back to normal. We could accomplish this strategy for our Factorial subroutine by beginning it with statements that copy the four numbers in the stack into four data memory locations and then ending it with statements that repopulate the stack with these same numbers.
But I am going to solve the problem using fewer statements. I studied the subroutine and saw that it was the calculator's auto-stack lift feature that was causing the value of 24 to float away through the top of the stack. Generally, the auto-lift feature is just what you want but in this case it works against us. Fortunately, I knew that the auto-lift feature is turned off for the instruction immediately following a CLX instruction (the purpose of this "clear X" instruction is to allow you to remove a mistaken entry from the X stack location). After adding two CLX statements and a Rolldown statement I had reworked the factorial subroutine such that the Y and Z stack locations upon the exit from the subroutine still held whatever values they held when the subroutine was called. With a few additional statements I could have preserved the T location as well.
The new, improved factorial subroutine is shown below. Note the new comment that states, "This subroutine preserves the original contents of the Y and Z stack positions." This type of comment alerts the caller as to what it can expect.
The new code can be found in the Combination.txt file. You can use it to verify that 4C2 = 6 and 43C3 = 12341. You might like to single-step the new code on the test case 4C2 to observe that the value of 24 no longer floats off the top of the stack.
My original implementation (in BadCombination.txt) displays a classic computer programming problem known as contention where two sections of code think they can both employ a certain resource (in this case, the operand stack) but they end up interfering with each other. And this example program has illustrated how detail oriented computer programming can be. The computer will do exactly what you tell it. The problem is usually that the human programmer doesn't comprehend the full ramifications of what his program tells the computer to do. Computer programmers need to be able to remember lots of little details and this is probably why computer programmers are usually in short supply and hence earn good salaries.
![]() |
Previous | Table Of Contents | Next | ![]() |