Как сделать монаду параллелизма Коэна Клаессена с чистыми переменными?

Известно, как создать монаду чистого параллелизма на основе _ 1_, основанный на функциональной жемчужине Коена Клаессена:

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? Бонусные баллы, если он полиморфен по типу передаваемых данных.


concurrency haskell monads continuation-passing
person Turion    schedule 03.02.2021    source источник
comment
В зависимости от того, какой тип чистой воды вам нужен, будет ли достаточно использовать _ 1_ в качестве базовой монады? Тогда вы могли бы по крайней мере устранить до чистой ценности, не полагаясь на темные искусства.   -  person luqui    schedule 04.02.2021
comment
@luqui Я хочу сохранить параметрическую базовую монаду, но, возможно, есть некоторые основные ограничения на базовую монаду, которые можно было бы сделать.   -  person Turion    schedule 04.02.2021

Ответы (1)


arrow_upward
5
arrow_downward

Я предполагаю, что под «реализацией общих переменных, таких как IORefs или MVars» вы имеете в виду другое, чем просто наличие базовой монады m, включающей IO и использование _5 _ / _ 6_. Это просто, примерно так:

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

Обычный способ добавления изменяемых переменных к «монаде параллелизма для бедняков» чисто - это добавление дополнительных действий к типу 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. Один метод - это семейство данных, которое позволяет относительно легко использовать _21 _ / _ 22_, когда доступно IO, и что-то еще, например, Int индекс в IntMap в противном случае.

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

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

Конечно, это всего лишь набросок; гораздо более конкретную реализацию можно найти в _ 27_, конструкция которого описана в Монаде для Детерминированный параллелизм (Марлоу, Ньютон и Пейтон Джонс, 2011 г.); его Par монада - это, по сути, монада продолжения вокруг типа действия, подобного этому, и ее IVar абстракция реализована аналогично этому, с некоторыми дополнительными ограничениями, такими как дополнительная строгость для обеспечения детерминизма и разрешения чистого выполнения внутренне нечистого кода (IVar тайно обертывает IORef ).

person Jon Purdy    schedule 03.02.2021
comment
что-то еще, например индекс Int в IntMap в противном случае. Полагаю, эта карта должна находиться в состоянии в m? - person Turion; 04.02.2021
comment
Я полагаю, что некоторые из ваших конструкций отсутствуют fmap или return, чтобы поднять внутренние вычисления в ContT на m. - person Turion; 04.02.2021
comment
Я ожидал, что шаблон async / await, приводящий к async :: ContT (Action m) m a -> ContT (Action m) m (Var a) и await :: Var a -> ContT (Action m) m a, будет проще реализовать непосредственно в типе Action m, чем переменные, но я не могу понять. Если у вас есть быстрое представление, мне было бы очень интересно :) в противном случае я мог бы задать дополнительный вопрос. - person Turion; 04.02.2021
comment
@Turion: Спасибо, я думаю, что исправил эти ошибки. Вот что происходит, когда вы не тестируете код! Да, гипотетический IntMap (или _ 2_) решение должно быть где-то в состоянии m. Фактически, IORef хранится в состоянии IO, но, конечно же, это просто среда выполнения Haskell. Не уверен насчет _6 _ / _ 7_, подумаю. monad-par для этого использует IVar: spawn разветвляет задачу и возвращает IVar, а использование get для этого IVar ожидает результата задачи. - person Jon Purdy; 04.02.2021