Funciones anónimas recursivas
Hace un tiempo ya que estoy dando clases como ayudante en Paradigmas de Programación. En dicha cátedra se pretende que el alumno tenga una visión con la cuál contemple los problemas a resolver con el paradigma más adecuado. Hay cosas que modelarlas orientadas a objetos o en objetos con Smalltalk, son mucho más sencillas que pensando en el paradigma imperativo. O problemas netamente lógicos, con soluciones recursivas e incluso de naturaleza declarativa, se resuelven mejor con el paradigma lógico, son swi-prolog por ejemplo.
Cabe destacar que los paradigmas, como la palabra lo indica, es una forma de pensar, un patrón, un modelo. Es independiente del lenguaje que usemos. Sin embargo, intentar programar orientado a objetos en C, puede ser más complicado que en C++, en Java o Smalltalk. Lo mismo con el lógico y con el funcional.
Por ejemplo, una de las características del paradigma funcional, es que se basa en el cálculo lambda. Mediante el cálculo lambda puedo definir abstracciones funcionales, las cuales no necesitan tener nombre si sólo quiero evaluarlas una vez. Puedo hacerlo de la forma
( (lambda (x) (* x x) ) 10) |
obteniendo el cuadrado del número.
Luego de la corta introducción, voy al problema que intenté resolver luego de una charla con un docente de la cátedra. En general cuando uno plantea una función recursiva, necesita de un nombre en la función para referenciarla. Por ejemplo:
sumatoria(L): si vacia L luego 0 sino cabeza(L) + sumatoria( cola (L) ) |
Si quisiera aprovechar lo que me provee el paradigma funcional, el cálculo lambda para abstraer dicha función recursiva para generar otras, me encontraría con el problema que necesito hacer referencia al nombre. Eso podría solucionarlo definiendo varios nombres de funciones. Ej:
(define reduce ( lambda (f d L) (if (null? L) d (f (car L) (reduce f d (cdr L) ) ) ) ) ) (define productoria ( lambda (L) ( reduce * 1 L) ) ) (productoria '(1 2 3 4 5)) |
Sin embargo sigo atado al espacio de nombres. ¿Podría definir de alguna manera una recursión sin necesitar de un espacio de nombres?
Para esto, pensé en unas soluciones posibles, quizá alguno tenga otras o se le ocurran otras en base a estas.
Podría definir una función, cuyos argumentos son una lista de números (o lo que necesite) y además una copia de si misma. Por ejemplo, veamos la siguiente abstracción funcional:
(lambda (f L) (if (null? L) 0 (+ (car L) (f f (cdr L) ) ) ) ) |
Esta abstracción, recibe como argumento una abstracción funcional (AF) y una lista. La AF que recibe, espera que se pueda aplicar a dos argumentos que, por lo que se puede ver en la definición, deberá ser una AF y una lista. De esta manera obtendré la recursión, si puedo asignar de alguna manera, una copia de sí misma como primer argumento.
Para esto, creo una nueva abstracción funcional, que aplica una AF como la que definimos a sí misma junto con una lista.
((lambda (f L) (f f L)) (lambda (f L) (if (null? L) 0 (+ (car L) (f f (cdr L)) ) ) ) '(1 2 3 4 5)) |
Da como resultado 15.
Un concepto similar, pero ya con un espacio de nombres sería el siguiente:
( define t (lambda (f L) (if (null? L) 0 (+ (car L) (f f (cdr L)) ) ) ) ) (t t '(1 2 3 4 5)) |
Otra forma de hacerlo, pero utilizando sólo un argumento y siguiendo la misma idea sería
(((lambda (f) (f f) ) (lambda (f) (lambda (L) (if (null? L) 0 (+ (car L) ((f f) (cdr L)) ) ) ) )) '( 1 2 3 4 5)) |
Personalmente creo que ésta última forma de declararlo es la más clara y entendible. Podríamos abstraer más en este caso la aplicación quitando el valor por defecto 0, y el «+», obteniendo una función fold o reduce sin nombre :-). Leyendo un poco en Internet, luego de un tiempo encontré lo que se conoce como Y combinator.
Más info en http://goodmath.blogspot.com/2006/05/why-oh-why-y.html.
Si tienen alternativas u otras curiosidades que les interese discutir, ¡adelante!
