¿Se pueden hacer eficientes los combinadores parser?

Se me ocurrió una solución Haskell que es 30× más rápida que la solución Haskell que publicaste (con mi expresión de prueba inventada).

Cambios importantes:

1. Cambie Parsec / String a Attoparsec / ByteString
2. En la función fact, cambiar read & many1 digit a decimal
3. Hizo la recursión chainl1 estricta(remove $! para la versión más perezosa).

Traté de mantener todo lo demás que tenía lo más similar posible.

import Control.Applicative
import Data.Attoparsec
import Data.Attoparsec.Char8
import qualified Data.ByteString.Char8 as B

expr :: Parser Int
expr = chainl1 term ((+) <$ char '+' <|> (-) <$ char '-')

term :: Parser Int
term = chainl1 fact ((*) <$ char '*' <|> div <$ char '/')

fact :: Parser Int
fact = decimal <|> char '(' *> expr <* char ')'

eval :: B.ByteString -> Int
eval = either (error . show) id . eitherResult . parse expr . B.filter (/= ' ')

chainl1 :: (Monad f, Alternative f) => f a -> f (a -> a -> a) -> f a
chainl1 p op = p >>= rest where
  rest x = do f <- op
              y <- p
              rest $! (f x y)
           <|> pure x

main :: IO ()
main = B.readFile "expr" >>= (print . eval)

Supongo que lo que concluí a partir de esto es que la mayoría de la desaceleración para el combinador de parser fue que estaba sentado en una base ineficiente, no que era un combinador de parser, per se.

Me imagino que con más tiempo y perfilado esto podría ir más rápido, ya que me detuve cuando pasé la marca de 25×.

No se si esto sería más rápido que el analizador de escalada precedente portado a Haskell. ¿Tal vez sería una prueba interesante?

En pocas palabras, los combinadores de parser son lentos para el lexing.

Había una biblioteca Haskell combinator para construir lexers (ver "Lazy Lexing is Fast" Manuel M. T. Chakravarty) - como las tablas se generaban en tiempo de ejecución, no había la molestia de la generación de código. La biblioteca se usó un poco - inicialmente se usó en uno de los preprocesadores FFI, pero no creo que nunca se haya subido a Hackage, así que tal vez fue un poco demasiado inconveniente para el uso regular.

En el código OCaml arriba, el analizador está coincidiendo directamente con las listas de caracteres, por lo que puede ser tan rápido como la desestructuración de listas en el lenguaje host (sería mucho más rápido que Parsec si se volviera a implementar en Haskell). Christian Lindig tenía una biblioteca OCaml que tenía un conjunto de combinadores de analizador y un conjunto de combinadores de lexer - los combinadores de lexer eran ciertamente mucho más simples que los de Manuel Chakravarty, y podría valer la pena rastrear esta biblioteca y marcarla antes de escribir un lexer generador.

¿Ha probado una de las bibliotecas de análisis rápido conocidas? Los objetivos de Parsec nunca han sido realmente la velocidad, sino la facilidad de uso y la claridad. Comparar con algo como attoparsec puede ser una comparación más justa, especialmente porque los tipos de cadena son probablemente más iguales (ByteString en lugar de String).

También me pregunto qué banderas de compilación se usaron. Siendo este otro trolling post del infame Jon Harrop, no me sorprendería si no se utilizaran optimizaciones para el Haskell codificar.