Representing partialled/curried functions in postfix notation?

I'm working on a small query language in JSON. A query consists of a JSON array of JSON elements, such as strings, numbers, booleans, etc. Strings starting with a '$' or '@' represent postfix unary or binary operators, respectively.

I want to include some functional aspects to my query language (e.g. a map operator that takes a function and an array, and produces a new array). However, I'm having trouble representing these "functions-as-arguments" in postfix notation! As an example, let's say I want to add a fixed number to each element of an array. I would instinctively want to write something like this:

[[0, 2, 4, 6, 8], 1, "@add", "@map"]

However, this would be interpreted as "perform an add operation on 1 and [0, 2, 4, 6, 8], and then call map". This would produce an error in my query! Instead, I want to interpret the query as "perform a map operation using add(1) on [0, 2, 4, 6, 8]". Is it possible to achieve this, given the use of postfix notation?

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.

Instead of [[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.

StackExchange Computer Science Q#112160, answer score: 6