Post Reply 
Chuck Moore on stack size, stack operators and function arguments
11-08-2024, 06:41 AM (This post was last modified: 11-08-2024 06:47 AM by carey.)
Post: #1
Chuck Moore on stack size, stack operators and function arguments
I just came across this Chuck Moore (original Forth developer) interview from 1999 in which he addresses some Forth stack matters that may be interesting to read in relation to similar (though not identical) matters in RPN and RPL calculator stacks. Forth was developed (1970) two years before the HP-35 (1972) and (along with LISP) influenced the development of RPL. I attended an Asilomar Forth Conference (early 1990's?) that Moore led. You can tell from the 1999 interview excerpts below that his views on the stack are minimalist...to the max! :)

Maxinum number of function arguments and stack size

"A Forth word should not have more than one or two arguments. This stack which people have so much trouble manipulating should never be more than three or four deep."

Stack operators and 1st two stack positions

"The words that manipulate that stack are DUP, DROP and OVER period. There's no ..., well SWAP is very convenient and you want it, but it isn't a machine instruction. But no PICK no ROLL, none of the complex operators to let you index down into the stack. This is the only part of the stack, these first two elements, that you have any business worrying about...The others are on the stack because you put them there and you are going to use them later after the stack falls back to their position. They are not there because your using them now. You don't want too many of those things on the stack because you are going to forget what they are."

Stack diagrams and stack operations

"So people who draw stack diagrams or pictures of things on the stack should immediately realize that they are doing something wrong. Even the little parameter pictures that are so popular. You know if you are defining a word and then you put in a comment showing what the stack effects are
and it indicates F and x and y

F ( x - y )

I used to appreciate this back in the days when I let my stacks get too complicated, but no more. We don't need this kind of information. It should be obvious from the source code or be documented somewhere else...So the stack operations that I use are very limited."
Find all posts by this user
Quote this message in a reply
11-08-2024, 08:06 AM
Post: #2
RE: Chuck Moore on stack size, stack operators and function arguments
What's Over? I like roll and swap!!
Find all posts by this user
Quote this message in a reply
11-08-2024, 08:14 AM
Post: #3
RE: Chuck Moore on stack size, stack operators and function arguments
I enjoy Forth immensely; but although I will be forever grateful to Chuck Moore for it, I have to disagree with him on various things.  Even in this one,
Quote: "A Forth word should not have more than one or two arguments,"
*/ has three, and that's pretty basic stuff.  Two counted strings you want to join may have four stack cells, starting address and count of one, and starting address and count of the next.  I know he didn't like CASE structures; but they sure clarify things if you lay them out correctly.  They may not take more than a stack cell or two when executing, but they can run up quite an inventory during compilation, depending on the number of cases.  I wrote dynamic memory allocator words in Forth seven years ago, ALLOC, FREE, and RESIZE, for non-fragmenting buffers for local variables, including arrays (which ANS's way does not accommodate), and even compile temporary Forth words which could be used to compile other words and then deleted after use without affecting the regular dictionary.  The stack gymnastics to do this were the worst I've ever had (although it took little or no debugging to get it working), and having the local variables would have made it easier.  Chicken and egg!

I don't like his ColorForth ideas either.  I don't like color syntax highlighting except in html where a tag's mate could be at any angle from it, rather than always directly below it or to its right.

I think he recanted his ideas on "The map is not the land."

(I might come back and post again after I've had time to watch the video.)

http://WilsonMinesCo.com  (Lots of HP-41 links at the bottom of the links page, at http://wilsonminesco.com/links.html#hp41 )
Visit this user's website Find all posts by this user
Quote this message in a reply
11-08-2024, 08:34 AM (This post was last modified: 11-08-2024 08:45 AM by floppy.)
Post: #4
RE: Chuck Moore on stack size, stack operators and function arguments
Interesting.

Since HP41, influenced by Forth, had more stack manipulation words (and others) than the HP71B Forth, hereunder is a try, to bring more Forth HP71B words to reach the HP41 level.

Link of new Forth or ASM words.
ASM in https://github.com/f4iteightiz/HP71B_for...n/MAFO.TXT

Code:
Compatibility comparison:

****************************************************************
* HP41 and HP71B Forth float functions (standard or new) 
* list created with HP41/ILPER with SF 15  CAT 3
* Legend: () means no need because covered by another function
*             or different behaviour
*         >> tbd word to be worked out
*
* .. regarding the ALPHA functions
* .. No ALPHA register on HP71B but several strings can be created and extensive output words can be used
* ARCL        () put reg data into the ALPHA register, om en page 70
*                STR$
* ASHF        () shift the left-most six characters in the ALPHA
*                SUB$ could create a new string from the character 7 on
* ASTO        () store ALPHA string into Register (max 6 letters), om en page 70
*                STRING define a new variable string then merge another string into it
*                with the use of S<&
* AVIEW       () show ALPHA string into screen, om en page 151
*                ." SOMETHING " 
*                INTEGERVAR @ .
*                STRINGVAR OUTPUT
*                FVAR1 F.
*                FS. the whole float stack
* CLA         () Clear ALPHA register (page 41).
*                Since several strings variables can be created and the display can be a line or
*                a screen, diverse methods can be defined
*                . Put the length of a string variable to zero means it would be cleared 
*                  : CLEARSTR DROP DUP 1 CHARS - 0 SWAP C! 0 ;
*                . Cleaning the HP71B screen line, use CR
*                . Cleaning a 80column screen 
*                  2 STRING RES2CHR 
*                  RES2CHR 27 CHR$ S<& 69 CHR$ S<& 2DROP
*                  RES2CHR OUTPUT .. OK { 0 } screen is clean 
*                  or : PAGE 27 EMIT 69 EMIT ;
*
* 00..N Registers   
*             >> N REG41CR  Creates an array of integer pointer of maximum N float register
*             >> NN RECREG     Recall the address of the NNth register
*             .. further to be done for simulating the registers 00 to 329 on HP41
*
* HP41        Forth HP71B
* +           F+ (Forth standard)
* -           F- (Forth standard)
* *           F* (Forth standard)
* /           F/ (Forth standard)
* 1/X         1/X (Forth standard)
* 10^X        10^X (Forth standard)
* ABS         FABS for real numbers (Forth standard)
* ACOS        ACOS (Forth standard)
* ADV         () advance paper if printer in system om en HP41 page 105
*                activate the printer as output in Forth then use CR
* AOFF        () takes the HP-41C out of ALPHA mode; HP71 entry are num AND ALPHA
*                therefore no need for a switch in Forth
* AON         () function places the HP-41C into ALPHA mode; HP71 entry are num AND ALPHA
*                therefore no need for a switch in Forth
* ARCL        see above
* ASHF        see above
* ASIN        ASIN (Forth standard)
* ASN         () Assign. not programmable on HP41, om en page 270
* ASTO        see above
* ATAN        ATAN (Forth standard)
* AVIEW       see above
* BEEP        BEEP41 (New ASM)
* BST         () Back step (om en page 132). Not programmable. See HP71B Forth debugger
* CAT         LIST ( = CAT 3)
* CF          ST=x  y  look at the ST Forth status flags in HP71B
* CHS         CHS for the X register (Forth standard)
*             FVCHS (New ASM float variable CHS)
* CLA         see above. PAGE word would clean the screen.
* CLD         () clear display (example something displayed with AVIEW): 
*                CR (Forth Word) or PAGE (Forth Word)
* CLP         FORGET (Word).. and all words after
* CLRG        CLFV (New ASM)
* CLs         >> Clear statistics registers (om en page 99)
* CLST        CLST (New ASM)
* CLX         CLX (New ASM)
* COPY        () " XYZ" LOADF, load xyz into FORTHRAM.. 
*             HP41 Copy (download or copy). 
*             Requires ALPHA program name input (om en page 260). 
*             Not programmable in HP41.
* COS         COS (Forth standard)
* D-R         DEG-RAD (New ASM)
* DEC         () Oct to Dec conversion page pdf 111 of om em manual 
*                or https://rosettacode.org/wiki/Non-decimal_radices/Convert#Forth
*                in Forth, use the 8 BASE ! NUMBERINTEGER1 DECIMAL for changing the values
*                in the INTEGER stack from OCT base to DECIMAL. 
*                example 8 BASE ! 326 DECIMAL .
*                        214  OK { 0 } 
*                        which mean 326 in OCT is 214 in decimal
*                The float stack is everytime DECIMAL and any FTOI will
*                be a change DECIMAL to BASE
* DEG         DEGREES
* DEL         () see editor
* DSE         DSE (New ASM) see I DO LOOP of Forth.
*                (of Variable FVARx X Y Z T L..)
* END         ; (Forth standard)
* ENG         ENG (Forth standard)
* ENTER^      FENTER (Forth standard)
* E^X         E^X (Forth standard)
* E^X-1       () see E^X
* FACT        FACT (new ASM)
*             FACX (new Forth; X fractional part ignored)
*             FACI (new Forth; for integer)
* FC?         () look at the ST Forth status flags in HP71B
* FC?C        () look at the ST Forth status flags in HP71B
* FIX         FIX (Forth standard)
* FRC         FP (Forth standard)
* FS?         () look at the ST Forth status flags in HP71B
* FS?C        () look at the ST Forth status flags in HP71B
* GRAD        >> tbd GRAD Mode. 360 degrees = 2 pi radians = 400 grads page pdf 98 hp41 manual
*             GRA>RAD ? since no GRADE mode. Only RADIANS and DEGREES mode so far defined in HP71B
*             GRA>DEG RAD>GRAD DEG>GRAD ?
* GTO         ()
* HMS         >> tbd decimal hours to hour minutes seconds
* HMS+        >> tbd see https://github.com/hp71b/jpcrom/blob/main/src/hms.as
* HMS-        >> tbd see https://github.com/hp71b/jpcrom/blob/main/src/hms.as
* HR          >> tbd HMS to decimal hours 
* INT         IP (Forth standard)
* ISG         ISG (New ASM) see I DO LOOP of Forth.
*                (of Variable FVARx X Y Z T L..)
* LASTX       LASTX (Forth standard)
* LBL         () look at the Forth word ":"
* LN          LN (Forth standard)
* LN1+X       () see LN
* LOG         LGT (Forth standard)
* MEAN        >> tbd see statistics
*
* MOD         PMOD (New Forth word)
* 78 7 PMOD .   > 1  OK { 0 } 
* -78 7 PMOD .  > 6  OK { 0 } 
* 78 -7 PMOD .  > -6  OK { 0 } 
* -78 -7 PMOD . > -1  OK { 0 }
* .. because MOD of HP41
* 78 7 MOD      > 1
* -78 7 MOD     > 6
* 78 -7 MOD     > -6
* -78 -7 MOD    > -1
* .. and MOD HP71 (standard word)
* 78 7 MOD .    > 1  OK { 0 } 
* -78 7 MOD .   > -1  OK { 0 } 
* 78 -7 MOD .   > 1  OK { 0 } 
* -78 -7 MOD .  > -1  OK { 0 } 
* .. and MOD Gforth
* 78 7 MOD .    > 1  ok
* -78 7 MOD .   > 6  ok
* 78 -7 MOD .   > -6  ok
* -78 -7 MOD .  > -1  ok
*
* OCT         () Dec to Oct conversion page pdf 111 of om em manual
*                in Forth, use the 8 BASE ! NUMBERINTEGER1 DECIMAL for changing the values
*                in the INTEGER stack from OCT base to DECIMAL. 
*                example 8 BASE ! 326 DECIMAL .
*                        214  OK { 0 } 
*                        which mean 326 in OCT is 214 in decimal
* OFF         () function simply turns the HP-41C power off
* ON          () When you execute the function ((xEQ) ON (APHA] ), 
*             the turn-off feature is disabled and the HP-41C will no
*             longer automatically turn itself off
* P-R         P-R Polar to Radian coordinates (om en manual page 94).
* PACK        () Pack program memory (page 141). Not programmable in 41
*                look at Forth 71B SHRINK and GROW for similar function
* %           %OF (New ASM)
* %CH         %CH (New ASM)
* PI          PI (New ASM)
* PROMPT      () displays the contents of the ALPHA register 
*                and stops program execution (om en manual page 51).
*                wait for data input.
*                EXPECT96 in Forth
* PSE         PAUSE (Forth standard)
* R^          RUP (Forth standard)
* R-D         DEG-RAD (New ASM)
* R-P         R-P (New ASM) Radial to Polar conversion om en page 92
* RAD         RADIANS (Forth standard)
* RCL         RCL (Forth standard)
* RDN         RDN (Forth standard)
* RND         Round HP41 om en page 78. RND (New Forth word) round according N in integer stack and 
*                  not accordingly the activ SCI or ENG stored value 
* RTN         ;
* SDEV        >> tbd standard deviation statistics (om en page 101)
* SCI         SCI, scientific notation display om en page 33
* SF          () look at the ST Forth status flags in HP71B
* s+          >> tbd statistics registers (om en page 99)
* s-          >> tbd statistics registers (om en page 99)
* sREG        >> tbd beginning of a block of six statistical registers (om en page 99)
* SIN         SIN (Forth standard)
* SIGN        XSIGN ( New ASM; put 1 in X if X>=0, else -1)
*             SIGN in Forth is for integer only (not float)
* SIZE        () allocate X registers (variable). Not programmable.
*             in Forth: make variable declarations? a float variable list?
* SQRT        SQRT  (Forth standard)
* SST         >> tbd with Forth bebugger. Single step (om en page 129, 132). Not programmable.
* ST+         ST+ (New ASM)
* ST-         ST- (New ASM)
* ST*         ST* (New ASM)
* ST/         ST/ (New ASM)
* STO         STO (Forth standard)
* STOP        () HP71B key ATTN Stops program execution (hp41 om en page 145).
* TAN         TAN (standard Forth)
* TONE        TONE (New ASM)
* VIEW        FV. (New in Forth)
* X=0?        X=0? (standard Forth)
* X#0?        X#0? (New ASM)
* X<0?        X<0? (New ASM)
* X<=0?       X<=0? (New ASM)
* X>0?        X>0? (New ASM)
* X=Y?        X=Y? (standard Forth)
* X#Y?        X#Y? (standard Forth)
* X<Y?        X<Y? (standard Forth)
* X<=Y?       X<=Y? (standard Forth)
* X>Y?        X>Y? (standard Forth)
* X<>         X<> (New ASM)
* X<>Y        X<>Y  (standard Forth)
* XEQ         () call the word in the Forth prompt
* X^2         X^2 (standard Forth)
* Y^X         Y^X (standard Forth)

HP71B 4TH/ASM/Multimod, HP41CV/X/Y & Nov64d, PILBOX, HP-IL 821.62A & 64A & 66A, Deb11 64b-PC & PI2 3 4 w/ ILPER, VIDEO80, V41 & EMU71, DM41X
Find all posts by this user
Quote this message in a reply
11-08-2024, 12:31 PM
Post: #5
RE: Chuck Moore on stack size, stack operators and function arguments
While Moore's views on stack depth are rather extreme, we must realize that a major reason for the "stackrobatics" that we see in RPL programs is speed. Stack operations are faster than algebraic expressions or STO and RCL operations, and the 48 series is not that fast to begin with, so programs tend toward heavy use of the stack. NewRPL and (presumably) DB48X have more efficient variable assignments and shouldn't be as dependent on the stack, so we may see lighter stack usage with these newer systems.
Find all posts by this user
Quote this message in a reply
11-08-2024, 05:51 PM
Post: #6
RE: Chuck Moore on stack size, stack operators and function arguments
(11-08-2024 08:06 AM)dm319 Wrote:  What's Over? I like roll and swap!!

OVER is in RPL.

It copies stack level 2 to level 1, with lift:

3 2 1 ➝ 3 2 1 2

It's equivalent to 2 PICK. As opposed to 2 ROLL, which moves rather than copies.

Also, OVER SWAP dupes level 2, with lift:

3 2 1 ➝ 3 2 2 1


Apologies if you already knew that, and I've just missed the point.

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 17B/II/II+ 28S 42S/DM42 32SII 48GX 50g 35s WP34S PrimeG2 WP43S/pilot/C47
Casio, Rockwell 18R
Find all posts by this user
Quote this message in a reply
11-08-2024, 08:03 PM
Post: #7
RE: Chuck Moore on stack size, stack operators and function arguments
(11-08-2024 05:51 PM)cdmackay Wrote:  Apologies if you already knew that, and I've just missed the point.

No I didn't know that, thank you for explaining. OVER seems a little esoteric - I'm not sure why it's more unnatural than SWAP. Were there any HP calculators that had OVER as a stack manipulation function/button?
Find all posts by this user
Quote this message in a reply
11-09-2024, 01:57 AM
Post: #8
RE: Chuck Moore on stack size, stack operators and function arguments
(11-08-2024 08:03 PM)dm319 Wrote:  OVER seems a little esoteric - I'm not sure why it's more unnatural than SWAP. Were there any HP calculators that had OVER as a stack manipulation function/button?

Sure. On the HP-41C/CV/CX and HP-42S, it is "RCL Y".
Find all posts by this user
Quote this message in a reply
11-09-2024, 02:14 AM
Post: #9
RE: Chuck Moore on stack size, stack operators and function arguments
(11-08-2024 06:41 AM)carey Wrote:  Forth was developed (1970) two years before the HP-35 (1972)

I know you didn't state that RPN on the HP-35 was influenced by Forth, but just in case anyone might get that idea, I'd point out that Forth was developed:

* two years after the HP-9100
* seven years after the Friden EC-130
* 25 years after the Zuse Z4
* 29 years after the Zuse Z3

All of those used RPN, though not in exactly the same form as that of the HP-35.

Forth may have been influenced by expression evaluation algorithms developed by computer scientists in the 1950s and 1960s.
Find all posts by this user
Quote this message in a reply
11-09-2024, 10:47 AM
Post: #10
RE: Chuck Moore on stack size, stack operators and function arguments
And although we all know and love RPN, we also know the real reason it was used in early machines was lack of space to build a good recursive descent parser.
-J
Find all posts by this user
Quote this message in a reply
11-09-2024, 10:48 AM
Post: #11
RE: Chuck Moore on stack size, stack operators and function arguments
(11-08-2024 08:03 PM)dm319 Wrote:  OVER seems a little esoteric - I'm not sure why it's more unnatural than SWAP.

You end up using it quite frequently in RPL. It's a major tool in the art of stackrobatics.

The big difference with SWAP is that it gives you a copy of level 2 and shifts everything upwards. It allows you to consume whatever is in level 2 without losing it like you would do using SWAP.

(11-08-2024 08:03 PM)dm319 Wrote:  Were there any HP calculators that had OVER as a stack manipulation function/button?

Not as a direct key as far as I'm aware but the HP 41C family and 42S certainly allowed RCL Y (41C) or RCL ST Y (42S).

Current daily drivers: HP-41CL, HP-15C, HP-16C
Find all posts by this user
Quote this message in a reply
11-09-2024, 11:31 AM
Post: #12
RE: Chuck Moore on stack size, stack operators and function arguments
(11-08-2024 12:31 PM)John Keith Wrote:  While Moore's views on stack depth are rather extreme, we must realize that a major reason for the "stackrobatics" that we see in RPL programs is speed. Stack operations are faster than algebraic expressions or STO and RCL operations, and the 48 series is not that fast to begin with, so programs tend toward heavy use of the stack. NewRPL and (presumably) DB48X have more efficient variable assignments and shouldn't be as dependent on the stack, so we may see lighter stack usage with these newer systems.

Well, I can comment on this specifically.

RPN calculators typically have the actual values in the stack or in registers. Except in the case of indirect accessing, the cost of accessing a stack register or memory register is roughly the same: you simply load the data from a known location. X, Y, Z or T are known locations or registers, so are R0, R19, etc.

In RPL in general, and DB48x in particular, the stack can contain arbitrary objects. This is achieve by having pointers to objects on the stack, where the objects themselves have some type identifier in their memory representation (a prologue for HP calculators or newRPL, an LEB128-encoded type ID for DB48x). This adds a level of indirection relative to RPN.

This means that the cost of accessing a stack element is constant: you just load a pointer, and you have your object. However, the cost of accessing a named global variable is not constant. You need to lookup the name by scanning the curent directory, and if that fails, the parent directory, and so on. Once you have found the value, you put a pointer to it on the stack, and from there, the cost of operations on that value is the same as for any object (it does not matter if the object is in a global or some temporary). But the lookup of a named global variable is not constant and potentially somewhat expensive. As far as I know, all existing RPL implementations do a simple linear search, so the cost is O(n) where n is the number of variables to search.

RPL also has a notion of local variables. The HP48 implementation uses the prologue 02E6D for local names, but they otherwise have the same structure as a regular name, i.e. they contain a number of characters and then the characters of the name. In other words, on the HP48, local names must must be looked up as well, although presumably on a smaller set of names. They may be a tiny bit faster, but the cost of lookup is still not fixed.

DB48x local names are implemented differently. Instead of storing the names in each local name, they are stored in the program declaring the locals. In other words words, on HP48, «→ A B C « A B × A B + C ÷ »» will store the character sequences for names A and B 3 times, and for C twice, whereas the DB48x implementation stores them only once. The local name references simply index the local variables, i.e. the inner program is really stored as « r0 r1 × r0 r1 + r2 ÷ ». It is only when decompiling the program that r0 is turned back into A. You can see this effect at the moment because the debugger is not smart enough to show the name, so it will show LocalVariable0 instead of A.

The benefit of the DB48x approach is that now local name references are fixed: it's just an index into an array of pointers similar to the stack. This means that on DB48x, local names are significantly faster than local names, and should be used whenever you can.

A similar optimization exists for XLIB objects (library objects). In that case, it's even more important because XLIB objects are loaded from disk, which is expensive. The first time you evaluate an XLIB, it is loaded from disk, compiled, and from there on, the cost of evaluation is the same as a stack object. No lookup is needed.

DB48X,HP,me
Find all posts by this user
Quote this message in a reply
11-09-2024, 01:20 PM
Post: #13
RE: Chuck Moore on stack size, stack operators and function arguments
(11-09-2024 11:31 AM)c3d Wrote:  As far as I know, all existing RPL implementations do a simple linear search, so the cost is O(n) where n is the number of variables to search.
...

This means that on DB48x, local names are significantly faster than local names, and should be used whenever you can.

Thanks, that was very informative, and leads me to another question: Would it be possible to encode global names with a hash table, binary tree or similar data structure with O(log2(n)) access time? And going further, would it be practical to add a set or dictionary data type to RPL?

Also I thank you for your work on this inspiring project. I was sad when Claudio discontinued work on NewRPL and DB48X gives me new hope. I am also hoping for Swiss Micros or others to make a hardware platform with a keyboard more suitable for an RPL calculator. In the mean time an Android emulator would be nice. Smile

BTW, I assume that in the quoted text you meant "global names are significantly faster than local names".
Find all posts by this user
Quote this message in a reply
11-09-2024, 02:14 PM
Post: #14
RE: Chuck Moore on stack size, stack operators and function arguments
(11-09-2024 01:20 PM)John Keith Wrote:  Would it be possible to encode global names with a hash table, binary tree or similar data structure with O(log2(n)) access time?

I asked myself the same question when I implemented variable lookup in Free42, and I decided that the added complexity, and the added computational overhead for maintaining these data structures when variables are added or deleted, wouldn't be worth it. I didn't do any empirical tests to confirm this intuition, but rather, I based it on the observation that typically, the number of variables is not that great, so the linear search isn't that expensive.

Also, since the search starts with the most recently created variables, its real-world efficiency is a lot closer to O(1) than O(n), at least assuming the current directory isn't full of old junk that never gets cleaned up.

(11-09-2024 01:20 PM)John Keith Wrote:  BTW, I assume that in the quoted text you meant "global names are significantly faster than local names".

This depends on the implementation, but typically, local variables are searched before global ones. In Free42 and Plus42 specifically, the current function's local variables are guaranteed to be searched before anything else, so they will be found very quickly. I imagine RPL is pretty similar under the hood.
Visit this user's website Find all posts by this user
Quote this message in a reply
11-09-2024, 07:08 PM
Post: #15
RE: Chuck Moore on stack size, stack operators and function arguments
Hey
Back in the 70's I thought I would never figure out the stack. Now I can't use a regular ='s calculator. People at work want to use my HP-11 and it's fun to watch them look for the equals key.

That being said how did HP decide that RPN was the way to go, did they use Forth or RPN exclusively for basic and advanced math and were there holdouts.
RH
Find all posts by this user
Quote this message in a reply
11-09-2024, 08:09 PM
Post: #16
RE: Chuck Moore on stack size, stack operators and function arguments
(11-09-2024 07:08 PM)knife31 Wrote:  ...
That being said how did HP decide that RPN was the way to go, did they use Forth or RPN exclusively for basic and advanced math and were there holdouts.
RH

To better understand RPN logic and why HP used it, you need to look at some of the history of electronic scientific calculators.

HP models, with their RPN logic and a four level stack, were able to provide a workable entry system that allowed most problems, even complex ones, to be solved without writing down intermittent results. The major advantage of using this logic system is that it greatly reduced the system complexity and RAM/ROM requirements over trying to implement an algebraic entry system that supported parenthesis and rules of operation precedence. The RPN methods used to break down a problem and to work it from the inside out also had the added advantage of mimicking the methods you would have used to solve the problem with a pencil and paper (or a slide rule). This made it easier to learn by someone who was already used to solving those type of complex problems in this manner.

Conversely, the early TI models without parenthesis keys (for example the SR-50 and SR-51) were not easy to use on complex calculations. The mental gyrations needed for calculating parenthesis heavy formulas could be daunting if you didn't break down the equation into simpler subsets first. Even then, this may have required intermediate results to be written down and re-entered in order to solve some problems. The fact that TI didn’t introduce a model with Algebraic Operating System (AOS) and parenthesis until September 1975 (the SR-52), a full 3-2/3 years after the HP-35, really drives home how difficult it was to implement at the time. Even these early TI models still used RPN entry for single argument functions like Sin and square root. It was not until around 1990 when TI introduced its EOS logic on the TI-81 that they had what could be considered a true algebraic entry system, 16 years after the introduction of the SR-50.

The following Datamath page describes the long evolution that TI had with algebraic entry on their calculator models.
http://www.datamath.org/Sci/WEDGE/SR-52_...ing_System:
Visit this user's website Find all posts by this user
Quote this message in a reply
11-09-2024, 08:55 PM
Post: #17
RE: Chuck Moore on stack size, stack operators and function arguments
(11-09-2024 01:20 PM)John Keith Wrote:  Thanks, that was very informative, and leads me to another question: Would it be possible to encode global names with a hash table, binary tree or similar data structure with O(log2(n)) access time?

There is already a binary search for keywords, although I added that relatively recently (when I added the ability for the help to show the various spellings, which implied that while displaying the help, I needed to do a few keyword lookups as well). For keywords, where there are a little over 1000 keywords at the moment, this gave me roughly a 2 to 3x improvements (from memory). This was after reducing the number of theoretical lookups from ~500 (1000/2 on average) down to ~10 (log2(1000)).

So why not a 50x improvement? That's because the binary search is a bit more complicated and probably not as cache efficient as a linear search. I'm not sure how smart prefetching is on such a small chip, but jumping at random in memory has to be less efficient than moving forward regularly.

So this means that the chances we get a real benefit for a number of global variables that, on a typical calculator, is in the order of a dozen at most, seems pretty low. In number of iterations, you'd get let's say from 32 down to 5, but then each of the iteration would cost you 15 times more if the keyword lookup is any indication, and since 5x15 is much higher than 32, you would lose.

Quote:And going further, would it be practical to add a set or dictionary data type to RPL?

That data type actually exists, it's called the directory. The functionality to use that as a true dictionary is not fully exposed yet, but it's in plan. At the moment, you need to enter the directory by evaluating it, use « Value Key Store » to associate Value to Key, use « Key Recall » to get the value for Key, use just Key to evaluate the value associated to the key, and so on.

While you might think that a directory only contains name/value pairs, it's really key/value pair internally. At the moment, the ability to use non-name keys in directories is somewhat limited, but it's already exposed in DB48x as follows:

- Some special names that are really keywords are allowed, e.g. 'EQ', 'PPAR' or 'ΣDat' or 'CST'. Two primary benefits are that these special names use only one or two bytes in the directory, and then they display according to user preferences, i.e. 'EQ' or 'eq' or 'Equation', 'CST' or 'CustomMenu' depending on RPL style.

- The `NumberedVariables` flag allows you to use numbers as names, mostly to facilitate the porting of code written for keystroke calculators. So with that flag set, you can replace "3 STO00" with "3 0 STO".

- The user-mode key assignments are stored in a variable called 'Keymap' that is actually a directory with numbered entries, the index being the native keycode. So if you run something like « 'abs' 24.2 AssignKey », on a DM42 you will be able to enter the KeyMap directory, and you will see a 104 entry that is the native keycode for shifted D, and if you recall that 104 you will see the 'abs' assigned to that key.

In the future, I expect a number of additional features that will let you use directories on the stack, and not just directories in global variables. Stay tuned.

Quote:Also I thank you for your work on this inspiring project. I was sad when Claudio discontinued work on NewRPL

Is this official, or just an observation that he stopped working on it?

Quote: and DB48X gives me new hope. I am also hoping for Swiss Micros or others to make a hardware platform with a keyboard more suitable for an RPL calculator. In the mean time an Android emulator would be nice. Smile

I heard that a few times. I actually tried building one, but for now it needs more work.

Quote:BTW, I assume that in the quoted text you meant "global names are significantly faster than local names".

Yes but the opposite, it's local names that are faster, because it's just a pointer load using some local variable index.

DB48X,HP,me
Find all posts by this user
Quote this message in a reply
11-09-2024, 10:37 PM
Post: #18
RE: Chuck Moore on stack size, stack operators and function arguments
Interesting that TI was behind the 8 ball on this one. Thanks for the insight.
RH
Find all posts by this user
Quote this message in a reply
11-10-2024, 01:55 PM
Post: #19
RE: Chuck Moore on stack size, stack operators and function arguments
(11-09-2024 08:55 PM)c3d Wrote:  Is this official, or just an observation that he stopped working on it?


Quote:BTW, I assume that in the quoted text you meant "global names are significantly faster than local names".

Yes but the opposite, it's local names that are faster, because it's just a pointer load using some local variable index.

My reference to NewRPL came from this post where Claudio said that NewRPL is "almost halted" due to personal reasons. And yes, I managed to switch "local" and "global" in my response. Thanks again for your detailed explanations.
Find all posts by this user
Quote this message in a reply
Post Reply 




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