Step-wise interpretation w/ continuations

2020-05-02 09:43:25

Hi there! I have a scenario where I want to decompose a Sem computation the following way:

Sem (MyEff ': r) a -> Sem r (MyEff m b, b -> Either a (Sem (MyEff ': r) a))

(As there might be r effects before MyEff)
in order to handle the effect step-wise.

My use case is having a bunch of these effectful programs in a collection, and moving them forward together whenever I have a b available.

How would I go about doing this with Polysemy?

Love Waern (King of the Homeless)

2020-05-10 20:29:32

Short answer: you can't do this in a safe way. This is one of the flaws inherent to the Effect Handlers In Scope approach (what I call "the weave abstraction") that polysemy is based upon. The same reason is why polysemy doesn't have a Coroutine effect, and why the continuation effects in polysemy-zoo have very restrictive interpreters.
However, the unsafe interaction is specifically that if you try to do this, higher-order actions of effects after MyEff get messed up (the ones that have already been interpreted are fine). So if you, say, have no higher-order effects of interest, you can do this.
The implementation would be messy and ugly and convoluted. But if you really want it, I can cook it up.

Love Waern (King of the Homeless)

2020-05-10 21:26:55

Figured "what the hell" and made it anyway:

import Polysemy

-- For evil internal magic
import Polysemy.Internal
import Polysemy.Internal.Union

-- From the 'free' package
import Control.Monad.Free
import Control.Monad.Free.Church


-- Boilerplate
cataSem :: (a -> b) -> (Union r (Sem r) b -> b) -> Sem r a -> b
cataSem b c sem = runF (runSem sem liftF) b c

stackify :: Sem r a -> Free (Union r (Sem r)) a
stackify = cataSem Pure Free

unstackify :: Free (Union r (Sem r)) a -> Sem r a
unstackify fm = Sem $ \k -> foldFree k fm

bomb :: a
bomb = error "step/s: Don't use any higher-order effects that are further down the \
                    \ effect stack than the effect you step through!"

-- Here's what you're interested in
data Steps e m a where
  Done :: a -> Steps e m a
  More :: e z a -> (a -> m (Steps e m b)) -> Steps e m b

data Step e m a where
  Floor :: a -> Step e m a
  Step  :: e z x -> (x -> m a) -> Step e m a

steps :: Sem (e ': r) a -> Sem r (Steps e (Sem r) a)
steps = cataSem (pure . Done) $ \u -> case decomp u of
  Right (Weaving e s _ ex _) -> pure (More e (ex . (<$ s)))
  Left g -> join $ liftSem $ hoist bomb g


step :: Sem (e ': r) a -> Sem r (Step e (Sem (e ': r)) a)
step = go . stackify
  where
    go (Pure a) = pure (Floor a)
    go (Free u) = case decomp u of
      Right (Weaving e s _ ex _) -> pure (Step e (unstackify . ex . (<$ s)))
      Left g -> liftSem (hoist bomb g) >>= go

Maybe it's worth adding to polysemy-zoo but that's a pretty big maybe seeing how unsafe it is. Also it's heavily dependant on Sem's internal representation as a free monad.

Step-wise interpretation w/ continuations - Polysemy