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

Question

众所周知，如何ContT基于 Koen Claessen 的功能性明珠基于 制作纯并发 monad ：

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这样的共享变量？或者至少有一个异步/等待机制？如果它在传递的数据类型中是多态的，则加分。

Answer 1

我认为是“实现诸如共享变量IORefs或MVars”你在某种程度上意味着其他不仅仅具有潜在的单子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来标识a可以在m.

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。一种方法是数据族，这使得它相对容易使用IORef/MVar何时IO可用，以及其他类似的Int索引IntMap。

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

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

当然这只是一个草图；可以在monad-par包中找到更加充实的实现，其设计在A Monad for Deterministic Parallelism (Marlow, Newton, & Peyton Jones 2011) 中有描述；它的Parmonad 基本上是一个围绕这样的动作类型的延续 monad，它的IVar抽象实现方式与此类似，还有一些额外的约束，例如额外的严格性以强制执行确定性并允许纯粹执行内部不纯代码（IVar秘密包装 an IORef）。