Download Programación Funcional - dccia

Programación Funcional
Índice
1
Lenguajes de programación............................................................................................... 2
2
Introducción a Scheme.......................................................................................................2
3
2.1
Expresiones....................................................................................................................2
2.2
Definiciones y entornos.................................................................................................3
2.3
Evaluación de una expresión......................................................................................... 4
2.4
Definición de nuevas funciones.....................................................................................4
2.5
Quote............................................................................................................................. 5
2.6
Algunas funciones de Scheme.......................................................................................5
2.7
Otros ejemplos de definición de funciones................................................................... 6
Programación Funcional.................................................................................................... 7
3.1
Modelo de sustitución....................................................................................................8
3.2
Orden de evaluación normal vs. de aplicación.............................................................. 9
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.
Programación Funcional
Nota:
Lectura:
Abelson & Sussman, Apartado 1.1 (páginas 1 -- 31)
1. Lenguajes de programación
En esta asignatura vamos a profundizar en la idea de lenguaje de programación. ¿Existen
características comunes a todos los lenguajes de programación? ¿Son características
independientes del paradigma de programación que se usa? Lo primero que debemos hacer
para poder reflexionar sobre estas cuestiones es concretar algo más qué entendemos por
"lenguaje de programación".
Nuestra idea de "lenguaje de programación" y de "programa" es la que plantean Abelson y
Sussman:
Nota:
"Vamos a estudiar la idea de un proceso computacional. Los procesos computacionales son seres abstractos que pueblan los
computadores. Al ejecutarse, los procesos manipulan otras cosas abstractas llamadas datos. El desarrollo de un proceso está
gobernado por un conjunto de reglas llamadas un programa. [...] Los programas que usamos para conjurar procesos son como
los encantamientos de los magos. Están compuestos de expresiones simbólicas en arcanos y esotéricos lenguajes de
programación que prescriben las tareas que queremos que realicen nuestros procesos. [...] El lenguaje de programación sirve
como un marco en el que organizamos nuestras ideas sobre procesos." (SICP, pp. 1,4)
Todo lenguaje de programación tiene tres mecanismos para conseguir esto:
• expresiones primitivas, que representan las entidades más simples que maneja el lenguaje
• mecanismos de composición, con los que construimos elementos más complicados a
partir de los más sencillos
• mecanismos de abstracción, con los que los objetos compuestos puede ser nombrados y
manipulados como una unidad.
2. Introducción a Scheme
En la asignatura "Lenguajes y Paradigmas de programación" (LPP) vamos a programar en
Scheme, que es un lenguaje interpretado. Esto significa que en lugar de escibrir un programa
y luego compilarlo, vamos a poder escribir una sencilla expresión y averiguar su valor. El
intérprete de Scheme realiza un bucle read-eval-print con el que lee la expresión, la evalúa e
imprime su resultado.
2.1. Expresiones
Por ejemplo (ponemos en cursiva lo que devuelve el intérprete):
Page 2
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.
Programación Funcional
> 2
2
> (* 3 2)
6
> (sqrt 4)
16
> (+ 2 3 4)
9
La sintaxis general de una expresión en Scheme es:
(<funcion> <arg1> ...<argn>)
Composición de funciones:
(+ (* 3 4) 5)
(- (+ 2 1) (/ 10 2))
2.2. Definiciones y entornos
Una característica fundamental de cualquier lenguaje de programación es la posibilidad de
definir nuevos nombres que van ampliando el vocabulario que podemos usar para construir
programas. Cada nombre nuevo representa un aumento de la capacidad de expresividad del
lenguaje, en la línea del dominio en el que queremos definir el programa. Para ser
consistentes con el libro de la asignatura, el idioma que vamos a usuar para la mayoría de los
nombres que inventemos será el inglés.
Por ejemplo, si estamos escribiendo un programa de geometría, es normal que definamos
nombres como "square", "point", "circle", etc.
¿A qué le podemos dar nombre? A las entidades propias del lenguaje. En el caso de Scheme
a datos elementales (enteros, strings, ...) y a funciones.
Si lo de "dar nombre a un entero" te puede parecer una forma muy retorcida de explicar un
DEFINE de C, ya ni me contarás con lo de "dar nombre a una función". ¿Por qué esa forma
de hablar? ¿Por qué no decir directamente "definir una función"? Ya verás dentro de poco
que realmente no es una forma de hablar... es la forma que tiene Scheme de funcionar.
Para definir nuevas entidades Scheme usa la forma especial define:
> (define pi 3.1415)
pi
> pi
3.1415
> (+ pi 7)
10.1415
> (define radio 10)
radio
> (define circunferencia (* 2 pi radio))
circunferencia
> circunferencia
62.8318
Page 3
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.
Programación Funcional
La forma especial define asocia un valor con un identificador. Su sintaxis es:
(define <identificador> <expresion>)
El intérprete evalúa la expresión y asocia al identificador el resultado de la evaluación.
Podemos pensar que esta asociación se guarda en una tabla o memoria que usa el intérprete y
que se denomina entorno. Un entorno no es más que una colección de parejas
(<identificador>,<valor>). El modelo de computación que veremos más adelante, el modelo
de sustitución, no necesita el concepto de entorno. Pero cuando pasemos al paradigma
procedural será muy importante su utilización.
Por ejemplo, después de ejecutar el "define" anterior, el entorno quedará como:
Identificador
pi
Valor
3.1415
2.3. Evaluación de una expresión
Para evaluar una expresión, Scheme sigue la siguiente regla:
Para evaluar (foo arg1 ... argn):
1. Si foo es una forma especial: aplicar foo a los argumentos sin evaluar. Cada forma
especial se aplica de una forma distinta.
2. Sino foo sólo puede ser una función:
1. Evaluar las subexpresiones: foo, arg1, ..., argn
2. Aplicar el procedimiento resultante de evaluar foo a los resultados de evaluar arg1,
..., argn
Por ejemplo, para evaluar (+ 2 3), Scheme evalúa el "3" (resulta el número 3), después el "2"
(resulta el número 2) y despúes el "+" (resulta el procedimiento "suma", que el intérprete
representa como "#[...]"). Y por último, aplica el procedimiento suma a 3 y 2, resultando 5.
Puede parecer raro eso de que se evalúe el "+". ¿Qué significa eso? Pués que en Scheme los
procedimientos son objetos primitivos del mismo nivel que otros objetos como enteros o
caracteres. Ya veremos en el tema 3 que en Scheme es posible pasar un procedimiento como
parámetro o incluso hacer que una función devuelva un procedimiento.
Los paréntesis "significan algo". En Scheme no puedes usar paréntesis a menos que vayas a
llamar a una función o a a una forma especial. Por ejemplo, si tecleas:
(+ (square 2) (3))
No obtendrás 7. Scheme devolverá un error porque 3 no es una función.
2.4. Definición de nuevas funciones
Page 4
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.
Programación Funcional
Y también se usa define para definir una función, con la siguiente sintaxis (que ya veremos
que es "azucar sintáctico"):
(define (<nombre-funcion> <param>)
<cuerpo>)
Ejemplos:
(define
(* x
(square
(square
(square x)
x))
5)
(+ 2 3))
;; definición de una función
;; llamada a la función
;; composición con funciones definidas
Terminología: el parámetro formal es el nombre del argumento (x); la expresión argumental
real es la expresión utilizada en la llamada ((+ 2 3)); el valor real del argumento es el
valor del argumento en la llamada (5). El nombre del argumento viene de la definición de la
función; el valor del argumento viene de la llamada.
2.5. Quote
La forma especial quote devuelve el identificador que se le pasa como argumento sin
evaluar, como el mismo identificador:
> (quote hola)
hola
> 'hola
hola
La tilde (') es una abreviatura de quote. Las dos expresiones anteriores son idénticas. A
quote se le puede pasar como argumento un identificador o una expresión:
> (quote (+ 1 2))
(+ 1 2)
2.6. Algunas funciones de Scheme
Hasta ahora hemos usado únicamente funciones numéricas. Vamos a ver algunos ejemplos
de otras funciones de Scheme.
Nota:
Una característica fundamental de Scheme es que es muy sencillo extender el lenguaje, definiendo nuevas primitivas. La
versión estándar, limpia, de Scheme está definida en al R5RS. Pero en clase vamos a usar desde el principio algunas funciones
que no están definidas en esta versión estándar, como "first" o "word". Para incorporar estas funciones en Scheme deberás
descargar en tu ordenador el fichero "simply.scm" que se encuentra en este enlace (programas/simply.scm.zip) . Debes
cargarlo en el DrScheme con el siguiente comando (load "/PATH_ABSOLUTO/simply.scm") siendo
/PATH_ABSOLUTO el path donde has guardado el fichero.
Algunos ejemplos de funciones de Scheme (propias del lenguaje y definidas en el fichero
"simply.scm"):
(first 274)
Page 5
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.
Programación Funcional
(butfirst 274)
(first 'hello)
(first" hello")
(first (bf 'hello))
(+ (first 23) (last 45))
(empty? (bf 'h))
(and #f #f #t)
(or #f #f #t)
Algunas consideraciones:
• Aunque para Scheme un identificador ('hello) no es exactamente igual que un string
("hello"), muchas funciones de las anteriores las consideran iguales
• Muchas funciones son polimórficas: pueden usarse con distintos tipos de objetos.
2.7. Otros ejemplos de definición de funciones
Vamos a definir algunas funciones más
(define (plural wd)
(word wd 's))
Este sencillo plural funciona correctamente (en inglés) para la mayoría de las palabras
(book, elephant, computer) pero no para las palabras que terminan en y. Vamos a mejorarlo:
(define (plural wd)
(if (equal? (last wd) 'y)
(word (bl wd) 'ies)
(word wd 's)))
if es una forma especial que sólo evalua una de las alternativas.
Pig Latin: Mueve consonantes iniciales al final de la palabra y añade "ay"; SCHEME se
convierte en EMESCHAY.
(define (pigl wd)
(if (pl-done? wd)
(word wd 'ay)
(pigl (word (bf wd) (first wd)))))
(define (pl-done? wd)
(vowel? (first wd)))
(define (vowel? letter)
(member? letter '(a e i o u)))
Pigl introduce recursión--- una función que se llama a ella misma. Veremos más sobre esto
en las próximas semanas.
Otro ejemplo: ¿Sabes jugar a Buzz? Comienzas a contar y si tu número es divisible por 7 o
tiene el dígito 7 tienes que decir "buzz" en lugar del número:
(define (buzz n)
(cond ((equal? (remainder n 7) 0) 'buzz)
Page 6
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.
Programación Funcional
((member? 7 n) 'buzz)
(else n)))
Esto introduce la forma especial cond para múltiples opciones. La forma especial cond es
la gran excepción a la regla sobre el significado de los paréntesis; las cláusulas no son
llamadas.
Nota:
RESUMEN
El define es el modo de abstracción más sencillo en Scheme, ya has visto que permite utilizar simples nombres para
referirse a resultados de funciones compuestas, como es el caso de la circunferencia.
En general, los objetos pueden tener estructuras muy complejas y sería muy tedioso si tuviésemos que recordar y repetir sus
detalles cada vez que queremos utilizarlos. Además, los programas complejos se generan construyendo, paso a paso, objetos
cada vez más complejos.
Asociar valores con símbolos y después reutilizarlos, significa que debe existir algún tipo de memoria que guarde las parejas
nombre-objeto. Ese tipo de memoria se denomina entorno (y más concretamente, entorno global). En temas posteriores
veremos que una ejecución puede involucrar diferentes entornos.
3. Programación Funcional
El primer paradigma de programación que vamos a ver es el paradigma de la Programación
Funcional. En este paradigma, las funciones no tienen "memoria" y no dejan efectos
colaterales, y además cada función siempre devuelve el mismo resultado para un mismo
parámetro. Por ejemplo,
(square 2)
4
(square 2)
4
Si le pasamos a square el argumento 2 siempre devolverá 4. Parece algo obvio, sin
embargo en el siguiente ejemplo verás una función que no forma parte de la Programación
Funcional:
(random 10)
4
(random 10)
7
La función random es un procedimiento que toma un argumento y aleatoriamente devuelve
un entero menor que el pasado como argumento. Para un mismo argumento devuelve
diferentes resultados. Eso no es una función.
Otro ejemplo donde se viola este principio de la Programación Funcional. Como todavía no
hemos visto cómo se hacen asignaciones en Scheme, lo vamos a escribir en C:
static int iCount = 0;
int getCount(int iIncrement){
iCount = iCount + iIncrement;
return iCount;
}
Page 7
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.
Programación Funcional
count = getCount(10);
count = getCount(10);
// devuelve 10
// devuelve 20
Fíjate que si llamamos a getCount dos veces se obtienen resultados distintos. Además hay
un efecto colateral después de llamar a getCount: el valor de la variable iCount varía.
Resumiendo, el Paradigma de la Programación Funcional tiene las siguientes características:
• Las funciones no deben tener "memoria" ni producir efectos colaterales. Después de una
llamada a una función, el sistema tiene que permanecer inalterable. Una llamada a una
función con un valor dado siempre debe devolver el mismo resultado.
• En lugar de secuencias de eventos, tenemos composición de funciones, como f(g(x)) de
las clases de matemáticas.
• Una función puede tener cualquier número de argumentos, incluyendo cero, pero siempre
debe devolver un único valor.
• La definición de función proporciona un parámetro formal (un nombre) y la llamada a la
función proporciona un argumento real (un valor). Estos encajan como en un
rompecabezas. No escribas una "función" que sólo funciona para un valor particular de
argumento.
3.1. Modelo de sustitución
Vamos a ver el primer modelo computacional. Es aplicable al paradigma funcional y sirve
para formalizar cómo se comportan los programas escritos en este paradigma. Se trata del
modelo de sustitución o de reescritura.
La regla que define el modelo de sustitución para evaluar una expresión es muy sencilla:
Para aplicar un procedimiento compuesto a unos argumentos, se debe evaluar el cuerpo del
procedimiento con cada parámetro formal reemplazado por el correspondiente argumento.
Para ilustrar esta regla, vamos a definir unas funciones:
(define (double x) (+ x x))
(define (square y) (* y y))
(define (f z) (+ square (double z)) 1))
Y ahora vamos a ver qué ocurre cuando ejecutamos (f (+ 2 1)) utilizando el modelo de
sustitución:
1. Evaluamos la expresión: f es un procedimiento; qué es (+ 2 1)? --> (f 3))
2. Ahora tomamos el cuerpo de f y sustituimos 3 por z: (+ square (double 3))
1)
3. Ahora evaluamos la expresión: + es +, 1 es 1. ¿Qué es (square (double 3))?
square es un procedimiento; y ¿qué es (double 3)? double es un procedimiento y
3 es 3. Así que, una vez hemos evaluado todo, podemos empezar a aplicar los
Page 8
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.
Programación Funcional
4.
5.
6.
7.
procedimientos. Empezamos por double sustituyendo el cuerpo de la función: (+
(square (+ 3 3)) 1)
Ahora, ¿qué es (+ 3 3)? --> (+ (square 6) 1)
Ahora se sustituye el cuerpo de square: (+ (* 6 6) 1)
¿Qué es (* 6 6)? --> (+ 36 1)
¿Y (+ 36 1)? --> 37
3.2. Orden de evaluación normal vs. de aplicación
El ejemplo del modelo de sustitución que hemos visto se ha hecho utilizando el "orden de
aplicación", donde se evalúa primero todos los procedimientos y argumentos antes de
ejecutar la llamada a la función.
Otra forma de evaluar expresiones es utilizando el "orden normal": expandir completamente
los procedimientos hasta que todo está expresado mediante operaciones primitivas y
autoevaluaciones, y entonces evaluar la expresión.
El mismo problema de antes: (f (+ 2 1))
1. Expandimos f, dejando (+ 2 1) sin evaluar: (+ (square (double (+ 2 1)))
1)
2. Ahora expandimos square: (+ (* (double (+ 2 1)) (double (+ 2 1)))
1)
3. Y ahora expandimos double: (+ (* (+ (+ 2 1) (+ 2 1)) (+ 2 1) (+ 2
1))) 1)
4. Por último, expandimos todo los operadores primitivos y autoevaluamos los valores. Se
hace uno por uno
(+
(+
(+
(+
(+
(+
(+
37
(*
(*
(*
(*
(*
(*
36
(+ 3
(+ 3
(+ 3
(+ 3
6 (+
6 6)
1)
(+ 2 1)) (+ (+ 2 1) (+ 2 1))) 1)
3) (+ (+ 2 1) (+ 2 1))) 1)
3) (+ 3 (+ 2 1))) 1)
3) (+ 3 3))) 1)
3 3)) 1)
1)
Hemos visto las dos formas de evaluación: con el orden aplicativo, evaluamos
completamente todas las subexpresiones antes de aplicar el procedimiento principal.
Mientras que en el orden normal, primero expandimos completamente los procedimientos
hasta que todo está expresado mediante operaciones primitivas y autoevaluaciones. Entonces,
en uno y en otro, podemos encontrar la solución de la expresión.
En programación funcional, el orden normal y el orden aplicativo siempre devolverán el
mismo resultado.
Vamos a definir una función que debería devolver siempre 0:
Page 9
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.
Programación Funcional
(define (zero x) (- x x))
; Esta función siempre debería devolver 0.
Ahora vamos a evaluar (zero (random 10)) con orden aplicativo y con orden normal.
Orden aplicativo:
(zero (random 10))
(random 10) ==> 5
(zero 5) ---->
(- 5 5) ==> 0
0
; El orden de aplicación devuelve 0
Orden normal:
(zero (random 10))
(zero (random 10)) ---->
(- (random 10) (random 10))
(random 10) ==> 4
(random 10) ==> 8
(- 4 8) ==> -4
-4
; El orden normal no
La regla es que si estás haciendo programación funcional, obtienes las mismas respuestas sea
cual sea el orden de evaluación. ¿Por qué no sucede así en el caso de (zero (random
10))? Porque no es una función. ¿Por qué?
Eficiencia: intenta computar
(square (square (+ 2 3)))
en orden normal y de evaluación. El orden de aplicación es más eficiente proque sólo suma 2
y 3 una vez, no cuatro. (Pero más adelante, veremos que esto no es una regla general, a veces
el orden normal es más eficiente).
Page 10
Copyright © 2006 Depto. de Ciencia de la Computación e IA, Universidad de Alicante All rights
reserved.