Introduction to Reverse Polish Notation

To learn how to use Qwerty RPN, you must learn how to write in reverse Polish notation. A typical mathematical expression puts the operator in the middle, like 2 + 3, while in RPN, you put the operator at last (and a space between the numbers): 2 3 +. Note the space before + is optional, to minimize typing. One advantage of using RPN is that you don't need parenthesizes. 2 * (6 + 7) is written as 2 6 7 + * (or with less spaces, 2 6 7+*) in RPN. What does it mean? When reading RPN expressions, you do not see which operators are binded to which numbers. You track the numbers on a stack. What is a stack? A stack is a list-like data structure that allows you to push a new value on the top of the stack, or pop to remove the value on top. For example, when you push 5 to an empty stack, the top of the stack is 5, then when you push 8, the top is 8, and when you pop the stack, you get 8 and only 5 remains on the stack. In RPN, a number pushes to the top of the stack and an operator pops the stack twice and pushes the result of the operation. Let's look at an example expression: 4 5 7 + * 8 -

An another way to look at an RPN expression is to parenthesize it: ((4 (5 7 +) *) 8 -), which can be switched to (4 * (7 + 5)) - 8. The basic procedure is to read the RPN expression from right-left, add a right parenthesis for every operators, then balance the parenthesis while making sure every parenthesized expressions have only two subexpressions and one operator.

If an operation is performed and there are not sufficient numbers on the stack, an error could occur. (for example: 1 + causes a stack underflow.)

In Qwerty RPN, functions also exist, for example, f is the factorial function, unlike other operations, it only need one number on the top of the stack. There are many more, such s for sine, r for square root. Some functions are either:

• nullary: They take nothing on the stack. However, they may or may not push the stack. For example, p pushes the constant π, while x exits the program.
• unary: takes one element on the stack, and pushes back the result. not(~) is an example.
• binary: takes two elements on top of the stack, and pushes back the result, most operations such as +, -, *, / are binary.
• variadic: they read everything on the stack, avg(A) is an example.

You can translate an n-ary function expression f(x₁, ..., x_n) to x1 ... xn f. Please note that the last argument of the function is on the top of the stack, then the second-last argument is on the second top of the stack, and so on. 5 2 - = 3. It's very easy to get confused of them.

Also, you can put comments by using ;, the text after it until a newline are ignored. Comments are used to explain the code.

However, most of they return values. Here is the full list:

 +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
 | ~ not  | ! pop  | @ getn | # putn | $ swap | % mod  | ^ pow  | & and  | * mul  | ( dec  | ) inc  | _ neg  | + add  |
 | ` xor  | 1 ---- | 2 ---- | 3 ---- | 4 ---- | 5 ---- | 6 ---- | 7 ---- | 8 ---- | 9 ---- | 0 ---- | - sub  | = eq   |
 +--------+--------+--------+--------+--------+--------+--------+--------+-----------------+--------+--------+--------+
 | Q      | W      | E 10^x | R root | T atan | Y      | U      | I      | O      | P      | { shl  | } shr  | | or   |
 | q x^2  | w      | e exp  | r sqrt | t tan  | y      | u      | i 1/x  | o      | p pi   | [ flr  | ] ceil | \ roun |
 +--------+--------+--------+--------+--------+--------+--------+--------+-----------------+--------+--------+--------+
 | A avg  | S asin | D rad  | F      | G      | H      | J      | K      | L log  | : dup  | " ge   |########|########|
 | a abs  | s sin  | d deg  | f fac  | g      | h      | j      | k      | l ln   | ;      | ' le   |########|########|
 +--------+--------+--------+--------+--------+--------+--------+--------+-----------------+--------+--------+--------+
 | Z      | X die  | C acos | V      | B      | N      | M max  | < lt   | > gt   | ? rand |########|########|########|
 | z      | x exit | c cos  | v      | b bool | n      | m min  | , getc | . putc | / div  |########|########|########|
 +--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

State Tracking and Flow Control: Variables and Labels

You can create variables in Qwerty RPN. Variables store values independent from the stack, and they are referenced by names called an identifier. A variable-set operation takes the top of the stack, and "moves" (literally, as the mov operation in most assemblers) the value to the variable. The equals sign, = followed by a variable name, consisting a non-broken sequence of letters and numbers, is the variable-set operation. While a dollar sign, $, followed by a variable name, is the variable-get operation. The following code returns 10:

10 =var $var

How to Use Arrays

One of the applications of variable-variables is the array functionality. Note you don't need the variables such as VALUE and INDEX, just make sure you keep track of the stack. To set an element in the array:

$VALUE $INDEX =$

To get an element from the array:

$INDEX $$

To iterate through the array:

0=I
>loop
 $I ; get the index I
 : $LENGTH > ; duplicate it, and compare with LENGTH
 <break ; if the last comparison returned false, the loop is over
 $$ ; get the current value
 ; -- DO SOMETHING HERE
 $I ) =I ; increase I by one
 1 <loop >break ; end loop

If you want to use multiple arrays in one program, consider limiting the array sizes and use offsets for different arrays. For example, the array A uses variable 0 from 100 and array B uses variables 101 from 201. You can also write your own memory management methods to do so.

Brainf**k to Qwerty RPN

(This is an optional section) Brainf**k is a typical esoteric programming language. It has a tape-like memory storage. Brainf**k programs can be transformed into Qwerty RPN by using the array technique above. Here is the basic procedure of translating Brainf**k to Qwerty RPN.

• The variable i tracks the program counter. The header of the code is therefore 0=i, which initializes it.
• - and +: Get the value, increase or decrease it, and write back: $i $$ ( $i =$ or $i $$ ) $i =$
• < and >: Simply decrease or increase the variable I: $i ( =i or $i ) =i
• Loops ([BODY]): Loops are transformed into goto labels, and the condition is the current memory cell. Let L be a unique label: >L BODY $i $$ <L
• I/O: , and .: , transforms into , $i =$, and . transforms into $i $$ .

See bf2qwerty.pl for a translator.