Diferença entre Estado, ST, IORef e MVar

91

Estou trabalhando em Escreva para você mesmo um esquema em 48 horas (até cerca de 85 horas) e cheguei à parte sobre como adicionar variáveis ​​e atribuições . Há um grande salto conceitual neste capítulo, e eu gostaria que tivesse sido feito em duas etapas, com uma boa refatoração no meio, em vez de pular direto para a solução final. De qualquer forma…

Eu me perdi com um número de diferentes classes que parecem servir o mesmo propósito: State, ST, IORef, eMVar . Os três primeiros são mencionados no texto, enquanto o último parece ser a resposta favorita para muitas perguntas do StackOverflow sobre os três primeiros. Todos eles parecem carregar um estado entre invocações consecutivas.

O que são cada um deles e como eles diferem um do outro?


Em particular, essas frases não fazem sentido:

Em vez disso, usamos um recurso chamado threads de estado , permitindo que Haskell gerencie o estado agregado para nós. Isso nos permite tratar variáveis ​​mutáveis ​​como faríamos em qualquer outra linguagem de programação, usando funções para obter ou definir variáveis.

e

O módulo IORef permite usar variáveis ​​com estado dentro da mônada IO .

Tudo isso torna a linha type ENV = IORef [(String, IORef LispVal)]confusa - por que a segunda IORef? O que vai quebrar se eu escrever em type ENV = State [(String, LispVal)]vez disso?

John F. Miller
fonte

Respostas:

119

A Mônada do Estado: um modelo de estado mutável

A mônada de estado é um ambiente puramente funcional para programas com estado, com uma API simples:

  • obter
  • colocar

Documentação no pacote mtl .

A mônada de estado é comumente usada quando precisa do estado em um único thread de controle. Na verdade, ele não usa o estado mutável em sua implementação. Em vez disso, o programa é parametrizado pelo valor do estado (ou seja, o estado é um parâmetro adicional para todos os cálculos). O estado só parece ser alterado em um único thread (e não pode ser compartilhado entre os threads).

A mônada ST e STRefs

A mônada ST é a prima restrita da mônada IO.

Permite um estado mutável arbitrário , implementado como memória mutável real na máquina. A API torna-se segura em programas sem efeitos colaterais, pois o parâmetro do tipo rank-2 evita que valores que dependem do estado mutável escapem do escopo local.

Assim, permite a mutabilidade controlada em programas puros.

Normalmente usado para matrizes mutáveis ​​e outras estruturas de dados que são mutadas e depois congeladas. Também é muito eficiente, já que o estado mutável é "acelerado por hardware".

API primária:

  • Control.Monad.ST
  • runST - inicia um novo cálculo de efeito de memória.
  • E STRefs : ponteiros para células mutáveis ​​(locais).
  • Matrizes baseadas em ST (como vetor) também são comuns.

Pense nele como o irmão menos perigoso da mônada de IO. Ou IO, onde você só pode ler e escrever na memória.

IORef: STRefs em IO

Estes são STRefs (veja acima) na mônada IO. Eles não têm as mesmas garantias de segurança que os STRefs sobre a localidade.

MVars: IORefs com bloqueios

Como STRefs ou IORefs, mas com um bloqueio anexado, para acesso simultâneo seguro de vários threads. IORefs e STRefs são seguros apenas em uma configuração multi-threaded ao usar atomicModifyIORef(uma operação atômica de comparação e troca). MVars são um mecanismo mais geral para compartilhar com segurança o estado mutável.

Geralmente, em Haskell, use MVars ou TVars (células mutáveis ​​baseadas em STM), sobre STRef ou IORef.

Don Stewart
fonte
3
O que significa M em MVars e T em TVars? Estou supondo "Mutável", "Transacional". Interessante como ST significa State Thread.
CMCDragonkai
10
Por que você diz que MVardeve ser preferido STRef? STRefgarante que apenas um thread pode sofrer mutação (e que nenhum outro tipo de IO pode ocorrer) - certamente isso é melhor se eu não precisar de acesso simultâneo ao estado mutável?
Benjamin Hodgson
@CMCDragonkai Sempre presumi que o M significa mutex, mas não consigo encontrá-lo documentado em lugar nenhum.
Andrew Thaddeus Martin,
37

Ok, vou começar com IORef. IOReffornece um valor que é mutável na mônada IO. É apenas uma referência a alguns dados e, como qualquer referência, existem funções que permitem alterar os dados a que se referem. Em Haskell, todas essas funções operam em IO. Você pode pensar nele como um banco de dados, arquivo ou outro armazenamento de dados externo - você pode obter e definir os dados nele, mas para fazer isso, é necessário passar pelo IO. A razão pela qual IO é necessário é porque Haskell é puro ; o compilador precisa de uma maneira de saber para quais dados a referência aponta a qualquer momento (leia postagem do blog "Você poderia ter inventado mônadas" da sigfpe).

MVars são basicamente a mesma coisa que um IORef, exceto por duas diferenças muito importantes. MVaré uma primitiva de simultaneidade, portanto, foi projetada para acessar vários threads. A segunda diferença é que MVaré uma caixa que pode estar cheia ou vazia. Portanto, onde um IORef Intsempre tem um Int(ou é inferior), um MVar Intpode ter um Intou pode estar vazio. Se um thread tentar ler um valor de um vazio MVar, ele bloqueará até que MVarseja preenchido (por outro thread). Basicamente, um MVar aé equivalente a umIORef (Maybe a) com semântica extra que é útil para simultaneidade.

Stateé uma mônada que fornece estado mutável, não necessariamente com IO. Na verdade, é particularmente útil para cálculos puros. Se você tiver um algoritmo que usa estado, mas não IO, umState mônada costuma ser uma solução elegante.

Há também uma versão do transformador de mônada do Estado StateT,. Freqüentemente, é usado para armazenar dados de configuração de programa ou tipos de estado de "estado do mundo do jogo" em aplicativos.

STé algo ligeiramente diferente. A principal estrutura de dados em STé o STRef, que é como um, IORefmas com uma mônada diferente. A STmônada usa truques do sistema de tipo (os "threads de estado" que os documentos mencionam) para garantir que os dados mutáveis ​​não escapem da mônada; ou seja, quando você executa um cálculo de ST, obtém um resultado puro. O motivo pelo qual ST é interessante é que ele é uma mônada primitiva como IO, permitindo cálculos para realizar manipulações de baixo nível em bytearrays e ponteiros. Isso significa que STpode fornecer uma interface pura enquanto usa operações de baixo nível em dados mutáveis, o que significa que é muito rápido. Da perspectiva do programa, é como se o STcálculo fosse executado em um thread separado com armazenamento local do thread.

John L
fonte
17

Outros fizeram as coisas essenciais, mas para responder à pergunta direta:

Tudo isso torna o tipo de linha ENV = IORef [(String, IORef LispVal)] confuso. Por que o segundo IORef? O que vai quebrar se eu fizer isso type ENV = State [(String, LispVal)]?

Lisp é uma linguagem funcional com estado mutável e escopo lexical. Imagine que você fechou em uma variável mutável. Agora você tem uma referência a essa variável dentro de alguma outra função - digamos (em pseudocódigo no estilo haskell) (printIt, setIt) = let x = 5 in (\ () -> print x, \y -> set x y). Agora você tem duas funções - uma imprime xe outra define seu valor. Ao avaliar printIt, você deseja pesquisar o nome de x no ambiente inicial em que printItfoi definido, mas deseja pesquisar o valor ao qual o nome está vinculado no ambiente em que printIté chamado (apóssetIt pode ter sido chamado várias vezes )

Existem maneiras além dos dois IORefs de fazer isso, mas você certamente precisa de mais do que o último tipo que você propôs, o que não permite alterar os valores aos quais os nomes estão vinculados de uma forma com escopo léxico. Pesquise no Google o "problema do funargs" para obter uma porção de pré-história interessante.

sclv
fonte