Cola-recursividad en Oz

Question

En el chapter about function in the Oz tutorial, se dice que:

similar a los lenguajes funcionales perezosos Oz permite ciertas formas de optimizaciones de cola-recursividad que se no se encuentran en ciertas estrictas lenguajes funcionales incluyendo el estándar ML, Scheme, y el funcional concurrente lenguaje Erlang. Sin embargo, las definiciones de función estándar en Oz no son flojas.

A continuación, pasa a mostrar la siguiente función que es recursiva de cola en Oz:

fun {Map Xs F} 
    case Xs 
    of nil then nil 
    [] X|Xr then {F X}|{Map Xr F} 
    end 
end 

Lo que esto hace es, que mapea la lista vacía a la lista vacía y lista no vacía, al resultado de aplicar la función F a su cabeza y luego anteponerla al resultado de llamar al Map en la cola. En otros idiomas, esto no sería recursivo de cola, porque la última operación es la llamada previa, no la recursiva al Map.

Así que mi pregunta es: si "las definiciones de funciones estándar en Oz no son flojas", ¿qué hace Oz que los lenguajes como Scheme o Erlang no pueden (o no) poder realizar la optimización de recursión de cola? para esta función? ¿Y exactamente cuándo es una función recursiva de la cola en Oz?

Answer 1

Esto se llama Tail Recursion Modulo Cons. Básicamente, anteponiendo a la lista directamente después de la llamada recursiva es la misma que añadiendo a la lista directamente antes la llamada recursiva (y así construir la lista como un "efecto secundario" de la puramente funcional " lazo"). Esta es una generalización de recursión de cola que funciona no solo con las listas cons, sino con cualquier constructor de datos con operaciones constantes.

Fue descrito por primera vez (pero no nombrado) como una técnica de compilación LISP en 1974 por Daniel P. Friedman y David S. Wise en Technical Report TR19: Unwinding Structured Recursions into Iterations y fue formalmente nombrado e introducido por David HD Warren en 1980 en el contexto de la escritura el primer compilador de Prolog.

Lo interesante de Oz, sin embargo, es que TRMC no es una característica del lenguaje ni una optimización explícita del compilador, es solo un efecto secundario de la semántica de ejecución del lenguaje. Específicamente, el hecho de que Oz es un lenguaje de restricción concurrente declarativo, lo que significa que cada variable es una variable de flujo de datos (o "todo es una promesa", incluidas todas las ubicaciones de almacenamiento). Como todo es una promesa, podemos modelar el retorno desde una función como primero configurando el valor de retorno como una promesa, y luego más tarde en cumpliéndolo.

Peter Van Roy, co-autor del libro Concepts, Techniques, and Models of Computer Programming by Peter Van Roy and Seif Haridi, también uno de los diseñadores de Oz, y uno de sus implementators, explica cómo funciona exactamente TRMC en un hilo de comentarios en Lambda Ultimate: Tail-recursive map and declarative agents:

El ejemplo anterior de código de esquema incorrecto se convierte en un buen código Oz recursivo cuando se traduce directamente en la sintaxis Oz. Esto da:

fun {Map F Xs} 
    if Xs==nil then nil 
    else {F Xs.1}|{Map F Xs.2} end 
end 

Esto se debe a que Oz tiene variables de asignación única. Para entender la ejecución, traducimos este ejemplo en el lenguaje núcleo Oz (Doy simplemente una traducción parcial para mayor claridad):

proc {Map F Xs Ys} 
    if Xs==nil then Ys=nil 
    else local Y Yr in 
     Ys=Y|Yr 
     {F Xs.1 Y} 
     {Map F Xs.2 Yr} 
    end end 
end 

Es decir, Map es recursiva de cola porque Yr está inicialmente unido. Esto no es solo un truco ingenioso; es profundo porque permite concurrencia declarativa y sistemas declarativos de agentes múltiples.

Answer 2

No estoy muy familiarizado con los lenguajes funcionales perezosos, pero si piensas en la función Mapa en tu pregunta, es fácil traducir a una implementación recursiva de cola si se permiten temporalmente valores incompletos en el montón (silenciados en más completa los valores una llamada a la vez).

Tengo que asumir que están hablando de esta transformación en Oz. Lispers solía hacer esta optimización a mano, todos los valores eran mutables, en este caso se usaría una función llamada setcdr, pero tenía que saber lo que estaba haciendo. Las computadoras no siempre tienen gigabytes de memoria. Estaba justificado hacer esto a mano, podría decirse que ya no lo es.

Volver a su pregunta, otros idiomas modernos no lo hacen automáticamente, probablemente porque sería posible observar el valor incompleto mientras se está construyendo, y esto debe ser lo que Oz ha encontrado una solución. ¿Qué otras diferencias hay en Oz en comparación con otros lenguajes que lo explicarían?