Qual é o padrão "Mônada Livre + Intérprete"?

Já vi pessoas conversando sobre o Free Monad com o Intérprete , particularmente no contexto de acesso a dados. Qual é esse padrão? Quando posso querer usá-lo? Como isso funciona e como eu o implementaria?

Entendo (de posts como este ) que se trata de separar o modelo do acesso a dados. Como ele difere do conhecido padrão de Repositório? Eles parecem ter a mesma motivação.

O padrão real é realmente significativamente mais geral do que apenas acesso a dados. É uma maneira leve de criar uma linguagem específica de domínio que fornece um AST e, em seguida, ter um ou mais intérpretes para "executar" o AST da maneira que desejar.

A parte de mônada gratuita é apenas uma maneira prática de obter um AST que você pode montar usando os recursos de mônada padrão da Haskell (como anotações) sem precisar escrever muito código personalizado. Isso também garante que o seu DSL seja comporável : você pode defini-lo em partes e depois juntá-las de maneira estruturada, permitindo tirar proveito das abstrações normais de Haskell, como funções.

O uso de uma mônada livre fornece a estrutura de uma DSL composível; tudo o que você precisa fazer é especificar as peças. Você acabou de escrever um tipo de dados que engloba todas as ações em sua DSL. Essas ações podem estar fazendo qualquer coisa, não apenas o acesso a dados. No entanto, se você especificou todos os seus acessos de dados como ações, obteria um AST que especifica todas as consultas e comandos para o armazenamento de dados. Você pode interpretar isso da maneira que desejar: executá-lo em um banco de dados ativo, em um simulador, basta registrar os comandos para depuração ou até tentar otimizar as consultas.

Vamos ver um exemplo muito simples para, digamos, um armazenamento de valores-chave. Por enquanto, trataremos apenas chaves e valores como strings, mas você pode adicionar tipos com um pouco de esforço.

data DSL next = Get String (String -> next)
              | Set String String next
              | End

O nextparâmetro permite combinar ações. Podemos usar isso para escrever um programa que obtém "foo" e define "bar" com esse valor:

p1 = Get "foo" $ \ foo -> Set "bar" foo End

Infelizmente, isso não é suficiente para uma DSL significativa. Como usamos nexta composição, o tipo de p1é o mesmo tamanho do nosso programa (ou seja, 3 comandos):

p1 :: DSL (DSL (DSL next))

Neste exemplo em particular, usar nextesse recurso parece um pouco estranho, mas é importante se queremos que nossas ações tenham variáveis ​​de tipo diferentes. Podemos querer um digitado gete set, por exemplo.

Observe como o nextcampo é diferente para cada ação. Isso sugere que podemos usá-lo para criar DSLum functor:

instance Functor DSL where
  fmap f (Get name k)          = Get name (f . k)
  fmap f (Set name value next) = Set name value (f next)
  fmap f End                   = End

De fato, esta é a única maneira válida de torná-lo um Functor, para que possamos derivingcriar a instância automaticamente, ativando a DeriveFunctorextensão.

O próximo passo é o Freepróprio tipo. É isso que usamos para representar nossa estrutura AST , construída sobre o DSLtipo. Você pode pensar nisso como uma lista no nível de tipo , onde "contras" está apenas aninhando um functor como DSL:

-- compare the two types:
data Free f a = Free (f (Free f a)) | Return a
data List a   = Cons a (List a)     | Nil

Portanto, podemos usar Free DSL nextpara fornecer programas de tamanhos diferentes dos mesmos tipos:

p2 = Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))

Qual tem o tipo mais agradável:

p2 :: Free DSL a

No entanto, a expressão real com todos os seus construtores ainda é muito difícil de usar! É aqui que entra a parte da mônada. Como o nome "mônada livre" implica, Freeé uma mônada - desde que f(neste caso DSL) seja um functor:

instance Functor f => Monad (Free f) where
  return         = Return
  Free a >>= f   = Free (fmap (>>= f) a)
  Return a >>= f = f a

Agora estamos chegando a algum lugar: podemos usar a donotação para tornar nossas expressões DSL mais agradáveis. A única questão é o que colocar next? Bem, a ideia é usar a Freeestrutura para composição, então vamos colocar Returnpara cada próximo campo e deixar a notação fazer todo o encanamento:

p3 = do foo <- Free (Get "foo" Return)
        Free (Set "bar" foo (Return ()))
        Free End

Isso é melhor, mas ainda é um pouco estranho. Temos Freee em Returntodo o lugar. Felizmente, há um padrão que pode explorar: a nossa forma de "levantar" uma ação de DSL em Freeé sempre o mesmo que envolvê-la em Freee aplicar Returnpara next:

liftFree :: Functor f => f a -> Free f a
liftFree action = Free (fmap Return action)

Agora, usando isso, podemos escrever boas versões de cada um de nossos comandos e ter uma DSL completa:

get key       = liftFree (Get key id)
set key value = liftFree (Set key value ())
end           = liftFree End

Usando isso, veja como podemos escrever nosso programa:

p4 :: Free DSL a
p4 = do foo <- get "foo"
        set "bar" foo
        end

O truque é que, embora p4pareça um pequeno programa imperativo, na verdade é uma expressão que tem o valor

Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))

Portanto, a parte de mônada livre do padrão nos deu uma DSL que produz árvores de sintaxe com boa sintaxe. Também podemos escrever subárvores compostáveis ​​não usando End; por exemplo, poderíamos ter o followque pega uma chave, obtém seu valor e depois a usa como uma chave:

follow :: String -> Free DSL String
follow key = do key' <- get key
                get key'

Agora followpode ser usado em nossos programas como getou set:

p5 = do foo <- follow "foo"
        set "bar" foo
        end

Portanto, também obtemos uma boa composição e abstração para nossa DSL.

Agora que temos uma árvore, chegamos à segunda metade do padrão: o intérprete. Podemos interpretar a árvore da maneira que desejamos, combinando-a com ela. Isso nos permitiria escrever código em um armazenamento de dados real IO, além de outras coisas. Aqui está um exemplo em relação a um armazenamento de dados hipotético:

runIO :: Free DSL a -> IO ()
runIO (Free (Get key k)) =
  do res <- getKey key
     runIO $ k res
runIO (Free (Set key value next)) =
  do setKey key value
     runIO next
runIO (Free End) = close
runIO (Return _) = return ()

É um prazer avaliar qualquer DSLfragmento, mesmo que não tenha terminado end. Felizmente, podemos criar uma versão "segura" da função que aceita apenas programas fechados end, definindo a assinatura do tipo de entrada como (forall a. Free DSL a) -> IO (). Enquanto o velho assinatura aceita um Free DSL apara qualquer a (como Free DSL String, Free DSL Inte assim por diante), esta versão só aceita um Free DSL aque funcione para todos os possíveis a-que só podemos criar com end. Isso garante que não esqueceremos de fechar a conexão quando terminarmos.

safeRunIO :: (forall a. Free DSL a) -> IO ()
safeRunIO = runIO

(Não podemos simplesmente dar runIOesse tipo porque ele não funcionará corretamente para nossa chamada recursiva. No entanto, poderíamos mover a definição de runIOpara um wherebloco safeRunIOe obter o mesmo efeito sem expor as duas versões da função.)

Executar nosso código IOnão é a única coisa que poderíamos fazer. Para teste, podemos querer executá-lo contra um puro State Map. Escrever esse código é um bom exercício.

Portanto, este é o padrão monad + intérprete gratuito. Fazemos uma DSL, aproveitando a estrutura de mônada livre para fazer todo o encanamento. Podemos usar a notação de doação e as funções padrão da mônada com nossa DSL. Então, para realmente usá-lo, temos que interpretá-lo de alguma forma; como a árvore é apenas uma estrutura de dados, podemos interpretá-la como quisermos para propósitos diferentes.

Quando usamos isso para gerenciar acessos a um armazenamento de dados externo, ele é realmente semelhante ao padrão do Repositório. Intermedia entre nosso armazenamento de dados e nosso código, separando os dois. De certa forma, porém, é mais específico: o "repositório" é sempre uma DSL com um AST explícito que podemos usar como quisermos.

No entanto, o próprio padrão é mais geral que isso. Pode ser usado para muitas coisas que não envolvem necessariamente bancos de dados ou armazenamento externos. Faz sentido onde você deseja um controle fino dos efeitos ou de vários alvos para uma DSL.

Uma mônada livre é basicamente uma mônada que cria uma estrutura de dados na mesma "forma" que a computação, em vez de fazer algo mais complicado. ( Existem exemplos a serem encontrados online. ) Essa estrutura de dados é passada para um pedaço de código que a consome e realiza as operações. * Não estou totalmente familiarizado com o padrão do repositório, mas pelo que li , parece que para ser uma arquitetura de nível superior, e um intérprete monad + gratuito pode ser usado para implementá-la. Por outro lado, o intérprete monad + gratuito também pode ser usado para implementar coisas totalmente diferentes, como analisadores.

* Vale a pena notar que esse padrão não é exclusivo das mônadas e, de fato, pode produzir um código mais eficiente com aplicativos gratuitos ou setas livres . ( Analisadores são outro exemplo disso. )