¢ Sample Program
Recursive Test Of Subroutine Limits

Author

GO-29, 2019.06.22
support@bigcatos.com

Theory
In GO-29's documentation, Part II - Programmatic Usage, the section Subroutines describes the nature and limits of the calculator's ¦ and § mechanism. In particular we learned that on an actual HP-29C, subroutine calls could be nested to a depth of three, although GO-29 extends that number. If the new, larger, subroutime call depth `n_29` had not been documented, how could you determine it?

With the aid of this diagram we discovered that if you wrote and called enough nested subroutines the LIFO § queue would lose its earliest entries and that the program would terminate prematurely before returning to the Main Program: As it happens, we can couple this observation of early program termination along with a recursive subroutine to discover `n_29`, GO-29's subroutine call depth, or § queue size.

Recursion is pretty opaque until you wrap your head around it, then it's amazingly awesome - search the web and read up on the topic! A recursive subroutine typically contains in its definition instructions that do stuff, then a call to itself to do similar stuff based upon what it just did. Makes perfect sense, right?

Study this simple example of a recursive subroutine, named © 9, which counts-up and displays whatever is stored in R₈. It then calls itself and displays R₈ + 1, etcetera. This will be the basis of our limit-testing recursive subroutine:

© 9
1
d + 8
f 8
U
¦ 9
§

The big problem here (ignoring the fact that R₈ hasn't been initialized) is that the count-up goes on forever, there is no test to exit the virtual loop! If you manually key GSB 9, the subroutine calls itself an infinite number of times. A recursive subroutine always needs a way out, a testable condition that can activate a clean exit from the subroutine. Here, two things should be obvious:

  1. The § from subroutine can never be executed.
  2. Had R₈ been initialized to zero prior to invoking © 9 for the first time, incrementing its value before every ¦ would indicate the current ¦ nesting level. Similarly, decrementing R₈ after every ¦ would account for the § instructions, and would keep the subroutine nesting level value in balance.

    Corollary: We assume that nesting level 0 represents the Main Program.

Let's examine these two observations in greater detail. For this experiment we are probing the calculator to find `n_29` by repeatedly making nested subroutine calls until we exceed the size of the call depth queue. The essential idea is to count-up as we ¦ deeper and create LIFO queue entries, then reverse course and count-down as we § and consume LIFO queue entries. If the call queue becomes truncated then there is no longer a one-to-one correspondence between ¦s and §s (too many ¦s and not enough § information), thus the count-down will stop too soon, and the final subroutine nesting level in R₈ will not be zero.

To do this we must add two small sections of code to subroutine © 9, the first to stop the recursion, and the second to count-down R₈. We stop the recursion by only allowing ¦s to a certain depth, the proposed call back depth, a number that we'll enter from the keyboard and store in R₉. Once the subroutine nesting level reaches this value we'll explicity return, which breaks recursion and initiates the §s that attempt to get back to the Main Program. And counting-down is easy enough, it's the opposite of counting-up!

© 9
1
d + 8
f 8
U
f 9
R
§
¦ 9
§
© 9
1
d + 8
f 8
U
f 9
R
§
¦ 9
1
d - 8
f 8
U
§
The listing on the left shows the additional 3 steps required to stop recursion once the proposed ¦ call limit has been reached.

The listing on the right shows the additional 4 steps required to count-down and display the current nesting level as §s are processed.

The R₈ rule says always increment before ¦ 9, always decrement afterwards.

And that is the completed recursive subroutine © 9, now it's time to visit the Main Program, consisting of two entry points, © 0 the initializer, and © 1 the recursive subroutine controller code. Note the use of the two 8* extended opcodes, |2 to signal an input error, and |1 to indicate succesful return to the Main Program. Theses opcodes are explained in GO-29's documentation, Part III - GO-29 Programs, in the section Special 8* Opcodes.

© 0
Q 0
n
d 9
°
e 1
|2
§
© 1
0
d 8
U
¦ 9
1
d - 8
f 8
U
|1
§
© 0 stores the proposed subroutine nesting limit in R₉, ensures the value is sane, then jumps to © 1.

© 1 controls the recursive subroutine © 9. Before initiating the recursion the nesting level is "incremented" to zero, and after the subroutine returns R₈ is decremented to account for the last §.

The R₈ rule says always increment before ¦ 9, always decrement afterwards.

Instructions
  1. Enter the proposed subroutine call depth to probe, `n_p` >= 1.
  2. Press GSB 0.
  3. The program ¦s and counts-up from 0 until the proposed call depth value is reached.
  4. The program §s and counts-down until either:
    • ✓ the program ends with a non-zero value `n_f` in the display, signifying it has terminated early without reaching the Main Program,

      ∴`n_29=n_p-n_f`

    • × the display shows 0 and the Main Program is reached. The value of `n_29` cannot be determined, go to step 1 and probe again using a larger value of `n_p`.
Program Listing
01 15 13 00 ; LBL 0
02 14 11 00 ; FIX 0
03    14 62 ; INT
04    23 09 ; STO 9
05    15 51 ; x>0
06    13 01 ; GTO 1
07    15 81 ; BEL2
08    15 12 ; RTN
09 15 13 01 ; LBL 1
10       00 ; 0
11    23 08 ; STO 8
12    14 74 ; PAUSE
13    12 09 ; GSB 9
14       01 ; 1
15 23 41 08 ; STO - 8
16    24 08 ; RCL 8
17    14 74 ; PAUSE
18    14 81 ; BEL1
19    15 12 ; RTN
20 15 13 09 ; LBL 9
21       01 ; 1
22 23 51 08 ; STO + 8
23    24 08 ; RCL 8
24    14 74 ; PAUSE
25    24 09 ; RCL 9
26    14 71 ; x=y
27    15 12 ; RTN
28    12 09 ; GSB 9
29       01 ; 1
30 23 41 08 ; STO - 8
31    24 08 ; RCL 8
32    14 74 ; PAUSE
33    15 12 ; RTN