recursion - recursividad - ¿Optimización de llamadas de la cola en Mathematica?

recursividad valor

Question

Al formular una respuesta a otra pregunta de SO , me encontré con un comportamiento extraño con respecto a la recursividad de la cola en Mathematica.

La documentación de Mathematica sugiere que se puede realizar una optimización de la cola de llamada . Pero mis propios experimentos dan resultados contradictorios. Contraste, por ejemplo, las siguientes dos expresiones. El primero bloquea el kernel 7.0.1, presumiblemente debido al agotamiento de la pila:

(* warning: crashes the kernel! *)
Module[{f, n = 0},
  f[x_] := (n += 1; f[x + 1]);
  TimeConstrained[Block[{$RecursionLimit = Infinity}, f[0]], 300, n]
]

El segundo se ejecuta hasta su finalización, aparentando explotar la optimización de la cola de llamadas para devolver un resultado significativo:

Module[{f, n = 0},
  f[x_] := Null /; (n += 1; False);
  f[x_] := f[x + 1];
  TimeConstrained[Block[{$IterationLimit = Infinity}, f[0]], 300, n]
]

Ambas expresiones definen una función recursiva de cola f . En el caso de la primera función, Mathematica aparentemente considera la presencia de un enunciado compuesto lo suficiente como para vencer cualquier posibilidad de optimización de cola. También tenga en cuenta que la primera expresión se rige por $RecursionLimit y la segunda por $IterationLimit , un signo de que Mathematica trata las dos expresiones de manera diferente. (Nota: la respuesta SO mencionada anteriormente tiene una función menos artificial que explota con éxito la optimización de la cola de llamadas).

Entonces, la pregunta es : ¿alguien sabe las circunstancias bajo las cuales Mathematica realiza la optimización de la llamada de cola de las funciones recursivas? Una referencia a una declaración definitiva en la documentación de Mathematica u otro material de WRI sería ideal. La especulación también es bienvenida.

Answer 1

La idea de esta respuesta es reemplazar los corchetes () por un contenedor que no hace crecer nuestras expresiones. Tenga en cuenta que la función para la que estamos buscando una alternativa es realmente Expresión Compuesta, ya que el PO era correcto al señalar que esta función estaba arruinando la recursión de cola (véase también la respuesta de Leonid). Se proporcionan dos soluciones. Esto define el primer contenedor

SetAttributes[wrapper, HoldRest];
wrapper[first_, fin_] := fin
wrapper[first_, rest__] := wrapper[rest]

Entonces tenemos eso

Clear[f]
k = 0;
mmm = 1000;
f[n_ /; n < mmm] := wrapper[k += n, f[n + 1]];
f[mmm] := k + mmm
Block[{$IterationLimit = Infinity}, f[0]]

Calcula correctamente Total [Rango [1000]].

------Nota-----

Tenga en cuenta que sería engañoso establecer

wrapper[fin_] := fin;

Como en el caso

f[x_]:= wrapper[f[x+1]]

La recursividad de cola no ocurre (debido al hecho de que el contenedor, teniendo HoldRest, evaluará el argumento singular antes de aplicar la regla asociada con el contenedor [fin_]).

Por otra parte, la definición anterior para f no es útil, ya que uno podría simplemente escribir

f[x_]:= f[x+1]

Y tiene la recursión de cola deseada.

------Otra nota-----

En caso de que proporcionemos al envoltorio muchos argumentos, puede ser más lento de lo necesario. El usuario puede optar por escribir

f[x_]:=wrapper[g1;g2;g3;g4;g5;g6;g7  , f[x+1]]

Segundo envoltorio

El segundo contenedor alimenta sus argumentos a CompoundExpression y, por lo tanto, será más rápido que el primer contenedor si se proporcionan muchos argumentos. Esto define el segundo contenedor.

SetAttributes[holdLastWrapper, HoldAll]
holdLastWrapper[fin_] := fin
holdLastWrapper[other_, fin_] := 
 Function[Null, #2, HoldRest][other, fin]
holdLastWrapper[others__, fin_] := 
 holdLastWrapper[
  Evaluate[CompoundExpression[others, Unevaluated[Sequence[]]]], fin]

Nota: Las secuencias de vuelta (vacías) pueden ser muy útiles en la recursión en general. Ver también mi respuesta aquí

https://mathematica.stackexchange.com/questions/18949/how-can-i-return-a-sequence

Tenga en cuenta que esta función seguirá funcionando si solo se proporciona un argumento, ya que tiene el atributo HoldAll en lugar de HoldRest, por lo que esa configuración

f[x]:= holdLastWrapper[f[x+1]]

Obtendrá una recursividad de cola (el reiniciador no tiene este comportamiento).

Comparación de velocidad

Vamos a crear una buena lista larga (en realidad una expresión con Head Hold) de instrucciones

nnnn = 1000;
incrHeld = 
  Prepend[DeleteCases[Hold @@ ConstantArray[Hold[c++], nnnn], 
    Hold, {2, Infinity}, Heads -> True], Unevaluated[c = 0]];

Para estas instrucciones, podemos comparar el rendimiento (y el resultado) de nuestras envolturas con CompoundExpression

holdLastWrapper @@ incrHeld // Timing
CompoundExpression @@ incrHeld // Timing
wrapper @@ incrHeld // Timing

-> {{0.000856, 999}, {0.000783, 999}, {0.023752, 999}}

Conclusión

El segundo contenedor es mejor si no está exactamente seguro de cuándo ocurrirá la recursión final o cuántos argumentos alimentará al contenedor. Si intenta alimentar los argumentos de wrapper 2, por ejemplo, en el caso en que se dé cuenta de que todo el segundo contenedor se alimenta a CompoundExpression y decide hacerlo usted mismo, el primer contenedor es mejor.

----- nota final ----

En CompoundExpression [args, Unevaluated [expr]], expr aún se evalúa antes de que CompoundExpression se elimine, por lo que las soluciones de este tipo no sirven de nada.

Answer 2

Puedo resumir las conclusiones a las que fui llevado por mi experiencia personal, con una advertencia de que lo que sigue puede no ser la explicación correcta. El anwer parece estar en las diferencias entre la pila de llamadas de Mathematica y las pilas de llamadas tradicionales, que se origina en las funciones definidas por el patrón de Mathematica que realmente son reglas. Entonces, no hay llamadas a funciones reales. Mathematica necesita una pila por una razón diferente: dado que la evaluación normal ocurre desde la parte inferior de un árbol de expresiones, debe mantener expresiones intermedias en caso de que partes más y más profundas de (sub) expresiones sean reemplazadas como resultado de la aplicación de reglas (algunas partes de una expresión crecer desde abajo). Este es el caso, en particular, de las reglas que definen lo que llamaríamos funciones no recursivas en otros idiomas. Entonces, una vez más, la pila en Mathematica es una pila de expresiones intermedias, no llamadas de función.

Esto significa que si, como resultado de la aplicación de una regla, una (sub) expresión puede reescribirse en su totalidad, la rama de expresión no necesita mantenerse en la pila de expresiones. Esto es probablemente lo que se conoce como optimización de llamadas finales en Mathematica, y esta es la razón por la cual en tales casos tenemos iteración en lugar de recursión (este es un muy buen ejemplo de las diferencias entre las aplicaciones de reglas y las llamadas a funciones). Las reglas como f[x_]:=f[x+1] son de este tipo. Sin embargo, si se vuelve a escribir alguna sub-expresión, produciendo más estructura de expresión, entonces la expresión se debe almacenar en la pila. La regla f[x_ /; x < 5] := (n += 1; f[x + 1]) f[x_ /; x < 5] := (n += 1; f[x + 1]) es de este tipo, que está un poco oculto hasta que recordamos que () representa CompoundExpression[] . Esquemáticamente lo que sucede aquí es f[1] -> CompoundExpression[n+=1, f[2]] -> CompoundExpression[n+=1,CompoundExpression[n+=1,f[3]]]->etc Aunque la llamada a f es la última cada vez, sucede antes de que se ejecute CompoundExpression[] completo, por lo que aún debe mantenerse en la pila de expresiones. Uno podría quizás argumentar que este es un lugar donde se podría optimizar, hacer una excepción para CompoundExpression, pero probablemente no sea fácil de implementar.

Ahora, para ilustrar el proceso de acumulación de pila que describí esquemáticamente más arriba, limitemos el número de llamadas recursivas:

Clear[n, f, ff, fff];
n = 0;
f[x_ /; x < 5] := (n += 1; f[x + 1]);

ff[x_] := Null /; (n += 1; False);
ff[x_ /; x < 5] := ff[x + 1];

fff[x_ /; x < 5] := ce[n += 1, fff[x + 1]];

Rastreando la evaluación:

In[57]:= Trace[f[1],f]
Out[57]= {f[1],n+=1;f[1+1],{f[2],n+=1;f[2+1],{f[3],n+=1;f[3+1],{f[4],n+=1;f[4+1]}}}}

In[58]:= Trace[ff[1],ff]
Out[58]= {ff[1],ff[1+1],ff[2],ff[2+1],ff[3],ff[3+1],ff[4],ff[4+1],ff[5]}

In[59]:= Trace[fff[1],fff]
Out[59]= {fff[1],ce[n+=1,fff[1+1]],{fff[2],ce[n+=1,fff[2+1]],{fff[3],ce[n+=1,fff[3+1]],   
{fff[4],ce[n+=1,fff[4+1]]}}}}

Lo que se puede ver a partir de esto es que la pila de expresiones se acumula para f y fff (esta última se usa para mostrar que se trata de un mecanismo general, con ce[] solo una cabeza arbitraria), pero no para ff , porque, para los fines de la coincidencia de patrones, la primera definición para ff es una regla intentada pero no coincidente, y la segunda definición reescribe ff[arg_] en su totalidad, y no genera ff[arg_] más profundas que necesitan más reescritura. Entonces, la conclusión es que debe analizar su función y ver si sus llamadas recursivas harán crecer la expresión evaluada desde abajo o no. Si es así, no es recursivo de la cola en lo que respecta a Mathematica.

Mi respuesta no estaría completa sin mostrar cómo hacer la optimización de la cola de forma manual. Como ejemplo, consideremos la implementación recursiva de Select. Trabajaremos con las listas enlazadas de Mathematica para que sea razonablemente eficiente en lugar de un juguete. A continuación se muestra el código para la implementación no recursiva de cola:

Clear[toLinkedList, test, selrecBad, sel, selrec, selTR]
toLinkedList[x_List] := Fold[{#2, #1} &, {}, Reverse[x]];
selrecBad[fst_?test, rest_List] := {fst,If[rest === {}, {}, selrecBad @@ rest]};
selrecBad[fst_, rest_List] := If[rest === {}, {}, selrecBad @@ rest];
sel[x_List, testF_] := Block[{test = testF}, Flatten[selrecBad @@ toLinkedList[x]]]

La razón por la que uso Block y selrecBad es para facilitar el uso de Trace. Ahora, esto arruina la pila en mi máquina:

Block[{$RecursionLimit = Infinity}, sel[Range[300000], EvenQ]] // Short // Timing

Puede rastrear en listas pequeñas para ver por qué:

In[7]:= Trace[sel[Range[5],OddQ],selrecBad]

Out[7]= {{{selrecBad[1,{2,{3,{4,{5,{}}}}}],{1,If[{2,{3,{4,{5,{}}}}}==={},{},selrecBad@@{2,{3,{4, 
{5,{}}}}}]},{selrecBad[2,{3,{4,{5,{}}}}],If[{3,{4,{5,{}}}}==={},{},selrecBad@@{3,{4,{5, 
{}}}}],selrecBad[3,{4,{5,{}}}],{3,If[{4,{5,{}}}==={},{},selrecBad@@{4,{5,{}}}]},{selrecBad[4,
{5,{}}],If[{5,{}}==={},{},selrecBad@@{5,{}}],selrecBad[5,{}],{5,If[{}==={},{},selrecBad@@{}]}}}}}}

Lo que sucede es que el resultado se acumula cada vez más en la lista. La solución es no aumentar la profundidad de la expresión resultante, y una forma de lograr eso es hacer que selrecBad acepte un parámetro adicional, que es la lista (vinculada) de resultados acumulados:

selrec[{fst_?test, rest_List}, accum_List] := 
    If[rest === {}, {accum, fst}, selrec[rest, {accum, fst}]];
selrec[{fst_, rest_List}, accum_List] := 
    If[rest === {}, accum, selrec[rest, accum]]

Y modifique la función principal en consecuencia:

selTR[x_List, testF_] := Block[{test = testF}, Flatten[selrec[toLinkedList[x], {}]]]

Esto pasará nuestra prueba de potencia muy bien:

In[14]:= Block[{$IterationLimit= Infinity},selTR[Range[300000],EvenQ]]//Short//Timing

Out[14]= {0.813,{2,4,6,8,10,12,14,16,18,20,
<<149981>>,299984,299986,299988,299990,299992,299994,299996,299998,300000}}

(Tenga en cuenta que aquí tuvimos que modificar $ IterationLimit, que es una buena señal). Y el uso de Trace revela la razón:

In[15]:= Trace[selTR[Range[5],OddQ],selrec]

Out[15]= {{{selrec[{1,{2,{3,{4,{5,{}}}}}},{}],If[{2,{3,{4,{5,{}}}}}==={},{{},1},selrec[{2,{3,{4, 
{5,{}}}}},{{},1}]],selrec[{2,{3,{4,{5,{}}}}},{{},1}],If[{3,{4,{5,{}}}}==={},{{},1},selrec[{3, 
{4,{5,{}}}},{{},1}]],selrec[{3,{4,{5,{}}}},{{},1}],If[{4,{5,{}}}==={},{{{},1},3},selrec[{4, 
{5,{}}},{{{},1},3}]],selrec[{4,{5,{}}},{{{},1},3}],If[{5,{}}==={},{{{},1},3},selrec[{5, 
{}},{{{},1},3}]],selrec[{5,{}},{{{},1},3}],If[{}==={},{{{{},1},3},5},selrec[{},{{{{},1},3},5}]]}}}

que es, esta versión no acumula la profundidad de la expresión intermedia, ya que los resultados se mantienen en una lista separada.