Recursividad anónima

... y hablando de raytracing, aquí tiene uno bastante exótico, planteado como una gigantesca consulta LINQ en C^# 3.0:

• A Fully LINQified Ray Tracer

Eso es jiu-jitsu y lo demás, tonterías. Como advierte el propio autor, no es una técnica "práctica", pero es un logro impresionante por su complejidad conceptual... y por la elegancia, no del código en sí quizás, pero sí de las ideas teóricas que lo soportan.

El algoritmo de raytracing tiene una característica importante: es recursivo. ¿Podemos, entonces, definir consultas recursivas en LINQ? Como las consultas LINQ están basadas en expresiones lambda, podemos ser más precisos: ¿se pueden definir expresiones lambdas recursivas en C^#?

La respuesta es afirmativa, pero la técnica necesaria es complicada... y resulta difícil de leer y mantener. Mads Torgersen la explica, desde una perspectiva teórica, aquí:

• Recursive lambda expressions

Existe, no obstante, una técnica alternativa y algo más sencilla para resolver el problema. Octavio Hernández la explica en la página 85 de su libro "C# 3.0 y LINQ" (que por cierto, puede adquirir a través de nosotros). Esto que sigue es una explicación ampliada de la técnica.

¿Cuál es la dificultad para definir una función lambda recursiva? De entrada, que no podemos llamar directamente a la función por tratarse de una función anónima. Lo que sí podríamos hacer es pasar un puntero a la función como parámetro de la misma, y ejecutar la función a la que hace referencia dicho puntero... o delegado, en la jerga de .NET. El primer paso, por lo tanto, es definir un tipo delegado para funciones que se ajusten a este prototipo. Para simplificar, nos limitaremos a funciones que calculan un valor entero a partir de otro entero:

delegate int Self(Self f, int n);

Construyamos ahora una función lambda que corresponda a este prototipo, y que simule el funcionamiento del factorial:

Self F = (f, n) => n == 0 ? 1 : n * f(f, n - 1);

Esta función F (en mayúsculas) se parece extraordinariamente al factorial. ¿Qué hace falta para que sea "realmente" el factorial? Simplemente, que al llamarla pasemos, en el primero de sus parámetros, la función factorial... es decir, ella misma. Por lo tanto, la función que necesitamos es:

Func<int, int> factorial = n => F(F, n);

Y ya tenemos función anónima recursiva. ¿Le cuesta todavía verlo claro? Bien, ahí va una pista:

• Observe que F es realmente una variable local, no una "constante de función".
• Cuando usamos F para definir factorial, en realidad estamos "capturando" la variable local F dentro del cuerpo de la función anónima.
• Es esta indirección la que permite, en definitiva, que el truco funcione.
• Dicho sea de paso, observe que el identificador f, usado al "inicializar" F, es en realidad un parámetro de tipo delegado.
• ¿Se ha dado cuenta de que he dicho "inicializar F" en vez de "definir F"?

Octavio termina su truco en este punto, y aunque se ha resuelto el problema, nos queda cierta insatisfacción, por haber utilizado el paso intermedio de la inicialización de F. Sin embargo, con muy poco esfuerzo más, se pueden mezclar las dos funciones anónimas y definir el factorial en un único paso. Esta es la expresión lambda que buscábamos:

Func<int, int> factorial = i =>
    new Self((f, j) => j == 0 ? 1 : j * f(f, j - 1))(
        (f, j) => j == 0 ? 1 : j * f(f, j - 1), i);

Es necesario utilizar explícitamente el constructor de Self, el tipo delegado, para que el compilador reconozca la expresión y pueda realizar la inferencia del resto de los tipos de parámetros. Para entender este monstruo, es mejor dividirlo en zonas:

Func<int, int> factorial = i =>
    new Self((f, j) => j == 0 ? 1 : j * f(f, j - 1))
    (
        (f, j) => j == 0 ? 1 : j * f(f, j - 1),
        i
    );

• La expresión amarilla se evalúa y produce un delegado. Observe que la usamos sintácticamente del mismo modo en que usaríamos Math.Sqrt o Console.WriteLine. En cierto sentido perverso y retorcido, Sqrt es una "constante de función", mientras que nuestro monstruo es una expresión que se evalúa y produce una función.
• ¿Se ha dado cuenta de que la expresión verde es estructuralmente idéntica a la amarilla? No obstante, la expresión verde no se evalúa directamente, sino que la pasamos como parámetro para que se ejecute más adelante.
• Finalmente, tenemos la simple y vulgar expresión azul. No hay misterio aquí, ¿verdad?

¿Complicado? Es cierto, pero la gracia de todo esto es que existe un truco alternativo, mucho más simple. Observe:

Func<int, int> factorial = null;
factorial = i => i == 0 ? 1 : i * factorial(i - 1);

Primero se declara una variable que apuntará a la función y se inicializa con un nulo. Luego se asigna el delegado definitivo... que hace referencia en su cuerpo a la variable local. Se trata de una captura de variable local, una técnica no sólo permitida por el lenguaje: es, en realidad, lo que hace que todo este rollo de las funciones anónimas tenga sentido. Lo que ahora importa es que, cuando ejecutemos el método asociado a la variable factorial, ésta ya estará debidamente inicializada.