![]() |
Previous | Table Of Contents | Next | ![]() |
Program Tracing
I used single-stepping to identify the problem in my BadCombination.txt example program. The other common method of debugging a program is to generate a trace file. Let's do this now. First we must request the trace file by selecting View/Options from the menu bar and then adding a checkmark to the Tracing option. On the resulting dialog we are told that the trace file will be named TRACELOG.TXT and will be found in whatever directory (folder) holds RPNCALC.EXE, which is the Windows executable for the RPN calculator. After requesting the trace file close the options dialog and then load the BadCombination.txt program. Then run the program as you normally do: 4, ENTER, 2, GSB 0. The program runs and then halts displaying the answer of .5 which is wrong.
At this point you can use Windows Explorer (i.e., Start/Programs/Windows Explorer) to show you the contents of whatever directory you chose to hold RPNCALC.EXE back when you installed this software (this location defaults to the C:\Computer Science Lab\RPNCalc folder). In this directory you will see the new file TRACELOG.TXT. By double-clicking on this .TXT file you will command Windows to activate Notepad to show you the contents of this file. Shown below are the contents of this trace file augmented with a new left-hand column that numbers every line:
Program from file 'D:\johnk\projects\RpnCalc\BadCombination.txt' run on Tue Apr 30 11:25:13 2002 Instruction X Y Reg[0] Subr Return Addr 1 01 LBL 0 +2.00 +4.00 +1.00 -- -- -- 2 02 STO 2 +2.00 +4.00 +1.00 -- -- -- 3 03 x<>y +4.00 +2.00 +1.00 -- -- -- 4 04 STO 3 +4.00 +2.00 +1.00 -- -- -- 5 05 GSB 5 +4.00 +2.00 +1.00 06 -- -- 6 15 LBL 5 +4.00 +2.00 +1.00 06 -- -- 7 16 STO 0 +4.00 +2.00 +4.00 06 -- -- 8 17 1 +1.00 +4.00 +4.00 06 -- -- 9 18 STO 1 +1.00 +4.00 +4.00 06 -- -- 10 19 LBL 6 +1.00 +4.00 +4.00 06 -- -- 11 20 RCL 0 +4.00 +1.00 +4.00 06 -- -- 12 21 STO* 1 +4.00 +1.00 +4.00 06 -- -- 13 22 DSZ +4.00 +1.00 +3.00 06 -- -- 14 23 GTO 6 +4.00 +1.00 +3.00 06 -- -- 15 19 LBL 6 +4.00 +1.00 +3.00 06 -- -- 16 20 RCL 0 +3.00 +4.00 +3.00 06 -- -- 17 21 STO* 1 +3.00 +4.00 +3.00 06 -- -- 18 22 DSZ +3.00 +4.00 +2.00 06 -- -- 19 23 GTO 6 +3.00 +4.00 +2.00 06 -- -- 20 19 LBL 6 +3.00 +4.00 +2.00 06 -- -- 21 20 RCL 0 +2.00 +3.00 +2.00 06 -- -- 22 21 STO* 1 +2.00 +3.00 +2.00 06 -- -- 23 22 DSZ +2.00 +3.00 +1.00 06 -- -- 24 23 GTO 6 +2.00 +3.00 +1.00 06 -- -- 25 19 LBL 6 +2.00 +3.00 +1.00 06 -- -- 26 20 RCL 0 +1.00 +2.00 +1.00 06 -- -- 27 21 STO* 1 +1.00 +2.00 +1.00 06 -- -- 28 22 DSZ +1.00 +2.00 +0.00 06 -- -- 29 24 RCL 1 +24.00 +1.00 +0.00 06 -- -- 30 25 RTN +24.00 +1.00 +0.00 -- -- -- 31 06 RCL 2 +2.00 +24.00 +0.00 -- -- -- 32 07 GSB 5 +2.00 +24.00 +0.00 08 -- -- 33 15 LBL 5 +2.00 +24.00 +0.00 08 -- -- 34 16 STO 0 +2.00 +24.00 +2.00 08 -- -- 35 17 1 +1.00 +2.00 +2.00 08 -- -- 36 18 STO 1 +1.00 +2.00 +2.00 08 -- -- 37 19 LBL 6 +1.00 +2.00 +2.00 08 -- -- 38 20 RCL 0 +2.00 +1.00 +2.00 08 -- -- 39 21 STO* 1 +2.00 +1.00 +2.00 08 -- -- 40 22 DSZ +2.00 +1.00 +1.00 08 -- -- 41 23 GTO 6 +2.00 +1.00 +1.00 08 -- -- 42 19 LBL 6 +2.00 +1.00 +1.00 08 -- -- 43 20 RCL 0 +1.00 +2.00 +1.00 08 -- -- 44 21 STO* 1 +1.00 +2.00 +1.00 08 -- -- 45 22 DSZ +1.00 +2.00 +0.00 08 -- -- 46 24 RCL 1 +2.00 +1.00 +0.00 08 -- -- 47 25 RTN +2.00 +1.00 +0.00 -- -- -- 48 08 / +0.50 +2.00 +0.00 -- -- -- 49 09 RCL 3 +4.00 +0.50 +0.00 -- -- -- 50 10 RCL 2 +2.00 +4.00 +0.00 -- -- -- 51 11 - +2.00 +0.50 +0.00 -- -- -- 52 12 GSB 5 +2.00 +0.50 +0.00 13 -- -- 53 15 LBL 5 +2.00 +0.50 +0.00 13 -- -- 54 16 STO 0 +2.00 +0.50 +2.00 13 -- -- 55 17 1 +1.00 +2.00 +2.00 13 -- -- 56 18 STO 1 +1.00 +2.00 +2.00 13 -- -- 57 19 LBL 6 +1.00 +2.00 +2.00 13 -- -- 58 20 RCL 0 +2.00 +1.00 +2.00 13 -- -- 59 21 STO* 1 +2.00 +1.00 +2.00 13 -- -- 60 22 DSZ +2.00 +1.00 +1.00 13 -- -- 61 23 GTO 6 +2.00 +1.00 +1.00 13 -- -- 62 19 LBL 6 +2.00 +1.00 +1.00 13 -- -- 63 20 RCL 0 +1.00 +2.00 +1.00 13 -- -- 64 21 STO* 1 +1.00 +2.00 +1.00 13 -- -- 65 22 DSZ +1.00 +2.00 +0.00 13 -- -- 66 24 RCL 1 +2.00 +1.00 +0.00 13 -- -- 67 25 RTN +2.00 +1.00 +0.00 -- -- -- 68 13 / +0.50 +2.00 +0.00 -- -- -- 69 14 RTN +0.50 +2.00 +0.00 -- -- --
A lot of this trace file should make perfect sense. For example, the first instruction that was executed was the LBL 0 instruction located in program memory location 01. This was because we initiated the program via GSB 0. The calculator then continued executing instructions in order until it came to the GSB 5 statement. Hence line 6 of the trace file shows that execution jumped from program memory location 05 to program memory location 15. Furthermore, the far right-hand column shows that the GSB 5 statement caused the 3 deep subroutine return address stack to be populated with the program memory address 06, which is the statement following the GSB statement. This is where execution should continue when we reach the RTN statement in the subroutine.
So we are now inside the factorial subroutine. The sequence of statements that then get executed is illustrated below. We can very clearly see that we iterate 4 times through the loop while computing 4!
I want to zoom in on the following lines taken from the trace file:
Notice how the subroutine return address stack has been populated the entire time we are inside the factorial subroutine but then when we hit the RTN statement the program memory address 06 is removed from the stack. This is why line 31 of the trace file shows that execution continues at program memory address 06. Note also that the Y stack location holds 24 = 4! so everything is okay at the moment.
Lines 32 through 47 of the trace file show the next call into the factorial subroutine. This time we only iterate twice through the loop since we are only computing 2! = 2. And line 47 shows what makes the program in the BadCombination.txt file bad: the Y stack location no longer holds 4! = 24.
Ignoring this fault, line 52 of the trace file shows that the program makes a third call into the factorial subroutine to compute (4-2)! . Lines 53 through 67 show that we only iterate twice through the loop since (4-2)! = 2!
Now take a look at the far right-hand column of the trace file. This column is labeled "Subr Return Addr" and shows the contents of the 3 deep stack. There are only 3 moments during the running of this program that this stack holds anything: these are the 3 moments when we are inside the factorial subroutine (i.e., LBL 5). Even though it is the same subroutine which is called, the return address is different. This is because the subroutine is called from 3 different places. Hence the RTN statement at the end of the factorial subroutine causes us to return to statements 06, 08, and 13. Again, the RTN statement is the same each time, but the contents of the return address stack are different each time execution reaches the RTN statement.
Once we discovered the flaw in the BadCombination.txt example program, I then provided you with a better program, Combination.txt, that does not suffer from the contention problem that exists in BadCombination.txt. But while Combination.txt correctly computes 4C2 = 6, it does not correctly compute 73C4. The problem is that the algorithm used in Combination.txt is a straight forward implementation of eq. [1], which I repeat below:
This equation involves three factorials and we have already pointed out that because the RPN calculator cannot deal with any number larger than 9.999999999e+99 it cannot correctly compute any factorial larger than 69!. To use eq. [1] to compute 73C4 requires that we compute 73!, 4!, and 69! and hence we get the wrong answer. Yet the right answer for 73C4, which is 1088430, is not such a large number. The final result of eq. [1] is a reasonable sized number because we take an immense numerator (73!) and divide it by an almost as immense denominator (69! * 4!).
If you are suspecting that there should be a way to write an RPN calculator program that can handle 73C4 you are correct. In fact, such a program can be found in the Combination2.txt file. This program is rather involved because it doesn't do the obvious thing implied by eq. [1]. The most hardy of you will be able to figure out the operation of the code in Combination2.txt from the comments that I have provided in that file. The rest of you can skip this example program since it doesn't introduce anything new and is getting so complicated that it would be better written in a higher-level language such as C, C++, or Java. But all of you should hear me say that a smarter algorithm always makes for a better program.
I'll close this section with some implementation details of the tracing capability of the RPN calculator. If a calculator program that is being traced runs indefinitely then the trace file could grow without bound. Eventually your hard disk drive would be full and the Windows operating system would croak. To prevent this I don't allow the trace file to grow larger than 1 megabyte. Everytime the TRACELOG.TXT file reaches 1 MByte I copy its contents over to TRACELOG_OLDER.TXT and empty TRACELOG.TXT. Hence, when you eventually inspect the contents of TRACELOG.TXT you will be looking at no more than the most recent 1 MByte of program activity. It's possible that older tracing activity can be found in the TRACELOG_OLDER.TXT file. With this design, tracing cannot consume more than 2 MBytes of your hard disk which is an inconsequential amount. You will notice that the trace file is always named TRACELOG.TXT . I chose to not name the trace file after the name of the calculator program because then your hard drive could get littered with multiple trace files as you traced different calculator programs.
![]() |
Previous | Table Of Contents | Next | ![]() |