The distinguishing quality of the postfix notation, a.k.a. reverse polish notation is that for its usual left-to-right evaluation strategy, just before an operator is feed from the notation, all of its operands (a.k.a as parameters or arguments) are on the top of the stack right next to each other in the expected order. Then the operator are applied to its operands immediately. The postfix notation thus has the following distinct advantages.
- No operator precedence or associativity rules are needed to evaluate the notation.
- Formulas can be expressed with the notation without parentheses.
- The memory needed to evaluate the notation is smaller.
- It is very easy to code the evaluation of the notation.
Here is one simple solution.
[[0, 2, 4, 6, 8], 1, "@add", "@map"], we will use
[[0, 2, 4, 6, 8], [1, "@add"], "@map"]
Here is how it will be processed.
[0, 2, 4, 6, 8] and
[1, "@add] are pushed onto the stack. When the operator "@map" is encountered, we will pop off
[1, "@add"], treating it as a function object. Then with the array
[0, 2, 4, 6, 8] popped off the stack, we will apply the function to the array, leaving
[1, 3, 5, 7, 9] on the top of the stack.
We can simplify further.
It is quite likely that an array can be recognized conveniently and efficiently as a function object at the time when it is read as the next element of the input. For example, we should be able to detect that whether an element is an array, and if it is, check whether the last element of that array is a binary operator or not. If it is, then the array represents a function object. Otherwise, the array consists of pure data. We can then use
[[0, 2, 4, 6, 8], [1, "@add"]]
so that we can do away with the entry "@map". Semantically, we are recognizing
[1, "@add"] as a unary operator on an array without the presence of "@map". Upon applying
[1, "@add"] to the array
[0, 2, 4, 6, 8], we will push the result
[1,3,5,7,9] to the stack. Similarly, upon processing the following JSON input,
[[0, 2, 4, 6, 8], [1, "@add"], [2, "@multiply"]],
we will leave
[2, 6, 10, 14, 18] on the top of the stack.
The solution above upholds that distinguishing quality of the postfix notation. It could be extended to function objects of multiple arguments and higher order naturally and unambiguously. It can be read easily—an array of two elements whose last element is a binary operator like
"@add" is a function object.
However, this solution is only one minor technique/hack to extend the primitive postfix notation. It might be helpful to study literature on postfix notation and stack-based languages for more complete and systemic usage of postfix notation. For example, check the syntax of Forth language, where new functions/words can be defined.