For the last two months I’ve been working intensively on a new software product, FE Builder. It’s a interactive shell to help scientists and engineers build custom finite-element applications. FE Builder takes care of 3D mesh generation and postprocessing, allowing researchers to concentrate on the physics of their solution. A key component is the fully-conformable postprocessor, FEVision. The goal is to allow the developer to define quantities for plots, interpolations, line scans, volume integrals and surface integrals through a configuration file. Quantities may be algebraic expressions of any degree of complexity that include five types of information:
- Common spatial operations at the current position (interpolations, gradients,…)
- Region physical properties passed from the solution program
- Run parameters set by the solution program
- Program parameters set by the developer
- Real-time parameters set by the user
The arrangement has worked so well that we are going to modify our dedicated postprocessors to allow users to extend functionality with custom calculations.
The key issue getting FEVision to work is speed. Generation of a single 2D slice plot may involve over 50,000 interpolations. Clearly, an algebraic interpreter would be out of the question – user functions must be compiled. We developed the FFI (Fast Function Interpreter) module for this purpose. In benchmark tests, FEVision runs at the same perceived speed as our hardwired programs.
A major factor in the speed of FFI is the function input format. The developer enters expressions in the configuration file in RPN (reverse Polish notation). Writing the RPN unit reminded me of my excitement when HP calculators first became available. The HP calculator with RPN logic was one of the most successful man-machine interfaces in the history of technology. Today, most scientists and engineers use algebraic calculators or none at all. I thought it would be interesting to say a few words about how RPN works and why it made the task of building FFI so much easier.
Consider how you would write a computer routine to find the numerical value represent by the following string:
5.0*4.5^3 + (9.2 + 0.6*0.9^(2+0.67))
The rules for parsing the line are complex, so your routine would be intricate and messy, possibly with recursive logic. I know because I wrote the general algebraic unit incorporated in many of our solution programs and I hated it. To make matters worse, suppose you had to compile the expression. By this, I mean generating and saving the expression symbolically so that the program didn’t have to reparse it every time an input changed. It’s not an impossible task, but certainly a difficult one.
The expression has the following form in RPN:
0.9 0.67 2 + ^ 0.6 * 9.2 + 4.5 3 ^ 5.0 * +
The string is parsed in order from left to right for expressions of any degree of complexity. An RPN calculator uses the stack shown in the figure below. Numbers are pushed and popped at the bottom. The first two stack registers have the special names X and Y. Evaluation of expressions is governed by three simple rules:
- If the entry is a number, push it on the stack.
- If the entry is a unary operator (exp, ln, sin,…), apply it to the number in the X register.
- If the entry is a binary operator (+,*,^,…) combine the numbers in the X and Y registers and move the stack down.
The result is the number that remains in the X register. By convention, the binary operators act in the following way: “+” = Y+X, “-” = Y-X, “*” = Y*X, “/” = Y/X and “^” = Y^X. On calculators, it is necessary to introduce an additional key (Enter) to designate a separation between two adjacent numbers. In this case, the series of operations would be:
0.9 Enter 0.67 Enter 2 + ^ 0.6 * 9.2 + 4.5 Enter 3 ^ 5.0 * +
RPN removes all issues of the order of parsing. Furthermore, it is simple to make a compiled version of an expression. For example, suppose we define the data structure
TYPE Entry
INTEGER Code
DOUBLE PRECISION Value
END TYPE Entry
TYPE (Entry) :: Exp(1:NEntMax)
A Code value of zero represents a number, negative values are unary operators and positive values are binary operators. Evaluation consists simply of filling in current Values for Code 0 entries and then running through entries sequentially, applying the three stack rules.
With this background, we can appreciate the brilliant concept of the early RPN HP calculators. In the act of entering them in RPN format, the user effectively compiled his expressions. The preprocessing greatly simplified the required logic in the calculator, increasing speed in an age when things ran pretty slowly. With simpler logic, a lot more functionality could be packed into the limited chips of the time. The user benefited because complex expressions could be defined with significantly fewer keystrokes. A perfect win-win symbiosis! As frosting on the user’s cake, RPN seemed like a neat new way to think about numbers.
It is still possible to buy an HP RPN calculator. The HP35S (a nice copy of the classic HP32) is available on the Internet for less than $50.00. It does offer the option of algebraic entry and contains the detestable parenthesis key. You can always cover it with WhiteOut.
You can get free RPN calculator programs to run on your PC. The best choice by far is the HP41CX emulation (shown in the figure below). It looks and acts exactly like the one in my desk drawer. The only thing missing is the babe-magnet leatherette case to attach to your belt. Here a download link: V41R8.exe. If you get the HP41, you’re going to need the instruction manuals. Use this link to download a scanned copy of the originals in PDF format:
HP41 calculator and RPN stack