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

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

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

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

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

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

return (doSomething() + doSomethingElse());

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

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

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

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

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

Ответ 1

Эта проблема сверхсеансифицирующего кода монады известна как "проблема коммутативных монадов" .

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

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).

Ответ 2

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

{-# 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, так как мы действительно полагаемся на призрачное действие на расстоянии, доступном через messing с токеном RealWorld. Чтобы получить правильное поведение, нам понадобится аннотация для оптимизатора, который показал, что мы были в порядке с недетерминированным выбором между двумя неэквивалентными альтернативами.

Ответ 3

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

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

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

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

Боковое примечание: не путайте Haskell return как нечто вроде C return