Tema 3: Características de la programación funcional
Sesión 7: El paradigma funcional (3)
martes 1 de marzo de 2011
Características de la programación funcional
• Evaluación sin efectos laterales: paradigma declarativo y modelo de sustitución
• Funciones como tipos de datos primitivos: forma especial lambda
• Ámbitos de variables: forma especial let
• Dualidad entre datos y programas: formas especiales eval y apply
• Listas como elemento fundamental de procesamiento
• Recursión
martes 1 de marzo de 2011
Ámbito global 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)))
martes 1 de marzo de 2011
Ámbito local: forma especial let
• En Scheme se define la forma especial let que permite crear un ámbito local en el que da valor a variables.
• Sintaxis:
• Las variables var1, … varn toman los valores devueltos por las expresiones exp1, … expn y el cuerpo se evalúa con esos valores.
(let ((<var1> <exp-1>) ... (<varn> <exp-n>)) <cuerpo>)
(let ((x 2) (y 5)) (+ x y))
martes 1 de marzo de 2011
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 programa
(define (distancia x1 y1 x2 y2) (let ((dx (- x2 x1)) (dy (- y2 y1))) (sqrt (+ (cuadrado dx) (cuadrado dy)))))
martes 1 de marzo de 2011
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
(define x 5)(let ((x 1) (y 2)) (+ x y))xy
martes 1 de marzo de 2011
let permite usar variables definidas en un ámbito superior
• 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))
martes 1 de marzo de 2011
Las variables del let pueden asociarse con cualquier valor
• Un ejemplo en el que definimos funciones de ámbito local: area-triangulo y apotema:
(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))))
martes 1 de marzo de 2011
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))
martes 1 de marzo de 2011
Semántica del let
• Evaluar todas las expresiones de la derecha de las variables y guardar sus valores en variables auxiliares locales.
• Definir un ámbito local en el que se ligan las variables del let con los valores de las variables auxiliares.
• Evaluar el cuerpo del let en el ámbito local
martes 1 de marzo de 2011
Es posible implementar let utilizando lambda
• La semántica anterior queda clara cuando comprobamos que let se puede definir en función de lambda. La expresión:
• Se puede implementar como:
(let ((<var1> <exp1>) ... (<varn> <expn>)) <cuerpo>)
((lambda (<var1> ... <varn>) <cuerpo>) <exp1> ... <expn>)
(define x 5)(let ((x (+ 2 3)) (y (+ x 3))) (+ x y))
((lambda (x y) (+ x y)) (+ 2 3) (+ x 3))
martes 1 de marzo de 2011
let* permite asignaciones secuenciales
• La forma especial let* permite una asignación secuencial de las variables y las expresiones:
• ¿Cómo se puede implementar con let?
(let* ((x (+ 1 2)) (y (+ x 3)) (z (+ y x))) (* x y z)
martes 1 de marzo de 2011
let* permite asignaciones secuenciales
• La forma especial let* permite una asignación secuencial de las variables y las expresiones:
• ¿Cómo se puede implementar con let?
(let* ((x (+ 1 2)) (y (+ x 3)) (z (+ y x))) (* x y z)
(let ((x (+ 1 2))) (let ((y (+ x 3))) (let ((z (+ y x))) (* x y z))))
martes 1 de marzo de 2011
let* permite asignaciones secuenciales
• El primer let crea 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).
(let ((x (+ 1 2))) (let ((y (+ x 3))) (let ((z (+ y x))) (* x y z))))
martes 1 de marzo de 2011
El ámbito definido en el let puede sobrevivir
• Un ejemplo avanzado del funcionamiento del let, en el que creamos una función en el ámbito del let:
• Sucede lo siguiente:
(define h (let ((x 3)) (lambda (y) (+ x y))))
1. Se invoca al let y se crea un entorno local en el que x vale 32. En ese entorno se crea una función de un parámetro que usa la variable x3. Se devuelve la función y se asocia a h
martes 1 de marzo de 2011
El ámbito definido en el let puede sobrevivir
• ¿Qué pasa cuando se llama a h? ¿Y si modificamos el valor de x en el ámbito global?
• Funcionamiento: cuando se llama a la función, el intérprete restaura el entorno que estaba activo cuando la expresión lambda se evaluó. Y lo aumenta con las variables de los parámetros formales ligadas al valor del argumento. En este ámbito se evalúa el cuerpo de la función.
(define h (let ((x 3)) (lambda (y) (+ x y))))
(h 5)(define x 10)(h 5)
martes 1 de marzo de 2011
El mismo efecto sin let
• En el ejemplo siguiente la llamada (make-sumador 3) produce exactamente el mismo efecto que el let anterior.
(define (make-sumador x) (lambda (y) (+ x y)))(define h (make-sumador 3))(define x 10)(h 5)
martes 1 de marzo de 2011
El ámbito definido en el let puede sobrevivir
• Importante:
• Seguimos estando en el paradigma de programación funcional declarativa en el que no hay efectos laterales.
• El modelo de sustitución no explica correctamente este comportamiento. Veremos más adelante el modelo de entornos que sí lo hace.
• Llamamos entorno (environment) a un conjunto de valores asociados a variables. Utilizamos las palabras ámbito y entorno como sinónimos.
martes 1 de marzo de 2011
Closure
• En muchos lenguajes de programación modernos existe el concepto de closure
• Se llama closure a una función creada en tiempo de ejecución junto con el entorno en el que ésta se ha creado
• Lo veremos en profundidad más adelante
martes 1 de marzo de 2011
Dualidad entre datos y programas
• Los programas en Scheme son expresiones entre paréntesis
• Una expresión es una lista de símbolos
• Esto permite tratar a los programas como datos y viceversa
• La forma especial eval evalúa una expresión
• Un ejemplo: supongamos que queremos sumar una lista de números
(define (suma-lista lista-nums) (eval (cons '+ lista-nums)))
martes 1 de marzo de 2011
Forma especial apply
• Permite llamar a una función con una lista de argumentos
• Sintaxis:
• Ejemplos:
(apply <func> <lista-args>)
(apply + '(1 2 3 4))(apply '+ '(1 2 3 4)) ; no funciona: '+ es un identificador(apply (lambda (x y) (* x y)) '(2 4))
martes 1 de marzo de 2011
Ejemplo de dualidad de datos y programa calculadora
• Este programa no es funcional: realiza pasos de ejecución para leer las expresiones introducidas por el usuario y para imprimir el resultado de su evaluación.
(define (calculadora) (display "Introduce parámetros entre paréntesis: ") (define params (read)) (display "Introduce cuerpo:") (define cuerpo (read)) (define func (eval (append '(lambda) (list params) (list cuerpo)))) (display "Introduce argumentos entre paréntesis: ") (define args (read)) (apply func args))
martes 1 de marzo de 2011
Ejemplo avanzado
(define (rep-loop) (display "mi-interprete> ") ; imprime un prompt (let ((expr (read))) ; lee una expresión (cond ((eq? expr 'adios) ; el usuario quiere parar? (display "saliendo del bucle read-eval-print") (newline)) (else ; en otro caso (write (eval expr)) ; evaluar e imprimir (newline) (rep-loop)))))
martes 1 de marzo de 2011