joshvera/effects

An implementation of "Freer Monads, More Extensible Effects".

effects's Issues

Investigate whether we need a strict version of `modify`.

The traditional State monad has a modify' function that is strict in the user state so as to prevent leaks. It is unclear whether this library's modify needs the same.

Interposing is ignorant of other effect handlers

This came up most recently in the context of #46, but we’ve seen it in a few different contexts overall. I’m aware of three useful lenses on the problem, so I’ll try to detail each of them.

1. interpose applies only to the effects inside it, not whatever effects they’re handled with.

   If you use resumable exceptions, Yield, or some effect-as-abstraction which hides the implementation details behind its requests & handlers, you have to be aware of the interactions with e.g. Exc and Reader. catchError and local both use interpose to intercept requests, but only within the action passed to them at the time at which they were called.

   Thus, local (+ (1 :: Int)) (send Foo) will increment the context value for any asks or further local inside the action it receives, send Foo, and not whatever action handles send Foo. Since there are no Reader actions within send Foo itself (only Foo, whatever that is), it’s as if we hadn’t bothered using local at all.

2. Effects inserted by handlers (relay, etc) are run in the context at which the handler is called, not in the context of the effects they’re handling; or, handlers can inject values, but not effects, into effectful actions.

   This is easiest to demonstrate by zooming out a bit from the local handler described above to encompass the Foo and Reader handlers as well:

   data Foo result where
     Foo :: Foo Int
   
   testFoo :: Eff '[] Int
   testFoo = runReader (0 :: Int) (relay pure (\ Foo yield -> ask >>= yield) (local (+ (1 :: Int)) (send Foo)))

   The relay handling Foo is free to send Reader requests, since Reader is handled above it. However, these requests are made in the context relay is called at, which only has the top-level runReader handler present, and not where the Foo effect is sent. Thus, the result of testFoo will be 0, despite the local increment—sending the Foo effect escapes from the local context and there’s no way to un-escape.

   This is the case even tho we’re calling yield to provide the Int back to the sending context—so we can inject values back in, but not effects. That takes us to the third angle on this.

3. Higher-order effects are inflexible.

   The one exception I’m aware of to the rule that handlers can inject values but not effects is if we have what I’m terming a higher-order effect, i.e. an effect whose result is an effectful action. We can define Foo thus by changing its result type:

   data Foo result where
     Foo :: Foo (Eff '[Foo, Reader Int] Int)

   Rather than encoding a request for an Int, Foo is now a request for an Eff producing an Int. Since we’ve changed the result type of Foo, we must also change its handler and requests:

   testFoo :: Eff '[] Int
   testFoo = runReader (0 :: Int) (relay pure (\ Foo yield -> yield ask) (local (+ (1 :: Int)) (join (send Foo))))

   Note that we’re yielding the ask action (rather than its result), and joining the result of the send. Now, the result of run testFoo is (correctly) 1, which is exactly the behaviour we want. Furthermore, it’s clear that the change to the semantics of the request are the only sensible way of injecting effects into an action; the effect has to specify that they’ll occur, the code making the request has to request and join them, and the handler has to satisfy that request with an effectful action.

   Unfortunately, this comes at a significant cost to flexibility. Foo’s result type enumerates all of the effects it’s able to perform. This same problem exists with Embedded, which makes it easier to encode a smaller list of effects, but in no way addresses the need to enumerate them. (Furthermore, as Embedded requests hold an Eff and return an a, they’re only able to express the passing of an action to a handler, rather than the handling of an effect by passing an action back.)

   This can pose a serious barrier to implementation, since we have to be careful not to mention the effects list itself, i.e. the naïve Member (Reader (Eff effects Int)) effects constraint we would wish to be able to employ is unsolvable due its request for the occurrence of effects within effects—and so we can’t actually handle the effect.

   The reason becomes obvious when you try to give a type for the handler: we start with Eff (Reader _ ': effects) a -> Eff effects a, and then try to fill in the hole. But since it’s self-referential, we have to fill it in with Eff (Reader _ ': effects) Int, and then again, ad infinitum. Attempts to resolve this with a type equality constraint on effects also fail, and while it’s not explicitly mentioned, I believe it’s due to the occurs check.

   When needing to break a cycle like this, the obvious solution is to employ a newtype, which we can indeed use successfully here. However, this is really just moving the problem around. While something like this:

   newtype Inner = Inner { runInner :: Eff (Reader (Inner effects Int) ': effects) a }

   does enable us to write the handler, now the actions making requests have to be aware that a) they need to use & unwrap Inner, and b) that it’s at the head of the effect list (a constraint imposed by Inner itself). While the former problem is quite minor, the latter means that they instantly become very inflexible, and can’t easily be run in different contexts.

These three problems—really the same problem—are the cause of significant complexity in our use cases. I think we might be able to make some headway by having Eff provide effects with the effect list as a parameter, but I’m not at all certain of that.

It’s also entirely possible that this is just a reality of using this system. In that case, we should at least document some best practices for handling these sorts of situations.

Membership constraints can’t be used to deduce other membership constraints

Because our redesign of Member to support fast(ish) compiled with Unions of hundreds of elements involved defining it using an ElemIndex type family where each branch is effectively a complete unrolling, there’s no relationship between different branches: you can’t infer Member t (U ': ts) from Member T ts, or vice versa.

While this is acceptable in cases where we aren’t dynamically extending the members (e.g. when used for à la carte ASTs), it’s counterproductive in its original use in Eff: you often end up having to carry around both the Member T ts and Member T (U ': ts) constraints, and this gets compounded every time you want to use T at a different level of embedding.

The inferred type roles for Union (and therefore Eff) are wrong

Union doesn’t visibly use its member list, so its inferred type role is phantom, which is wrong. It should probably be nominal (I’m not sure it shouldn’t be representational, but maybe).

The same therefore applies to Eff.

Unfortunately, we rely on this behaviour to embed effects in values, so any resolution to this should come hand-in-hand with a resolution to #47, i.e. higher-order effects.

runPrintingTrace should go to stderr instead of stdout

Printing to stdout makes runPrintingTrace much less useful.

Members constraints lead to slow compiles

This seems to be an instance of the well known type and coercion pile-up problems with recursive type families:

https://ghc.haskell.org/trac/ghc/wiki/Performance/Compiler#Typepile-up

Port Embeddable effect

It looks like Embeddable might give us the ability to embed an effect in another. https://github.com/TaktInc/freer/pull/4/files

/cc @tclem

Benchmark FTCQueue against FastCatQueue

FTCQueue has worst-case constant-time >< & |> + amortized constant time tviewl. type-aligned also offers FastCatQueue with worst-case constant-time ><, |>, <|, and tviewl. We should benchmark them to see how they stack up in practice.

Use -XAllowAmbiguousTypes & -XTypeApplications instead of Proxy for Apply

-XTypeApplications has zero runtime cost, Proxy has non-zero runtime cost.

This will mean that any caller of apply & friends will need to have TypeApplications on. We could provide Proxy-using wrappers for backwards-compatibility.

msplit should be a higher-order effect

msplit is incorrect right now, as it won’t draw samples from embedded actions, only from continuations. We should instead define it as a higher-order effect, and then interpret it with the desired semantics, so that we can do logic programming in Eff.

CI

It’d be good to have CI to run the tests.

Higher-order effects can’t be type-constrained

Embedded actions are essentially functorial, with the result type changed when threading handlers through. It is therefore impossible to write a valid Effect instance which constrains the result type, e.g.:

data F v m a where
  F :: m v -> F v m v

instance Effect (F v) where
  handleState c dist (Request (F m) k) = Request (F (dist (m <$ c))) (dist . fmap k)

The problem is that distributing the handler through the m v action results in m (c v), and since the effect constrains its result type to be the same as the embedded action’s result type and both to be the same as the type index, the effect that gets constructed is of type F (c v) m (c v), and not the expected F v m (c v).