diff options
| -rw-r--r-- | .gitignore | 45 | ||||
| -rw-r--r-- | weblog/factoring-and-refactoring.md | 86 |
2 files changed, 87 insertions, 44 deletions
@@ -8,50 +8,6 @@ /feed.xml /index.html /notes/index.html -/notes/sync/random/SLC-bars.html -/notes/sync/recipes/carmelized-onion-burgers.html -/notes/sync/recipes/chicken-noodle-soup.html -/notes/sync/recipes/chicken-piccata.html -/notes/sync/recipes/cocktails/american-single-malt-old-fashioned.html -/notes/sync/recipes/cocktails/aperol-spritz.html -/notes/sync/recipes/cocktails/bicicletta.html -/notes/sync/recipes/cocktails/boston-sour.html -/notes/sync/recipes/cocktails/clarified-new-york-sour.html -/notes/sync/recipes/cocktails/daiquiri.html -/notes/sync/recipes/cocktails/division-bell.html -/notes/sync/recipes/cocktails/final-ward.html -/notes/sync/recipes/cocktails/fresh-lemon-rum-martini.html -/notes/sync/recipes/cocktails/frozen-lemon-daiquiri.html -/notes/sync/recipes/cocktails/gin-basil-smash.html -/notes/sync/recipes/cocktails/gold-rush.html -/notes/sync/recipes/cocktails/honey-bee.html -/notes/sync/recipes/cocktails/index.html -/notes/sync/recipes/cocktails/kentucky-maid.html -/notes/sync/recipes/cocktails/killer-bee.html -/notes/sync/recipes/cocktails/last-word.html -/notes/sync/recipes/cocktails/margarita.html -/notes/sync/recipes/cocktails/moscow-mule.html -/notes/sync/recipes/cocktails/old-fashioned.html -/notes/sync/recipes/cocktails/paloma.html -/notes/sync/recipes/cocktails/paper-plane.html -/notes/sync/recipes/cocktails/rum-sour.html -/notes/sync/recipes/cocktails/sawyer.html -/notes/sync/recipes/cocktails/siesta.html -/notes/sync/recipes/cocktails/southside.html -/notes/sync/recipes/cocktails/sparkling-tangawizi.html -/notes/sync/recipes/cocktails/whiskey-smash.html -/notes/sync/recipes/cocktails/white-lady.html -/notes/sync/recipes/cocktails/white-russian.html -/notes/sync/recipes/colinflower-pasta.html -/notes/sync/recipes/index.html -/notes/sync/recipes/penne-arrabiata.html -/notes/sync/recipes/pork-and-mash-gratin.html -/notes/sync/recipes/potato-soup.html -/notes/sync/recipes/sourdough-bread.html -/notes/sync/recipes/spaghetti-with-marinara.html -/notes/sync/recipes/turkey-chili.html -/notes/sync/technologies/freebsd/pf.html -/notes/sync/technologies/index.html /projects/index.html /weblog/a-new-post-script.html /weblog/advent-of-code.html @@ -61,6 +17,7 @@ /weblog/censorship.html /weblog/dealerships-are-the-worst.html /weblog/deplatforming.html +/weblog/factoring-and-refactoring.html /weblog/from-packer-to-lazy-nvim.html /weblog/geminis-killer-app.html /weblog/gopher-item-types-a-gemini-miss.html diff --git a/weblog/factoring-and-refactoring.md b/weblog/factoring-and-refactoring.md new file mode 100644 index 0000000..fc87727 --- /dev/null +++ b/weblog/factoring-and-refactoring.md @@ -0,0 +1,86 @@ +# Factoring and refactoring + +I'm a man of some quirky obsessions, and the factor programming language is hitting me just right. + +## Genesis of the interest + +Alongside the interest in [slide rules](the-simple-joys-of-the-humble-slide-rule.md), for years I've had a strong preference for [RPN](https://en.wikipedia.org/wiki/Reverse_Polish_notation) calculators. My daily driver for quick calculations on the laptop or iphone is [Plus42](https://thomasokken.com/plus42/), itself an emulator of the venerable [HP-42s](https://en.wikipedia.org/wiki/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 + +```python +5 * (4 + 3) +``` + +is expressed in RPN as + +```factor +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](https://re.factorcode.org/), the best factor blog I could find, and quickly came across [this early one](https://re.factorcode.org/2008/10/clamp.html) 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! + +```factor +: 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: + +```factor +{ [ 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. + +```factor +{ [ 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. + +```factor +[ 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. + +```factor +: 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. |