如何使用纯变量制作 Koen Claessen 的并发 monad？

Question

已知如何基于 ContT 制作纯并发 monad，基于 Koen Claessen 的功能珍珠：

data Action m where
  Atom :: m (Action m) -> Action m
  Fork :: [Action m] -> Action m
  Stop :: Action m

fork :: Applicative m => [ContT (Action m) m a] -> ContT (Action m) m ()
fork processes = ContT $ \next -> Fork <$> sequenceA (next () : [ process $ const $ pure $ Const | ContT process <- processes ])

我将如何实现像 IORefs 或 MVars 这样的共享变量？或者至少是 async/await 机制？如果传递的数据类型是多态的，则加分。

Answer 1

我假设“实现像 IORefs 或 MVars 这样的共享变量”，你的意思是 other 而不是仅仅拥有底层 monad m 包括 IO 并使用 IORef/MVar。很简单，像这样：

newVar :: a -> ContT (Action IO) IO (IORef a)
newVar x = ContT $ \ k -> Atom $ do
  v <- newIORef x
  pure $ k v

将可变变量添加到“穷人的并发 monad”纯粹的一种常规方法是通过向 Action 类型添加额外的操作来创建、读取和编写可变变量。假设我们有一些类型 Var m a 标识可以在 m.

中创建和访问的 a 类型的可变变量

data Action m where
  Atom :: m (Action m) -> Action m
  Fork :: [Action m] -> Action m
  Stop :: Action m

  New   :: (Var m a -> Action m) -> Action m
  Read  :: Var m a -> (a -> Action m) -> Action m
  Write :: Var m a -> a -> Action m -> Action m

请注意，类型参数 a 不会出现在这些新构造函数的结果类型中，因此它是存在量化的，因此变量可以包含任何类型的值。 New 是一个以新变量作为参数继续另一个动作的动作； Read，给定一个变量，以该变量的值继续下一个动作； Write，给定一个变量和一个新值，在继续之前将值写入变量。

像 fork 一样，这些将由在 ContT (Action m) m 中产生动作的辅助函数构造：

newVar
  :: (Applicative m)
  => ContT (Action m) m (Var m a)
newVar = ContT $ \ k -> pure (New (Atom . k))

readVar
  :: (Applicative m)
  => Var m a -> ContT (Action m) m a
readVar v = ContT $ \ k -> pure (Read v (Atom . k))

writeVar
  :: (Applicative m)
  => Var m a -> a -> ContT (Action m) m ()
writeVar v x = ContT $ \ k -> pure (Write v x (Atom (k ())))

之后，您只需决定 Var 的合适表示即可。一种方法是数据族，这使得在 IO 可用时使用 IORef/MVar 变得相对容易，而其他类似 Int 索引到 IntMap 否则。

data family Var (m :: Type -> Type) (a :: Type) :: Type

data instance Var IO a = IOVar { unIOVar :: !(MVar a) }

当然这只是草图；在 monad-par package, whose design is described in A Monad for Deterministic Parallelism（Marlow、Newton 和 Peyton Jones 2011）中可以找到更充实的实现；它的 Par monad 基本上是围绕这样一个动作类型的延续 monad，它的 IVar 抽象实现与此类似，有一些额外的约束，比如额外的严格性来强制确定性并允许纯粹执行内部不纯的代码（一个 IVar 秘密包装一个 IORef）。

如何使用纯变量制作 Koen Claessen 的并发 monad？

How to make Koen Claessen's concurrency monad with pure variables?

monads

concurrency

haskell

continuation-passing