Variable-Length Operators In Reverse Polish Notation (Postfix)

Question

Background: In traditional Reverse Polish Notation, all operators must have fixed lengths, which allows RPN to be easily evaluated and manipulated by code because every token, expression, and subexpression are all "self-contained" such that one can blindly substitute the y in x y * for y 1 + to get x y 1 + *, which is another valid expression that does exactly what you want it to do. Here is an interactive demo of a simple RPN calculator with named variable support. Note that the demos try to present the gist of an algorithm; they don't correlate to or represent production code.

var rpn = prompt("Please enter RPN string, where each token is " +
  "separated by a space", "x 1 x + * 2 /").trim().split(/\s+/);

var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0; i < len; i=i+1|0) {
    if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
        stack.push( rpn[i] );
    } else if (/^[a-z]$/i.test(rpn[i])) {
        stack.push( rpn[i] );
        if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
    } else {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const firstPop = stack.pop(); //lacks check if stack empty
        stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
    }
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);

for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
    values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);

variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));

Question: How can RPN be modified or adapted to accommodate variable-length "operators" (think functions)?

Research and proposed solutions: I am using RPN as an intermediary representation of code before it is finalized into a specified code language. I want to preserve as much of the usefulness and ease of RPN as possible while still representing variable-length operators. I devised three solutions and implemented them in rather simplistic demos below.

1. A special ARGUMENTS_BEGIN prefix operator (we'll use # for the purposes of this question). This solution flies in the face of traditional RPN in that it adds prefix operators to denote where the arguments begin. This makes the arguments list auto-expand in size, and assists with debugging because no malformed token substitution can disrupt the arguments list, allowing one to localize the error more easily. This could make manipulation of arguments more complex due to more code needed to handle cases such as nested function calls, but I am not entirely sure what all complications could arise. It is my guess that I will encounter obstacles parsing syntax that includes prefix and postfix operators. It also makes direct evaluation more difficult because back-tracking or a separate stack is needed to locate the start of the arguments.

var rpn = prompt("Please enter a RPN string, where each token is " +
  "separated by a space", "# # x 210 gcd x 6 * 126 gcd").trim()
  .split(/\s+/);

var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0; i < len; i=i+1|0) {
    if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
        stack.push( rpn[i] );
    } else if (/^[a-z]$/i.test(rpn[i])) {
        stack.push( rpn[i] );
        if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
    } else if (/^[a-z]\w*$/i.test(rpn[i])) {
        const s = stack.lastIndexOf("#");
        if(s<0) throw Error("No start of arguments to " + rpn[i]);
        stack.push( rpn[i]+"(" + stack.splice(s).slice(1) + ")" );
    } else if (rpn[i] === '#') {
        stack.push( '#' ); // sparks a syntax error if misused
    } else {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const firstPop = stack.pop();
        stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
    }
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);

for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
    values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);

variables.push( "gcd" );
values.push( function gcd(a, b) {return b ? gcd(b, a % b) : a;} );

variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));

2. Comma operators to group arguments together (we'll use , for grouping the last two items and ~ to denote the a zero-length group for the purposes of this question). This solution is traditional RPN except with slightly special handling of the comma and zero-group operators. Every variable-length operator is treated as having a length of one (zero arguments is represented with ~). Commas build arguments lists out of two items, each of which can be an ordinary token, an arguments list, or a zero-group operator. Advantages include easy manipulation and parsing of the code, compliance with the simplicity of RPN, and preservation of the token-independentness of RPN. Disadvantages include the RPN being harder to debug because a tiny malformed token can upset an entire arguments list and snowball out of control with no way to detect whether it is deliberate or accidental.

var rpn = prompt("Please enter RPN string, where each token is " +
  "separated by a space", "x 6 * 126 , 210 , gcd ~ PI %")
  .trim().split(/\s+/);

var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0; i < len; i=i+1|0) {
    if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
        stack.push( rpn[i] );
    } else if (/^[a-z]$/i.test(rpn[i])) {
        stack.push( rpn[i] );
        if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
    } else if (/^[a-z]\w*$/i.test(rpn[i])) {
        if(stack.length<1)throw Error("No operand for " + rpn[i]);
        stack.push( rpn[i] + "(" + stack.pop() + ")" );
    } else if (rpn[i] === ',') {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const p2 = "" + stack.pop(), p1 = "" + stack.pop();
        stack.push( p1 && p2 ? p1 + "," + p2 : p1 || p2 );
    } else if (rpn[i] === '~') {
        stack.push( "" ); // zero-length group
    } else {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const firstPop = stack.pop(); //lacks check if stack empty
        stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
    }
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);

for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
    values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);

variables.push( "gcd", "PI" );
values.push( function gcd(a, b) {return b ? gcd(b, a % b) : a;} );
values.push( function PI() {return Math.PI;} );

variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));

3. The operator intrinsically stores its length (we'll append a number onto the function name for the purposes of this question). This solution inherits all of the advantages of traditional RPN. Additionally, it makes the reading aspect of the parser simple. Additionally, debugging is easier because there is no accidental insertion of new arguments. However, it makes manipulations and generation of RPN code more complex. Updating and generating arguments lists is difficult because this solution deviates from the token-independentness aspect of RPN such that adding an argument (and changing the arity) requires two actions and one lookup (verses the traditional one action and zero lookups): (1.) insert the argument, (2.) lookup the position of the variable-length operator, and (3.) update the length of the operator.

var rpn = prompt("Please enter RPN string, where each token is " +
  "separated by a space", "x 210 gcd2 x 6 * 126 gcd3").trim()
  .split(/\s+/);

var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0, m; i < len; i=i+1|0) {
    if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
        stack.push( rpn[i] );
    } else if (/^[a-z]$/i.test(rpn[i])) {
        stack.push( rpn[i] );
        if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
    } else if (m = rpn[i].match(/^([a-z]+)(\d+)$/i)) {
       if(stack.length<m[2])throw Error("No operand for "+rpn[i]);
        stack.push( m[1] + "(" + stack.splice(-m[2]) + ")" );
    } else {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const firstPop = stack.pop(); //lacks check if stack empty
        stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
    }
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);

for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
    values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);

variables.push( "gcd" );
values.push( function gcd(a, b) {return b ? gcd(b, a % b) : a;} );

variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));

4. Nested arrays on the stack (no demo possible). This solution involves storing the arguments in a list before the operator on the stack, which makes direct execution of the code very easy. However, this violates the entire precept and advantage of RPN, which is to have a flat list of items. Perhaps, if lists were only one deep, there would not be too much of a problem; however, for my use case, I would end up with deeply nested lists. Thus, manipulation of the RPN and generation of the RPN becomes very difficult.

Extrapolation of the single question: Are there any other possible solutions to this problem? What is the standard (most-used) solution to this problem? Are there fundamental problems with my solutions (please provide counter examples)? Did I overlook some pros/cons of my solutions? Could my solutions' algorithms be improved?

Occupy

Not sure what you mean by "adding an argument requires two actions and one lookup (verses the traditional one action and zero lookups)". With traditional fixed-arity functions, you can't add an argument without removing another argument to preserve arity. Anyway another option is to have the arity be another parameter to the operator. arg1 arg2 arg3 ... argN N op. That's what forth's pick and roll words do. – Doggerel

@RaymondChen Thank you for your input. Your idea is the same algorithm as the 3rd option listed above, which is to store the length as an explicit integer somewhere. Regardless of whether the length is stored as part of the name of the function (like in the demo) or as another parameter (like in your suggestion), it's the same algorithm because the length is in the same atomic unit as the operator. As for your question, I'm talking about changing arity because my optimizer will throw the concept of a fixed number of arguments out the window and append arguments in the JS code to reduce size. – Occupy

I would use an object oriented programming language for the development of Your calculator. You have only to care about the connection between the name the user enters and the internally used array, variable, value or function. So if You are defining a function that takes n arguments, the arity of that function is irrelevant, since the arguments are on the stack and are processed from there. – Frutescent

@Frutescent Thank you. You are correct that I'm using object oriented JavaScript. However, I'm not developing a calculator; I'm representing language-agnostic code syntax in RPN so that it can be optimized before getting transpiled into the target code language. The arity of the functions matters a ton because I am generating a piece of code text (not executing the RPN; rather just stringifying the RPN together into a piece of text written in the target code language). Additionally, the demos do not represent my actual code at all. The actual code is one internal stage in a long pipeline. – Occupy

In this case I would prefer variant 3. That's highly interesting. I am curious to see something of the result. If You need any suggestions, here is a RPN language that looks quite useful. – Frutescent

RetroForth, Factor, Joy, RPL (reverse polish Lisp), and others support lists on the stack. Using this, a variadic function just takes a list of arguments. – Salpingectomy

@Salpingectomy That's a possible idea. I'll add it to the list of possible suggestions. However, I'm almost certainly not going to be able to use it because it eliminates the greatest advantage of RPN, which is a flat list view. – Occupy

7th solves this problem by using a special word fn that separates the parameters from the rest of the stack. See help fn. – Frutescent

@Frutescent Thank you for your input. I do not know 7th very well, but it appears that fn serves a similar purpose to # in option 1. fn appears to begin a list of arguments ended by the function to call them with, allowing multiple levels of fns to be nested. This is the same behavior as the # in option one. Please correct me if I am wrong. – Occupy

It's similar. fn is a placeholder on the stack. However, it is mainly intended for calling Java functions. For 7th words fn>cnt is necessary to remove fn and place the count of the following parameters onto the stack. Like in Forth, as Chen stated. – Frutescent

Answer 1

I think you have covered the options already: if you have to be able to pass a variable-length list of arguments, then either your language needs to have a native data structure allowing the whole list to be a single value on the stack (i.e. nested lists as in #4, or a simulacrum of them as in #2 where lists are represented as strings, comma-separated, and cannot contain other lists), or otherwise the list elements must be separate values on the stack. In that case the variable length must be determined either by a sentinel (as in #1) or a length field (as in #3). That seems exhaustive.

As for advantages and disadvantages:

• #2 is basically a version of #4 but with weird semantics (the , operator can either create a 2-item list, append or prepend an item to a list, or concatenate two lists, depending on context) and the lists aren't first-class objects because a list cannot contain lists.
• #1 and #3 are similar to the similarities/differences between null-terminated vs. length-prefixed strings. It's generally considered nowadays that length-prefixed sequences are better than using a sentinel, because you can read off the length in O(1) time, and if some value is treated differently as a sentinel then it can't occur in the sequence (unless there is some way of escaping it).

Personally, I favour option #4 because a programming language is not very useful for general purposes if it doesn't have lists/arrays as first-class objects. I am not sure exactly what you mean by "this violates the entire precept and advantage of RPN [...] manipulation of the RPN and generation of the RPN becomes very difficult." It is quite possible to have a syntax for creating lists and nested lists in a concatenative language like RPN.

Taking my own toy language fffff as an example, the code [1 2 3]. creates a sequence by opening a new stack with the [ operator, pushing the literal values 1, 2 and 3 to this new stack, and then closes the new stack with the ]. operator, which also pushes a reference to the new stack onto the previously-current stack. This obeys the concatenative property because if, for example, the function three_and_close is defined as doing 3 ]. then the code [1 2 three_and_close has the same behaviour as the original code; so factoring out parts of the code is still just as easy as in standard RPN.

Pinkiepinkish

Thank you for your constructive answer. #2 and #4 are distinct in that they employ unrelated algorithms. Suprisingly, I am actually leaning towards #2 because it seems to be a more cohesive continuation of RPN. There's never any need to have nested lists due to way rpn work (nested lists would always produce errors. Think of them like varags; you can't nest a list of arguments). Also, the semantics for #2 are pretty straightforward: 1 2 , -> [1, 2]; and ~ 1 , -> [*empty*, 1] -> [1]; and 1 ~ , -> [1, *empty*] -> [1]. Nested commas get flattened into a 1-deep list. The problem – Occupy

I have with #1, #3, and #4 is that it adds additional semantics that has to be accounted for. It deviates from the simple model of RPN. With #2, commas behave just like an addition operator. With #1, #3, and #4, additional logic is needed to detect and handle special cases, which makes the code more complex, so its harder to develop and might take longer to debug. Let me be clear: my mind is not made up. I'm asking this question in case if there are some aspects of #1, #3, and #4 that I have not taken into consideration. I don't want to use #2, then later realize I need to restart from scratch – Occupy

That being said, you are correct that #2 and #4 are conceptual twins of each other. Each operator has a list of arguments that go with it. #2 looks promising to me for the same reasons you like #4, and the reason I am looking towards #2 is that it seems to be much easier to implement because it is so much more cohesive in that, implementation-wise, it stays true to the concept of postfix operators and a fixed number of operands. Additionally, I agree with your comparison between #1 and #3 and I agree that #3 would be easier to implement than #1. – Occupy

Regarding "you can't nest a list of arguments", you can, if the function accepts lists as its arguments. I'm not really sure what you mean by special cases in #4 - if you mean that operations like + will have to check that their operands are numbers and not arrays, then you still have that problem with code like 1 2 , 3 + for example. – Pinkiepinkish

Thank you for your insights. That is an excellent point that operators will have to validate the types of their input. The reason for why you can't nest a list of arguments is because the list of arguments doesn't mean anything by itself. In order to create an array, you need a special operator, say MAKE_ARRAY. With this, doing 1 2 , 3 , mean calls mean with three arguments, whereas 1 2 , 3 , MAKE_ARRAY mean calls mean with a single argument. To nest: 1 2 , MAKE_ARRAY 3 4 , MAKE_ARRAY , 5 6 , MAKE_ARRAY , MAKE_ARRAY flatten is equivalent to flatten([[1,2],[3,4],[5,6]]). – Occupy

Answer 2

I'm not sure if your plan is (was) to treat every function you implement as a separate operator with its own distinct arity or to have one "function call" operator that pulls the required number of arguments off the evaluator's operand stack before calling the function.

If the latter, the most straightforward Reverse Polish conversion might be from:

name(expr1, expr2...exprN)

to this:

name expr1 expr2...exprN N callFunc

Keeping in mind that any "exprX" might be arbitrarily complex, including function calls of its own. It doesn't matter; by the time "callFunc" is reached you need only worry about the topmost N+2 items on the operand stack. The most tricky bit is keeping track of how many arguments are actually present and making sure that count gets into the RPN just before "callFunc".

That needs some sort of stack to account for nested functions, but otherwise isn't too difficult. It's actually possible to use the operator stack (keep the count "under" the "callFunc" operator, a known offset, and update it each time a comma is encountered. That naturally takes care of function nesting, but it's not the only way).

In execution "callFunc" takes one argument, N, the number of arguments to pull off the operand stack. These you can put into a list or array that you can pass to "name" once you pull that off and call it (most likely indirectly using some sort of dictionary).

To be complete you'll probably want to do error checking while parsing to make sure the number and type of arguments are correct for the function being called (you can keep that information in same dictionary that points to the code which evaluates the function). Also watch for commas appearing where they shouldn't, just as for all malformed expressions. Then the evaluator can run merrily along without having to worry about any of that.

Weeds