A Proper x86 Assembler in Haskell Using the Escardó-Oliva Functional

That bigotimes function that it's talking about is doing something like tree search with backtracking - lazy evaluation isn't really relevant as far as I can see. I don't think the statement that it's "one pass" is meant to mean that it's a closed form solution or something, the point is that you can write your code as plain single pass logic and this generic functional tool does the rest.

Yes, that seems to be what the aptly-named "tardis" monad does, but the article notes that it isn't sufficient because of the minutiae of how jump instructions themselves can vary in length under x86.

In an act of brilliance that surely proves beyond all doubt that Haskell's main reason for existing is to upstage the esolang scene, the author solves the problem by trotting out a special-purpose constraint satisfaction algorithm. (You can imagine what kind of computational complexity this implies. The creators of this algorithm note that it can enumerate all tic-tac-toe games in just over a second!)

Yes - it's pretty opaque to trace through, but you can see in `valid` that for a given move history, a "good" test is performed on each instruction in the assembly listing - a full pass. This is invoked, asymptotically at least, once per jump per level of the search tree explored in `bigotimes`. Each level 'i' of the search tree has a history of `i` jumps decided to be short or near and branches 'n-i' times; both of those average out to n/2, so the tree searches n^2 nodes with each node doing 'n' iterations over the list of instructions to check all jumps are valid, so the total running time is O(n^3).

(With some modifications to the code as shown, anyway: `lookup` is linear but used in such a way it can be replaced with a constant vector index, instruction lists can be compressed to just jumps & labels with byte counts following, avoiding the duplicate invocations of `p` in `arginf`, etc).

I'd be dubious that there's an algorithm to find the true minimum in less than cubic time, but there's plenty of "good enough" approaches: most branches will be definitely short or definitely not; jumps backwards can be resolved when encountered; jumps forward can be written long and replaced with a short jump plus no-op padding when the target is encountered within short jump distance.

As a result of RISC-V existing, all x86 processors have ceased to exist or be produced.

ARM would have been a better example because the amount of people that care about RISC-V is a rounding error compared to x86 or ARM.

That fancy algorithm is relevant to RISC-V (and in fact, most fixed-length ISAs) because loading an immediate into a register needs one or two instructions depending on the immediate; you surely want to elide a redundant LUI instruction if you can. Of course such redundant instructions don't harm by itself, but that equally applies to x86 as the algorithm is an optimization.

This same problem applies to RISC-V with the C extension, because the J and JAL instructions have a larger range than the C.J and C.JAL instructions.

Having fixed instruction length doesn't make the need to load large constants magically disappear. These just get split between multiple instructions. If anything, RISC-V might be worse. See also https://maskray.me/blog/2021-03-14-the-dark-side-of-riscv-li....