Title: Programación funcional 2/3 Author: Domingo Gallardo Date: 5 febrero 2012 ## Tema 3: Programación funcional (2/3) Hoy: 1. Funciones como tipos de datos primitivos 1. Tipos de datos primitivos 2. Forma especial `lambda` 3. Funciones de orden superior, `apply`, `map`, generalización 4. Funciones en tipos de datos compuestos (listas) 2. Forma especial `let` 1. Ámbitos locales 2. `let` se construye a partir de `lambda` 3. Closures #### Objetivos * Conocer las condiciones para definir un tipo de dato como primitivo * Entender y saber utilizar la forma especial `lambda` para crear funciones sin darles un nombre * Entender el funcionamiento de la forma especial `define` para construir una función * Entender y diseñar funciones *de orden superior* * Entender y saber utilizar la forma especial `let` * Entender la semántica de la forma especial `let` y cómo se puede construir usando `lambda` * Entender la forma especial `let*` * Entender los ámbitos de variables en Scheme, saber representar gráficamente los ámbitos creados por expresiones `let` y `lambda` * Entender el concepto y los ejemplos de *closures* y saber crear este tipo de funciones * Diferenciar el funcionamiento del *deep* y el *shallow* binding #### Bibliografía * SICP: Cap. 1.3 --- #### Programación funcional * Entendemos por programación funcional las características del LISP y de los lenguajes funcionales menos puros que derivan de él (Scheme) * Tiene características que van más allá del paradigma de programación funcional puro / declarativo que vimos en la sesión anterior * Algunas de ellas: * Funciones como tipos de datos primitivos y funciones de orden superior * Polimorfismo * Símbolos y dualidad entre datos y código #### Funciones como tipos de datos primitivos Un tipo primitivo (o *first-class* en la terminología de Abelson & Sussman) es aquel que: * Puede ser asignado a una variable * Puede ser pasado como argumento a una función * Puede ser devuelto como resultado de una invocación a una función * Puede ser parte de un tipo mayor Por ejemplo, en Scheme, al igual que en la mayoría de lenguajes de programación, los valores de booleanos, enteros, caracteres, cadenas, etc. cumplen las condiciones anteriores y son objetos o tipos primitivos. La característica importante de la programación funcional es que las funciones son tipos primitivos. #### Forma especial lambda La forma especial lambda es la forma en Scheme de construir funciones sin darles un nombre. Igual que al escribir "hola" se crea una cadena (que antes no existía), al llamar a lambda se crea una función en tiempo de ejecución. Por ejemplo, la siguiente expresión crea una función sin nombre con un argumento *x* que eleva al cuadrado su argumento (lambda (x) (* x x)) **Sintaxis** (lambda ( ... ) ) #### Con la función creada por `lambda` podemos Invocarla: ((lambda (x) (* x x)) 3) Darle un nombre: (define cuadrado (lambda (x) (* x x))) #### ¿Qué hay en el nombre de una función? En Scheme los nombres de las funciones son realmente símbolos a los que están ligados objetos primitivos de tipo *función* Si escribimos en el intérprete el nombre de una función, el identificador se evalúa y devuelve el *objeto función* al que está ligado > + > (define suma +) > (suma 1 2 3 4) 10 ![Los nombres de función son símbolos ligados a objetos función][Suma] [Suma]: ./suma.png width=300px #### Azucar sintáctico La forma especial `define` para definir una función no es más que *azucar sintáctico*. La forma especial (define ( ) ) siempre se convierte internamente en: (define (lambda () )) #### Una función puede ser el argumento de otra función (define (aplica f x y) (f x y)) (aplica + 2 3) (aplica * 4 5) (aplica string-append "hola" "adios") (aplica (lambda (x y) (sqrt (+ (* x x) (* y y)))) 3 4) Otro ejemplo: (define (aplica-2 f g x) (f (g x))) (define (suma-5 x) (+ x 5)) (define (doble x) (+ x x)) (aplica-2 suma-5 doble 3) #### Una función puede ser el valor devuelto por otra La siguiente función crea y devuelve una función que suma *k* a su entrada. Es una *closure* (definiremos el término más adelante) (define (hacer-sumador-k k) (lambda (x) (+ x k))) (define g (hacer-sumador-k 5)) (g 10) #### Funciones de orden superior * Llamamos funciones de orden superior (*higher order functions* en inglés) a las funciones que toman otras como parámetro o devuelven otra función * Permiten definir funciones con un alto grado de abstracción * Ejemplo sencillo: la función `compose f g` * Ejemplos en Scheme: `apply` y `map` #### Función `compose` Un ejemplo de función de orden superior: la función `compose` que toma como argumento dos funciones de un argumento y construye y devuelve una función que realiza la composición de ambas. Matemáticamente: compose(f,g) = h que cumple h(x) = f(g(x)) En Scheme: (define (compose f g) (lambda (x) (f (g x)))) Un ejemplo de utilización: (define (cuadrado x) (* x x)) (define (suma-5 x) (+ x 5)) (define h (compose suma-5 cuadrado)) (h 3) #### Función `apply` Parámetros: `(apply función lista)` Devuelve el resultado de llamar a la función con la lista de argumentos Ejemplos: (apply + '(1 2 3 4)) (define (cuadrado x) (* x x)) (apply cuadrado '(3)) **Cuidado**, los siguientes ejemplos **no funcionan**. Piensa por qué: (apply 'cuadrado '(3)) (apply cuadrado 3) #### Función `map` Parámetros: `(map función lista)` La función `map` toma como parámetros una función y una lista. Devuelve una nueva lista resultante de aplicar la función a cada uno de los elementos de la lista inicial. (map cuadrado '(1 2 3 4 5)) También es posible que la función a mapear tenga más de un parámetro. En ese caso hay que pasarle como argumentos tantas listas como parámetros tenga la función. Los elementos de las listas se irán cogiendo de forma correlativa como parámetros de la función que se mapea. (define (suma x y) (+ x y)) (map suma '(1 2 3) '(4 5 6)) (map * '(1 2 3) '(4 5 6)) #### Implementación de `map` La función `map` se podría definir de forma recursiva como sigue. Llamamos a la siguiente función `mi-map` para evitar que se modifique la función original: (define (mi-map f lista) (if (null? lista) '() (cons (f (car lista)) (mi-map f (cdr lista))))) #### Generalización Las funciones de orden superior son una poderosa herramienta de abstracción. Veamos un ejemplo. Supongamos que queremos calcular el sumatorio de a..b de x: (define (sum-x a b) (if (> a b) 0 (+ a (sum-x (+ a 1) b)))) Supongamos ahora que queremos calcular el sumatorio de a..b de x al cuadrado: (define (sum-x a b) (if (> a b) 0 (+ (* a a) (sum-x (+ a 1) b)))) Y el sumatorio de a..b de x al cubo: (define (sum-x a b) (if (> a b) 0 (+ (* a a a) (sum-x (+ a 1) b)))) ¿Cómo generalizarlo?









Definiendo una función de orden superior que toma la función f que se aplica sobre a como un parámetro. Sumatorio desde a..b de f(x): (define (sum-x a b f) (if (> a b) 0 (+ (f a) (sum-x (+ a 1) b)))) Las funciones anteriores son casos particulares de esta función que las generaliza. Por ejemplo, para calcular el sumatorio desde a..b de x al cubo: (define (cubo x) (* x x x)) (sum-x a b cubo) #### Las funciones pueden formar parte de otras estructuras de datos La última característica de los tipos primitivos es que pueden formar parte de tipos de datos compuestos. Podemos hacerlo con las funciones, por ejemplo creando una lista de funciones. Veamos un ejemplo de cómo usarlo en `(aplica-funcs lista-funcs x)` que aplica de forma sucesiva todas las funciones de lista-funcs al número x. Por ejemplo, si en lista-funcs tenemos: (cuadrado cubo suma-1) La llamada a `(aplica-funcs lista-funcs 5)` devolverá: (cuadrado (cubo (suma-1 5)) 46656 La función se define como sigue: (define (aplica-funcs lista-funcs x) (if (null? (cdr lista-funcs)) ((car lista-funcs) x) ((car lista-funcs) (aplica-funcs (cdr lista-funcs) x)))) (define lista-funcs (list (lambda (x) (* x x)) (lambda (x) (* x x x)) (lambda (x) (+ x 1)))) (aplica-funcs lista-funcs 5) ### Ambito de variables, let y closures #### Ámbito global de variables Ahora que hemos introducido la forma especial lambda y la idea de que una función es un objeto primitivo, podemos revisar el concepto de ámbito de variables. En Scheme existe un ámbito global de las variables en el que se les da valor utilizando la forma especial define. (define a "hola") (define b (string-append "adios" a)) (define cuadrado (lambda (x) (* x x))) #### Ámbito local Cuando se invoca a una función se crea un ámbito local en el que los argumentos de la función toman los valores de los parámetros usados en la llamada a la función. Ejemplo: (define x 5) (define (suma-3 x) (+ x 3)) (suma-3 12) ;-> 15 La invocación a `(suma-3 12)` crea un ámbito local en el que la variable x (el argumento de `suma-3`) toma el valor 12. Dentro de ese ámbito se evalúa el cuerpo de la función, la expresión `(+ x 3)`, devolviéndose el valor 15. La siguiente figura representa los ámbitos creados: ![Ámbito local creado por la llamada (suma-3 12)][ambito-funcion] [ambito-funcion]: ./ambito-funcion.png width=250px En el ámbito local también se pueden utilizar variables definidas en el ámbito superior. Por ejemplo: (define y 12) (define (suma-3-bis x) (+ x 3 y)) (suma-3-bis 5) ;-> devuelve 20 La expresión `(+ x 3 y)` se evalúa en el ámbito local en el que x vale 5, pero y no está definida. Se utiliza la definición del ámbito superior: ![Variables no definidas en el ámbito local][ambito-funcion-2] [ambito-funcion-2]: ./ambito-funcion-2.png width=250px #### Forma especial let En Scheme se define la forma especial let que permite crear un ámbito local en el que se da valor a variables. Sintaxis: (let (( ) ... ( )) ) Las variables var1, … varn toman los valores devueltos por las expresiones exp1, … expn y la exp se evalúa con esos valores. Ejemplos: (let ((x 1) (y 2)) (+ x y)) #### Let mejora la legibilidad de los programas El uso de `let` permite abstraer operaciones y dar un nombre a los resultados, aumentando la legibilidad de los programas: (define (distancia x1 y1 x2 y2) (let ((dx (- x2 x1)) (dy (- y2 y1))) (sqrt (+ (cuadrado dx) (cuadrado dy))))) #### El ámbito de las variables definidas en el let es local Las variables definidas en el `let` sólo tienen valores en el ámbito de la forma especial. El funcionamiento es idéntico al que hemos visto anteriormente de una llamada a una función. (define x 5) (let ((x 1) (y 2)) (+ x y)) ; -> 3 x ;-> 5 y ; error, no definida Cuando ha terminado la evaluación del `let` el ámbito local desaparece y quedan los valores definidos en el ámbito superior. #### Let permite usar variables definidas en un ámbito superior Al igual que en la invocación a funciones, desde el ámbito definido por el `let` se puede usar el ámbito superior. Por ejemplo, en el siguiente código se usa la variable z definida en el ámbito superior. (define z 8) (let ((x 1) (y 2)) (+ x y z)) Podemos representar el comportamiento de esta expresión con la siguiente figura: ![Ámbito definido con el let][ambito-let] [ambito-let]:./ambito-let.png width=300px #### Las variables del let pueden asociarse con cualquier valor Un ejemplo en el que definimos funciones de ámbito local. En el siguiente ejemplo ligamos las variables locales `area-triangulo` y `apotema` con funciones creadas con `lambda`: (define (area-hexagono lado) (let ((area-triangulo (lambda (base altura) (/ (* base altura) 2))) (apotema (lambda (lado) (* (sqrt 3) (/ lado 2)))))) (* 6 (area-triangulo lado (apotema lado)))) #### Variables en las asignaciones del let Las expresiones del let se evalúan todas antes de asociar ningún valor con las variables. No se realiza una asignación secuencial (define x 1) (let ((w (+ x 3)) (z (+ w 2))) ;; Error (+ w z)) #### Semántica del let 1. Evaluar todas las expresiones de la derecha de las variables y guardar sus valores en variables auxiliares locales. 2. Definir un ámbito local en el que se ligan las variables del let con los valores de las variables auxiliares. 3. Evaluar el cuerpo del let en el ámbito local #### Let se define utilizando lambda La semántica anterior queda clara cuando comprobamos que let se puede definir en función de lambda. En general, la expresión: (let (( ) ... ( )) ) se puede implementar con la siguiente llamada a lambda: ((lambda ( ... ) ) ... ) Ejemplos: (define x 5) (let ((x (+ 2 3)) (y (+ x 3))) (+ x y)) Equivale a: ((lambda (x y) (+ x y)) (+ 2 3) (+ x 3)) #### Se puede hacer una asignación secuencial con let* La forma especial `let*` permite una asignación secuencial de las variables y las expresiones: (let* ((x (+ 1 2)) (y (+ x 3)) (z (+ y x))) (* x y z)) ¿Cómo se puede implementar con let? 








(let ((x (+ 1 2))) (let ((y (+ x 3))) (let ((z (+ y x))) (* x y z)))) El primer let crear un ámbito local en el que se evalúa el segundo let, que a su vez crea otro ámbito local en el que se evalúa el tercer let. Se crean tres ámbitos locales anidados, y en el último se evalúa la expresión `(* x y z)`. ![Ámbitos anidados creados con múltiples lets][ambitos-anidados] [ambitos-anidados]:./ambitos-anidados.png width=300px #### El ámbito definido en el let puede sobrevivir Un ejemplo avanzado del funcionamiento del let. Veamos el siguiente ejemplo, en el que creamos una función en el ámbito del let: (define h (let ((x 3)) (lambda (y) (+ x y)))) Sucede lo siguiente: 1. Se invoca al let y se crea un entorno local en el que x vale 3 2. En ese entorno se crea una función de un parámetro (y) que usa la variable x 3. Se devuelve la función y se asigna a h ![El entorno se cierra alrededor de la función (closure)][entorno] [entorno]:./entorno.png width=400px ¿Qué pasa cuando creamos un valor x en el ámbito global y se llama a h? (define x 10) (h 5) Se ejecuta la función h con su parámetro y valiendo 5 y una variable libre x. ¿Dónde se evalúa la expresión `(+ x 5)`? ¿En el entorno global o en el entorno del `let` en el que se ha creado la función h? Pruébalo en el intérprete y comprueba qué valor devuelve `(h 5)`.





Puedes comprobar que la llamada `(h 5)` devuelve 8. O sea, que `(+ x 5)` se evalúa en el ámbito local creado por el `let`: ![Resultado de evaluar `(h 5)`][entorno2] [entorno2]:./entorno2.png width=400px Este ejemplo ilustra el funcionamiento general de Scheme, denominado *deep binding*, en el que el cuerpo de `h` se evalúa en el entorno en el que la función h se creó. El conjunto del ámbito local más el objeto función creado en él se denomina *clausura* (o *closure* en inglés). #### El mismo efecto sin let En el ejemplo siguiente la llamada `(make-sumador 5)` produce exactamente el mismo efecto que el let anterior, ya que en la llamada a `(make-sumador 5)` el parámetro x es el que toma el valor de 5 y queda *encerrado* en el ámbito junto con la función devuelta por `lambda`. (define (make-sumador x) (lambda (y) (+ x y))) (define x 10) (define h (make-sumador 5)) (h 8) * Ejecútalo en el intérprete y comprueba qué devuelve (h 8) * Dibuja los entornos creados por el código anterior. #### Closure Lo que hemos visto se define con el nombre de closure: una función creada en tiempo de ejecución junto con el entorno en el que ésta se ha creado. Mediante el uso de clausuras es posible asociar una función con una o más variables libres a un ámbito local en el que se definen estas variables. En muchos lenguajes de programación modernos existe el concepto de closure, aunque pueden recibir nombre variados. Por ejemplo, en Objective-C recibe el nombre de *block*: #include #include typedef int (^IntBlock)(); IntBlock MakeCounter(int start, int increment) { __block int i = start; return Block_copy( ^ { int ret = i; i += increment; return ret; }); } int main(void) { IntBlock mycounter = MakeCounter(5, 2); printf("First call: %d\n", mycounter()); printf("Second call: %d\n", mycounter()); printf("Third call: %d\n", mycounter()); /* because it was copied, it must also be released */ Block_release(mycounter); return 0; } /* Output: First call: 5 Second call: 7 Third call: 9 */ #### Funciones anónimas Muchos lenguajes de programación permiten utilizar código como objeto primitivo y pasarlo como parámetro a otras funciones. Este tipo de funciones también recibe el nombre de *funciones anónimas* (ver un interesante [artículo en la Wikipedia](http://en.wikipedia.org/wiki/Anonymous_function) con ejemplos en muchos lenguajes de programación). Es muy importante tener en cuenta de que no todas las funciones anónimas usan el mismo tipo de semántica. En lenguajes dinámicos como Scheme, las funciones son creadas en tiempo de ejecución, quedando encerradas en el ámbito en que han sido creadas y ejecutándose precisamente en ese ámbito. También sucede en otros lenguajes como Objective-C. Es lo que se llama *deep binding* y cuyos efectos hemos visto en los puntes anteriores. En otros lenguajes las funciones anónimas se implementan mediante código *pre-compilado* que se evalúa en el ámbito en el que finalmente se ejecuta. Esto no daría lugar a una clausura. #### Deep binding La característica por la que una función siempre se ejecuta en al entorno en el que fue creada recibe el nombre técnico de *deep binding*. Un enfoque alternativo sería lo que se denomina *shallow binding*, en el que una función siempre se ejecuta en el entorno en el que finalmente se usa. Los lenguajes que usan shallow binding no pueden implementar clausuras. Los términos `deep binding` y `shallow binding` sólo tienen sentido en los lenguajes de programación en los que las funciones son objetos primitivos. #### Ejemplo de Deep binding vs Shallow binding Supongamos las sigientes funciones: (define x 100) (define (func1) (let ((x 1)) (lambda () (+ x 1)))) (define (func2) (let ((x 10)) ((func1)))) (func2) Al principio definimos una variable `x` con el valor 100. Después definimos la función `func1` en la que se declara una variable `x` con el valor 1 y se crea una función que devuelve el valor de una variable `x` más 1. En `func2` se crea el otra variable `x` con el valor 10 y se invoca la función devuelta por `func1`. ¿Qué devolverá `func2`?











![Deep vs. Shallow binding][deep-shallow] [deep-shallow]:./deep-shallow.png width=600px En Scheme, que usa *deep binding* devolverá 2. Los lenguajes que usen *shallow binding* devolverán 11.