Haskell: параллельные вычисления и «последовательное свойство» монад

Меня смущает, почему функция REPA computeP упаковывает свой результат в монаду. Он имеет следующую сигнатуру типа.

computeP :: (Load r1 sh e, Target r2 e, Source r2 e, Monad m) =>
            Array r1 sh e -> m (Array r2 sh e)

В этом руководстве говорится

Причина этого в том, что монады дают четко определенное понятие последовательности и, таким образом, calculateP обеспечивает завершение параллельного вычисления в определенной точке монадических вычислений.

Аналогичным образом, этот ответ о переполнении стека гласит, что

Причина, по которой параллельные вычисления в Repa должны быть монадическими, частично связана с ленью, но в основном с неспособностью Repa работать с вложенным параллелизмом. Последовательное свойство монады решает эту проблему по большей части[.]

Вопросы

  • Что именно означает наличие этого «последовательного свойства»?
  • Как монада обеспечивает это?

  • Для примера computeP: нет ограничений на используемую монаду, поэтому я мог бы использовать монаду идентичности. Можно ли тогда вместо этого использовать следующую функцию, которая просто распаковывает монаду, или это даст неожиданные результаты, поскольку в ней отсутствует это последовательное свойство? Если все в порядке, есть ли вообще необходимость использовать монаду?

    import Data.Functor.Identity
import Data.Array.Repa.Eval
import Data.Array.Repa

myComputeP :: (Load r1 sh e, Target r2 e, Source r2 e) => Array r1 sh e -> Array r2 sh e
myComputeP = runIdentity . computeP

Любая помощь будет здорово.


haskell monads repa
person Safron    schedule 03.01.2020    source источник
comment
Вы должны сосредоточиться на одном вопросе за раз.   -  person Michael Litchard    schedule 04.01.2020
comment
@MichaelLitchard Я предполагаю, что вы имеете в виду оба вопроса What does having this 'sequential property' mean и why does computeP pack its result in a monad. Последнее на самом деле подразумевается как пример первого: я предполагаю, что calculateP использует монаду из-за этого свойства последовательности, но я хотел бы получить некоторые разъяснения о том, как именно работает это свойство последовательности. Это то, что ты имеешь в виду? Если вы можете уточнить, я был бы более чем готов уточнить вопрос или разделить его на несколько вопросов.   -  person Safron    schedule 04.01.2020
comment
На самом деле это будет работать для любой монады / монады сбивают с толку бит hellppp, который, кажется, отклоняется от темы, по крайней мере, для меня. Но я также думаю, что это достойный вопрос, и три подвопроса довольно хорошо передают то, что вы хотите понять.   -  person luqui    schedule 04.01.2020
comment
@luqui Хорошо, я понимаю, что ты имеешь в виду. Миру не нужны еще монады, которые сбивают с толку вопрос hellppp, и я не собирался позволять ему выглядеть так. Думаю, я надеялся найти ответ, объясняющий эту последовательную вещь, используя мою собственную интуицию в качестве отправной точки, но он может отклоняться от реального вопроса. Я удалю последнюю часть моего вопроса.   -  person Safron    schedule 04.01.2020
comment
Для воли это работает для любой части монады: здесь нужно бросить вызов необходимости монады. Уточню вопрос.   -  person Safron    schedule 04.01.2020
comment
@Safron К вашему сведению, есть massiv, который по духу похож на Repa, но не имеет ограничения от ваш вопрос, так что с вложенным параллелизмом все в порядке.   -  person lehins    schedule 06.01.2020

Ответы (1)


arrow_upward
2
arrow_downward

Это монадное ограничение является эвристическим трюком. Это помогает дисциплинированным пользователям избежать вложенного параллелизма, но ничего не делает против злонамеренных или невежественных пользователей.

Вложенный параллелизм — это ситуация, когда при параллельном вычислении некоторого массива вам приходится параллельно вычислять другой массив. Repa его не поддерживает (причина не важна), поэтому старается его избегать.

Тип computeP помогает гарантировать, что параллельные вычисления выполняются последовательно друг с другом, но он далеко не герметичен; это всего лишь абстракция "наилучшего усилия".

Как монада обеспечивает это?

На самом деле ожидается, что computeP будет работать только с монадами, чье связывание (>>=) является строгим в своем первом аргументе, так что в u >>= k функция k будет применена только после того, как u будет вычислено. Тогда, если вы используете computeP с такой монадой,

do w <- computeP v
   k w

гарантируется, что вектор w оценивается до того, как он будет передан в k, который может безопасно выполнять другие computeP операции.

  • Примеры строгих монад: IO, строгие State, Maybe, [].
  • Примеры ленивых монад: Identity, ленивые State, Reader. (Ленивые монады можно сделать строгими, но не наоборот. В частности, вы можете определить строгую идентификационную монаду, если хотите выполнять только вычисления Repa.)

Чтобы предотвратить вложенный параллелизм, тип computeP намеренно делает его громоздким для использования в операциях, которые, вероятно, будут выполняться параллельно, таких как map :: (a -> b) -> Array _ _ a -> Array _ _ b и fromFunction :: sh -> (sh -> a) -> Array _ _ a, которые принимают немонадические функции. Можно еще явно развернуть computeP, например, с runIdentity, как вы заметили: вы можете выстрелить себе в ногу, если хотите, но вы должны зарядить пистолет, направить его вниз и нажать на спусковой крючок.

Надеюсь, это отвечает на вопрос, что происходит в Repa. Далее следует теоретическое отступление, чтобы ответить на этот другой вопрос:

Что именно означает наличие этого «последовательного свойства»?

Эти цитаты довольно неуклюжи. На мой взгляд, отношение между «последовательностью» и «монадами» двоякое.

Во-первых, для многих монад в Haskell определение (>>=) естественным образом диктует порядок вычисления, обычно потому, что оно сразу же соответствует шаблону в первом аргументе. Как объяснялось ранее, это то, на что Repa полагается, чтобы обеспечить последовательное выполнение computeP вычислений (и именно поэтому он сломается, если вы настроите его на Identity; это не строгая монада). По большому счету, это довольно незначительная деталь ленивых вычислений, а не что-либо, свойственное монадам в целом.

Во-вторых, одной из основных идей чисто функционального программирования являются первоклассные вычисления с явным определением эффектов и композиции. В этом случае эффектом является параллельная оценка векторов, а интересующая нас композиция — это последовательная композиция. Монады обеспечивают общую модель или интерфейс для последовательной композиции. Это еще одна причина, по которой монады помогают решить проблему предотвращения вложенного параллелизма в Repa.

Дело не в том, что монады по своей природе имеют последовательный аспект, а в том, что последовательная композиция по своей сути монадична: если вы попытаетесь перечислить общие свойства, которые вы ожидаете от чего-либо, достойного названия «последовательная композиция», вы, скорее всего, закончите. со свойствами, которые вместе называются «монадой»; это один из пунктов основополагающей статьи Моджи «Понятия вычислений и монад».

«Монады» — это не волшебное понятие, а чрезвычайно общее понятие, так что многие вещи оказываются монадами. Ведь главное требование — наличие ассоциативной операции; это довольно разумное предположение о последовательной композиции. (Если, когда вы слышите «ассоциативность», вы думаете «моноид» или «категория», обратите внимание, что все эти понятия объединены под эгидой «моноидальных объектов», так что, что касается «ассоциативности», они все та же идея, только в разных категориях.)

person Li-yao Xia    schedule 05.01.2020