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." |
|||
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!!
|
|||
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 ) |
|||
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: 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 |
|||
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.
|
|||
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 |
|||
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? |
|||
11-09-2024, 01:57 AM
Post: #8
|
|||
|
|||
RE: Chuck Moore on stack size, stack operators and function arguments | |||
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. |
|||
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 |
|||
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 |
|||
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 |
|||
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. 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. BTW, I assume that in the quoted text you meant "global names are significantly faster than local names". |
|||
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. |
|||
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 |
|||
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: ... 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: |
|||
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. 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 |
|||
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 |
|||
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? 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. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 4 Guest(s)