Motivação
Quando comecei a aprender Haskell, fiquei muito irritado com o uso generalizado de abstrações complexas em vez de com soluções específicas. Pareceu-me que é muito melhor sempre seguir o princípio do KISS e escrever bicicletas usando construções de linguagem elementar do que entender todas essas classes de tipos para escrever uma construção supostamente conveniente em algum lugar.
Não tive um bom exemplo de onde os esforços despendidos no desenvolvimento do "material" seriam recompensados. Para mim, um dos exemplos mais bem-sucedidos foi o analisador. Agora, muitas vezes falo sobre eles quando me perguntam quais tarefas comuns você pode usar maravilhosamente o Haskell.
Eu quero oferecer aos iniciantes que também sigam esse caminho e criem uma pequena base de funções a partir do zero para uma implementação conveniente dos analisadores, e depois usem-na para escrever seu próprio analisador, cujo código repetirá literalmente a gramática usada para a análise.
Espero que isso ajude alguém a superar o medo das abstrações e ensiná-las a usá-las adequadamente (sim, ainda acho que às vezes é mais eficiente escrever uma bicicleta).
Não tenho propósito e desejo fazer um curso de Haskell a partir do zero, de modo que assumo que o leitor esteja familiarizado com a sintaxe e com programas simples desenvolvidos de forma independente. Apenas no caso, falarei brevemente sobre classes de tipos antes de passar para a descrição da implementação.
Para aqueles que nunca escreveram para Haskell, mas querem entender o que está acontecendo aqui, recomendo que você olhe primeiro para a página correspondente no Learn X em Y minutos . Como um excelente livro em russo para iniciantes, aconselho "Sobre Haskell como ser humano", de Denis Shevchenko.
Vou tentar usar as construções de linguagem mais simples que os iniciantes possam entender. No final do artigo, é fornecido um link para o repositório de origem, onde em algumas partes do código uma entrada mais conveniente e mais curta é usada, o que pode ser menos claro à primeira vista.
E sim, senhores haskellistas, muitas coisas são explicadas de maneira muito simples e desajeitada, para casos especiais, não muito abstratos, sem usar termos da teoria das categorias e outras palavras assustadoras. Fico feliz que você os conheça e, é claro, eles os dominaram facilmente. Eu também os conheço, mas não acho necessário despejar tanta quantidade de informações nesse contexto em leitores despreparados.
Classes de tipos
Classes do tipo Haskell não têm nada a ver com classes em C ++ e outras linguagens orientadas a objetos. Se traçarmos uma analogia com o OOP, as classes de tipo serão mais como uma sobrecarga de métodos e funções.
As classes determinam quais ações podem ser executadas com objetos dos tipos que compõem a classe. Por exemplo, todos os números podem ser comparados em termos de igualdade, mas tudo pode ser ordenado, exceto os complexos e, em geral, as funções não podem ser comparadas. A classe de tipos que podem ser comparados é chamada Eq , ordenada - Ord (os tipos não precisam ser numéricos). O que pode ser impresso pela conversão em uma string pertence à classe Show , possui a classe Read "oposta", que determina como converter as strings em objetos do tipo desejado.
Para um conjunto de classes de tipo padrão (como Eq , Show , Read ...), você pode solicitar ao compilador que implemente a funcionalidade desejada de maneira padrão, usando a palavra-chave deriving após determinar o tipo:
data Point = Point { xCoord :: Float , yCoord :: Float } deriving (Eq, Show)
Você pode definir suas próprias classes de tipo:
class PrettyPrint a where pPrint :: a -> String
Aqui PrettyPrint é o nome da classe, a é uma variável de tipo. A palavra-chave where é seguida por uma lista dos chamados métodos de classe, ou seja, funções que podem ser aplicadas a objetos de tipo dessa classe.
Para indicar a pertença de um tipo de dados a uma classe, a seguinte construção é usada:
instance PrettyPrint Point where pPrint (Point xy) = "(" ++ show x ++ ", " ++ show y ++ ")"
A linguagem permite especificar restrições nas classes de tipo às quais os argumentos da função devem se relacionar:
showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String) showVsPretty x = (show x, pPrint x)
Para cada chamada de função, o compilador verifica se esses requisitos de tipo são atendidos e, em caso de falha, exibe um erro (é claro, isso acontece no estágio de compilação).
>>> showVsPretty (Point 2 3) ("Point {xCoord = 2.0, yCoord = 3.0}","(2.0, 3.0)") >>> showVsPretty "str" error: No instance for (PrettyPrint [Char]) arising from a use of 'showVsPretty'
Implementação
O analisador recebe uma string de entrada que deve analisar de acordo com regras predefinidas e obter o valor do tipo que precisamos (por exemplo, um número inteiro). Nesse caso, a linha de entrada pode não terminar e o restante servirá como uma entrada para análises adicionais. Além disso, nosso analisador geralmente não é determinístico, ou seja, retornará vários resultados possíveis de análise como uma lista.
Uma tupla de dois elementos (String, a) adequada para descrever um resultado da operação do analisador, em que a é uma variável de tipo que pode denotar qualquer tipo de usuário.
Como o analisador analisa a string de acordo com algumas regras, a descrevemos como uma função que recebe uma string como entrada e retorna uma lista de resultados:
newtype Parser a = Parser { unParser :: String -> [(String, a)] }
Consideraremos a análise bem-sucedida se a lista de resultados consistir em um elemento e a sequência de entrada tiver sido completamente processada. Implementamos uma função auxiliar que tenta analisar exclusivamente a cadeia inteira:
parseString :: String -> Parser a -> Maybe a parseString s (Parser p) = case (ps) of [("", val)] -> Just val _ -> Nothing
Analisadores simples
Implementamos vários analisadores simples, que serão úteis na criação de combinações mais complexas.
Começamos analisando um único caractere que deve satisfazer um predicado. Se a sequência de entrada estiver vazia, o resultado do trabalho será uma lista vazia. Caso contrário, verificamos o valor do predicado no primeiro caractere da string. Se True retornado, o resultado da análise é esse caractere; retorne-o com o restante da string. Caso contrário, a análise também falhará.
predP :: (Char -> Bool) -> Parser Char predP p = Parser f where f "" = [] f (c : cs) | pc = [(cs, c)] | otherwise = []
Agora podemos escrever um analisador que assume um caractere específico no início da linha. Para fazer isso, use o predP recém-escrito e passe como argumento uma função que compara seu argumento com o caractere de que precisamos:
charP :: Char -> Parser Char charP char = predP (\c -> c == char)
O caso mais simples a seguir: um analisador que aceita apenas uma determinada sequência como um todo. stringP chamá-lo de stringP . A função dentro do analisador compara a linha de entrada com a desejada e, se as linhas forem iguais, retorna uma lista de um elemento: um par de linhas vazias (não resta mais nada na entrada) e a original. Caso contrário, a análise falhou e uma lista vazia de resultados será retornada.
stringP :: String -> Parser String stringP s = Parser f where fs' | s == s' = [("", s)] | otherwise = []
Freqüentemente, é necessário pular caracteres que tenham uma determinada propriedade enquanto eles vão para o início da linha (por exemplo, caracteres de espaço em branco). Além disso, o resultado da análise não é importante para nós e não será útil no futuro. Escrevemos uma função de skip que ignora os caracteres iniciais da string enquanto o valor verdadeiro do predicado é preservado. Como resultado da análise, usamos uma tupla vazia.
skip :: (Char -> Bool) -> Parser () skip p = Parser (\s -> [(dropWhile ps, ())])
Os próximos dois analisadores são muito parecidos entre si. Ambos verificam o prefixo da linha de entrada, apenas o primeiro, se bem-sucedido, retorna esse prefixo e o segundo retorna uma tupla vazia, ou seja, permite que você pule uma linha arbitrária no início da entrada. A implementação usa a função isPrefixOf definida no módulo Data.List .
prefixP :: String -> Parser String prefixP s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, s)] else [] skipString :: String -> Parser () skipString s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, ())] else []
Um pouco mais tarde, consideraremos uma implementação mais simples da última função e nos livraremos da duplicação de código.
Analisador como um functor
Podemos distinguir uma classe inteira de tipos de contêiner para os quais o seguinte é verdadeiro: se você souber converter objetos dentro de um contêiner, poderá converter os contêineres. O exemplo mais simples é uma lista como um contêiner e uma função de map , disponível em quase todos os idiomas de alto nível. De fato, você pode passar por todos os elementos de uma lista do tipo [a] , aplicar a -> b função a a -> b a cada um e obter uma lista do tipo [b] .
Essa classe de tipo é chamada Functor ; a classe possui um método fmap :
class Functor f where fmap :: (a -> b) -> fa -> fb
Suponha que já sabemos analisar cadeias de caracteres em objetos de um determinado tipo a e, além disso, sabemos como converter objetos do tipo a em objetos do tipo b . É possível dizer que existe um analisador para objetos do tipo b ?
Se expresso na forma de uma função, terá o seguinte tipo:
(a -> b) -> Parser a -> Parser b
Esse tipo coincide com o tipo da função fmap , então vamos tentar tornar o analisador um functor. Vamos criar um analisador de valores do tipo b do zero, que primeiro chamará o primeiro analisador (já temos um) e, em seguida, aplicamos a função aos resultados de sua análise.
instance Functor Parser where fmap :: (a -> b) -> Parser a -> Parser b fmap f (Parser p1) = Parser p2 where p2 :: String -> [(String, b)] p2 s = convert (p1 s) convert :: [(String, a)] -> [(String, b)] convert results = map (\(s, val) -> (s, f val)) results
A função fmap possui um sinônimo de infixo conveniente: fmap fx == f <$> x .
Se usarmos uma função como argumento para o fmap que simplesmente substitui seu primeiro argumento por um novo valor, obteremos outra operação útil que já está implementada para todos os functores, mesmo em duas instâncias (eles diferem apenas na ordem dos argumentos):
(<$) :: Functor f => a -> fb -> fa ($>) :: Functor f => fa -> b -> fb
Lembra do analisador que pula uma linha específica ( skipString )? Agora você pode implementá-lo da seguinte maneira:
skipString :: String -> Parser () skipString s = () <$ prefixP s
Combinações do analisador
No Haskell, todas as funções são curry por padrão e são parcialmente utilizáveis. Isso significa que uma função de n argumentos é realmente uma função de um argumento, retornando uma função de n-1 argumentos:
cons :: Int -> [Int] -> [Int] cons = (:) cons1 :: [Int] -> [Int] cons1 = cons 1
Aplicamos uma função de três argumentos a algum valor dentro do analisador usando fmap . Os tipos serão os seguintes:
f :: c -> a -> b p :: Parser c (fmap fp) :: Parser (a -> b)
O analisador de funções acabou ?! Obviamente, é possível uma situação em que a representação da função realmente esteja na linha de entrada, mas eu gostaria de poder usar essa função, ou melhor, combinar os Parser (a -> b) e Parser a para obter o Parser b :
applyP :: Parser (a -> b) -> Parser a -> Parser b
O tipo dessa função é muito semelhante ao tipo fmap , apenas a própria função que precisa ser aplicada também está no contêiner. Isso fornece uma compreensão intuitiva de como deve ser a implementação da função applyP : obtenha a função do contêiner (como resultado da aplicação do primeiro analisador), obtenha os valores aos quais a função deve ser aplicada (resultado da aplicação do segundo analisador) e "empacote" os valores convertidos usando essa função de volta no contêiner (crie um novo analisador). Na implementação, usaremos a compreensão da lista:
applyP :: Parser (a -> b) -> Parser a -> Parser b applyP (Parser p1) (Parser p2) = Parser f where fs = [ (sx, fx) | (sf, f) <- p1 s,
Existe uma classe Applicative que possui um método com o mesmo protótipo. O segundo método da classe é chamado pure e é usado para "quebrar" ou "elevar" ( elevar ) um valor, incluindo um funcional. No caso da implementação do analisador, a função pure adiciona seu argumento ao resultado do analisador, sem alterar a sequência de entrada.
class Functor f => Applicative f where pure :: a -> fa (<*>) :: f (a -> b) -> fa -> fb instance Applicative Parser where pure x = Parser (\s -> [(s, x)]) pf <*> px = Parser (\s -> [ (sx, fx) | (sf, f) <- unParser pf $ s, (sx, x) <- unParser px $ sf])
A função applyP é a <*> da classe Applicative . Os tipos pertencentes a essa classe são chamados de functores aplicativos.
Para functores aplicativos, duas funções auxiliares são implementadas que serão úteis para nós:
(*>) :: fa -> fb -> fb (<*) :: fa -> fb -> fa
Essas funções executam duas ações consecutivas e retornam o resultado de apenas uma delas. Para analisadores, eles podem ser usados, por exemplo, para ignorar espaços à esquerda antes de analisar uma parte de uma sequência que carrega uma carga semântica.
Ao combinar <$> e <*> , você pode criar designs muito convenientes. Considere o seguinte tipo de dados:
data MyStructType = MyStruct { field1 :: Type1 , field2 :: Type2 , field3 :: Type3 }
O construtor dos valores MyStruct também é uma função, nesse caso, é do tipo Type1 -> Type2 -> Type3 -> MyStructType . Você pode trabalhar com o construtor, assim como com qualquer outra função. Suponha que os analisadores já tenham sido gravados para os tipos de campos de estrutura:
parser1 :: Parser Type1 parser2 :: Parser Type2 parser3 :: Parser Type3
Usando a função fmap , você pode aplicar parcialmente o MyStruct ao primeiro desses analisadores:
parserStruct' :: Parser (Type2 -> Type3 -> MyStructType) parserStruct' = MyStruct <$> parser1
Vamos tentar aplicar a função que está agora "dentro" do analisador. Para fazer isso, você já precisa usar <*> :
parserStruct'' :: Parser (Type3 -> MyStructType) parserStruct'' = parserStruct' <*> parser2 parserStruct :: Parser MyStructType parserStruct = parserStruct'' <*> parser3
Como resultado, obtivemos um analisador para toda a estrutura (é claro, aqui usamos a suposição de que na linha original as representações de seus campos estão seguidas). O mesmo pode ser feito em uma linha:
parserStruct :: Parser MyStructType parserStruct = MyStruct <$> parser1 <*> parser2 <*> parser3
Tais construções geralmente são encontradas em casos de uso.
Agora, suponha que estamos tentando escrever um analisador que analisa expressões aritméticas simples nas quais números inteiros e identificadores podem estar presentes como operandos. Vamos criar um tipo separado de Operand para eles:
data Operand = IntOp Int | IdentOp String
Se já sabemos analisar inteiros e identificadores (por exemplo, como em C), precisamos de um analisador para operandos que possam analisar um ou outro. Esse analisador é uma alternativa dos outros dois, portanto, precisamos de uma função que possa combinar analisadores para que os resultados de seu trabalho sejam combinados. O resultado do analisador é uma lista e a combinação de listas é sua concatenação. Implementamos a função altP combinando dois analisadores:
altP :: Parser a -> Parser a -> Parser a altP (Parser p1) (Parser p2) = Parser (\s -> p1 s ++ p2 s)
Em seguida, o analisador de operando pode ser implementado usando esta função (aqui é assumido que parserInt e parserIdent já parserIdent descritos em algum lugar:
parserOperand :: Parser Operand parserOperand = altP parserIntOp parserIdentOp where parserIntOp = IntOp <$> parserInt parserIdentOp = IdentOp <$> parserIdent
Obviamente, para alternativas já criamos uma classe separada, chamada Alternative . Possui outro método, empty , que descreve o elemento neutro para a operação alternativa. No nosso caso, é um analisador que nunca analisa nada, ou seja, sempre retorna uma lista vazia de resultados. Para o analisador, a implementação dos métodos da classe Alternative parece com isso:
class Applicative f => Alternative f where empty :: fa (<|>) :: fa -> fa -> fa instance Alternative Parser where empty = Parser (const []) px <|> py = Parser (\s -> unParser px s ++ unParser py s)
A operação <|> é a função altP apenas na notação infix, que é mais conveniente de usar combinando vários analisadores seguidos.
Para todos os tipos nesta classe, duas funções são implementadas, some e many tipo fa -> f [a] . Cada um deles pode ser expresso através do outro:
some v = (:) <$> v <*> many v many v = some v <|> pure []
Em termos de analisadores, essas funções permitem analisar sequências de dados se você souber analisar um único elemento de dados. No caso de usar some sequência deve ser não vazia.
Exemplo de uso
Agora estamos prontos para escrever seu próprio analisador, por exemplo, para expressões aritméticas simples com a seguinte gramática:
expr ::= constExpr | binOpExpr | negExpr const ::= int int ::= digit{digit} digit ::= '0' | ... | '9' binOpExpr ::= '(' expr ' ' binOp ' ' expr ')' binOp ::= '+' | '*' negExpr ::= '-' expr
A expressão consiste em constantes inteiras, o menos unário e duas operações binárias infix: adição e multiplicação. Os colchetes são necessários em torno de uma expressão com uma operação binária, o símbolo da operação é separado dos operandos por exatamente um espaço, não sendo permitido espaços à esquerda e à esquerda.
Exemplos de escrita correta da expressão:
"123" "-(10 + 42)" "(1 + ((2 + 3) * (4 + 5)))"
Exemplos de entradas incorretas:
" 666 " "2 + 3" "(10 * 10)"
Declaramos os tipos de dados necessários (a própria expressão e a operação binária):
data Expr = ConstExpr Int | BinaryExpr Expr Operator Expr | NegateExpr Expr data Operator = Add | Mul
Você pode começar a analisar! A expressão em si consiste em três alternativas. Então escrevemos:
Uma constante é um número inteiro positivo. No nosso tipo de dados, ele é "empacotado" no construtor, portanto, não podemos usar o analisador para um número inteiro diretamente, mas podemos usar o fmap para obter o valor do tipo desejado.
Um número inteiro, de acordo com a gramática, é representado como uma sequência de números não vazia. Para analisar um dígito, usamos a função auxiliar predP e o predicado isDigit do módulo Data.Char . Agora, para construir um analisador para analisar uma sequência de dígitos, usamos a função some (não many , porque deve haver pelo menos um dígito). O resultado desse analisador retorna uma lista de todas as opções de análise possíveis, iniciando com o registro mais longo. Por exemplo, se a sequência de entrada for "123ab", a lista de resultados será a seguinte: [("ab", "123"), ("3ab", "12"), ("23ab", "1")] . Precisamos analisar a sequência mais longa de dígitos e convertê-la para o tipo Int . Toda a implementação é a seguinte:
A próxima maneira de escrever uma expressão é usar uma operação binária. De acordo com a gramática, o colchete de abertura deve primeiro incluir o colchete de abertura, o primeiro operando, o espaço, o símbolo da operação, outro espaço, o segundo operando e o colchete de fechamento. Para analisar caracteres individuais (colchetes e espaços), usamos a função charP . Operandos são expressões e já existe um analisador ( exprParser ) para analisá-los. Para analisar o símbolo de operação binária, descrevemos o analisador auxiliar logo abaixo. Resta combinar perfeitamente esse conjunto de analisadores. Deve haver colchetes no início e no final da expressão: você precisa verificar isso, mas descartar o resultado em si. Para fazer isso, use *> e <* :
binParser :: Parser Expr binParser = charP '(' *> ??? <* charP ')'
Entre esses analisadores para parênteses, uma expressão deve ser construída usando o construtor BinaryExpr e analisadores para a expressão e operação. Não se esqueça dos espaços ao redor do símbolo de operação, usando o mesmo método dos colchetes. Esta parte é a seguinte:
BinaryExpr <$> exprParser
Substituímos esta expressão por pontos de interrogação:
Uma operação binária é um caractere + que analisa o valor Add ou * que analisa o Mul :
O que resta é a parte mais simples da gramática, a negação da expressão. Com um símbolo - fazemos o mesmo que com colchetes e espaços. Em seguida, aplique o construtor NegateExpr ao resultado da análise recursiva:
Portanto, todas as partes do analisador são implementadas. O código é muito parecido com uma gramática e coincide completamente com ele na estrutura.
O código-fonte está disponível no GitLab: https://gitlab.com/fierce-katie/applicative-parsers-demo .
Lá é mais fácil avaliar seu volume e grau de expressividade, pois há muito menos comentários. Você pode compilar o projeto com o utilitário Stack e executar o interpretador primitivo usando o analisador que escrevemos:
$ stack build $ stack exec demo-parser
Para aqueles que desejam praticar mais por conta própria, posso aconselhar o seguinte:
- A gramática pode ser aprimorada de todas as formas, por exemplo, para permitir espaços iniciais e pendentes, adicionar novas operações, etc.
- O analisador converte a sequência na representação interna da expressão. Essa expressão pode ser calculada e transformada pelo intérprete para que ela imprima não o resultado da análise, mas o resultado do cálculo.
- Explore as possibilidades das
attoparsec parsec , attoparsec , applicative-parsec e optparse-applicative e tente usá-las.
Obrigado pela atenção!
Materiais úteis
- Aprenda Haskell em Y minutos
- Denis Shevchenko. "Sobre Haskell como ser humano"
- Biblioteca Parsec
- Biblioteca Attoparsec
- Biblioteca application-parsec
- Biblioteca optparse-aplicativa