Factoring and refactoring

Genesis of the interest

Alongside the interest in slide rules, for years I've had a strong preference for RPN calculators. My daily driver for quick calculations on the laptop or iphone is Plus42, itself an emulator of the venerable HP-42s.

RPN-style calculation is extraordinarily logical. Like many things in our daily lives, algebraic notation is a suboptimal approach full of minor hindrances that you don't even realize until you break out of the mold. Parenthesis to white-knuckle sequencing, PEMDAS rules, all of this that we need to keep in our heads and think about when the actual calculation is going to proceed one step at a time. RPN, or suffix notation, simply lets you punch in the calculations in the same order as execution flow.

I've thought before that this must have positive implications on the language implementation, after all this is so close to how a CPU actually functions, and the stack interpreter paradigm is the most robust and performant model of building interpreters and is used heavily in lua among others.

Reverse-Polish (prefix) notation

RPN's logical ordering is achieved by placing operands first where simply stating an operand implies pushing it onto a stack, and then the stack is consumed by operations that come at the end (hence RPN also being called "postfix notation"). So what would have been algebraically entered as

5 * (4 + 3)

is expressed in RPN as

4 3 + 5 *

the 4 and 3 each push onto the stack, + then pops the top two items from the stack (which at this point we know to be the 4 and 3) then pushes their sum, then 5 pushes onto the stack again, and finally * pops the top two items (now 7 and 5) and pushes their product, leaving only the final result of 35 on the stack, ready for the next operation.

I've thought before that this must have implications for the calculator's implementation - after all there's not an arbitrary number of sub-expressions that need storing, or alternatively a sort of query-planning pass to re-arrange the whole thing into the proper order.

Factor: RPN applied heavily to programming

Factor is a programming language that, like Forth before it, applies ("broadens" even) this concept to writing software.

An example

I started reading through the catalog of posts from Re: Factor, the best factor blog I could find, and quickly came across this early one on implementing clamp (limit a value by both a minimum and a maximum). As soon as I understood what it's asking for, I took my "listener" (the main Factor REPL) and covered up the body of the post on my screen with it, to try it myself first.

My first version worked, with only the slightest bit of bugfixing!

: clamp ( min max x -- x' ) {
    { [ 2dup < ] [ drop nip ] }
    { [ 3dup nip > ] [ drop drop ] }
    [ nip nip ]
} cond ;

It's a very "let's see, there are 3 cases" approach. cond is in the driver's seat, and it takes pairs of "quotations" ([ ]-surrounded chunks of code which amount to anonymous functions which can be passed around on the stack) where in each pair the first produces a boolean on the stack, and the second is only executed if that boolean is t - then it short-circuits and exits once one of them runs.

At the beginning ( min max x -- x' ) explained that this expects 3 items on the stack, the names of which don't matter to the code here but should be self-explanatory: min, max, and x, and then after the -- it explains what the word (function) will leave on the stack, there's one item and I've called it x'.

With that stack in mind (min, max, x) let's see our 3 cases:

{ [ 2dup < ] [ drop nip ] }

2dup will duplicate the top 2 items on the stack, so our stack becomes min max x max x, then < replaces the 2 new copies on top with a boolean (our desired net stack affect: one boolean pushed on top) that is true if max is less than x - the upper clamping case. Then drop nip runs against our original stack min max x - drop first drops the top of the stack leaving us with min max, and nip then drops the second-from-the-top item min, leaving us with only max - the right answer for the upper clamp case.

{ [ 3dup nip > ] [ drop drop ] }

3dup is similar but will copy our whole triple, so our min max x becomes min max x min max x, then nip removes the second element from the top, leaving us min max x min x - our original input stack plus min and x, which is exactly what we need to check the lower-clamp case. > does just that, returning true only if min is greater than x, and putting us back to our original stack plus one boolean. drop drop will then remove the top two items from our original stack, changing min max x to just min, the right answer for the lower-clamp case we tested.

[ nip nip ]

The third item pushed onto the stack for cond was just a single quotation rather than another 2-array, which is how you can express an else case. nip again removes the second item from the top of the stack, and doing so twice takes the original stack min max x to just x, the right answer when we didn't hit either clamp.

Test that and it works, fantastic! Let's see what the blog post had.

: clamp ( a value b ) -- x )
    min max ;

Of course. Not surprising that min and max both exist in the standard library, and they would both naturally be binary operators (stack effect is replacing the top 2 items on the stack with 1). This exact implementation min max works for my argument order as well, where my input value was on top.

But I think we both got the order wrong. The input value is the thing the user most likely had already, and along with the clamp word the things they're most likely to need to provide are the boundaries. Stack effects expressed as ( x lo hi ) is probably the right choice, making the implementation max min. 10 99 clamp then would be a sequence of words that always clamps the top of the stack to a positive 2-digit number.

I'm glad I got the over-complicated version working, learning cond along the way. But I clearly have a lot to learn, and some work to do to internalize this whole paradigm.