Reverse Polish notation: the stack’s natural order (Łukasiewicz 1924, Hamblin 1957)

Łukasiewicz wrote logic with operators before their operands, which needs no parentheses. Hamblin reversed it for computers: in reverse Polish notation, (1 + 2) * 3 is 1 2 + 3 *, and a machine evaluates it by pushing each number and letting each operator replace the top two values with the result. Dijkstra’s shunting-yard algorithm (1961) translates ordinary notation into that order. Every stack virtual machine, from Forth to the EVM, runs programs in this form.

What to look for

The compiled program is just the RPN sequence, one instruction per token, and its result matches Python’s. The stack height rises with each pending operand and falls with each operator.

The history behind this experiment: Breakthroughs in Replicated Execution. See Exercises: execution for a worked solution to the exercise.

Infix to RPN to instructions

import matplotlib.pyplot as plt

import blockchainkit as bk
from blockchainkit.vm.visualizers import plot_execution_trace

expression = "(1 + 2) * 3 - 8 / (4 - 2)"
rpn = bk.vm.to_rpn(expression)
program = bk.vm.compile_expression(expression)
print(" ".join(rpn))
for instruction in program:
    print(instruction)
result = bk.vm.execute(program, trace=True)
assert result.stack == ((1 + 2) * 3 - 8 // (4 - 2),)
assert len(program) == len(rpn)

1 2 + 3 * 8 4 2 - / -
('PUSH', 1)
('PUSH', 2)
('ADD', None)
('PUSH', 3)
('MUL', None)
('PUSH', 8)
('PUSH', 4)
('PUSH', 2)
('SUB', None)
('DIV', None)
('SUB', None)

Arithmetic is the machine’s

Results wrap modulo 2**256, and / is floor division.

assert bk.vm.execute(bk.vm.compile_expression("0 - 1")).stack == (2**256 - 1,)

fig, ax = plt.subplots(figsize=(9, 4.5))
plot_execution_trace(result.trace, ax=ax)
fig.tight_layout()

Exercise

Write 2 * (3 + 4) in Polish (prefix) notation and in RPN by hand. Why can an RPN evaluator scan left to right with one stack, while a prefix evaluator naturally scans right to left?