martes, febrero 19, 2008

Recursividad anónima

... y hablando de raytracing, aquí tiene uno bastante exótico, planteado como una gigantesca consulta LINQ en C# 3.0:
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í:
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.

Etiquetas: , ,

3 Comments:

Blogger Andrés Ortíz said...

Hola Ian

Bueno gracias por la explicación, como siempre resulta muy interesante leerte.

No se aún si tomar un curso a distancia contigo a con CAMPUS MVP.

Lo único es que tú solo me ofreces ADO.NET. Ian por favor trata de preperate un curso con otros temas. Por que la verdad preferiría tomar un curso contigo, pero es que ADO.NET no me interesa mucho.

Preperate un cargador con: LINQ, OBAs,WCF y mejor dicho ahi si sería muy interesante.

Por cierto qué pasó con OBAs, tú fuiste mi primer maestro en el tema de automatizar Office, crei que te gustaba el tema porque en la cara oculta de CPPB 4 tienes el mejor capítulo que he leido de automatizar office en un libro.
Y comos sabes eso actualmente es una delicia de programar con todo lo nuevo de VSTO 3.0

Un abrazo

viernes, febrero 22, 2008 4:07:00 p. m.  
Blogger Ian Marteens said...

Hola, Andrés:

No se aún si tomar un curso a distancia contigo a con CAMPUS MVP.

Si no necesitas ADO.NET, la elección es clara: un curso de Campus. Tenemos enfoques diferentes, e incluso diferentes estrategias de mercado. Yo he elegido la especialización. Por eso, entre otras razones, el curso de ADO.NET de IntSight es más caro (si no recuerdo mal).

De todos modos, hay planes para ampliar la oferta de cursos, pero sería tras la publicación de La Cara Oculta de C# 3, en cualquier caso. Ahora mismo tengo empezados cursos sobre Windows Forms, WPF, WCF y uno que le estoy cogiendo cariño: estructuras de datos con C#, en plan "programación avanzada".

A más largo plazo, voy a sacar uno sobre "networking". Es en lo que estoy trabajando ahora, pero tengo que madurarlo un poco más.

sábado, febrero 23, 2008 12:57:00 p. m.  
Blogger Giselle said...

Hola, cómo se hace para comprar tu libro "La cara oculata de C#?
El envío sería a Austria

saludos

jueves, diciembre 18, 2008 8:54:00 a. m.  

Publicar un comentario

<< Home