ArticlesIntroduction to RPN
Many computer scientists, and some old-timer engineers, will be familiar with postfix notation – perhaps better known as RPN (Reverse Polish Notation).
It is an obscure way of writing down arithmetic. We traditionally use infix notation, e.g. (1 + 2) * 3. The same arithmetic in postfix notation would be written as 1 2 + 3 *.
From an elegance perspective, postfix notation rocks! No ambiguity means no brackets!
From an software implementation perspective, postfix is simple! All the operands store in one stack. Easy!
So we saw RPN being implemented in:
- early calculators (especially those from Hewlett-Packard),
- dc (a very early Unix desktop calculator program), and
- early programming languages, including Postscript (1976) and Forth (1977 and earlier).
I am going to claim Lisp (1958) here too. It actually uses prefix notation (or Polish Notation), but that’s close enough to help my point.
Whatever happened to RPN?
RPN is not nearly as popular now as it was back in the 70s. Why? Because it wasn’t human.
Due to whatever historical quirk, we are taught at primary school to do maths the infix way. As computers and calculators became just slightly more powerful, it became clear that the computer should adapt to the quirks of humans, rather than trying to get all the humans to adapt to the quirks of computers.
Modern programming languages, modern calculators and modern software allow you to enter your arithmetic in infix notation with all of its clumsy brackets, and the world is a better place because of it.
(Why am I going on about RPN? Bear with me. I’m building up a framework for an argument. I’ll come back to this later on.)
Comment by Alastair on October 25, 2005
Wikipedia points to the Rope scripting language, which is used in to filter IP packets within the Linux kernel. Interesting!
And Forth is alive and well inside the Open Firmware interpreter that boots my Powerbook.
I’m not sure where you’re going with your argument, but I think that these two applications are ideally suited to a lightweight stack-based language, which in turn implies RPN.
I agree with your point that infix notation is more convenient for humans, but this doesn’t mean that RPN should be purged from the computing world altogether… (If that’s in fact what you are arguing for – you used the phrase “modern software” which is pretty inclusive!)
Comment by Julian on October 25, 2005
Alastair,
I think you are right – there is still space for hard-to-understand, but easy-to-implement software systems along the edges of the software development. Both the Powerbook and the Rope examples are going to be used only by hard-core, low-level, bit-flipping developers, who are willing to trade-off usability for simpler design.
I would add that there is still space for RPN in generated languages, such as Postscript – where it is rare for a human to have to understand the data being passed between two software components.
I used the term “modern software” too loosely, sorry. I’m not going to propose stamping out RPN. It has already been relegated to its rightful place.
I note with approval that Rope provides a concession to humans: it’s anchored RPN supports a usability hack: brackets are permitted to revert to prefix notation.
So, according to the manual, both of the following lines to the same thing – they print out the value 140.
Comment by Sunny Kalsi on October 25, 2005
nihongoga wakarimasuja arimasen-ne?
I’ve totally ruined the joke if that makes no sense… However, my point remains.
Comment by Alan Green on October 26, 2005
So you want us to leave this argument on the stack while you make further calculations?
Comment by Julian on October 26, 2005
Sunny,
Unfortunately, you have totally ruined the joke. I am assured that this does not make sense in Japanese.
I would humbly suggest that your point doesn’t remain! I’m afraid I don’t know what it was.
Comment by Sunny Kalsi on October 28, 2005
It was supposed to be “you don’t understand japanese, eh?” Except I think I probably over-generalised at the ja-arimasen part.
Japanese tends to be written with the nouns first, then the … applicators… (verbs?). This is why romaji can often be written without spaces. I’ve been told that it’s actually “reverse polish”. I suppose I have no real proof, as I cannot actually construct complex sentences in Japanese, but it seems to be correct. To say “do you understand english” you’d say “you english understand?”, where “?” is the operator that turns a sentence into a question (anatawa eigoga wakarimasuka).
The point here is, that RPN actually (probably) IS intuitive in some cultures.