3 ms·

One pass, but.. I'm willing to bet there is some transitional internal state which had to be looped over to do this, subsuming the "pass" inside lazy eval. You

by ggm 2y ago

One pass, but.. I'm willing to bet there is some transitional internal state which had to be looped over to do this, subsuming the "pass" inside lazy eval. You have to know the indeterminate "where" to jump to, which depends on subsequent state. So you preserve execution state, calculate on, and return at end to fill in the gaps.

lmm 2y ago
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.
- ggm 2y ago
  It's a showcase for Haskell and well worth reading. I should be less snide. Nowadays "multipass" means Mila Jovovich but it used to mean "another complex language with massive implications we deal with by divide-and-conquer-through-the-filesystem" and in the case of the York ada compiler that was some amazing number like 10 or more passes. There was a fashion for running your C instrumented and then recompiling it after runtime branch choice evidence was collected. I think the Dec Alpha OSF/1 compiler did it optionally.
  - astrange 2y ago
    > There was a fashion for running your C instrumented and then recompiling it after runtime branch choice evidence was collected. I think the Dec Alpha OSF/1 compiler did it optionally. This is called profile-guided optimization and new compilers (well, GCC and LLVM) have it. I mostly think it's bad and not statistically sound; given profile data the compiler is both overly trusting of it (no error bars) and can't find much useful to do with it (because there's no way to hint a modern OoO CPU).
rhet0rica 2y ago
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!)
- asplake 2y ago
  Explanation here: https://kcsongor.github.io/time-travel-in-haskell-for-dummies/ https://kcsongor.github.io/time-travel-in-haskell-for-dummie...
- jsjohnst 2y ago
  > The creators of this algorithm note that it can enumerate all tic-tac-toe games in just over a second! This is achievable in most languages, no?
codebje 2y ago
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.

by ggm 2y ago

lmm 2y ago

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.

ggm 2y ago
It's a showcase for Haskell and well worth reading. I should be less snide. Nowadays "multipass" means Mila Jovovich but it used to mean "another complex language with massive implications we deal with by divide-and-conquer-through-the-filesystem" and in the case of the York ada compiler that was some amazing number like 10 or more passes. There was a fashion for running your C instrumented and then recompiling it after runtime branch choice evidence was collected. I think the Dec Alpha OSF/1 compiler did it optionally.
- astrange 2y ago
  > There was a fashion for running your C instrumented and then recompiling it after runtime branch choice evidence was collected. I think the Dec Alpha OSF/1 compiler did it optionally. This is called profile-guided optimization and new compilers (well, GCC and LLVM) have it. I mostly think it's bad and not statistically sound; given profile data the compiler is both overly trusting of it (no error bars) and can't find much useful to do with it (because there's no way to hint a modern OoO CPU).

rhet0rica 2y ago

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!)

asplake 2y ago
Explanation here: https://kcsongor.github.io/time-travel-in-haskell-for-dummies/ https://kcsongor.github.io/time-travel-in-haskell-for-dummie...
jsjohnst 2y ago
> The creators of this algorithm note that it can enumerate all tic-tac-toe games in just over a second! This is achievable in most languages, no?

codebje 2y ago

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.