Разница между State, ST, IORef и MVar - PullRequest
85 голосов
/ 05 апреля 2011

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

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

Что это такое и чем они отличаются друг от друга?


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

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

и

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

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

Ответы [ 3 ]

112 голосов
/ 05 апреля 2011

Монада состояний: модель изменяемого состояния

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

  • get
  • put

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

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

Монада ST и STRefs

Монада ST - ограниченный родственникмонады ввода-вывода.

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

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

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

Основной API:

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

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

IORef: STRefs в IO

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

MVars: IORefs с замками

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

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

36 голосов
/ 05 апреля 2011

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

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

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

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

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

18 голосов
/ 05 апреля 2011

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

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

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

Есть несколько способов, кроме двух IORef, чтобы сделать это, новам, безусловно, нужно больше, чем последний предложенный вами тип, который не позволяет вам изменять значения, с которыми связаны имена, в лексической области видимости.Гугл "проблема funargs" для множества интересных предысторий.

...