We create Simple, a Turing complete programming language using the Reverse Polish Notation. We when show the power of Simple by creating a standard library containing the for-loop and list-get-item functions.
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).
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.
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:
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.
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
The function that asks for a user input is read.
Example
read 1 + println
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 } }.
In addition to the stack, the Small interpreter allows variables. Variable are stored in the environmen. 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.
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
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
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?
1 2 3 4 5 6 7 8 9 10 11 12 | |
*Answer: It prints natural numbers between 1 and 10.
Let’s see the code in details (The first number is the line number).
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.
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 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.
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.
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.
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
head
}
getitem set
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.
As always, if you have any comments or questions, please do not hesitate to ask about them in the comments.
Also, if you want to create so challenges in Small, you can also post them in the comments. I am sure other readers will enjoy trying to solve them.
Keep in mind that this version of Small is still very minimal (to string manipulation, to file reading/writing, no threading, etc.) and that Small is not supposed to replace C++ or Java anytime soon :).
The next time I talk about Small, I will show you some nice stuff with some Turtle Logo like commands.