Creation and experiments with the Small Reverse Polish Notation Programming Language (Small for short)

1. Introduction

Do you know Lua? This is a simple scripting programming language with a very small interpreter (around 600kB once compiled) and that can be easily included and linked into any software. Essentially, Lua allows users to program and add new functions to an existing software without having to edit its source code and to recompile it. Lua is quite popular – especially in video game development: You would be surprised by the number of games that use Lua (World of Warcraft, Crysis, Civilization 5, SimCity 4, Stalker, etc. – https://en.wikipedia.org/wiki/Category:Lua-scripted_video_games for more)

Lua allows game designers and artists to customize the high level mechanics of the game on the fly – i.e. without having to recompile or even to restart it! As you can imagine, doing so reduce drastically the development time.

The reason I am talking about Lua is because it is a very nice language that I wish I hard learn about before: When I was a kid, and a long time before I learned about Lua, I figured that being able to change code on the fly was very useful for my video games. I had no idea about Lua and therefore I designed my own programming language script. The tasks I wanted to execute were quite simple (mostly event triggers, timers and entity property editing). However, I was far to have the knowledge to make a real programming language. The language I created was really simple. It was essentially a reverse polish notation interpreter with some specific function e.g. “giveItem”, “wait”, etc. I had a “if” operator, but I could not loop or call subroutines.

The game for which I initially designed this scripting language is called “Cronos Battle” (Here is an old screen shot). The reverse polish notation calculator

For those who don’t know, the “reverse polish notation” (or RPN) is an “old way” to write mathematical equations. Some of you might still have calculators with RPN. RPN works with a stack and a list of operators. The user puts “things” (generally numbers) in the stack, and then call an operator. The operator takes the last elements of the stack, use them to compute some operation, and then it pushes back the result in the stack. Depending on the operator more or less elements will be taken from the stack. For example + takes two elements from the stack, while sin (sinus) only takes one.

For example “5 8 +” computes the sum of 5 and 8. In other words, “5 8 2 + *” computes (8+2)*5=50.

The picture shows an old HP-65 that used RPN. When I was a kid, my father used to have one. Since the calculator erases all it memory every time it is shutdown, there is a little magnetic band (with the same dimensions as a chewing gum) that we put on one side of the calculator. The calculator then automatically drags the magnetic band with a little motor, until it exits on the other side with the content of the calculators memory written on it. One nice property of the RPN is that it does not require parenthesis. Also, it has this “indescriptible” flow that makes it enjoyable to use.

However, RPN is also quite difficult to debug or follow. For example, try to guess what is the result of “4 5 6 7 8 * / + 1 +”?

The answer is 0. The details are 4 ( 5 + ( 6 / (7 * 8 ) ) ) + 1 = 0 with integer rounding.

Another nice feature of RPN is that the interpreter is really simple: A reverse polish notation calculator can be implemented with a couple of tens of lines in Python. And probably just a bit more in C:

Just for fun, here is a reverse polish notation interpreter I implemented in Python:

import sys

def main():
while(True):
sys.stdout.write('> ') # Print ">"
line = raw_input() # Get a user input
stack = []
for ex in line.split(): # For all items in the inputs (i.e. numbers or operators)
if ex == "+":
a2 = stack.pop()
a1 = stack.pop()
stack.append( a1 + a2 )
elif ex == "-":
a2 = stack.pop()
a1 = stack.pop()
stack.append( a1 - a2 )
elif ex == "*":
a2 = stack.pop()
a1 = stack.pop()
stack.append( a1 * a2 )
elif ex == "/":
a2 = stack.pop()
a1 = stack.pop()
stack.append( a1 / a2 )
elif ex == "sin":
a1 = stack.pop()
stack.append( sin(a1) )
else:
stack.append( float(ex) )
print(stack)

if __name__ == "__main__":
main()

This interpreter support the operation: + / * and sin. It is very simple and lacks some error handling system, but it works.

The Small programming language

Recently, I came back to this idea of reverse polish notation calculator: I was wondering how I could augment the basic RPN calculator syntax to become a nice and full programming language. Several points were important for me:

1. Any classical reverse polish notation program should still be valid.
2. The language should be Turing complete.
3. The language should be usable (We don’t need another “Brainfuck”).
4. The interpreter should remain as small as possible.
5. The language should be as small as possible i.e. the minimum number of keywords.
6. The language should be augmentable with libraries.

Also, I wanted to keep the flow of RPN and see how it would translate for the programming language.

Therefore I created the “Small Reverse Polish Notation Programming Language”. The name is probably a bit too long, so let’s just call it “Small”.

The remaining of this sections shows and illustrates the operators of Small.

Println

The first function of Small is “println”. “println” simply prints the last value in the stack on the screen. The Hello world in Small is:

“Hello println World println”

Example

This program asks for the user to enter an input number, add one to it, and print the result.

Like in classical RPN, the stack is by definition a FILO (First In Last Out) that can store numbers. In Small, I also want to stack to store, strings of characters, and lists. These lists can contains other lists (i.e. recursive list). Also, list can also be interpreted at instructions!

Example

“Hello { 1 2 { 3 , 4 } }”

After executing the program, the stack contains two elements: “Hello” and the recursive list “{ 1 2 { 3 4 } }”.

Set and get

In addition to the stack, the Small interpreter allows variables. Variable are stored in the “environment”. Each variable has a name and a value.

To deal with variable, Small has two functions: “set” and “get”. “set” take a value in the stack and put it in a variable. “get” takes a value of a variable and put it in the stack. The name of the variable is also taken from the stack.

Examples

“5 a set” : Assign the value 5 to the variable “a”.

“a get” : Get the value of “a” in the stack.

Duplicate and throw

In addition, and to help dealing with the stack, Small has two functions: “duplicate” and “throw”. “duplicate” duplicates the last element in the stack. “throw” remove the last element in the stack.

Example:

“5 duplicate”

At the end, the stack is “5 5”.

“1 2 3 throw”

At the end, the stack is “1 2”.

Note that “duplicate” and “throw” would be emulated with variables: throw is equivalent to tmp set and duplicate is equivalent to tmp get tmp tmp set set

If

To deal with flows, Small has a “if” key word. “if” takes the last three elements in the stack, The first argument should be a Boolean value (true or false). The second and third arguments are lists. If the first argument is true, the second argument is executed as a list of instructions. Otherwise, the third argument is executed as a list of instructions.

Example

“1 2 < { toto println } { tata println } if”

Since 1<2, the program prints “toto”.

Note that the operator < takes to numbers and return true if and only is the second argument is greater than the first one.

This second example gives exactly the same result as the first one:

“1 2 < { toto } { tata } if print”

Exec

Finally, the last and probably most important function of Small is “exec”. “exec” takes the last argument in the stack, and execute it.

Example

“{ hello print } exec”

By using exec, get and set, we can start doing do some recursion

What do you think the next program does?

0
{
1 +
duplicate println
duplicate 10 <
{ f get exec }
{ }
if
}
duplicate
f set
exec
Answer: It prints natural numbers between 1 and 10.

Let’s see the code in details (The first number is the line number).

1 : We put the number 0 in the stack
2 : We put the recursive list of instructions defined between lines 2 and 9 in the stack.
10 : We duplicate this recursive list in the stack.
11 : We define f to be this list. At this point, the stack only has one copy.
12 : We execute the recursive list in the stack as a set of instruction

3 : We take the number in the stack, and we add 1 to it.
4 : We print this number. We duplicated this number to keep a copy after the printing.
5 : We test if this number if bellow 10 and put the result in the stack
6 : We define some instructions and put them in the stack.
7 : We define some instructions and put them in the stack.
8 : If the result of line 5 is true, we execute the instructions defined in line 6. Otherwise, we execute the empty list of instructions defined in list 7.

6 : We put the content of f in the stack, and execute it. Remember, f is a list of instructions.

Because lists are important, Small has four functions “head”, “trail”, “merge” and “length” to deal with them. “head” takes a list and return the first element. “tail” takes a list, remove the first element, and return the remaining of the list.“merge” takes two lists and merge them into a single list. “length” return the number of elements in a list. Note that the “length” function could be computer with recursion.

Example

{ 1 2 3 } head

Put 1 in the stack

{ 1 2 3 } throw

Put { 2 3 } in the stack.

{ 1 2 3} { 4 5 6 } merge

Put { 1 2 3 4 5 6 } in the stack.

Finally, to deal with libraries and files, Small has three functions “load”, “export” and “vars”. “load” takes a path as argument, and load this file content into the stack as a list. “export” takes a list of variable names, and export them to the parent environment. “vars” creates a list with all. We will see more about that later.

Trace

“trace” is the debugging function of Small. “trace” don’t take any argument and don’t generate any result. When you call trace, the interpreter will print the content of the stack and the value of the variables.

Example

5 a set
1 2 3 4 5
trace

You will see the content of the stack and the variables printed.

Getting Small

You can download small on my github page https://github.com/achoum/small. The repo contains the interpreter, some simple examples and a “standard library” (you will see about that in the next section).

You can just execute “small.py” in python to start the interactive mode. You can also run the examples in the “test.py” file. The standard library is in the file “std.sml”. “test.sml” is an example of Small script that is used in “test.py”.

Before continuing to read this article, I recommend that you play a bit with small yourself. For example, you can try to run the examples of the previous section. If you enable the debug option (by default it is enable in test.py), Small will print automatically the trace of each sub call of if and exec.

The Small standard library

For loops

We already saw an example of recursion in the example of the exec key word. If you are used to recursion you are probably fine. However, if you are the type of person that only use for loops, this might be hard for you.

Don’t worry, it is not a problem! Let’s just add a new operator “for” in the language – but wait, maybe these is another solution. Maybe we can create a “for” function in the Small language.

If you are a C user (or Java, or Python, or C++, etc.), you are probably puzzled now: “for” is not a function and it cannot be made with a function (except maybe now with some lambda calculus).

Small is different!

Let’s define a variable named “for” that contains the instructions to do a “for loop”. Instead of the reclusive example shown for the operator exec, I want to get the same result (printing all values between 0 and 10) in the following way:

i 1 10
{ i get println }
for get exec

In this example, the “for” function takes 4 arguments: A variable name, the beginning and ending value for the loop, and the segment of code to execute. Note that for is actually a variable that contains a list that contains instructions.

The definition of “for” should look something like that:

{
f set e set b set s set
b get s get set
{
s get get e get <=
{
f get exec
s get get 1 + s get set
h get exec
}
{ }
if
}
h set
h get exec
}
for set

As you can see, “for” is a function that defines a sub function in its core. This sub function is actually iterating on itself and unrolling the “for” loop. for is actually a recursive list!

You can also see that Small does not make difference between type of content: Variable names, vales and instructions are stored next to each other.

To make sure that you don’t have to include this “for” function is all your code, this “for” function is part of the “standard library” of Small.

To load the standard library, to type “std.sml load exec” at the beginning of your code! std.sml load load and parse the content of std.sml in the stack, and exec execute the instruction.

Get the i-th item in a list

Given a list of elements, another important and practical operation is to be able to get the i-th element of this list.

Here again, we could add a new “getitem” operator, or we could create a “getitem” function and put it in the standard library.

Using “getitem”, here is how we want to get the 3-th element in a list (i.e. the element at the index 2).

{ 10 11 12 13 } 2
getitem get exec

That would be cool right?

How, here is the definition of “getitem”. Note that we reused the “for” function.

{
n set
i 1 n get
{
tail
}
for get exec
}
getitem set

Conclusion and further work

That’s it for now. If you had the courage to read this post until the end, I should congratulate you.

I hope you enjoyed this little play and hack, and that you enjoyed teasing you mind with RPN and recursion.