[Free42] RTN Stack Full - Printable Version

[Free42] RTN Stack Full - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: Not HP Calculators (/forum-7.html)
+--- Forum: Not quite HP Calculators - but related (/forum-8.html)
+--- Thread: [Free42] RTN Stack Full (/thread-21163.html)

[Free42] RTN Stack Full - Thomas Klemm - 01-14-2024 10:29 PM

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.

RE: [Free42] RTN Stack Full - Thomas Okken - 01-14-2024 11:20 PM

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.

RE: [Free42] RTN Stack Full - Thomas Klemm - 01-15-2024 12:17 AM

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.

RE: [Free42] RTN Stack Full - Thomas Okken - 01-15-2024 02:14 AM

(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.