Критика монады IO, рассматриваемой как государственная монада, действующая в мире

46

IOМонады в Haskell часто объясняется как государственной монады , где государство является мир. Таким образом, значение типа IO amonad рассматривается как нечто подобное worldState -> (a, worldState).

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

Изменить: статья кажется потерянной, поэтому давайте начнем собирать различные аргументы здесь. Я начинаю вознаграждение, чтобы сделать вещи более интересными.

Редактировать: статья, которую я искал, - « Борьба с неловким составом: монадический ввод / вывод, параллелизм, исключения и вызовы на иностранном языке в Haskell » Саймона Пейтона Джонса. (Благодаря ответу TacTics.)

Петр Пудлак
источник
1
Это эта статья (или эта старая версия )?
Иоахим Зауэр
@JoachimSauer Спасибо, это тоже интересная статья, но это не та, которую я ищу. Тот был сфокусирован на парадигме состояния мира.
Петр Пудлак
Сверху головы, комментарии здесь - хорошее начало
Адам
1
Что означает «мир» в этом контексте? Я предполагаю, что это не означает «Земля». Это какой-то глобальный охват? Автор, который написал это, продает себя коротко. Если он хочет одновременно запутать и сокрушить эго своих читателей, он должен назвать это «Государство - это Вселенная» или «Государство-Бог». Мир. Тьфу! Вы, молодые люди, не стремитесь достаточно высоко в эти дни!
ГленПетерсон

Ответы:

33

Проблема в IO a = worldState -> (a, worldState)том, что если бы это было правдой, то мы могли бы доказать это forever (putStrLn "Hello") :: IO aи undefined :: IO aбыть равными. Вот доказательство любезности dolio (2010, irc):

forever m
 =
m >> forever m
 =
fix (\r -> m >> r)
 = {definition of >> for worldState -> (a, worldState)}
fix (\r -> \w -> r (snd $ m w))

Лемма: (\r w -> r (snd $ m w)) ⊥ = ⊥

(\r w -> r (snd $ m w)) ⊥
  =
\w -> ⊥ (snd $ m w))
  =
⊥ . snd . m
  =
⊥

Следовательно forever m = fix (\r -> \w -> r (snd $ m w)) = ⊥

В частности forever (putStrLn "Hello") = ⊥и, следовательно, forever (putStrLn "Hello")и undefinedэквивалентные программы. Тем не менее, очевидно, что они не должны рассматриваться как эквивалентные программы, в теории или на практике.

Обратите внимание, что эта модель неверна даже без вызова параллелизма.

Рассел О'Коннор
источник
7
Кто-нибудь удивляется, что нетерминирующая программа эквивалентна undefinedчистой семантике Haskell? Предполагается, что разные объекты неразличимы в чистой семантике Хаскелла! Но когда мы оперативно думаем о наших программах, мы хотим различать и разные виды, даже когда они IOне задействованы; Мне важно, выдает ли моя программа исключение или входит в бесконечный цикл, даже если вы можете доказать, что они равны, доказав, что они оба ⊥. На самом деле это не противоречие.
Бен
3
Обозначения ⊥ и [0,1 ..] различны, даже если они оба «не заканчиваются». Разница в том, что ⊥ is обозначает не завершающие и непроизводительные вычисления, в то время как [0,1 ..] не является завершающими, но продуктивными. Мы ожидаем, что (навсегда (putStrLn "Hello")) будет иметь аналогичное неразрывное, но продуктивное обозначение.
Рассел О'Коннор
1
Но forever (putStrLn "Hello")не похоже [0,1..], конечно. Ваше доказательство не является особенным worldState, поэтому оно также относится к обычной государственной монаде. Так forever (someModificationWith "Hello")что также денотально эквивалентно ⊥. Я совершенно не удивлен этим результатом; это не продуктивно в денотационной семантике, и то, что компьютер делает оперативно, пока мы ждем вечно, не имеет значения. То же самое для forever (putStrLn "Hello"); оно не создает и не должно создавать новое мировое состояние, которое мы можем лениво потреблять.
Бен
Являются ли языки программирования, такие как Mercury и Clean, которые используют явную передачу состояния мира, чтобы обеспечить декларативную модель для IO, в корне неверно?
Бен
@Ben вы имеете в виду, как передача по миру работает с параллелизмом? Вы видели код розетты для параллелизма Меркурия? Я задавался вопросом, что это означает семантически тоже.
CMCDragonkai
12

Вот простой ответ: любое изменение состояния государственной монады происходит из-за любых действий, выполняемых в монаде. Если действительно объяснение «WorldState -> (a, WorldState)» требует того же свойства, а WorldState является чистым значением, которое изменяется только монадой ввода-вывода, это неправильно. Время изменяется, содержимое файлов, состояние дескрипторов и т. Д. Могут меняться независимо от того, что происходит в монаде ввода-вывода. В этом смысл монады IO. Тот факт, что GHC передает значение RealWorld (или то, что было), является гарантией того, что все работает по порядку, насколько я знаю, если это (возможно, это просто что-то, что можно ввести в значение ST).

Кристофер Готово
источник
8
это на самом деле не проблема. Вы можете смоделировать операцию связывания как выполнение изменения состояния мира, полученного из некоторого фиксированного, но непознаваемого хранилища правил.
SCLV
1
@sclv: да, но это фиксированное, но непознаваемое хранилище правил является дифференцирующим фактором, который делает IO не государственной монадой, это несоответствие не обнаружено в государственной монаде
Джимми Хоффа
Аргумент, который я слышал против состояния WorldState, связан с параллелизмом, хотя я не могу вспомнить точный аргумент. Но даже несмотря на это, я предполагаю, что WorldState может закодировать и будущее, поэтому я все еще не вижу проблемы. Конечно, я полагаю, что что-то упустил.
Томас Эдинг
@JimmyHoffa: Вы можете носить с собой магазин правил в штате.
SCLV
1
@JimmyHoffa: это цель абстракции. Кроме того, в продолжение моего первоначального комментария, очистите модели ввода-вывода как явные и счастливые передачи мира, используя типы уникальности, чтобы не обманывать и «дублировать» мир. Это один из способов обеспечения абстракции.
SCLV
12

Я написал сообщение в блоге на тему, как смоделировать IO как форму асимметричной сопрограммы, взаимодействующей с системой времени исполнения для вашего языка. (По общему признанию третья часть серии)

http://comonad.com/reader/2011/free-monads-for-less-3/

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

Эдвард КМЕТТ
источник
+1 - особенно интересно, так как я давно планировал реализовать IO языка, который я проектирую, аналогично этому! :)
Жюль
8

См. Борьба с неуклюжим отрядом .

Основная причина в том, что модели состояний монады ввода-вывода RealWorld не работают с параллелизмом. SPJ в этой читаемой классике предпочитает использовать операционную семантику, чтобы понять это.

тактика
источник
Я считаю, что это оригинальная статья, которую я искал, в основном раздел 3.1. Если бы вы опубликовали его до того, как я отредактировал вопрос, я бы принял ваш ответ, но теперь я думаю, что будет более справедливо подождать до конца, чтобы увидеть все идеи, которые будут публиковать другие.
Петр Пудлак
5

Основная претензия к моделям состояния RealWorld заключается в том, что, как говорит TacTics, передача мира не обязательно работает с параллелизмом. Но Вутер Свирстра и Торстен Альтенкирх показали, как рассуждать о параллелизме как о «проходящем мире» эффекте, с фиксированной, но произвольной последовательностью чередующихся потоков в своей статье «Красота в чудовище: функциональная сематика для неуклюжего отряда»: http : //www.staff.science.uu.nl/~swier004/Publications/BeautyInTheBeast.pdf

Код, соответствующий этому, находится на Hackage как IOSpec: http://hackage.haskell.org/package/IOSpec

Я думаю, что тезис Ваутера становится более подробным: http://www.staff.science.uu.nl/~swier004/Publications/Thesis.pdf

sclv
источник