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.