Scoped effects is broken

[re-xyr]

Turns out cleff suffers the same problem as eff (though I'm not sure if the cause is the same):

good2 :: String
good2 = runPure $ runReader "unlocaled" $ interpret (\SomeAction -> ask) do
  local (const "localed") someAction

-- >>> good2
-- "unlocaled"

Cause:

• All effect operations in the interpreter of SomeAction will use the environment at that time.
• local will make a new environment in which direct calls to ask will refer to the new value correctly
• But not other interpreted effects that call ask. They still use the environment they captured.

effectful does not have this problem because its Reader actually uses a thread-local mutable variable. cleff can't be thread-local hence cannot do the same to fix the problem. I also don't know how we can retroactively change an environment captured in the past (maybe we can't).

This also shows that cleff interpretation machanism has flaws. I'm not sure if this library is worth continuing planning for release or anything; it will likely stay at an experimental state. I will try to investigate this issue but this is likely to be fundamental to this approach.

Investigation:

• Does polysemy also have this problem? If not, how does it solve that? If we adapt the same thing will we need to give up other things?

(cc @arybczak)

---

Edit: maybe use IntMap as the underlying implementation of Rec. Access is as good as constant time and modify is constant as well. This may give rise to some solutions.

[re-xyr]

Maybe-solution:

Instead of mapping each effect to a handler, map each effect to a reference to a handler. Obviously we cannot use IORef. Or TVar. Or anything like that. What we need is a reference that can point to different things on different threads.

Therefore what we need is an immutable table that is passed around along with the Env; namely, an IntMap (Or a Vector - not sure which will turn out to be more efficient). The reference is simply a unique integer. This can be achieved via Unique. (Unique is thread safe.)

Additionally this allows Env to use a PrimArray which is hopefully a bit faster than SmallArrays.

[re-xyr]

Regression:

• aqn: 3.9s -> 5.5s
• big-stack: 44us -> 136us
• countdown: 14us -> 66.2us
• file-sizes: no change
• reinterpretation: no change

[re-xyr]

@arybczak I've experimented with the fix mentioned in the previous comment and got considerable regression (also put above). Its performance in microbenchmarks is now close to fused-effects (not to say that is any valuable observation - just to show the size of the regression). I haven't done extensive profiling yet so I'm not entirely sure whether this regression is fundamental to this approach, but I tend to guess so because the obvious overhead of IntMap.

At the same time, if this regression is fundamental, it further shows that cleff and effectful are very different. effectful does not suffer this problem with its HO semantics because its expressivity is limited. cleff on the other hand cares about expressivity very much, and so it is willing to adapt for an approach that preserves expressivity and correctness, albeit slower. Note that there is no way to integrate this fix also into effectful because that will harm its performance, which is more important for effectful.

[re-xyr]

Well, it turns out that it wasn't a fundamental problem. It was because:

1. GHC failed to inline some short functions so I had to manually {-# INLINE #-} them;
2. GHC doesn't like curried functions for reasons I don't know yet. Therefore this type:

data Eff es a = Eff (Rec es -> Mem -> IO a)

performs way worse than:

data Eff es a = Eff ((Rec es, Mem) -> IO a)

Both of these are addressed in 65be66e. The regression now is small and acceptable in my opinion.