[Free42] RTN Stack Full

[Thomas Klemm]

I used pl0_hp42s.py to compile this recursive PL/0 program to calculate the factorial of a number \(n\):

Code:

VAR n,f;

PROCEDURE fact;
BEGIN
    IF n > 1 THEN
        BEGIN f := n*f; n := n-1; CALL fact
        END
END ;

BEGIN
    ?n; f := 1; CALL fact; !f
END .

This is the result:

Code:

GTO 00     # main
# Register 01: n
# Register 02: f
# Procedure 01: fact
LBL 01     # fact
1
RCL 01     # n
X≤Y?
GTO 02     # if true
RCL 01     # n
RCL 02     # f
×
STO 02     # f
RCL 01     # n
1
-
STO 01     # n
XEQ 01     # fact
LBL 02     # end if
RTN        # return fact
LBL 00     # main
INPUT 01   # n
1
STO 02     # f
XEQ 01     # fact
RCL 02     # f
PROMPT
END        # main

To my surprise it worked using Free42.

To analyse it further, I reduced the program to:

Code:

00 { 19-Byte Prgm }
01 GTO 00
02▸LBL 01
03 X=0?
04 GTO 02
05 1
06 -
07 XEQ 01
08▸LBL 02
09 RTN
10▸LBL 00
11 XEQ 01
12 PI
13 END

You can run it with any integer number from 0 to 1023 and will get \(\pi\).
However, with 1024 you will get an error message:

RTN Stack Full

In HISTORY I found the following remark:

Quote:

Code:

* Dynamically growing RTN stack. It is not unlimited; in order to prevent
  infinite recursion from eating up all memory, it maxes out at 1024 levels.
  The new stack behaves a bit different than the old version (and the real
  HP-42S): when an XEQ happens while the stack is full, the old version would
  silently discard the oldest RTN, while with the new version, this returns a
  "RTN Stack Full" error.

On a real HP-42S or an HP-41C the program would stop at line 09 when all return addresses are consumed.
Instead of \(\pi\) it would display \(0\).

In case of the fact program from above the following lines are not executed:

Code:

RCL 02     # f
PROMPT
END        # main

Therefore the result is not displayed.

Conclusion

For any meaningful program, recursion doesn't work on a real HP-42S.
However, if the target machine is Free42, it can be used within the limitation of 1024 stack levels.

[Thomas Okken]

I should point out that the RTN stack in Free42 and Plus42 is dynamic, so it's not a fixed 1024-entry array, and it could be allowed to grow to more than 1024 levels. The reason I put in the 1024-level limit is to provide a graceful failure mode for programs with infinite recursion bugs.

I could make the limit user-configurable, but there hasn't seemed to be a reason to do so yet.

[Thomas Klemm]

In this case we can easily eliminate the tail-call by replacing the XEQ with a GTO command.
This makes it effectively a while-loop.

IIRC Python uses a similar limit but it can be configured.
If it is not a big effort, then why not?

OTOH I will probably never need it.
Apart from recursion, 6 stack levels has been enough for me.

[Thomas Okken]

(01-15-2024 12:17 AM)Thomas Klemm Wrote:  IIRC Python uses a similar limit but it can be configured.
If it is not a big effort, then why not?

I think I rejected the idea originally because adding a field in the Preferences dialog is such a hassle. But then again, if I make it a setting in the MODES menu, it won't affect the shell at all, and then the coding effort is minimal. Hmm...

(01-15-2024 12:17 AM)Thomas Klemm Wrote:  OTOH I will probably never need it.
Apart from recursion, 6 stack levels has been enough for me.

Indeed. I implemented the dynamic RTN stack (and LSTO) specifically to support recursive programming. Though they turned out to be useful for equations in Plus42 as well.