Is RPN still relevant?

[3298]

(12-21-2023 01:27 PM)rprosperi Wrote:  The incomplete question "Is RPN still relevant?" is simply not clear enough for any kind of consensus, as the disparate and diverse replies show.

Is RPN still relevant for the public at large?

Is RPN still relevant for high-end calculator users?

Is RPN still relevant for readers of this MoHPC Forum?

Is RPN relevant for American (or substitute UK, EU, China, Indonesian, 3rd-world, etc.) school children?

are all questions that might reasonably be debated, likely with differing conclusions, but as initially asked is so wide open as to be impossible to reach a conclusion.

This separation into different domains is indeed important, thank you. While I have nothing to add on the latter three domains, the "public at large" one is in need of some addition.

In certain (admittedly somewhat niche) topics reverse polish notation remains relevant, maybe even inescapable. The one that immediately comes to my mind is parsers (for programming languages, mathematical expressions, etc). Case in point: just yesterday independent game development studio Wube Software released a blog post in their Factorio Friday Facts series containing the following tidbit with a mention of RPN.

FFF-390 Wrote:The parser was split into three logical parts.

1. Tokenizer, which processes a stream of characters and categorises individual character groups to token types. The operator character set is based on Lua with a few exceptions where both C++ and Lua syntax are supported. Apart from regular numbers, it supports scientific notation, and other formats can be added as needed.
2. PostfixTokenizer, which converts infix tokens to postfix (reverse Polish) notation. This step is responsible for following operator precedence rules and for making sure that resulting expressions are unambiguous. It uses a modified version of the shunting yard algorithm to process data.
3. NoiseExpressionParser, which takes postfix tokens and converts them to a noise expression tree (AST).

(Original post here.)

Ironically the need for a parser means modern algebraic calculators likely contain some RPN deep inside their bowels. You'd have to get their firmware source code or engage in an excessive amount of reverse engineering to find it, but there's a very good chance it's there.

Outside the world of calculators, here's a piece of what Clang can spit out when instructed to print the Abstract Syntax Tree of a C program. In particular, this is a function call.

Code:

|   |-CallExpr 0x559193b5a4b0 <line:19:1, col:41> 'void'
|   | |-ImplicitCastExpr 0x559193b5a498 <col:1> 'void (*)(struct list *, void *)' <FunctionToPointerDecay>
|   | | `-DeclRefExpr 0x559193b5a3e0 <col:1> 'void (struct list *, void *)' Function 0x559193b597c8 'appendToList' 'void (struct list *, void *)'
|   | |-ImplicitCastExpr 0x559193b5a4e0 <col:16> 'struct list *' <LValueToRValue>
|   | | `-DeclRefExpr 0x559193b5a400 <col:16> 'struct list *' lvalue Var 0x559193b5a0d8 'l' 'struct list *'
|   | `-ImplicitCastExpr 0x559193b5a4f8 <col:27> 'void *' <LValueToRValue>
|   |   `-DeclRefExpr 0x559193b5a420 <col:27> 'void *' lvalue Var 0x559193b5a020 'elem' 'void *'

Printed this way, it looks more similar to RPN's sibling Polish Notation, but the Reverse part is just a matter of traversing the same AST differently (parent nodes after their children instead of before). In code generation there's bound to be a part processing this into instructions to place parameters onto the target processor's stack, followed by the instruction to actually issue the call. It'll be obscured by handling for (platform-specific) register-passed parameters and other optimizations, of course, but if you can look past that, you'll recognize the RPN basics even in this widely used program.

Other compilers similarly have a pinch of RPN (or maybe in some cases just PN) in them. And in the world of academia, the compiler-adjacent automata theory works with a stack once you move past type 3 automata in the Chomsky hierarchy into type 2, This stack obviously lends itself to RPN style utilization. Types 1 and 0 correspond to Turing machines (with a certain limitation for type 1), with a tape memory instead, but that could be described as two stacks (one in each direction of the type head), or maybe as a stack you can ROLL like we do in RPL.
Either way, deep within computers, RPN is lurking. Not many people dig that deep anymore (which I think is a problem as it easily leads to misconceptions), but once you need to, you'd be better off if you can wrap your brain around RPN.