¿Cómo puedo saber si una función es recursiva de cola en F #

Question

Escribí la siguiente función:

let str2lst str =
    let rec f s acc =
      match s with
        | "" -> acc
        | _  -> f (s.Substring 1) (s.[0]::acc)
    f str []

¿Cómo puedo saber si el compilador F # lo convirtió en un bucle? ¿Hay alguna forma de averiguarlo sin usar Reflector (no tengo experiencia con Reflector y no sé C #)?

Editar: Además, ¿es posible escribir una función recursiva de cola sin usar una función interna, o es necesario que el bucle resida en?

Además, ¿hay una función en F # std lib para ejecutar una función determinada varias veces, cada vez que le da la última salida como entrada? Digamos que tengo una cadena, quiero ejecutar una función sobre la cadena y luego ejecutarla nuevamente sobre la cadena resultante, y así sucesivamente ...

Answer 1

Lamentablemente no hay una forma trivial.

No es demasiado difícil leer el código fuente y usar los tipos y determinar si algo es una llamada de cola por inspección (es "lo último" y no en un bloque de "prueba"), pero la gente en segundo lugar Adivinarse y cometer errores. No hay una forma automatizada simple (aparte de, por ejemplo, inspeccionar el código generado).

Por supuesto, puedes probar tu función en una gran parte de los datos de prueba y ver si explota o no.

El compilador F # generará instrucciones .tail IL para todas las llamadas de cola (a menos que se utilicen las marcas de compilación para desactivarlas, que se usan cuando se desean mantener los cuadros de la pila para la depuración), con la excepción de que las funciones recursivas de cola directamente Será optimizado en bucles. (EDITAR: Creo que en la actualidad el compilador F # también falla en emitir .tail en los casos en que puede probar que no hay bucles recursivos a través de este sitio de llamadas; esta es una optimización, dado que el código de operación .tail es un poco más lento en muchas plataformas).

'tailcall' es una palabra clave reservada, con la idea de que una versión futura de F # puede permitirte escribir, por ejemplo,

tailcall func args

y luego recibe una advertencia / error si no es una llamada de cola.

Solo las funciones que no son naturalmente recursivas en la cola (y, por lo tanto, necesitan un parámetro acumulador adicional) te "forzarán" en el lenguaje de "función interna".

Aquí hay un ejemplo de código de lo que pediste:

let rec nTimes n f x =
    if n = 0 then
        x
    else
        nTimes (n-1) f (f x)

let r = nTimes 3 (fun s -> s ^ " is a rose") "A rose"
printfn "%s" r

Answer 2

Me gusta la regla de oro que Paul Graham formula en En Lisp : si hay trabajo por hacer , por ejemplo. manipulando la salida de llamada recursiva, entonces la llamada no es recursiva de cola.