Funciones recursivas en expresiones de cálculo

Question

Algunos antecedentes primero. Actualmente estoy aprendiendo algunas cosas sobre los combinadores de analizadores monádicos. Mientras trataba de transferir la función 'chainl1' de this paper (Pág. 16-17), se me ocurrió con esta solución:

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 
} 

probé la función con alguna entrada grande y tiene un StackOverflowException. Ahora me pregunto, ¿es posible volver a escribir una función recursiva, que utiliza alguna expresión de cálculo, de modo que esté usando la recursividad de cola?

Cuando amplío la expresión de cálculo, no puedo ver cómo sería generalmente posible.

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

En su código, la siguiente función no es recursiva de cola, porque - en cada iteración - que hace que sea una elección entre p' o 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 función de la aplicación de los combinadores de analizadores sintácticos, la después de reescritura podría trabajar (no soy un experto aquí, pero puede valer la pena probar este):

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 general, el patrón de cola para escribir funciones recursivas dentro de expresiones de cálculo funciona. Algo como esto va a funcionar (por expresiones de cálculo que se implementan de una manera que permite que la cola de recursión):

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

Como se puede comprobar, la nueva versión coincide con este patrón, pero el original no lo hizo.

Answer 2

En general, es posible escribir expresiones de cálculo recursivo de cola (ver 1 y 2), incluso con múltiples fijaciones let! gracias al mecanismo de 'retraso'.

En este caso, la última afirmación de chainl1 es lo que te lleva a una esquina, creo.