Релаксные упорядоченные ограничения в монадических вычислениях - PullRequest
Новая
       74

Релаксные упорядоченные ограничения в монадических вычислениях

24 голосов
/ 05 мая 2011

вот пища для размышлений.

Когда я пишу монадический код, монада налагает упорядоченность на выполненные операции.Например, если я напишу в монаде ввода-вывода: 

do a <- doSomething
   b <- doSomethingElse
   return (a + b)

Я знаю, doSomething будет выполнено раньше doSomethingElse.

Теперь рассмотрим эквивалентный код на языке, подобном C: 

return (doSomething() + doSomethingElse());

Семантика C не определяет, в каком порядке будут оцениваться эти два вызова функций, поэтому компилятор может свободно перемещать объекты по своему усмотрению.

Мой вопросэто: Как бы я написал монадический код на Haskell, который также оставляет этот порядок оценки неопределенным? В идеале, я бы получил некоторые преимущества, когда оптимизатор моего компилятора смотрит на код и начинает что-то менять.

Вот несколько возможных техник, которые не справляются с работой, но в правильном «духе»:

  • Напишите код в стиле функториала , то естьнапишите plus doSomething doSomethingElse и позвольте plus запланировать монадические вызовы.Недостатки: вы теряете совместное использование результатов монадических действий, и plus все еще принимает решение о том, когда все закончится, оценивая.
  • Используйте lazy IO , то есть unsafeInterleaveIO, который откладывает планирование к требованиям ленивых оценки.Но lazy отличается от строгого с неопределенным порядком: в частности, я хочу, чтобы все мои монадические действия выполнялись.
  • Lazy IO в сочетании с немедленной последовательностью всех аргументов.В частности, seq не накладывает ограничений на порядок.

В этом смысле я хочу что-то более гибкое, чем монадическое упорядочение, но менее гибкое, чем полная лень.

Ответы [ 3 ]

16 голосов
/ 05 мая 2011

Эта проблема чрезмерной секвенизации кода монады известна как "проблема коммутативных монад" .

Коммутативные монады - это монады, для которых порядок действий не имеет значения (они коммутируют), то есть когда следующий код: 

do a <- f x
   b <- g y
   m a b

совпадает с: 

do b <- g y
   a <- f x
   m a b

есть много монад, которые коммутируют (например, Maybe, Random).Если монада коммутативна, то операции, захваченные в ней, могут быть вычислены, например, параллельно.Они очень полезны!

Однако у нас нет хорошего синтаксиса для монад, которые коммутируют , хотя многие люди спрашивают о такой вещи -- это все еще открытая исследовательская задача .

Помимо этого, аппликативные функторы действительно дают нам такую ​​свободу для переупорядочения вычислений, однако вы должны отказаться от понятия bind(в качестве предложений, например, liftM2 show).

9 голосов
/ 05 мая 2011

Это очень грязный хак, но, похоже, мне это нужно. 

{-# OPTIONS_GHC -fglasgow-exts #-}
{-# LANGUAGE MagicHash #-}
module Unorder where
import GHC.Types

unorder :: IO a -> IO b -> IO (a, b)
unorder (IO f) (IO g) = IO $ \rw# ->
           let (# _, x #) = f rw#
               (# _, y #) = g rw#
           in (# rw# , (x,y) #)

Поскольку это дает недетерминированность в руки компилятора, он должен вести себя "правильно" (т.е. недетерминированно) в отношении проблем управления потоком (то есть исключений).

С другой стороны, мы не можем использовать тот же трюк, что и большинство стандартных монад, таких как State и Either a, так как мы действительно полагаемся на жуткое действие на расстоянии, которое можно получить, связавшись с токеном RealWorld. Чтобы получить правильное поведение, нам понадобится некоторая аннотация, доступная оптимизатору, которая будет указывать, что мы согласны с недетерминированным выбором между двумя неэквивалентными альтернативами.

3 голосов
/ 05 мая 2011

Семантика C фактически не определяет порядок, в котором будут оцениваться эти два вызова функций, поэтому компилятор может свободно перемещать объекты по своему усмотрению.

Но что, если doSomething() вызывает побочный эффект, который изменит поведение doSomethingElse()? Вы действительно хотите, чтобы компилятор связывался с порядком? (Подсказка: нет) Тот факт, что вы находитесь в монаде, предполагает, что это может иметь место. Ваше замечание о том, что «вы теряете совместное использование результатов», также предполагает это.

Однако обратите внимание, что monadic не всегда означает секвенированный. Это не совсем то, что вы описываете, но вас может заинтересовать Par monad , которая позволяет вам выполнять ваши действия параллельно.

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

Примечание: не путайте return на Haskell с чем-то вроде C return

...