Разница между государством, ST, IORef и MVar

Я работаю через Напишите себе схему за 48 часов (я до примерно 85 часов), и я получил часть о Добавление переменных и присвоений. В этой главе есть большой концептуальный прыжок, и я бы хотел, чтобы это было сделано в два этапа с хорошим рефакторингом между ними, а не с прямым выходом к окончательному решению. В любом случае...

Я потерялся с несколькими разными классами, которые, похоже, выполняют одну и ту же цель: State, ST, IORef и MVar. Первые три упоминаются в тексте, в то время как последний, по-видимому, является предпочтительным ответом на многие вопросы StackOverflow о первых трех. Кажется, что все они несут состояние между последовательными вызовами.

Каковы каждый из них и как они отличаются друг от друга?

В частности, эти предложения не имеют смысла:

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

Модуль IORef позволяет использовать переменные состояния внутри монады IO.

Все это делает строку type ENV = IORef [(String, IORef LispVal)] запутанной - почему вторая IORef? Что сломается, если я напишу type ENV = State [(String, LispVal)] вместо этого?

Ответ 1

Государственная Монада: модель изменчивого состояния

Государственная монада - это чисто функциональная среда для программ с состоянием, с простым API:

получить
поместить

Документация в пакете mtl.

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

Монастыня ST и STRefs

Монада ST является ограниченным кузеном монады IO.

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

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

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

Первичный API:

Control.Monad.ST
runST - запуск нового вычисления эффекта памяти.
И STRefs: указатели на (локальные) изменяемые ячейки.
Также широко распространены массивы на основе ST (такие как вектор).

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

IORef: STRIF в IO

Это STREF (см. выше) в монаде IO. Они не имеют одинаковых гарантий безопасности, таких как STRef о локальности.

MVars: IORef с блокировками

Подобно STRefs или IORefs, но с прикрепленной блокировкой для безопасного одновременного доступа из нескольких потоков. IORefs и STRef безопасны только при многопоточной настройке при использовании atomicModifyIORef (операция сравнения и замены). MVars - более общий механизм безопасного обмена изменяемым состоянием.

Как правило, в Haskell используйте MVars или TVars (изменяемые ячейки STM), поверх STRef или IORef.

Ответ 2

Хорошо, я начну с IORef. IORef предоставляет значение, изменяемое в монаде IO. Это просто ссылка на некоторые данные, и, как и любая ссылка, есть функции, которые позволяют вам изменять данные, на которые она ссылается. В Haskell все эти функции работают в IO. Вы можете думать об этом как о базе данных, файле или другом внешнем хранилище данных - вы можете получить и установить в нем данные, но для этого требуется пройти через IO. Причина IO необходима вообще, потому что Haskell чистый; компилятору нужен способ узнать, на какие данные указывает ссылка в любой момент времени (прочитайте sigfpe "Вы могли придумать монад" blogpost).

MVar - это в основном то же самое, что и IORef, за исключением двух очень важных отличий. MVar является примитивом concurrency, поэтому он предназначен для доступа из нескольких потоков. Второе отличие состоит в том, что MVar - это поле, которое может быть полным или пустым. Поэтому, когда IORef Int всегда имеет Int (или внизу), MVar Int может иметь Int, или он может быть пустым. Если поток пытается прочитать значение из пустого MVar, он будет блокироваться до тех пор, пока MVar не будет заполнен (другим потоком). В принципе, MVar a эквивалентен IORef (Maybe a) с дополнительной семантикой, которые полезны для concurrency.

State является монадой, которая обеспечивает изменяемое состояние, не обязательно с IO. Фактически, это особенно полезно для чистых вычислений. Если у вас есть алгоритм, который использует состояние, но не IO, монада State часто является изящным решением.

Существует также версия трансформатора монады, StateT. Это часто используется для хранения данных конфигурации программы или состояний состояния "игровой мир" в приложениях.

ST немного отличается. Основной структурой данных в ST является STRef, которая похожа на IORef, но с другой монадой. Монада ST использует обман системы типов ( "потоки состояний", упомянутые в документах), чтобы гарантировать, что изменчивые данные не смогут избежать монады; то есть, когда вы запускаете ST-вычисление, вы получаете чистый результат. Причина ST интересна в том, что это примитивная монада, например IO, позволяющая вычислениям выполнять низкоуровневые манипуляции на байтах и указателях. Это означает, что ST может обеспечить чистый интерфейс при использовании операций низкого уровня на изменяемых данных, что очень быстро. С точки зрения программы, как будто вычисление ST выполняется в отдельном потоке с локальным хранилищем потоков.

Ответ 3

Другие сделали основные вещи, но чтобы ответить на прямой вопрос:

Все это делает тип линии ENV = IORef [(String, IORef LispVal)]сбивает с толку. Почему второй IORef? Какие сломается, если я сделаю type ENV = State [(String, LispVal)] вместо?

Lisp - это функциональный язык с изменяемым состоянием и лексической областью. Представьте, что вы закрыли переменную. Теперь у вас есть ссылка на эту переменную, зависающую внутри какой-либо другой функции - скажем (в псевдокоде в стиле хэскелл) (printIt, setIt) = let x = 5 in (\ () -> print x, \y -> set x y). Теперь у вас есть две функции: одна печатает x и устанавливает ее значение. Когда вы оцениваете printIt, вы хотите найти имя x в начальной среде, в которой был определен printIt, но вы хотите найти значение, с которым связано имя, в среде, в которой вызывается printIt ( после setIt можно было назвать любое количество раз).

Для этого существуют способы, позволяющие использовать два IORef, но вам, безусловно, нужно больше, чем предлагаемый вами последний тип, который не позволяет вам изменять значения, имена которых связаны в лексическом режиме. Google "проблема с эффектами" для целой серии интересных предысторий.