Stack Overflow Sensing

[hansklav]

In 1978 in his excellent book 'Algorithms for RPN Calculators' John A. Ball in a separate chapter gave several 'Suggestions for Future Developments' in RPN calculators. Most of these eventually found their way into later calculator models, the most recent being the eight-register stack in the WP 31S and 34S.

He also gave a somewhat elaborate scheme to sense Stack Overflow, which never materialized, maybe because it was a bit too convoluted. His proposal needed a special symbol for 'clear' (which was an incarnation of zero), a CLR key which 'cleared' all stack registers, and an extended R↑ key which also could be used as a number separator instead of ENTER↑. On pressing R↑ a 'clear' appeared in X (the display), provided the stack was not full. By watching for a 'clear' after each R↑ keypress one could ensure that no numbers were lost off the top of the stack. Of course R↑ should temporarily disable stack lift, just like ENTER↑.

I suppose few people would question the usefulness of Stack Overflow Sensing in RPN calculators with a limited stack height. An extended stack height like the eight-register stack makes its need less pressing, but even in the WP 34S in complex number mode the stack height is only four.

A simple Stack Overflow Sensing scheme would be welcome in these calculators. Imho the only essential ingredients would be:
- an 'empty' symbol
- a CLS key which clears the stack registers above X by making them 'empty'. The X register could still be cleared to zero. This key also sets a 'no overflow' flag, which makes an annuntiator NO ('No Overflow') visible
- an extra stack overflow sensing register above the Top of the stack which would clear the 'no overflow' flag and so would make the NO ('No Overflow') annuntiator invisible when a non-empty number would be copied into it from the Top of the stack.

Such a Stack Overflow Sensing scheme can be ignored when you don't need it.
Only when you would like to watch for stack overflow in a very complex calculation you start the calculation by pressing CLS and you watch that the NO ('No Overflow') annuntiator remains visible. In this way you can be certain that the stack did not overflow during your calculation and you can be more confident of your result. Top stack level repetition ('top copy on pop') and Roll up and down would still function.

Interestingly the original HP-35 had most of the hardware needed for the above SOS scheme already on board: a CLR key and the red dot (which could have functioned as a No Overflow indicator).

Hans

[Garth Wilson]

You don't need any extra hardware. My initial exposure to a stack was my HP-41, so it was natural to think of things getting copied from one register to the next like the manuals show. This is very inefficient though. What is routinely done in programming at levels that give the user tighter control of the machine, primarily meaning (but not limited to) assembly language, does not involve so much (or necessarily any) copying, but rather just incrementing or decrementing a pointer which acts as an offset to the stack area of memory. The pointer rolls over wherever the number of bits hits a limit; so if you have 8 registers, you use 3 bits for the pointer. When it goes from binary 111 to 000, or vice-versa, you have stack underflow or overflow, depending on the direction you make the stack grow. The depth of the stack could be displayed all the time if desired, or checked only when desired. Stack initialization can be as simple as zeroing the pointer.

[hansklav]

(10-06-2014 12:27 AM)Garth Wilson Wrote:  You don't need any extra hardware. My initial exposure to a stack was my HP-41, so it was natural to think of things getting copied from one register to the next like the manuals show. This is very inefficient though. What is routinely done in programming at levels that give the user tighter control of the machine, primarily meaning (but not limited to) assembly language, does not involve so much (or necessarily any) copying, but rather just incrementing or decrementing a pointer which acts as an offset to the stack area of memory. The pointer rolls over wherever the number of bits hits a limit; so if you have 8 registers, you use 3 bits for the pointer. When it goes from binary 111 to 000, or vice-versa, you have stack underflow or overflow, depending on the direction you make the stack grow. The depth of the stack could be displayed all the time if desired, or checked only when desired. Stack initialization can be as simple as zeroing the pointer.

I suppose you're right that an extra Stack Overflow sensing register above the T register would not be necessary. The firmware would only have to watch for a state where a stack lift is done while the T register is "non-empty". But stack initialization with Stack Overflow Sensing ON would need more than zeroing a pointer, it would need to set at least Y, Z and T to the "empty" state. X could be left unchanged (maybe that is even more useful than setting it to zero for historical reasons).

The only "hardware" needed would be a CLS key function (that could even be named "SOS") and a NO ("No Overflow") annuntiator that appears on pressing the CLS/SOS key and disappears on Stack Overflow.

Very unintrusive when you don't need it, very useful when you would like to watch for stack overflow in a complicated long calculation on an RPN calculator with a limited stack height.

Hans

[walter b]

Could you please show me a real world calculation leading to a stack overflow in an 8-level stack?

d:-?

[hansklav]

(10-07-2014 08:15 PM)walter b Wrote:  Could you please show me a real world calculation leading to a stack overflow in an 8-level stack?

Of course that depends on your definition of 'real world calculation' ;-)

As said the need for Stack Overflow Sensing in an 8-level RPN calculator is less pressing, but it would still be useful for the novice to get instant confidence in his machine when doing a complex calculation without having to count the stack levels used or checking the whole calculation on WolframAlpha.

And in Complex Mode also the WP 34S has only 4 stack levels, and there SOS would even be helpful for the more seasoned user.

Hans

[Garth Wilson]

(10-07-2014 07:56 PM)hansklav Wrote:  I suppose you're right that an extra Stack Overflow sensing register above the T register would not be necessary. The firmware would only have to watch for a state where a stack lift is done while the T register is "non-empty". But stack initialization with Stack Overflow Sensing ON would need more than zeroing a pointer, it would need to set at least Y, Z and T to the "empty" state. X could be left unchanged (maybe that is even more useful than setting it to zero for historical reasons).

Imagine this, per my earlier post: You have an 8-level stack, in memory addresses $F8 to $FF, ie, base address $F8 and a 3-bit index value 0 through 7 (7 being 111 in binary, so one more would wrap around). For the case of simplicity of discussion, if it's on a calculator, let's say these memory locations each consist of as many bits as the calculator's normal registers, like the HP-41's 56 bits. When the stack is empty, the index is 7, so the next location to be written is $F7. What's in Z? The index value has to be 4 or less to even have a Z, so you can consider Z to be empty, non-existent, or zero, however you like, and it won't matter what's in any of the addresses $F8 through $FF. The When you push something onto the stack, it goes in $F7, and the index is decremented to 6. The fact that the index is now 6 means the stack is now one cell deep. When the index gets down to 0, you have only one cell left to push something onto the stack with. After that push, any more will mean an overflow. Going the other direction, any attempt to drop a cell off the stack when the index is at 7 will mean an underflow. Unused registers don't have to be zeroed, because the index tells you that the stack is too shallow to use those memory spaces.

hansklav Wrote:Could you please show me a real world calculation leading to a stack overflow in an 8-level stack?

To quote an earlier (5/28/2004) post of mine: Ah, but now you're thinking of just one equation, done by hand. Think of a program where you're using let's say 3 levels on the stack, and you want to run a subroutine to get the next number to work with. Let's say that subroutine needs 3 levels as well, and futher, that subroutine calls another one that needs 2 or 3 or 4, etc.. As you're programming, you don't have to care what's beyond the few levels you're working with at the moment. Each routine is concerned with only its few stack levels, even if there are 23 other things on the stack below. It doesn't matter. You won't get confused. We do this in Forth all the time, and most things work the first time we try them, unlike the case with other languages. Stack comments in the code only mention the few things that are relevant to the particular routine, regardless of what else uses that routine and leaves other numbers pending on the stack. The maximum stack depth is deep enough that we never have to worry about overflowing it.

To further add to the stack space requirement, I've had control-timer interrupts on my 41cx, and I/O interrupts in other environments, which would hit at any time-- and you better have the stack depth to service them without fouling things up for the main program when the calculator or computer gets back to it. If you don't, then the interrupt needs extra overhead to store away the existing stack so it can restore it when it's ready to give control back to the main program.

[Paul Dale]

(10-07-2014 08:15 PM)walter b Wrote:  Could you please show me a real world calculation leading to a stack overflow in an 8-level stack?

This is very easy to do when programming.

For manual calculations, I tend to agree.


- Pauli

[hansklav]

(10-07-2014 10:18 PM)Paul Dale Wrote:  

(10-07-2014 08:15 PM)walter b Wrote:  Could you please show me a real world calculation leading to a stack overflow in an 8-level stack?

This is very easy to do when programming.

For manual calculations, I tend to agree.

It is interesting that John A. Ball in his famous 1978 book in the chapter on 'Suggestions for Future Developments in RPN calculators' mentions both the 8-level stack and stack overflow sensing.

I suspect that he would have considered both improvements highly desirable in a calculator striving to "come pretty close to the ultimate RPN scientific calculator".

Hans