HP calculators, slide rules, and Forth all have something in common: reverse polish notation or RPN. Admittedly, slide rules don’t really have RPN, but you work problems on them the same way you do with an RPN calculator. For whatever reason, RPN didn’t really succeed in the general marketplace, and you might wonder why it was ever a thing. The biggest reason is that RPN is very easy to implement compared to working through proper algebraic, or infix, notation. In addition, in the early years of computers and calculators, you didn’t have much to work with, and people were used to using slide rules, so having something that didn’t take a lot of code that matched how users worked anyway was a win-win.
What is RPN?
If you haven’t encountered RPN before, it is an easy way to express math without ambiguity. For example, what’s 5 + 3 * 6? It’s 23 and not 48. By order of operations you know that you have to multiply before you add, even if you wrote down the multiplication second. You have to read through the whole equation before you can get started with math, and if you want to force the other result, you’ll need parentheses.
With RPN, there is no ambiguity depending on secret rules or parentheses, nor is there any reason to remember things unnecessarily. For instance, to calculate our example you have to read all the way through once to figure out that you have to multiply first, then you need to remember that is pending and add the 5. With RPN, you go left to right, and every time you see an operator, you act on it and move on. With RPN, you would write 3 6 * 5 +.
While HP calculators were the most common place to encounter RPN, it wasn’t the only place. Friden calculators had it, too. Some early computers and calculators supported it but didn’t name it. Some Soviet-era calculators used it, too, including the famous Elektronika B3-34, which was featured in a science fiction story in a Soviet magazine aimed at young people in 1985. The story set problems that had to be worked on the calculator.
How to Do Algebraic
It is illustrative to see how complex it is to do algebraic expressions the “normal” way. The usual method is to use two stacks and a precedence table. The steps are:
1. Grab a token
2. If the token is a number, push it on the value stack.
3. If the token is an operator, check to see if it is lower in precedence than the top of the operator stack (e.g., this is a plus sign, and the top of the stack is for multiplication). If so, do the indicated operation from the top of the stack, update the value stack, and then repeat this step.
4. Once the current operator is higher in precedence than the top of the operator stack, push it on the operator stack.
5. Repeat all steps until you are done, and then work through whatever is left on the stack.
Usually, you have a low precedence start marker and a high precedence end marker that are fake tokens. Open parenthesis is also high precedence. After that, you have the operators in their usual order. So consider (5+2) + 6*3. If you add the start and end markers (I’ll use []), you get [(5+2)+6*3].
After processing the first plus sign, the operator stack will contain: [(+, and the value stack will have 5 (and, soon, 5 2). The close parenthesis will cause 5+2 to calculate and remove the opening match. So then the value stack will have 7, and the operator stack will be empty except for the start marker.
When you read the end marker, the value stack will be 7 6 3, and the operator stack will be [+ *. Since the end marker is higher than everything else, step 3 will cause it first to compute 6*3, leaving the stacks to contain 7 18 and [+. Another pass through step 3 leaves 25 and [ which matches the ], and the operation is complete.
While this isn’t that hard, it does take two stacks and a table. The stacks can be arbitrarily long, although in practice, that isn’t necessary. But it still seems like a lot of work.
Python RPN
Processing RPN, on the other hand, is easy. If you see a number, push it on the value stack. If you see an operator, pop off enough stuff from the stack, do the operation, and put the result back on the stack. In Python, this is very simple (see the entire code on this gist):
# parse an RPN string and execute it
def parse(self,s):
tokens=s.split()
for token in tokens:
try:
num=float(token)
rpn.push(num)
except ValueError:
if token=="x" or token=="X": # exchange top of stack
exchange()
elif token=="?": # dump stack
self.dump()
elif token=="+":
rpn.add()
elif token=='-':
rpn.sub()
elif token=="*":
rpn.mul()
elif token=="/":
rpn.div()
elif token[0]=="!":
self.vars[token[1:]]=self.peek() # store tos in var
elif token[0]=="@":
self.push(self.vars[token[1:]]) # push var to tos
else:
raise Exception("Unknown operator or number:" + token)
This handles the four basic math functions and a few special operators to exchange the two top stack elements or display the stack. It can also store named variables (!somevar) and use them again later (@somevar). Prefer C? There is a simple version in the gist, also.
Why Not?
If you need to represent math in a program, you might consider RPN. It is fast to write and easy on resources. Of course, you can just as easily make the infix algorithm spit out RPN code instead of doing the work itself, but there isn’t much benefit to that unless you are writing a compiler. Going the other way is possible, too, but a little harder.
Then again, if you don’t mind having a lot more power and you are using Python, you might think about using eval() for infix notation. However, since it can execute anything Python, that’s not the right answer for all programs, especially not those that process user input. Not to mention, that’s notoriously hard to do in compiled languages like C.
Some pretty beefy computer/calculators used RPN. Or, you can homebrew one.
Its Friden, not Frieden.
As someone who once owned a Flexowriter, I should have caught that typo myself :(
FORTH was the first computer language I came across that used RPN or “post-fix” notation. Subsequently I was surprised to see a malfunctioning first generation Mac mini drop into a FORTH command line. (According to Wikipedia FORTH is still used in a number of boot loaders.)
It is OpenBoot / OpenFirmware as originally created at SUN. You can enter with a KB combination. Device Tree descends from this IIRC. It was made by Mitch Bradley who was a member of the Forth Interest Group Silicon Valley or SV-FIG and worked at SUN.
Good to know. Thanks.
I love my RPN on my calculator since I can do several intermediate calculations, then e.g., sum them all up by pressing ‘+’ a few times. But, for writing code, Polish Notation (not Reverse Polish Notation) is easier for me to read/think in. I.e., as used in Lisp:
(* (+ 1 2 3 4) 7)
= 70
(mapcar ‘+ ‘(1 3 5 7) ‘( 2 4 6 8))
= (3 7 11 15)
Working at HP I naturally had our daughter learn RPN. She got engaged to a Georgia Tech ME. I asked her one day:” is he an RPN guy”, she replied “I don’t know”. I while later I asked her if she ever found out. O yeah he said ” What’s that?” The engagement didn’t last.
You can consider any C (or Python) function call Polish notation.
var result = call_function(var1, var2, var3);
The REAL fun begins when you try to deal with the implicit operations, and unary negation (with the minus sign doing doth unary and binary duties)
One should keep in mind that algebraic notation is not the same as the infix we use in most programming languages. Algebraic notation takes several years for students to become comfortable with, but provides a lot of cues (position, size, etc) that infix does not, but provides a lot of advantages when dealing with math as math, rather than math as numeric evaluation.
Should one be inspired to write their own infix–>postfix routine, or direct infix evaluator, it is useful to keep two precedence classes for each operator: one as an input token, and one as a token on the operator stack. This greatly reduced the complexity of the logic with nothing but another column in the table. For example, open paren is only high precedence on input. Once it is stacked up, it is low, since any operator but its matching close that follows it will go to the stack.
Named functions are actually fairly easy to build in, as well, as the function name (and open paren for the parameter) are treated as an open paren, matching with a close. When popped, the appropriate function is invoked like any other operator. For example, sin( invokes sine, sqrt( invokes the root, and a ( on its own invokes a null function.
The fun comes when you try to fit it into a couple Kbytes
RPN syntax is really neat for test software, because you can write a simple parser. e.g. for an arduino sktech:
uint16_t gParam0, gParam1;
void Ui(char ch) {
switch(ch) {
case ‘a’ : TestFuncA(gParam0); Pop(); break;
case ‘b’ : TestFuncB(gParam0, gParam1); Pop(); Pop(); break;
case ‘….etc..’ : TestFuncEtc(…); Pop(s); break;
case ‘ ‘ : gParam1=gParam0; gParam0=0; break;
default:
if(ch>=’0’ & ch<'9') { gParam0=gParam0*10+ch-'9'; }
}
}
void Pop() { gParam0=gParam1; gParam1=0; }
It takes a certain dedication to write a whole article about a thing, and never explain that it’s called Reverse Polish Notation.
While using Python’s eval() is probably not what you want, using ast.literal_eval() works much better.
First sentence: HP calculators, slide rules, and Forth all have something in common: reverse polish notation or RPN.
He was reading it in reverse, using Polish.
I am quite surprised that Forth is not mentioned.
I published quite a few books on amazon
https://www.amazon.co.uk/Juergen-Pintaske/e/B00N8HVEZM
or just try it online with easyforth
https://skilldrick.github.io/easyforth/
you can see what happens on the stack there
I think the first sentence of this piece got skipped by a lot of readers: HP calculators, slide rules, and Forth all have something in common: reverse polish notation or RPN.
Sorry Al, you are right. Going back I have seen it now.
But as Forth is a real language like C and Python, still used today, and NASA used it quite a bit in the past – not just a calculator,it should have been made clearer I think.
And EasyForth as the easiest way to try it out.
What? Try reading the first sentence.
> So then the value stack will have 7, and the operator stack will be empty.
What happened to the [ that was at the bottom of the operator stack?
Next paragraph:
> When you read the end marker, the value stack will be 7 6 3, and the operator stack will be [+ *
Oh, the operator stack has the [ again.
Ah… I had omitted them at first and then decided to put them in again… sigh.
Regarding slide rules and RPN: The thing with slide rules is, with my circular KL-1 for instance (I never used the conventional sort), you have two independent variables in the state of the device (two knobs, or one cursor and one slide), but you have lots of virtual/dependent variables which are functions of those two, and which can be used for I/O (different rows of print to look at). You also have more actions available than there are math operations, because you can perform the same math operation multiple ways depending on what you want. The relationships between these virtual variables are such that by choosing a valid action, you can store the result of a math operation between two variables on another variable.
There’s always two stored pieces of real information in “memory”, but sometimes you invalidate and ignore one of them because you moved something which made it useless. Generally, you would really like not only to store the information but also to be able to *read* the information in the result, so you may ignore information that’s no longer got a readable or useful value anywhere. But even apart from that, an example. You might have an operand value of 3.2 in any of the variables, and must look for an operation which allows you to read off a final result after multiplying by 6. So the variable which stores 3.2 is given and can’t be invalidated, the variable you enter 6 into must be possible to read a 6 on so that you can input it, and must be related to the other variables such that one of them lets you read off a multiplied result of the two inputs. Described that way, it seems a lot harder than it really is to find the right action, but to me that doesn’t sound like RPN except in that it saves on reordering parentheses before beginning. Though it’s not really infix either.
It is not called ‘reverse polish notation’, because it has nothing to do with polishing things. It is called ‘reverse Polish notation’, because the normal version of the notation was invented by a Polish logician, Jan Łukasiewcz.
Well, it probably polishes your geek-image if you are using an RPN calculator.
Learned that in my Algorithms and Data Structures class. Proud owner of HP-25 and HP-41. Emulators for the 41 on all my modern gear.
I personally find RPN to be OK, but it tends to be somewhat overrated IMHO.
Apparently Woz has an interesting anecdote about it
Used to be available at http://archive.woz.org/letters/general/57.html
“Infix to postfix was common to computer scientists in 1970. But this was back when very few colleges even had computer science programs for undergraduates. Postfix notation was not common to average people who use the infix written system. Computer scientists tend to find postfix to be more ‘pure’ than infix. It does have the qualities of left to right operation and no parentheses. But it requires a stack, which would translate to extra memory steps for a human if we wrote expressions in postfix. I’d guess that computer scientists would feel that early expression writers stuck us with a worse system, kind of like the QWERTY keyboard. The computer scientist view of postfix is similar to the scientists’ view of the metric system.
At Hewlett Packard we were so proud that our calculators, the first scientific ones ever, were years ahead of competition. They used postfix partly because the least logic or ROM chips were quite expensive back then. It would have taken extra keys and an infix to postfix translator to use infix. Also, a larger and more expensive desktop HP machine from the division in Colorado Springs used postfix, for the same reasons. The HP-35 was an attempt to miniaturize this machine.
Our marketing department had a card with a monstrous formula to demonstrate how powerful our calculators were and what postfix calculation was capable of. They challenged people to solve it on a slide rule the normal way. Well, we could all solve it on our HP calculators but it took a few tries to get the steps accurate enough, there were so many of them.
Finally Texas Instruments introduced an infix ‘algebraic entry’ scientific calculator. The first one showed up in our lab one day. We were all pooh-poohing it and laughing at the arithmetic entry as being too weak for engineers. Someone pulled out our big formula challenge and we all laughed, sure that nobody could ever do it with the TI calculator. A challenge went up for someone to try. After a short silence I said that I’d try.
Well I started staring at the formula and looking at the keys and trying to decide which steps to calculate first, as you would do with an HP calculator. I finally realized that I’d never be able to solve the formula this way. With my fellow engineers watching I was very self conscious but I wanted to succeed. I managed to let go of my thinking and then came up with a very amazing concept. I just copied the formula from left to right! This was such an incredible concept that I pressed the keys as fast as I could on the TI calculator, risking a wrong press but impressing my colleagues. I had to guess whether this calculator used the square root button as prefix or postfix but I guessed right and got the proper answer the first time.
My colleagues couldn’t believe it. I told them that you just copy the formula from left to right but not one of them could see through their postfix fog. After all, these were the calculator experts of the world. They are well accustomed to thinking ahead and analyzing an expression to come up with the order of steps to take on an HP postfix calculator, and they had to remember which sub-expressions were in what order on the calculator’s stack. None of them could do what I had done, forget that they have to be smart.
I was strongly affected for life by this experience. There’s a lot of rightness in using the same system on a calculator that we all learn to use on paper, a system that has been around for hundreds of years. My pure side prefers postfix but it’s not what I’d recommend to others for a calculator. I also type on a Dvorak keyboard now, but I wouldn’t recommend it.”
Can’t argue with the ease of implementation of rpn, having implemented many of both. Also, there are other ways to implement algebraic notation. There are many simple expression parsers available, but it is easy to write your own too.
https://github.com/codeplea/tinyexpr
https://github.com/wdas/SeExpr/
Great story.
The trick with RPN (IMO) is that it’s actually the natural order of things, so it’s a lot easier on the machine. Take two numbers, add them. It maps directly to the machine language, but also to the real world of actions: you can’t hammer in a nail until you’ve got both the hammer and nail in hand. 2 2 +.
The problem is that we’ve all learned this multi-pass-parsing algebraic notation some time in grade school. So we all think that way “naturally”.
So RPN on the machine requires _you_ to do the parsing in your head while writing the code or typing into the calculator. And we’re pretty good at doing the parsing — see “natural” above. So it’s not a bad allocation of resources when the machine is small.
When the machine is big, it starts to make more sense to move the algebraic parsing over to the machine, b/c it’s just one less thing for the human to worry about. It’s more keystrokes, and making sure all your parentheses do what you want is another hassle, but again, it’s the “natural” hassle. Does that match your experience?
Your RPN example of 5 + 3 * 6 is not correct for calculators.
You don’t have to reorder the arguments in an RPN calculator with a stack — just enter 5, 3, 6, *, + to get the answer.
I still use RPN on my M2 Mac and iPhone 14 with an HP48 emulator :-).
You don’t have to push things on the stack ahead of time but you can. I usually work problems like I did on a slide rule, so you don’t have 5 3 6 * + but, of course, you can do that. I wouldn’t say it is “not correct” either way.
5 enter 3 enter 6 * +
For some reason an my HP 15 I think 5 up 3 up 6 * + as if the stock is pushed upwards. Don’t know why. Maybe because the Roll button has a down arrow. In Forth I think of it as pushed downwards.
No matter the article nitpicking…. I’ve always liked my RPN calculators. Even wrote a ‘script’ interpreter that would accept a RPN style syntax. enter (push), mul, goto, cos, etc. with a few extensions for input/output for fun … In C of course.
Sandia National Laboratories sponsored ~6-1o forth courses from ~1982 to ~90.
Forth proved a ‘hard-sell’ to engineers who preferred BASICS … and hp 9800 series computers …
for the weapons tester work.
64-bit Intel MSC BASIC-52 VM implementation using fig forth routines possible?
ENCLOSE, FIND, … can be written in transparent portable gcc c.
Coded ENCLOSE in gcc c, then tested on x86 Raspberry Pi 4B ARM processors. Worked on both platforms.
BASICs, like forth, can be standalone RTOs.
Beats batch c/c++ in app development speed and app reliability?
I wrote my own postfix calculator years ago in PHP. It was quite basic and not exactly well architected, but it worked and was quick to make. Since then, I’ve refactored and expanded it to be fairly powerful (although I admit to not knowing how powerful commercial postfix calculators are) and integrated it as the expression evaluation engine for a simple function plotter. It’s theoretically Turing compete, but not in practice because there’s a type of loop needed that I don’t currently have working.
I’m currently in the process of rewriting it in C++ to be faster and support things well beyond the scope of the original version, as well as make some breaking changes to its syntax, but that’s not particularly close to done yet.
No mention of dc, which predates even C, and which both Linux & macOS users almost certainly have readily available.
– https://en.wikipedia.org/wiki/Dc_(computer_program)
– https://linux.die.net/man/1/dc
– https://esolangs.org/wiki/Dc
The source code of various implementations, from naive interpreters to full-on Turing-complete virtual machine-alikes, is available under many licenses.
I still have a Sinclair calculator that uses RPN. It still works too with very small seven segment LED’s. Like others have said Forth uses RPN. I made a lot of money using the Rockwell 65F12. It was really a 6502 with forth added on. You switched it on with a serial terminal attached and typed in Forth.To ship a product the Forth code was written to an EPROM and voila! The nearest modern equivalent would be an Rpi Pico loaded with MicroPython – or with Mecrisp Forth for a real deja vu!
Loved my Rockwell 65F12 system. We shipped over $5m in machines using the 65F12. I modified the compiler to drop code into all 16 banks.
Took over 25 minutes to compile ~200k text file !
RPN is natural if you imagine nailing 2 pieces of wood together. First you put 1 piece on the bench, then another on top, then nail em both !
Python? RPN? Well, friends, you can have both these things and more with my wee project, Codswallop RPL, available wherever fine Githubs are sold. It’s a loose reinterpretation of HP’s later stack language Reverse Polish Lisp, written in Python, with documentation and an example.
That’s quite interesting, especially when I have never used code before only used the electronics like a battery operated calculator to do math problems!
Want to evaluate expressions in Python? Don’t use eval(), use SimpleEval, which elegantly leverages Python’s AST parser.
https://pypi.org/project/simpleeval/
As a mid-70’s EE student, I made the transition to RPN because my wife saw me constantly lusting over magazine pictures of the HP-67 unit; she financed one as a gift and I still have it in working order (sans the card reader which needs a 3rd rebuild.)
My real appreciation of RPN was actually implementation in pure C on an 8051’ish chip as a long weekend project recently. These are hours I will never recover!
https://hackaday.io/project/191722-rpn-integer-calculator-from-smart-response-pe
Stupidly, I also subsequently implemented it in C++ integrated with tiny BASIC Plus. I have since resolved the memory leak that forced a reboot after RPN calculations on the XE but that code has not been published (yet.).
https://hackaday.io/project/193043-rpn-basic-on-smartresponse-xe
I have found that I can just shout at ALEXA, “Alexa, what is the square root of 355?”
(shouting at spouse is ill-advised)
So simple.
At one point, early during the pandemic, I implemented an RPN calculator and die-roller in python as a discord bot. The calculator and roller portion was dead simple; the hard parts were getting the RegEx right.