Análise: a inicialização lenta e mutuamente recursivas mônadas em F #

Question

Eu tenho escrito uma pequena biblioteca monádico parser-combinator em F # (um pouco semelhante ao FParsec ) e agora tentou implementar um pequeno analisador para uma linguagem de programação.

A primeira vez que implementou o código em Haskell (com Parsec) que funcionou perfeitamente bem. Os analisadores de expressões infixas são projetados mutuamente recursiva.

parseInfixOp :: Parser String -> Parser Expression -> Parser Expression
parseInfixOp operatorParser subParser = ignoreSpaces $ do
                                          x <- ignoreSpaces $ subParser
                                          do
                                            op <- ignoreSpaces $ operatorParser
                                            y  <- parseInfixOp operatorParser subParser
                                            return $ BinaryOp op x y
                                           <|> return x

parseInfix :: [String] -> Parser Expression -> Parser Expression
parseInfix list = parseInfixOp (foldl1 (<|>) $ map string list)

parseExpr :: Parser Expression
parseExpr = parseInfix0

parseInfix0 = parseInfix ["==", "<>", "And", "Or", "Xor", "<", ">", "<=", ">="] parseInfix1
parseInfix1 = parseInfix ["+", "-", "Mod"] parseInfix2
parseInfix2 = parseInfix ["*", "/", "\\"] parseInfix3
parseInfix3 = parseInfix ["^"] parseInfix4
parseInfix4 = parseFactor

parseFactor :: Parser Expression
parseFactor = parseFactor' <|> (betweenChars '(' ')' parseExpr)

parseFactor' :: Parser Expression
parseFactor' = parseString
           <|> parseBool
           <|> parseNumber
           <|> parseVariable
           <|> (try parseFunCall) <|> parseIdentifier  

Uma vez que a ordem das funções não importa e Haskell está avaliando de uma forma não-estrito, este é OK, mas F # está avaliando rigorosamente.

let rec parseExpr = parseInfix0
and parseFactor = (parseFactor') <|> (betweenChars '(' ')' parseExpr)
and parseInfix2 = parseInfix ["^"] parseFactor BinaryOp
and parseInfix1 = parseInfix ["*"; "/"] parseInfix2 BinaryOp
and parseInfix0 = parseInfix ["+"; "-"] parseInfix1 BinaryOp
and parseFunCall = parser {
        let! first = letter
        let! rest = many (letter <|> digit)
        let  funcName = toStr $ first::rest

        do! ignoreSpace
        let! args = betweenChars '(' ')' $ sepBy (parseExpr) ","

        return FunCall(funcName, args)
    }
and parseFactor' =
    parseNumber
<|> parseString
<|> parseBool
<|> parseFunCall
<|> parseIdentifier

F # agora quer se queixa de objetos recursiva e apenas lança uma StackOverflowException em tempo de execução devido a um loop infinito ou ele mesmo não compilar o código fonte porque "um valor seria parte de seu próprio definion".

Qual é a melhor maneira de evitar isso erros. Os conselhos depurador me para fazer funções de uso ou lazys vez, mas o que eu deveria fazer preguiçoso aqui?

Answer 1

O que é o aviso sobre objetos recursiva? Mostrar o texto; há um tal aviso de que é ignorable (na verdade, em um sentido desejável) para este caso.

Se não compilar porque de valores recursiva, você simplesmente precisa para transformar os 'valores sintáticas' em 'funções sintáticas'. Ou seja, em vez de

...
and parseInfix2 = body
...

uso

...
and parseInfix2 x = (body) x
...

embora o tipo de 'parseInfix2' é o mesmo tipo de função de qualquer forma ... F # (ao contrário Haskell), por vezes, vai exigir que você seja explícito (ver eta-conversão como acima).

Eu ignorar sugestões sobre como inserir 'preguiçoso', analisadores são realmente funções, não valores, de modo que o eta-conversão irá cobrir a mesma questão (nada disto será avaliada ansiosamente em tudo, todas as necessidades para 'espera' até passar a string a ser analisado antes de qualquer coisa começa a 'run').

Em relação StackOverflowExceptions, se você postar um trecho looping da pilha pode ajudar, mas você talvez possa ver por si mesmo, por exemplo, se você tiver uma parte esquerda-recursiva da gramática que não consome qualquer entrada e fica preso em um loop. Eu acho que é uma armadilha fácil para a maioria das tecnologias de análise na maioria dos idiomas.

Answer 2

? conversão não é necessariamente uma grande solução -. Se você fizer isso, você vai ter que provar que a função de atraso é executado no máximo uma vez, ou pagar um monte de sobrecarga para chamá-lo durante a análise

Você quer algo parecido com isto:

let rec p1 = lazy (...)
and p2 = ... p1.Value ..

A melhor maneira, se você tem um construtor de workflow, é definir o membro Delay para fazer isso para você:

type Builder() =
    member this.Delay(f: unit -> Parser<_>) : Parser<_> = 
        let promise = Lazy.Create f
        Return () |> Bind (fun () -> promise.Value)

let parse = new Builder()


let rec p1 =
    parse {
        ...
    }

and p2 =
    parse {
        ...
    }

Answer 3

Nem a reescrita eta nem o atraso preguiçoso é uma coisa certa. O compilador F # parece ter dificuldade em lidar com recursions profundas. O que funcionou para mim foi a entrar em colapso a recursão em uma função de nível superior único (passando a função a ser chamada de forma recursiva como um argumento). Este nível superior está escrito estilo eta.

de nível superior, eu tenho:

let rec myParser s = (parseExpr myParser) s

Nota wikipedia diz: "Em uma linguagem rigorosa como OCaml, podemos evitar o problema recursão infinita, forçando o uso de um fecho.". Isso é o que funcionou para mim.