Maybe reimplement the demand and force for MonadValue, MonadThunk and such

[Anton-Latukha]

Progress:

Proper order the arguments in:
class MonadThunk t m a | t -> m, t -> a implementations & all uses of:

• ✔️ force
• ✔️ forceEff
• ✔️ further
• ✔️ queryM

class MonadValue v m:

• ✔️ demand

With #864 factor-out the Kleisli arrows from implementation, and do a new refactor over the code.

• ✔️ force
• ✔️ forceEff
• ✔️ further
• ✔️ queryM

class MonadValue v m:

• ✔️ demand

---

The thunk family of functions are what are the most computationally costly in the system.

demand does the force (also known as forseThunk) - which is one of the most computational-intensive parts of the project:

Currently, they look as:

instance ...
  => MonadThunk (StdThunk m) m (StdValue m) where
  force    = force . _stdCited . _stdThunk
  
instance ...
  => MonadValue (Judgment s) (InferT s m) where
  demand = flip ($)
  inform j f = f (pure j)

instance ...
  => MonadValue (StdValue m) m where
  demand (Pure v) f = force v (flip demand f)
  demand (Free v) f = f (Free v)

  inform (Pure t) f = Pure <$> further t f
  inform (Free v) f = Free <$> bindNValue' id (flip inform f) v

Notice how thunk gets passed first into the function.

But the thunk (v) - is what these functions were created to change, the thunk never gets reused in them.

---

And, as I belabored everywhere already, - the source code does a lot of flipping of the arguments for them, and the implementation of them flips the arguments internally & to recurse on itself, which suggests that implementation itself should be flipped.

The resulting code:

instance ...
  => MonadThunk (StdThunk m) m (StdValue m) where
  force df v = force df (_stdCited $ _stdThunk v)  -- notice

instance ...
  => MonadValue (Judgment s) (InferT s m) where
  demand f v = f v  -- superflous
  inform f v = f $ pure v  -- superfluous
  -- becomes completely superfluous instance, reduction of it preserves code from superfluous type class overhead, simplifies the code and its readability.

instance ...
  => MonadValue (StdValue m) m where
  demand f (Pure v) = force (demand f) v
  demand f t = f t  -- is superflous
  
  inform f (Pure t) = Pure <$> further f t  -- ... to be investigated during refactor
  inform f (Free v) = Free <$> bindNValue' id (inform f) v  -- ... to be investigated during refactor

That looks both a lot more intuitive and efficient. demand f passes demand f, inform f - inform f - stack reuse, and more importantly the most costly one of them force df now does a tail call of itself.

  -- Because before it really was:
  force       = force . _stdCited . _stdThunk   -- is:
  force v df  = force (_stdCited $ _stdThunk v) df  -- passes thunk as 1-st arg that always gets changed.
  --- now
  force df v  = force df (_stdCited $ _stdThunk v)

We get a tail recursion on force - and reduce all arg flipping at once in the codebase. Which makes code more understandable.
Is this sound thing to do, or am I tripping?

---

So, Thunk.Basic also flips force which is an alias of forceThunk, and now it becomes:

forceThunk
  :: forall m v a
   . (MonadVar m, MonadThrow m, MonadCatch m, Show (ThunkId m))
  => (v -> m a)
  -> NThunkF m v
  -> m a
forceThunk k (Thunk n active ref) = do
  eres <- readVar ref
  case eres of
    Computed v      -> k v
    Deferred action -> do
      nowActive <- atomicModifyVar active (True, )
      if nowActive
        then throwM $ ThunkLoop $ show n
        else do
          v <- catch action $ \(e :: SomeException) -> do
            _ <- atomicModifyVar active (False, )
            throwM e
          _ <- atomicModifyVar active (False, )
          writeVar ref (Computed v)
          k v

Notice, in this forceThunk the very same thing - the first arg passed is never modified, and k gets returned first, what forceThunk operates on - is the thunk.
This way, probably means that constant k being the first argument - it is probably would get memory reuse.

---

And moreover, we see that 1-st arguments passed do not get used, they just get passed-through the whole (*sic) chain. This means there should be an elegant way to not pass them, but just apply them to the result of all this. Which would save a lot of computations.

The forceThunk ends everywhere in k v - shows that is just a passed-around function application that asks to become exterior, so after refactor the forceThunk just returns the v.

Recently ByteString, which seen as a pretty optimized library, in the 0.11 did so, bodigrim rewrote 1-3 HOFs so that they do not pass args superfluously, and by that ByteString suddenly got ~25% performance increase, probably that args passing was the ByteString bottleneck.

---

(Judgment s) (InferT s m) infer wraps in Pure and demand is just f a. -- established as vacuous
(StdValue m) m demand just unwraps the Pure and otherwise is just f a . -- seems also vacuous, maybe it can be simplified even further, especially since any force use always wrapped inside of demand (~100 cases), or where it is used raw - surrounding code simulates demand (all other cases). Since all force use gets wrapped with 1 logic gate - it seems logical to put it inside the force, and go do current recursion internally, and reduce demand to force everywhere. Anyway "demand" is a synonym to "force", which is in itself a suggestion. Reduction of demand also means the reduction of type class inference search in those ~100 cases.

Are these sound things, or am I tripping?

[Anton-Latukha]

This refactor seems fully compatible to do after the work that guys do in #804.

[sorki]

Nice find! I'm looking forward to benchmarks 🚀

[Anton-Latukha]

Yeah.

That was a style during HNix writing. Actions were threaded through the code, to resolve right at the very end of the functional stack.

[Anton-Latukha]

Currently, working gradually from the tail-up.

[Anton-Latukha]

In the #873 in the profiler, the presence of computation chain of force -> demand - plummeted.
Now one needs to look quite deep into the computational statistics to find the demand.

Now, basically what is happening is just: f <=< demand <=< force.

After a couple of moves to the forceF would be switched from, and so force* would also probably plummet a bit more.

In the profiler it is now seen - the main computational complexity that is left is the frame messaging system (probably because it is declared with RankNTypes forall a .. z, GHC simply can not permit itself to do with the code anything and because of the data types processing) and the scopes (with wich the Obsidian guys have the idea what to do).

[Anton-Latukha]

Completed.

Note into the future: there are now class Monad{Thunk,Value}F which get Kleisli arrows and do Kleisli composition with implementation into aka "Kleisli-composite", in other words, it allows to wrap the customization into it and use other resulting structures.