Estoy familiarizado con la idea de la eliminación básica de la recursividad de la cola, donde las funciones que devuelven el resultado directo de una llamada pueden reescribirse como bucles iterativos.
foo(...):
# ...
return foo(...)
También entiendo que, como un caso especial, la función aún se puede reescribir si la llamada recursiva se envuelve en una llamada a cons
.
foo(...):
# ...
return (..., foo(...))
¿Qué propiedad de cons
permite esto? ¿Qué funciones además de cons
pueden envolver una llamada de cola recursiva sin destruir nuestra capacidad de reescribirla iterativamente?
GCC (pero no Clang) puede optimizar este ejemplo de " multiplicación de módulo de recursión de cola" , pero no está claro qué mecanismo le permite descubrir esto o cómo hace sus transformaciones.
pow(x, n):
if n == 0: return 1
else if n == 1: return x
else: return x * pow(x, n-1)
if(n==0) return 0;
(no devuelve 1 como en su pregunta).x^0 = 1
Entonces, eso es un error. Sin embargo, no es importante para el resto de la pregunta; el asm iterativo busca primero ese caso especial. Pero curiosamente, la implementación iterativa introduce una multiplicación de la1 * x
que no estaba presente en la fuente, incluso si hacemos unafloat
versión. gcc.godbolt.org/z/eqwine (y gcc solo tiene éxito con-ffast-math
).return 0
ha sido reparado. La multiplicación por 1 es interesante. No estoy seguro de qué hacer con eso.float
fuera-ffast-math
, a pesar de que se multiplica el mismo valor cada vez. (Excepto por el 1.0f ', ¿cuál podría ser el punto de conflicto?)Respuestas:
Si bien es probable que GCC use reglas ad-hoc, puede derivarlas de la siguiente manera. Lo usaré
pow
para ilustrar ya que sufoo
definición es tan vaga. Además,foo
podría entenderse mejor como una instancia de optimización de última llamada con respecto a las variables de asignación única como el lenguaje que Oz tiene y como se discute en Conceptos, Técnicas y Modelos de programación de computadoras . El beneficio de usar variables de asignación única es que permite permanecer dentro de un paradigma de programación declarativa. Esencialmente, puede hacer que cada campo de losfoo
retornos de la estructura esté representado por variables de asignación única que luego se pasanfoo
como argumentos adicionales.foo
luego se convierte en una cola recursivavoid
función de retorno. No se necesita inteligencia particular para esto.Volviendo a
pow
, primero, transformarse en un estilo de paso continuo .pow
se convierte en:Todas las llamadas son llamadas de cola ahora. Sin embargo, la pila de control se ha movido a los entornos capturados en los cierres que representan las continuaciones.
A continuación, desfuncionalice las continuaciones. Como solo hay una llamada recursiva, la estructura de datos resultante que representa las continuaciones desfuncionalizadas es una lista. Obtenemos:
Lo que
applyPow(k, acc)
hace es tomar una lista, es decir, monoide libre, comok=Cons(x, Cons(x, Cons(x, Nil)))
y hacerlax*(x*(x*acc))
. Pero como*
es asociativo y generalmente forma un monoide con unidad1
, podemos reasociar esto((x*x)*x)*acc
y, por simplicidad, agregar un punto1
de partida para producir(((1*x)*x)*x)*acc
. La clave es que en realidad podemos calcular parcialmente el resultado incluso antes de que lo hayamos hechoacc
. Eso significa que en lugar de pasark
como una lista que es esencialmente una "sintaxis" incompleta que "interpretaremos" al final, podemos "interpretarla" a medida que avanzamos. El resultado es que podemos reemplazarNil
con la unidad del monoide,1
en este caso, yCons
con la operación del monoide*
, y ahorak
representa el "producto en ejecución".applyPow(k, acc)
luego se convierte enk*acc
lo que podemos volver apow2
alinear y simplificar produciendo:Una versión de estilo original recursiva y de acumulación de cola
pow
.Por supuesto, no digo que GCC haga todo este razonamiento en tiempo de compilación. No sé qué lógica usa GCC. Mi punto es simplemente haber hecho este razonamiento una vez, es relativamente fácil reconocer el patrón e inmediatamente traducir el código fuente original a esta forma final. Sin embargo, la transformación CPS y la transformación de desfuncionalización son completamente generales y mecánicas. A partir de ahí, podrían usarse técnicas de fusión, deforestación o supercompilación para intentar eliminar las continuaciones reificadas. Las transformaciones especulativas podrían descartarse si no es posible eliminar toda la asignación de las continuaciones reificadas. Sin embargo, sospecho que eso sería demasiado costoso para hacer todo el tiempo, en general, por lo tanto, más enfoques ad-hoc.
Si desea ser ridículo, puede consultar las Continuaciones de reciclaje en papel, que también utiliza CPS y representaciones de continuaciones como datos, pero hace algo similar pero diferente a modulo-recursión de cola. Esto describe cómo puede producir algoritmos de inversión de puntero por transformación.
Este patrón de transformación y desfuncionalización de CPS es una herramienta bastante poderosa para la comprensión, y se utiliza con buenos resultados en una serie de documentos que enumero aquí .
fuente
Voy a andar por las ramas por un tiempo, pero hay un punto.
Semigrupos
La respuesta es la propiedad asociativa de la operación de reducción binaria .
Eso es bastante abstracto, pero la multiplicación es un buen ejemplo. Si x , y y z son algunos números naturales (o enteros, o números racionales, o números reales, o números complejos, o matrices N × N , o cualquiera de un montón más de cosas), entonces x × y es del mismo tipo de número como x e y . Comenzamos con dos números, por lo que es una operación binaria, y obtuvimos uno, por lo que redujimos el recuento de números que teníamos en uno, haciendo de esta una operación de reducción. Y ( x × y ) × z es siempre lo mismo que x × ( y ×z ), que es la propiedad asociativa.
(Si ya sabe todo esto, puede pasar a la siguiente sección).
Algunas cosas más que a menudo ves en informática que funcionan de la misma manera:
"a"+"b"+"c"
es"abc"
si comienzas con"ab"+"c"
o"a"+"bc"
)[a]++[b]++[c]
es similar[a,b,c]
de atrás hacia adelante o de adelante hacia atrás.cons
en cabeza y cola, si piensas en la cabeza como una lista única. Eso solo concatena dos listas.&
,|
y^
Algunas cosas que no:
int print2(int x, int y) { return printf( "%d %d\n", x, y ); }
, comoprint2( print2(x,y), z );
yprint2( x, print2(y,z) );
tienen una salida diferente.Es un concepto lo suficientemente útil como lo llamamos. Un conjunto con una operación que tiene estas propiedades es un semigrupo . Entonces, los números reales bajo multiplicación son un semigrupo. Y su pregunta resulta ser una de las formas en que este tipo de abstracción se vuelve útil en el mundo real. Las operaciones de semigrupo pueden optimizarse de la forma en que pregunta.
Prueba esto en casa
Hasta donde yo sé, esta técnica se describió por primera vez en 1974, en el artículo de Daniel Friedman y David Wise, "Plegar las recursiones estilizadas en iteraciones" , aunque asumieron algunas propiedades más de las que resultaban necesarias.
Haskell es un gran lenguaje para ilustrar esto, porque tiene la
Semigroup
clase de tipo en su biblioteca estándar. Llama a la operación de unSemigroup
operador genérico<>
. Como las listas y las cadenas son instancias deSemigroup
, sus instancias se definen<>
como el operador de concatenación++
, por ejemplo. Y con la importación correcta,[a] <> [b]
es un alias para[a] ++ [b]
, que es[a,b]
.Pero, ¿qué pasa con los números? Acabamos de ver que los tipos numéricos son menores de semigrupos ya sea además o multiplicación! Entonces, ¿cuál llega a ser
<>
para unDouble
? Bueno, cualquiera de los dos! Haskell define los tiposProduct Double
,where (<>) = (*)
(es decir la definición real en Haskell), y tambiénSum Double
,where (<>) = (+)
.Una arruga es que usaste el hecho de que 1 es la identidad multiplicativa. Un semigrupo con una identidad se llama monoide y se define en el paquete Haskell
Data.Monoid
, que llama al elemento de identidad genérico de una clase de tiposmempty
.Sum
,Product
y la lista tiene un elemento de identidad (0, 1 y[]
, respectivamente), por lo que son instancias deMonoid
así comoSemigroup
. (No debe confundirse con una mónada , así que solo olvide que incluso los mencioné).Esa es suficiente información para traducir su algoritmo en una función Haskell usando monoides:
Es importante destacar que este es un módulo de semigrupo de recursión de cola: cada caso es un valor, una llamada recursiva de cola o el producto de semigrupo de ambos. Además, este ejemplo se usó
mempty
para uno de los casos, pero si no lo hubiéramos necesitado, podríamos haberlo hecho con la clase de tipos más generalSemigroup
.Carguemos este programa en GHCI y veamos cómo funciona:
¿Recuerdas cómo declaramos
pow
un genéricoMonoid
, a cuyo tipo llamamosa
? Dimos GHCi suficiente información para deducir que el tipoa
aquí esProduct Integer
, que es unainstance
deMonoid
cuyas<>
operación es la multiplicación de enteros. Entonces sepow 2 4
expande recursivamente a2<>2<>2<>2
, que es2*2*2*2
o16
. Hasta aquí todo bien.Pero nuestra función usa solo operaciones monoides genéricas. Anteriormente, dije que hay otra instancia de
Monoid
llamadaSum
, cuya<>
operación es+
. ¿Podemos intentar eso?La misma expansión ahora nos da en
2+2+2+2
lugar de2*2*2*2
. ¡La multiplicación es la suma como la exponenciación es la multiplicación!Pero di otro ejemplo de un monoide de Haskell: listas, cuya operación es la concatenación.
Escribir
[2]
le dice al compilador que esta es una lista,<>
en las listas también++
lo[2]++[2]++[2]++[2]
es[2,2,2,2]
.Finalmente, un algoritmo (dos, de hecho)
Simplemente reemplazando
x
con[x]
, convierte el algoritmo genérico que usa el módulo de recursión de un semigrupo en uno que crea una lista. Cual lista La lista de elementos a los que se aplica el algoritmo<>
. Debido a que solo usamos operaciones de semigrupo que las listas también tienen, la lista resultante será isomorfa al cálculo original. Y como la operación original era asociativa, podemos evaluar igualmente bien los elementos de atrás hacia adelante o de adelante hacia atrás.Si su algoritmo llega a un caso base y termina, la lista no estará vacía. Como el caso terminal devolvió algo, ese será el elemento final de la lista, por lo que tendrá al menos un elemento.
¿Cómo se aplica una operación de reducción binaria a cada elemento de una lista en orden? Así es, un pliegue. Así se puede sustituir
[x]
porx
, obtener una lista de elementos para reducir en<>
, y luego o bien haga doble o izquierda veces la lista:La versión con
foldr1
existe realmente en la biblioteca estándar, comosconcat
porSemigroup
ymconcat
paraMonoid
. Hace un doblez derecho perezoso en la lista. Es decir, se expande[Product 2,Product 2,Product 2,Product 2]
a2<>(2<>(2<>(2)))
.Esto no es eficiente en este caso porque no puede hacer nada con los términos individuales hasta que los genere todos. (En un momento tuve una discusión aquí sobre cuándo usar pliegues derechos y cuándo usar pliegues izquierdos estrictos, pero fue demasiado lejos).
La versión con
foldl1'
es un pliegue izquierdo estrictamente evaluado. Es decir, una función recursiva de cola con un acumulador estricto. Esto se evalúa(((2)<>2)<>2)<>2
, calculado inmediatamente y no más tarde cuando es necesario. (Al menos, no hay demoras dentro del pliegue en sí: la lista que se está plegando se genera aquí por otra función que podría contener una evaluación diferida). Entonces, el pliegue calcula(4<>2)<>2
, luego calcula inmediatamente8<>2
, luego16
. Es por eso que necesitábamos que la operación fuera asociativa: ¡acabamos de cambiar la agrupación de paréntesis!El estricto pliegue izquierdo es el equivalente de lo que está haciendo GCC. El número más a la izquierda en el ejemplo anterior es el acumulador, en este caso un producto en ejecución. En cada paso, se multiplica por el siguiente número de la lista. Otra forma de expresarlo es: iterar sobre los valores que se multiplicarán, mantener el producto en ejecución en un acumulador y, en cada iteración, multiplicar el acumulador por el siguiente valor. Es decir, es un
while
bucle disfrazado.A veces se puede hacer igual de eficiente. El compilador podría ser capaz de optimizar la estructura de datos de la lista en la memoria. En teoría, tiene suficiente información en tiempo de compilación para darse cuenta de que debería hacerlo aquí:
[x]
es un singleton, por lo que[x]<>xs
es lo mismo quecons x xs
. Cada iteración de la función podría reutilizar el mismo marco de pila y actualizar los parámetros en su lugar.Un pliegue derecho o un pliegue izquierdo estricto podría ser más apropiado, en un caso particular, así que sepa cuál desea. También hay algunas cosas que solo puede hacer un pliegue derecho (como generar una salida interactiva sin esperar toda la entrada y operar en una lista infinita). Aquí, sin embargo, estamos reduciendo una secuencia de operaciones a un valor simple, por lo que lo que queremos es un pliegue izquierdo estricto.
Entonces, como puede ver, es posible optimizar automáticamente el módulo de recursión de la cola de cualquier semigrupo (uno de los cuales es cualquiera de los tipos numéricos habituales en multiplicación) a un doblez derecho o un doble izquierdo estricto, en una línea de Haskell
Generalizando más
Los dos argumentos de la operación binaria no tienen que ser del mismo tipo, siempre que el valor inicial sea del mismo tipo que el resultado. (Por supuesto, siempre puede voltear los argumentos para que coincidan con el orden del tipo de plegado que está haciendo, izquierda o derecha). Por lo tanto, puede agregar repetidamente parches a un archivo para obtener un archivo actualizado, o comenzar con un valor inicial de 1.0, dividir por enteros para acumular un resultado de coma flotante. O anteponga elementos a la lista vacía para obtener una lista.
Otro tipo de generalización es aplicar los pliegues no a listas sino a otras
Foldable
estructuras de datos. A menudo, una lista enlazada lineal inmutable no es la estructura de datos que desea para un algoritmo dado. Un problema que no mencioné anteriormente es que es mucho más eficiente agregar elementos al frente de una lista que al reverso, y cuando la operación no es conmutativa, la aplicaciónx
a la izquierda y a la derecha de la operación no lo mismo. Por lo tanto, necesitaría usar otra estructura, como un par de listas o un árbol binario, para representar un algoritmo que podría aplicarse tantox
a la derecha<>
como a la izquierda.También tenga en cuenta que la propiedad asociativa le permite reagrupar las operaciones de otras maneras útiles, como dividir y conquistar:
O paralelismo automático, donde cada subproceso reduce un subrango a un valor que luego se combina con los demás.
fuente
pow(float x, unsigned n)
versión gcc.godbolt.org/z/eqwine solo se optimiza con-ffast-math
, (lo que implica-fassociative-math
. El punto flotante estricto no es asociativo, ya que los diferentes temporales = redondeo diferente). Introduce un1.0f * x
que no estaba presente en la máquina abstracta C (pero que siempre dará un resultado idéntico). Entonces, las multiplicaciones n-1do{res*=x;}while(--n!=1)
son las mismas que las recursivas, por lo que esta es una optimización perdida.