Fonctions récursives dans les expressions de calcul

Question

Un peu d'arrière-plan en premier. J'apprends actuellement des trucs sur les combinateurs d'analyseurs monadiques. Alors que j'ai essayé de transférer la fonction « chainl1 » de this paper (. P 16-17), je suis venu avec cette solution:

let chainl1 p op = parser { 
    let! x = p 
    let rec chainl1' (acc : 'a) : Parser<'a> = 
     let p' = parser { 
      let! f = op 
      let! y = p 
      return! chainl1' (f acc y) 
      } 
     p' <|> succeed acc 
    return! chainl1' x 
} 

J'ai testé la fonction avec une entrée large et a obtenu un StackOverflowException. Maintenant, je me demande, est-il possible de réécrire une fonction récursive, qui utilise une expression de calcul, d'une manière qui utilise la récursivité de la queue?

Lorsque je développe l'expression de calcul, je ne vois pas comment cela serait généralement possible.

let chainl1 p op = 
    let b = parser 
    b.Bind(p, (fun x -> 
    let rec chainl1' (acc : 'a) : Parser<'a> = 
     let p' = 
      let b = parser 
      b.Bind(op, (fun f -> 
      b.Bind(p, (fun y -> 
      b.ReturnFrom(chainl1' (f acc y)))))) 
     p' <|> succeed acc 
    b.ReturnFrom(chainl1' x))) 

Answer 1

Dans votre code, la fonction suivante est pas récursive, car - à chaque itération - il fait un choix entre soit p' ou succeed:

// Renamed a few symbols to avoid breaking SO code formatter 
let rec chainl1Util (acc : 'a) : Parser<'a> = 
    let pOp = parser { 
    let! f = op 
    let! y = p 
    return! chainl1Util (f acc y) } 
    // This is done 'after' the call using 'return!', which means 
    // that the 'cahinl1Util' function isn't really tail-recursive! 
    pOp <|> succeed acc 

En fonction de votre mise en œuvre de combinateurs analyseur, la réécriture suivante pourrait travailler (je ne suis pas un expert, mais il peut être intéressant d'essayer cela):

let rec chainl1Util (acc : 'a) : Parser<'a> = 
    // Succeeds always returning the accumulated value (?) 
    let pSuc = parser { 
    let! r = succeed acc 
    return Choice1Of2(r) } 
    // Parses the next operator (if it is available) 
    let pOp = parser { 
    let! f = op 
    return Choice2Of2(f) } 

    // The main parsing code is tail-recursive now... 
    parser { 
    // We can continue using one of the previous two options 
    let! cont = pOp <|> pSuc 
    match cont with 
    // In case of 'succeed acc', we call this branch and finish... 
    | Choice1Of2(r) -> return r 
    // In case of 'op', we need to read the next sub-expression.. 
    | Choice2Of2(f) -> 
     let! y = p 
     // ..and then continue (this is tail-call now, because there are 
     // no operations left - e.g. this isn't used as a parameter to <|>) 
     return! chainl1Util (f acc y) } 

En général, le modèle pour l'écriture des fonctions récursif queue dans les expressions de calcul fonctionne. Quelque chose comme cela fonctionnera (pour les expressions de calcul qui sont mises en œuvre d'une manière qui permet la queue-récursion):

let rec foo(arg) = id { 
    // some computation here 
    return! foo(expr) } 

Comme vous pouvez le vérifier, la nouvelle version correspond à ce modèle, mais l'original n'a pas.

Answer 2

En général, il est possible d'écrire des expressions de calcul récursif queue (voir 1 et 2), même avec plusieurs let! fixations grâce au mécanisme de « délai ».

Dans ce cas, la dernière déclaration de chainl1 est ce qui vous met dans un coin, je pense.