Viktor Fedotov

Have you ever wanted to have an embedded scripting language for your Unity project? Would it be to quickly tweak a MonoBehaviour without script recompilation, or control custom animation sequences, or simply out of curiosity? There is a simple yet powerful solution - writing a custom interpreter which uses Reverse Polish Notation (also known as Postfix Notation).

The main davantage of postfix notation is the ease of parsing. In fact the final interpreter is going to be very simple: it will be basically a glorified calculator with some nice custom extensions.

Regular languages like C#, JavaScript and many others have very complicated grammars, at the same time we don't need to worry about anything like this at all. A simple trick of placing a function name after its arguments removes the need for parsing.

This in not a new idea, one of the most notable exmaples of postfix languages is PostScript which is extensively used in printers.

Postfix notation

Postfix notation is a way of writing each function call in a such way that a function is placed after its arguments.

Consider the regular way of writing a method call in C#:

Move(linearSpeed, steeringSpeed, duration);

As you can see the MethodName is placed before the arguments. In the postfix notation this would look something like this:

linearSpeed steeringSpeed duration MethodName

Mathematical expressions will also look different:

• 1 + 2 becomes 1 2 +
• 3 * (4 + 5) becomes 3 4 5 + * (see explanation on Wikipedia)
• Random(1, 5) * 2 + 3 becomes 1 5 Random 2 * 3 +

A command:

Move(1, RandomRange(-90, 90), 2);

Becomes:

1 -90 90 RandomRange 2 Move

This might look odd at the first glance, but it's totally worth it since the evaluation of these expressions becomes very simple.

Evaluation with stack machine

The plan is to use a stack - a storage were all the arguments values and temporary values will be stored in. All the operators are going to operate on this stack.

Algorithm: to execute a script we are going to iterate over the words (also known as tokens) from the input and do:

• If token is a number → place it on the stack.
• If token is an operator (defined by us) → execute it. Operators work by taking arguments from the stack, doing something with them, and then placing result into the stack. For example the operator + will do:
  1. Pop() the value from the stack and use it as s second argument a.
  2. Pop() the value from the stack and use it as a first argument b.
  3. Add them up.
  4. Push the sum a + b into the stack.

• Otherwise we can report and error, push the token on a stack as a string, or do something completely different depending on your imagination.

Example: let's take a look at the last command one more time: 1 -90 90 RandomRange 2 Move

It will be evaluated as follows:

• Push 1 in the stack.
• Push -90 in the stack.
• Push 90 in the stack.
• Call RandomRange operator:
  • Pop 90 from the stack and use it as the second argument high.
  • Pop -90 from the stack and use it as the first argument low.
  • Generate random number between low and high.
  • Push it in the stack.
• Push 2 in the stack.
• Call Move operator:
  • Pop 2 and use it as a third argument duration.
  • Pop a random value generated previously and use it as a second argument steeringSpeed.
  • Pop 1 and use it a first argument linearSpeed.

C# implementation

Create a stack first:

var stack = new Stack();

Let's take a look at the last command one more time:

var text = "1 -90 90 RandomRange 2 Move";

The first step to execute this command will be splitting the input string into separate tokens (this process is also called lexing or tokenization):

var tokens = text.Trim().Split(new []{' ', '\r', '\n', '\t'}, StringSplitOptions.RemoveEmptyEntries);

And the algorithm itself:

foreach (var token in tokens) {
    switch (token) {

        case "+":
        case "-":
        case "*":
        case "/":
            dynamic b = stack.Pop();
            dynamic a = stack.Pop();

            stack.Push(token switch {
                "+" => a + b,
                "-" => a - b,
                "*" => a * b,
                "/" => a / b
            });
            break;

        // Operator which maps onto UnityEngine.Random.Range()
        case "RandomRange":
            dynamic high = stack.Pop();
            dynamic low = stack.Pop();
            stack.Push(Random.Range(low, high));
            break;

        default:

            // Token is an integer number:
            if (int.TryParse(token, out var intValue))
                stack.Push(intValue);

            // Token is a float number:
            else if (float.TryParse(token, out var floatValue))
                stack.Push(floatValue);

            else
                Debug.LogError($"Unrecognized token: {token}");

            break;
    }
}

Note: the usage of dynamic type on popped values will make sure to call summation, subtraction etc dinamically with correct types.

Now we have on our hands a working calculator, which can evaluate a mathematical expression with support of +, -, *, / and RandomRange operators. It will crunch through the code and leave a single value in the stack - the result of computation.

Let's make it more interesting.

Using it in coroutines

It would be nice to be able to write something like this in the inspector: