HP-71 BASIC funny quirks

[robve]

(01-27-2023 04:21 PM)J-F Garnier Wrote:  The HP BASIC program lines are not directly readable, they are in token form, moreover the numeric expressions are stored in an internal RPN form.

The benefit of the tokens and RPN forms is a more compact and faster executing code.

I'm not sure if I buy that RPN tokenization of BASIC algebraic expressions results in a noticeable faster execution speed.

Let's take a closer look. By contrast, a "standard" BASIC interpreter uses operator precedence parsing (an improved form of the simplistic shunting yard algorithm) to evaluate expressions, which is known to be a simple and efficient algorithm. It scans each token only once from the left to the right in the input. Similar to LR(1) parsing, an operator precedence parser uses a stack to decide to reduce or shift a token on the operator stack. A reduction applies an operator to its operands (operands are on the parameter stack, like RPN). The only extra overhead is pushing and popping a byte (the operator token) from an operator stack and consult a small table with operator precedences to decide if an operator should be applied or should be applied later. For example a+b*c results in a and b on the parameter stask and + on the operator stack. Then * is compared to +. Since * has higher precedence, + is not yet applied and c is pushed on the stack. Then the operator stack is unwound by applying * and +. Some happens with parenthesis. What is this extra cost of a push/pop per operator? Perhaps tens of extra CPU cycles. Much less than applying the operator to a BCD floating point number, which takes hundreds or even thousands of CPU cycles on an 4 or 8 bit machine with floating point in software rather than floating point hardware.

Secondly, I'm not sure if RPN tokenization is worth it with respect to BASIC program complexity. It adds a lot more complexity to the tokenization and decompilation steps. This can slow down program editing, i.e. to store and recall a program line to edit. Nor makes it a program a lot smaller (operations and operands are the same, just reordered in memory), unless a lot of parenthesis are present and needed in the algebraic formulation of an expression, since RPC does use them, of course. And most expressions in BASIC programs are rather short, like one or two operators applied to two or three operands, such as X = X+1 for example.

So why does the HP-71B use RPN tokenized BASIC? It's a wonderfully over engineered machine. That's why. And that's why I like it

- Rob