[Free42] RTN Stack Full
01-14-2024, 10:29 PM
Post: #1
 Thomas Klemm Senior Member Posts: 2,104 Joined: Dec 2013
[Free42] RTN Stack Full
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.
01-14-2024, 11:20 PM
Post: #2
 Thomas Okken Senior Member Posts: 1,893 Joined: Feb 2014
RE: [Free42] RTN Stack Full
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.
01-15-2024, 12:17 AM
Post: #3
 Thomas Klemm Senior Member Posts: 2,104 Joined: Dec 2013
RE: [Free42] RTN Stack Full
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.

01-15-2024, 02:14 AM
Post: #4
 Thomas Okken Senior Member Posts: 1,893 Joined: Feb 2014
RE: [Free42] RTN Stack Full
(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.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)