RPN Script: Reverse Polish Notation Script

Intro

This is a small demo project to demonstrate some concepts about programming language design. This is inspired by forth in some aspects notably the RPN based syntax (which I grant is not a very popular syntax and will probably put off many). The benefit of such a language over other languages is that the RPN based languages are smaller in size and also faster mainly due to the fact that very little or no time is lost in parsing the source file. Also interpreted is a misnomer for this kind of language as it is something between a bytecode and full interpretation. What it does is compile the source code in memory before executing it. Such languages are called Threaded Interpretive Languages (Not to be confused with Threads as in Multi-threading). Although the form is borrowed from Forth most of the other things are borrowed from c family of languages to keep the language familiar. For the VM see here

When I was doing my Bachelors in Computer Applications I created a stack based postfix language named RIPL - RPN-based Interpretive Programming Language for my final year project. This is a reboot of the project but improved in many ways which are as follows:-

1. In RIPL I had used unions to hold the variables here I have used std::any which is a more efficient approach than unions.
2. In RIPL little thought was given to memory leaks but here I have used std::shared_ptr.
3. There were no break or continue statements in RIPL they are included here.
4. RIPL was a single header file but RPN-Script is divided into multiple files.
5. I had used Visual Studio 6 to write the code for RIPL (Yes! RIPL is that old.). I have used a combination of CMake and Neovim here.
6. The coding style was very bad then but hopefully that has improved now.
7. The stress, now, is on reusing what already exists instead of reinventing it.
8. This code is more aware of the SOLID Principles. Which are 1. Single Responsibility Principle, 2. Open Closed Principle, 3. Liskov Substitution Principle, 4. Interface Segregation Principle and 5. Dependency Inversion Principle.

How to use

This is a CMake project so you can use any editor that supports CMake to open this project. Make sure you have all the tools such as c++ compiler, cmake and other build tools installed. I used clang but you can use any modern c++ compiler. To build it execute the following steps:-

1. create a folder named out/ in the root of the project. mkdir out/
2. cd out/
3. cmake ..
4. make

Why RPN syntax

RPN or Reverse Polish Notation has been used in some programming notably Forth. Some other writers have published books on the subject one of which I have read - "Write your own Programming Language using C++" by Norman E. Smith. This was the book that got me started with RPN. RPN is more raw in nature compared to many languages so it is easy to see what goes on under the hood and thus make a great choice to teach students about programming languages. This project also has similar aspirations. Most books on language design go into mathematical treatment of the theory as parsing forms the major part of a compiler design. With RPN syntax the parsing part is minimal if at all and thus we can demonstrate subjects other than parsing. Theory of Computation can be very dry and off-putting (at least in my case, so I am assuming there are many more like me) and programming is juicier. Actually Writing a Recursive Descent Parser is fun without the dry theory except the CFG part which I think is usually necessary to develop a parser.

Features currently in this language:-

1. Arithmetic Operations: +, -, *, /, %
2. Relational Operations: ==, !=, >, <, >=, <=
3. Logical Opeartions: &&, ||, !
4. Increment and Decrement: ++, --
5. Stack Operations: dup, swap, rotup, rotdn, drop
6. Branching and Looping: if-else-endif, for-endfor, while-endwhile.
7. Printing: =
8. Support for types: double, long, string and bool
9. break and continue statements (can handle any level of nesting).
10. user input support: expect
11. Subroutines
12. Variables (global only)

Tour of the language

What we usually write as say a + b / c would be written as a b c / + in an RPN syntax. So, now create a file with the name test.rpn, write the following:- 10 30 3 / + = It prints out 20. (10 + 30 / 3)

Now replace with the following:- 10 for "Hello" = endfor end

It will print out Hello 10 times. First we push the number of times the for loop is to be executed then we push the string "Hello" inside the for loop and also print it out.

Make sure you separate each token with at least a white space(space, tab or newline) because thats how the language works. I have not made it bomb proof as I was doing it for demo purposes to illustrate vaeious aspects of a programming language design and error handling would drown out the actual concepts.

I have read in many places to use exceptions to implement break and continue statements which is an idea I don't particularly like because exceptions should be used to denote error conditions and not program logic. Probably, it might work in case of tree-walking and not in case of threaded interpretation, still, I am still not sure how that would work out in this case so, I have used an auxilliary stack to implement break and continue.

Break demo

10 # Initialize loop to run 10 times for # Start For loop dup # duplicate the loop index 5 == # compare it to 5 if # If it is 5. that is if the top is true then... drop # destroy the loop index break # break out of the loop endif # endif "Hello" = # print Hello endfor # endfor end # end of program

The script will print out Hello 5 times.

Comments

#This is a comment "Hello World" # Store a string to stack = #print it end

Continue statements

10 # Initialize for loop index for dup # duplicate it because the next statement will consume it 5 == if # if the index is = 5 then don't print it. continue endif dup = # duplicate the top once more to print it. endfor end

This script will skip the printing of 5

Factorial

"Enter a number:" = # Print the message expect # wait for user input i var # declare a variable named i 1 # push 1 on top of stack i <- # assign the value to i for dup # n n duplicate the value entered by user i -> * # push the value of i on stack # multiply it with the value i <- # assign it back to i leaving the stack clean endfor i -> = # print the value of i end

Fibinacci numbers

"Enter the number of Fibonacci:" = # Show the message expect # wait for user input 1 1 1 1 = = # push 1 4 times to stack and print twice first var # declare a variable named first second var # declare a variable named second third var # declare a variable named third first <- # assign the topmost value to first removing it from stack second <- # assign the topmost value to second removing it from stack for # the topmost value now is the number entered by the user first -> # push the value of first to stack second -> + # push the value of second to stack and add them third <- # assign the result to third second -> # push the value of second to stack first <- # assign the value to first third -> # push the value of third to stack second <- # assign it to second third -> = # push the value of third to stack and print it out endfor end

For loop

10 for dup = endfor end # this will print numbers from 10 to 1

Subroutines

"Hello world from RIPL!" # Push a string on stack say_hello call # call the named subroutine say_hi call # call the second subroutine end say_hello { = } # define the first subroutine say_hi { "Hi Pankaj" = } # define the second subroutine

make sure you define the subroutines after the end statement otherwise the results will be unpredictable.

"Hello World!!" say_hello call 34 76 + say_hi call end say_hello { = } say_hi { = }

Variables

hello var # declare a variable named hello 2 # push 2 on top of stack 4 # push 4 on top of stack hello <- = # assign the topmost value(4) to the variable named hello and print the top of the stack which will be 2 hello -> = # push the value of hello on stack and print it. this will be 4 3 hello <- # push 3 on top of stack and assign it to hello hello -> = # push the value of hello on stack (3) and then print it end

While loop

true # push the value true on stack while # we enter the loop because the topmost value is true "Continue loop?" = # print the message expect # wait for user input "y" == # compare it with y endwhile # basically as long as you keep typing y the loop will continue end

To Do

1. Arrays
2. File Handling
3. String Concatenation and other common string functions
4. switch-case statements.
5. Some operators:- +=, -=, *=, /=, %= (not sure if these should be implemented or that they make any sense in this context)
6. Print newline statement.
7. Improve the while statement's condition handling.
8. Add REPL(Read Evaluate Print Loop) interface.

How this project is organised

Most elements are clumped together by related funtionality. Eg. You will find all the builders and executables for branching and looping in the file named branching_looping, similarly all subroutine related code is located in subroutines.hpp and so on. This approach keeps the explosion of files under control.

The code here follows the command pattern with two base classes named Executable and Buildable which are heavily subclassed. Instead of putting the compilation code in a giant switch case block I have used a command pattern where the appropriate Buildable or Executable is looked up in a table. Once found, the appropriate code is then executed.

I have provided the scripts in the scripts folder. You can use them to test out the code.

Outro

I have purposely kept the code simple to illustrate the basic concepts. Hopefully this will provide you with a good starting point. Please let me know what you think of this project and what else you would like to see here.