GNU Astronomy Utilities

6.2.1 Reverse polish notation

The most common notation for arithmetic operations is the infix notation where the operator goes between the two operands, for example, \(4+5\). The infix notation is the preferred way in most programming languages which come with scripting features for large programs. This is because the infix notation requires a way to define precedence when more than one operator is involved.

For example, consider the statement 5 + 6 / 2. Should 6 first be divided by 2, then added by 5? Or should 5 first be added with 6, then divided by 2? Therefore we need parenthesis to show precedence: 5+(6/2) or (5+6)/2. Furthermore, if you need to leave a value for later processing, you will need to define a variable for it; for example, a=(5+6)/2.

Gnuastro provides libraries where you can also use infix notation in C or C++ programs. However, Gnuastro’s programs are primarily designed to be run on the command-line and the level of complexity that infix notation requires can be annoying/confusing to write on the command-line (where they can get confused with the shell’s parenthesis or variable definitions). Therefore Gnuastro’s Arithmetic and Table (when doing column arithmetic) programs use the post-fix notation, also known as reverse polish notation. For example, instead of writing 5+6, we write 5 6 +.

The Wikipedia article on the reverse polish notation provides some excellent explanation on this notation but here we will give a short summary here for self-sufficiency. In short, in the reverse polish notation, the operator is placed after the operands. As we will see below this removes the need to define parenthesis and lets you use previous values without needing to define a variable. In the future151 we do plan to also optionally allow infix notation when arithmetic operations on datasets are desired, but due to time constraints on the developers we cannot do it immediately.

To easily understand how the reverse polish notation works, you can think of each operand (5 and 6 in the example above) as a node in a “last-in-first-out” stack. One such stack in daily life is a stack of dishes in the kitchen: you put a clean dish, on the top of a stack of dishes when it is ready for later usage. Later, when you need a dish, you pick the top one (hence the “last” dish placed “in” the stack is the “first” dish that comes “out” when necessary).

Each operator will need a certain number of operands (in the example above, the + operator needs two operands: 5 and 6). In the kitchen metaphor, an operator can be an oven. Every time an operator is confronted, the operator takes (or “pops”) the number of operands it needs from the top of the stack (so they do not exist in the stack any more), does its operation, and places (or “pushes”) the result back on top of the stack. So if you want the average of 5 and 6, you would write: 5 6 + 2 /. The operations that are done are:

  1. 5 is an operand, so Arithmetic pushes it to the top of the stack (which is initially empty). In the kitchen metaphor, you can visualize this as taking a new dish from the cabinet, putting the number 5 inside of the dish, and putting the dish on top of the (empty) cooking table in front of you. You now have a stack of one dish on the table in front of you.
  2. 6 is also an operand, so it is pushed to the top of the stack. Like before, you can visualize this as taking a new dish from the cabinet, putting the number 6 in it and placing it on top of the previous dish. You now have a stack of two dishes on the table in front of you.
  3. + is a binary operator, so it will pop the top two elements of the stack out of it, and perform addition on them (the order is \(5+6\) in the example above). The result is 11 which is pushed to the top of the stack.

    To visualize this, you can think of the + operator as an oven with a place for two dishes. You pick up the top-most dish (that has the number 6 in it) and put it in the oven. The top dish is now the one that has the number 5. You also pick it up and put it in the oven, and close the oven door. When the oven has finished its cooking, it produces a single output (in one dish, with the number 11 inside of it). You take that output dish and put it back on the table. You now have a stack of one dish on the table in front of you.

  4. 2 is an operand so push it onto the top of the stack. In the kitchen metaphor, you again go to the cabinet, pick up a dish and put the number 2 inside of it and put the dish over the previous dish (that has the number 11). You now have a stack of two dishes on the table in front of you.
  5. / (division) is a binary operator, so pull out the top two elements of the stack (top-most is 2, then 11) and divide the second one by the first. In the kitchen metaphor, the / operator can be visualized as a microwave that takes two dishes. But unlike the oven (+ operator) before, the order of inputs matters (they are on top of each other: with the top dish holder being the numerator and the bottom one being the denominator). Again, you look at your stack of dishes on the table.

    You pick up the top one (with value 2 inside of it) and put it in the microwave’s bottom (denominator) dish holder. Then you go back to your stack of dishes on the table and pick up the top dish (with value 11 inside of it) and put that in the top (nominator) dish holder. The microwave will do its work and when it is finished, returns a new dish with the single value 5.5 inside of it. You pick up the dish from the microwave and place it back on the table.

  6. There are no more operands or operators, so simply return the remaining operand in the output. In the kitchen metaphor, you see that your recipe has no more steps, so you just pick up the remaining dish and take it to the dining room to enjoy a good dinner.

In the Arithmetic program, the operands can be FITS images of any dimensionality, or numbers (see Invoking Arithmetic). In Table’s column arithmetic, they can be any column in the table (a series of numbers in an array) or a single number (see Column arithmetic).

With this notation, very complicated procedures can be created without the need for parenthesis or worrying about precedence. Even functions which take an arbitrary number of arguments can be defined in this notation. This is a very powerful notation and is used in languages like Postscript 152 which produces PDF files when compiled.




See the EPS and PDF part of Recognized file formats for a little more on the Postscript language.