Motivación
Cuando comencé a aprender Haskell, me molestó mucho el uso generalizado de abstracciones complejas en lugar de soluciones específicas. Me pareció que es mucho mejor seguir siempre el principio de KISS y escribir bicicletas usando construcciones de lenguaje elemental que comprender todas estas clases de tipos para escribir una construcción supuestamente conveniente en alguna parte.
No tenía un buen ejemplo en el que los esfuerzos dedicados al desarrollo del "material" valieran la pena. Para mí, uno de los ejemplos más exitosos fue el analizador sintáctico. Ahora, a menudo hablo de ellos cuando me preguntan qué tareas comunes puedes usar Haskell.
Quiero ofrecer a los principiantes que también vayan de esta manera y creen una pequeña base de funciones desde cero para la implementación conveniente de analizadores, y luego la utilicen para escribir su propio analizador, cuyo código casi literalmente repetirá la gramática utilizada para analizar.
Espero que esto ayude a alguien a superar el miedo a las abstracciones y les enseñe cómo usarlas adecuadamente (sí, todavía creo que a veces es más eficiente escribir una bicicleta).
No tengo ningún propósito y deseo hacer un curso de Haskell desde cero a partir de un artículo, así que supongo que el lector está familiarizado con la sintaxis y los programas simples desarrollados independientemente. Por si acaso, hablaré brevemente sobre las clases de tipos antes de pasar a la descripción de la implementación.
Para aquellos que nunca han escrito a Haskell, pero quieren entender lo que está sucediendo aquí, les recomiendo que primero consulten la página correspondiente en Learn X en Y minutos . Como excelente libro en ruso para principiantes, aconsejo "Acerca de Haskell como ser humano" de Denis Shevchenko.
Intentaré usar las construcciones de lenguaje más simples que los principiantes puedan entender. Al final del artículo, se proporciona un enlace al repositorio de origen, donde en algunas partes del código se usa una entrada más conveniente y más corta, que puede ser menos clara a primera vista.
Y sí, caballeros Haskellistas, muchas cosas se explican de manera muy simple y torpe, para casos especiales, no muy abstractos, sin usar términos de la teoría de categorías y otras palabras aterradoras. Me alegra que los conozca y, por supuesto, los domine fácilmente. También los conozco, pero no creo que sea necesario volcar esa cantidad de información en este contexto en lectores no preparados.
Clases de tipo
Las clases de tipo Haskell no tienen nada que ver con las clases en C ++ y otros lenguajes orientados a objetos. Si dibujamos una analogía con OOP, las clases de tipo son más como una sobrecarga de métodos y funciones.
Las clases determinan qué acciones se pueden realizar con objetos de los tipos que componen la clase. Por ejemplo, todos los números se pueden comparar por igualdad, pero todo se puede ordenar, excepto los complejos, y en general, las funciones no se pueden comparar en absoluto. La clase de tipos que se pueden comparar se llama Eq , ordenada - Ord (los tipos no tienen que ser numéricos). Lo que se puede imprimir traduciendo a una cadena pertenece a la clase Show , tiene la clase de Read "opuesta", que determina cómo convertir cadenas en objetos del tipo deseado.
Para un conjunto de clases de tipo estándar (como Eq , Show , Read ...), puede pedirle al compilador que implemente la funcionalidad requerida de manera estándar, utilizando la palabra clave deriving después de determinar el tipo:
data Point = Point { xCoord :: Float , yCoord :: Float } deriving (Eq, Show)
Puede definir sus propias clases de tipos:
class PrettyPrint a where pPrint :: a -> String
Aquí PrettyPrint es el nombre de la clase, a es una variable de tipo. La palabra clave where es seguida por una lista de los llamados métodos de clase, es decir, funciones que se pueden aplicar a objetos de tipo de esta clase.
Para indicar la pertenencia de un tipo de datos a una clase, se utiliza la siguiente construcción:
instance PrettyPrint Point where pPrint (Point xy) = "(" ++ show x ++ ", " ++ show y ++ ")"
El lenguaje le permite especificar restricciones en las clases de tipo con las que deben relacionarse los argumentos de la función:
showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String) showVsPretty x = (show x, pPrint x)
Para cada llamada de función, el compilador verifica si se cumplen estos requisitos de tipo y, si falla, muestra un error (por supuesto, esto sucede en la etapa de compilación).
>>> 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'
Implementación
El analizador recibe una cadena de entrada que debe analizar de acuerdo con las reglas predefinidas y obtener el valor del tipo que necesitamos (por ejemplo, un entero). En este caso, la línea de entrada puede no terminar y el resto servirá como entrada para un análisis posterior. Además, nuestro analizador será generalmente no determinista, es decir devolverá varios resultados de análisis posibles como una lista.
Una tupla de dos elementos (String, a) adecuada para describir un resultado de la operación del analizador, donde a es una variable de tipo que puede denotar cualquier tipo de usuario.
Como el analizador analiza la cadena de acuerdo con algunas reglas, la describimos como una función que toma una cadena como entrada y devuelve una lista de resultados:
newtype Parser a = Parser { unParser :: String -> [(String, a)] }
Consideraremos el análisis exitoso si la lista de resultados consta de un elemento y la cadena de entrada se ha procesado por completo. Implementamos una función auxiliar que intenta analizar de forma exclusiva toda la cadena:
parseString :: String -> Parser a -> Maybe a parseString s (Parser p) = case (ps) of [("", val)] -> Just val _ -> Nothing
Analizadores simples
Implementamos varios analizadores simples, que luego serán útiles para crear combinaciones más complejas.
Comenzamos analizando un solo carácter que debe satisfacer un predicado. Si la cadena de entrada está vacía, el resultado del trabajo es una lista vacía. De lo contrario, verificamos el valor del predicado en el primer carácter de la cadena. Si True devuelve True , el resultado del análisis es este carácter; devuélvelo con el resto de la cadena. De lo contrario, el análisis también falla.
predP :: (Char -> Bool) -> Parser Char predP p = Parser f where f "" = [] f (c : cs) | pc = [(cs, c)] | otherwise = []
Ahora podemos escribir un analizador que tome un carácter específico al comienzo de la línea. Para hacer esto, use el predP recién escrito y páselo como argumento, una función que compara su argumento con el carácter que necesitamos:
charP :: Char -> Parser Char charP char = predP (\c -> c == char)
El siguiente caso más simple: un analizador que acepta solo una determinada cadena como un todo. stringP . La función dentro del analizador compara la línea de entrada con la deseada y, si las líneas son iguales, devuelve una lista de un elemento: un par de líneas vacías (no queda nada en la entrada) y la original. De lo contrario, el análisis falló y se devuelve una lista vacía de resultados.
stringP :: String -> Parser String stringP s = Parser f where fs' | s == s' = [("", s)] | otherwise = []
Muy a menudo, debe omitir los caracteres que tienen una determinada propiedad mientras van al comienzo de la línea (por ejemplo, los espacios en blanco). Además, el resultado del análisis no es importante para nosotros y no será útil en el futuro. Escribimos una función de skip que omite los caracteres iniciales de la cadena mientras se conserva el verdadero valor del predicado. Como resultado del análisis, usamos una tupla vacía.
skip :: (Char -> Bool) -> Parser () skip p = Parser (\s -> [(dropWhile ps, ())])
Los siguientes dos analizadores son muy similares entre sí. Ambos verifican el prefijo de la línea de entrada, solo el primero si tiene éxito devuelve este prefijo, y el segundo devuelve una tupla vacía, es decir le permite omitir una línea arbitraria al comienzo de la entrada. La implementación utiliza la función isPrefixOf definida en el 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 []
Un poco más adelante consideraremos una implementación más simple de esta última función y eliminaremos la duplicación de código.
Analizador como functor
Podemos distinguir una clase completa de tipos de contenedores para los que se cumple lo siguiente: si sabe cómo transformar objetos dentro de un contenedor, puede convertir los contenedores ellos mismos. El ejemplo más simple es una lista como contenedor y una función de map , que está disponible en casi todos los idiomas de alto nivel. De hecho, puede revisar todos los elementos de una lista de tipo [a] , aplicar a -> b función a a -> b a cada uno y obtener una lista de tipo [b] .
Esta clase de tipo se llama Functor ; la clase tiene un método fmap :
class Functor f where fmap :: (a -> b) -> fa -> fb
Supongamos que ya sabemos cómo analizar cadenas en objetos de cierto tipo a y, además, sabemos cómo convertir objetos de tipo a en objetos de tipo b . ¿Es posible decir que hay un analizador para objetos de tipo b ?
Si se expresa en forma de una función, tendrá el siguiente tipo:
(a -> b) -> Parser a -> Parser b
Este tipo coincide con el tipo de la función fmap , así que tratemos de hacer que el analizador sea un functor. Creemos un analizador de valores de tipo b desde cero, que primero llamará al primer analizador (ya tenemos uno), y luego aplicaremos la función a los resultados de su análisis.
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
La función fmap tiene un conveniente sinónimo infijo: fmap fx == f <$> x .
Si usamos una función como argumento para fmap que simplemente reemplaza su primer argumento con un nuevo valor, obtenemos otra operación útil que ya está implementada para todos los functores, incluso en dos casos (difieren solo en el orden de los argumentos):
(<$) :: Functor f => a -> fb -> fa ($>) :: Functor f => fa -> b -> fb
¿Recuerdas el analizador que omite una línea específica ( skipString )? Ahora puede implementarlo de la siguiente manera:
skipString :: String -> Parser () skipString s = () <$ prefixP s
Combinaciones de analizador
En Haskell, todas las funciones están programadas por defecto y son parcialmente utilizables. Esto significa que una función de n argumentos es en realidad una función de un argumento, devolviendo una función de n-1 argumentos:
cons :: Int -> [Int] -> [Int] cons = (:) cons1 :: [Int] -> [Int] cons1 = cons 1
Aplicamos una función de tres argumentos a algún valor dentro del analizador usando fmap . Los tipos serán los siguientes:
f :: c -> a -> b p :: Parser c (fmap fp) :: Parser (a -> b)
La función analizador resultó?! Por supuesto, una situación es posible cuando la representación de la función realmente está en la línea de entrada, pero me gustaría poder usar esta función, o más bien combinar el Parser (a -> b) y el Parser a para obtener el Parser b :
applyP :: Parser (a -> b) -> Parser a -> Parser b
El tipo de esta función es muy similar al tipo fmap , solo la función en sí que debe aplicarse también está en el contenedor. Esto proporciona una comprensión intuitiva de cómo debería ser la implementación de la función applyP : obtener la función del contenedor (como resultado de aplicar el primer analizador), obtener los valores a los que debe aplicarse la función (resultado de aplicar el segundo analizador) y "empacar" los valores convertidos utilizando esta función en el contenedor (cree un nuevo analizador). En la implementación, utilizaremos la comprensión de la lista:
applyP :: Parser (a -> b) -> Parser a -> Parser b applyP (Parser p1) (Parser p2) = Parser f where fs = [ (sx, fx) | (sf, f) <- p1 s,
Hay una clase Applicative que tiene un método con el mismo prototipo. El segundo método de la clase se llama pure y se utiliza para "ajustar" o "levantar" ( levantar ) un valor, incluido uno funcional. En el caso de la implementación del analizador, la función pure agrega su argumento al resultado del analizador, sin cambiar la cadena 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])
La función applyP es el <*> de la clase Applicative . Los tipos que pertenecen a esta clase se denominan functores aplicativos.
Para los functores aplicativos, se implementan dos funciones auxiliares que nos serán útiles:
(*>) :: fa -> fb -> fb (<*) :: fa -> fb -> fa
Estas funciones realizan dos acciones consecutivas y devuelven el resultado de solo una de ellas. Para los analizadores, pueden usarse, por ejemplo, para omitir los espacios iniciales antes de analizar una parte de una cadena que lleva una carga semántica.
Al combinar <$> y <*> , puede crear diseños muy convenientes. Considere el siguiente tipo de datos:
data MyStructType = MyStruct { field1 :: Type1 , field2 :: Type2 , field3 :: Type3 }
El constructor de valores MyStruct también es una función, en este caso es de tipo Type1 -> Type2 -> Type3 -> MyStructType . Puede trabajar con el constructor como con cualquier otra función. Supongamos que los analizadores ya se han escrito para los tipos de campos de estructura:
parser1 :: Parser Type1 parser2 :: Parser Type2 parser3 :: Parser Type3
Usando la función fmap , puede aplicar parcialmente MyStruct al primero de estos analizadores:
parserStruct' :: Parser (Type2 -> Type3 -> MyStructType) parserStruct' = MyStruct <$> parser1
Intentemos aplicar la función que ahora está "dentro" del analizador. Para hacer esto, ya necesita usar <*> :
parserStruct'' :: Parser (Type3 -> MyStructType) parserStruct'' = parserStruct' <*> parser2 parserStruct :: Parser MyStructType parserStruct = parserStruct'' <*> parser3
Como resultado, obtuvimos un analizador para toda la estructura (por supuesto, aquí usamos el supuesto de que en la línea original las representaciones de sus campos están en una fila). Lo mismo se puede hacer en una línea:
parserStruct :: Parser MyStructType parserStruct = MyStruct <$> parser1 <*> parser2 <*> parser3
Tales construcciones se encontrarán a menudo en casos de uso.
Ahora supongamos que estamos tratando de escribir un analizador sintáctico que analice expresiones aritméticas simples en las que los enteros e identificadores pueden estar presentes como operandos. Creemos un tipo separado de Operand para ellos:
data Operand = IntOp Int | IdentOp String
Si ya sabemos cómo analizar enteros e identificadores (por ejemplo, como en C), entonces necesitamos un analizador para los operandos que pueden analizar uno u otro. Este analizador es una alternativa de los otros dos, por lo que necesitamos una función que pueda combinar analizadores para que se combinen los resultados de su trabajo. El resultado del analizador es una lista, y la combinación de listas es su concatenación. Implementamos la función altP combinando dos analizadores:
altP :: Parser a -> Parser a -> Parser a altP (Parser p1) (Parser p2) = Parser (\s -> p1 s ++ p2 s)
Luego, el analizador de operandos se puede implementar utilizando esta función (aquí se supone que parserInt y parserIdent ya se describen en alguna parte:
parserOperand :: Parser Operand parserOperand = altP parserIntOp parserIdentOp where parserIntOp = IntOp <$> parserInt parserIdentOp = IdentOp <$> parserIdent
Por supuesto, para las alternativas ya hemos creado una clase separada, que se llama Alternative . Tiene otro método, empty , que describe el elemento neutral para la operación alternativa. En nuestro caso, es un analizador que nunca analiza nada, es decir siempre devuelve una lista vacía de resultados. Para el analizador, la implementación de los métodos de la clase Alternative ve así:
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)
La operación <|> es la función altP solo en notación infija, que es más conveniente de usar combinando varios analizadores en una fila.
Para todos los tipos de esta clase, se implementan dos funciones, some y many tipo fa -> f [a] . Cada uno de ellos se puede expresar a través del otro:
some v = (:) <$> v <*> many v many v = some v <|> pure []
En términos de analizadores, estas funciones le permiten analizar secuencias de datos si sabe cómo analizar un único elemento de datos. En el caso de usar some secuencia no debe ser vacía.
Ejemplo de uso
Ahora estamos listos para escribir su propio analizador, por ejemplo, para expresiones aritméticas simples con la siguiente gramática:
expr ::= constExpr | binOpExpr | negExpr const ::= int int ::= digit{digit} digit ::= '0' | ... | '9' binOpExpr ::= '(' expr ' ' binOp ' ' expr ')' binOp ::= '+' | '*' negExpr ::= '-' expr
La expresión consta de constantes enteras, el menos unario y dos operaciones binarias infijadas: suma y multiplicación. Se requieren corchetes alrededor de una expresión con una operación binaria, el símbolo de la operación está separado de los operandos por exactamente un espacio, no se permiten espacios iniciales y colgantes.
Ejemplos de escritura de expresión correcta:
"123" "-(10 + 42)" "(1 + ((2 + 3) * (4 + 5)))"
Ejemplos de entradas incorrectas:
" 666 " "2 + 3" "(10 * 10)"
Declaramos los tipos de datos necesarios (la expresión en sí y la operación binaria):
data Expr = ConstExpr Int | BinaryExpr Expr Operator Expr | NegateExpr Expr data Operator = Add | Mul
¡Puedes comenzar a analizar! La expresión misma consta de tres alternativas. Entonces escribimos:
Una constante es un entero positivo. En nuestro tipo de datos, está "envuelto" en el constructor, por lo que no podemos usar el analizador para un entero directamente, pero podemos usar fmap para obtener el valor del tipo deseado.
Un número entero, según la gramática, se representa como una secuencia de números no vacía. Para analizar un dígito, utilizamos la función auxiliar predP y el predicado isDigit del módulo Data.Char . Ahora, para construir un analizador sintáctico para analizar una secuencia de dígitos, usamos la función some (no many , porque debe haber al menos un dígito). El resultado de dicho analizador devuelve una lista de todas las opciones de análisis posibles, comenzando con el registro más largo. Por ejemplo, si la cadena de entrada es "123ab", la lista de resultados será la siguiente: [("ab", "123"), ("3ab", "12"), ("23ab", "1")] . Necesitamos analizar la secuencia más larga de dígitos y convertirla a tipo Int . Toda la implementación es la siguiente:
La siguiente forma de escribir una expresión es usar una operación binaria. Según la gramática, el paréntesis de apertura debe incluir primero el paréntesis de apertura, el primer operando, el espacio, el símbolo de operación, otro espacio, el segundo operando y el paréntesis de cierre. Para analizar caracteres individuales (corchetes y espacios) utilizamos la función charP . Los operandos son expresiones, y ya hay un analizador ( exprParser ) para analizarlos. Para analizar el símbolo de operación binaria, describimos el analizador auxiliar justo debajo. Queda por combinar perfectamente este conjunto de analizadores. Debe haber corchetes al principio y al final de la expresión: debe verificar esto, pero descartar el resultado en sí. Para hacer esto, use *> y <* :
binParser :: Parser Expr binParser = charP '(' *> ??? <* charP ')'
Entre estos analizadores para paréntesis, se debe construir una expresión usando el constructor BinaryExpr y analizadores para la expresión y la operación. No olvide los espacios alrededor del símbolo de operación, utilizando el mismo método que para los corchetes. Esta parte es la siguiente:
BinaryExpr <$> exprParser
Sustituimos esta expresión en lugar de signos de interrogación:
Una operación binaria es un carácter + que analiza el valor Add o * que analiza el Mul :
Lo que queda es la parte más simple de la gramática, la negación de la expresión. Con un símbolo - lo mismo que con corchetes y espacios. A continuación, aplique el constructor NegateExpr al resultado del análisis recursivo:
Por lo tanto, se implementan todas las partes del analizador. El código es muy parecido a una gramática y coincide completamente con él en la estructura.
El código fuente está disponible en GitLab: https://gitlab.com/fierce-katie/applicative-parsers-demo .
Allí es más fácil evaluar su volumen y grado de expresividad, ya que hay muchos menos comentarios. Puede compilar el proyecto con la utilidad Stack y ejecutar el intérprete primitivo utilizando el analizador que escribimos:
$ stack build $ stack exec demo-parser
Para aquellos que quieran practicar más por su cuenta, puedo aconsejar lo siguiente:
- La gramática se puede mejorar en todos los sentidos, por ejemplo, para permitir espacios iniciales y colgantes, agregar nuevas operaciones, etc.
- El analizador traduce la cadena en la representación interna de la expresión. Esta expresión se puede calcular y el intérprete convertido para que imprima no el resultado del análisis, sino el resultado del cálculo.
- Explore las posibilidades de las
attoparsec parsec , attoparsec , optparse-applicative y optparse-applicative e intente usarlas.
Gracias por su atencion!
Materiales utiles
- Aprende Haskell en Y minutos
- Denis Shevchenko. "Sobre Haskell como ser humano"
- Biblioteca Parsec
- Biblioteca Attoparsec
- Biblioteca aplicativa-parsec
- Biblioteca de aplicación selectiva