The Scheme-book

Lenguajes y paradigmas de la programacion

Curso 2004/2005

Jose Perez Martnez

jpm33@alu.ua.es

Universidad de Alicante
 JOSE PEREZ MARTINEZ

The Scheme-book

UNIVERSIDAD DE ALICANTE
Ttulo The Scheme-book
Autor: Jose Perez Martnez, jpm33@alu.ua.es

Este documento ha sido fruto del esfuerzo

de todos su autor.
Si tiene cualquier noticacion que
realizarle pongase en contacto con
el en su respectiva direccion
electronica.

Texto compuesto con TEX (http://www.tug.org) y

LATEX 2 (http://www.latex-project.org).
 Indice general

Indice general 3

Indice de guras 5

1. Programacion Funcional 7
1.1. Lenguajes de programacion . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. Introduccion a Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1. Expresiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2. Evaluacion de una expresion . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3. Denicion de nuevas funciones . . . . . . . . . . . . . . . . . . . . . 10
1.2.4. Quote . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.5. Algunas funciones de Scheme . . . . . . . . . . . . . . . . . . . . . 11
1.2.6. Otros ejemplos de denicion de funciones . . . . . . . . . . . . . . . 11
1.2.7. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3. Programacion Funcional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4. Modelo de sustitucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1. Orden de evaluacion normal vs. de aplicacion . . . . . . . . . . . . 15

2. Recursion 17
2.1. Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2. Procesos recursivos e iterativos . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1. Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2. Numeros de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . 23

3. Procedimientos de orden superior 25

3.1. Funciones como datos de primera clase . . . . . . . . . . . . . . . . . . . . 25
3.1.1. Funciones como argumentos . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2. Listas en Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.3. Filtro sobre elementos de una lista . . . . . . . . . . . . . . . . . . 27
3.1.4. Funciones sin nombre . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.5. Tipos de datos de primera clase . . . . . . . . . . . . . . . . . . . . 27
3.1.6. Funciones que devuelven funciones . . . . . . . . . . . . . . . . . . 27
3.2. Let . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3
4 INDICE GENERAL

4. Abstraccion de datos 29

5. Datos jerarquicos 31

6. Representacion de datos abstractos 33

7. Asignacion, estado y entornos 35

7.1. Modelo de evaluacion de entornos . . . . . . . . . . . . . . . . . . . . . . . 35
7.1.1. Conceptos previos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.1.2. Reglas para evaluar una expresion en el entorno actual . . . . . . . 35

8. Tipos de datos mutables 37

9. Programacion Orientada a Objetos 39

10.Streams 41

A. Ejemplos de clase 43
A.1. Clase 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
A.2. Clase 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.3. Clase 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.4. Clase 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.5. Clase 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.6. Clase 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.7. Clase 7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.8. Clase 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.9. Clase 9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.10.Clase 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.11.Clase 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.12.Clase 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.13.Clase 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.14.Clase 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.15.Clase 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.16.Clase 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.17.Clase 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.18.Clase 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.19.Clase 19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.20.Clase 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.21.Clase 21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.22.Clase 22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.23.Clase 23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.24.Clase 24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
A.25.Clase 25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
 Indice de guras

2.1. Calculo de f ib(5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5
6 INDICE DE FIGURAS
 Tema 1
Programacion Funcional

1.1. Lenguajes de programacion

En esta asignatura vamos a profundizar en la idea de lenguaje de programacion. Ex-
isten caractersticas comunes a todos los lenguajes de programacion? Son caractersticas
independientes del paradigma de programacion que se usa? Lo primero que debemos hacer
para poder reexionar sobre estas cuestiones es concretar algo mas que entendemos por
lenguaje de programacion.
Nuestra idea de lenguaje de programacion y de programa es la que plantean
Abelson y Sussman:

Vamos a estudiar la idea de un proceso computacional. Los procesos com-

putacionales son seres abstractos que pueblan los computadores. Al ejecutarse,
los procesos manipulan otras cosas abstractas llamadas datos. El desarrollo
de un proceso esta gobernado por un conjunto de reglas llamadas un pro-
grama. [...] Los programas que usamos para conjurar procesos son como los
encantamientos de los magos. Estan compuestos de expresiones simbolicas en
arcanos y esotericos lenguajes de programacion que prescriben las tareas
que queremos que realicen nuestros procesos. [...] El lenguaje de programacion
sirve como un marco en el que organizamos nuestras ideas sobre procesos.
(SICP, pp. 1,4)

Todo lenguaje de programacion tiene tres mecanismos para conseguir esto

expresiones primitivas, que representan las entidades mas simples que maneja el
lenguaje

mecanismos de composicion, con los que construimos elementos mas complicados a

partir de los mas sencillos

mecanismos de abstraccion, con los que los objetos compuestos puede ser nombrados
y manipulados como una unidad.

7
8 1.2. Introduccion a Scheme

1.2. Introduccion a Scheme

En la asignatura Lenguajes y Paradigmas de programacion (LPP) vamos a programar
en scheme, que es un lenguaje interpretado. Esto signica que en lugar de escibrir un
programa y luego compilarlo, vamos a poder escribir una sencilla expresion y averiguar
su valor. El interprete de scheme realiza un bucle read-eval-print con el que lee la
expresion, la evalua e imprime su resultado.

1.2.1. Expresiones
Por ejemplo si ejecuatamos en el interprete:
> 2
2
> ( 3 2)
6
> ( sqrt 4)
16
> (+ 2 3 4)
9

La sintaxis general de una expresion en scheme es:

(< f u n c i o n > <a r g1 > . . . < a r gn >)

Composicion de funciones:
(+ ( 3 4) 5)
( (+ 2 1) (/ 10 2))

Deniciones y entornos
Una caracterstica fundamental de cualquier lenguaje de programacion es la posibilidad
de denir 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 lnea del dominio en el que queremos denir el programa.
Para ser consistentes con el libro de la asignatura, el idioma que vamos a usuar para la
mayora de los nombres que inventemos sera el ingles.
Por ejemplo, si estamos escribiendo un programa de geometra, es normal que de-
namos nombres como square, point, circle, etc . . .
A que 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 contaras con lo de dar nombre a una
funcion. Por que esa forma de hablar? Por que no decir directamente denir
una funcion? Ya veras dentro de poco que realmente no es una forma de hablar...
es la forma que tiene Scheme de funcionar.
1. Programacion Funcional 9

Para denir nuevas entidades Scheme usa la forma especial define:

> ( define pi 3.1415)
pi
> pi
3.1415
> (+ p i 7 )
10.1415
> ( d ef i n e radio 10)
radio
> ( define c ircunferencia ( 2 pi radio ))
circunferencia
> circunferencia
62.8318

La forma especial define asocia un valor con un identicador. Su sintaxis es:

( d e f i n e < i d e n t i f i c a d o r > < e x p r e s i o n >)

El interprete evalua la expresion y asocia al identicador el resultado de la evalu-

acion. Podemos pensar que esta asociacion se guarda en una tabla o memoria que usa
el interprete y que se denomina entorno. Un entorno no es mas que una coleccion de
parejas (<identificador>,<valor>). El modelo de computacion que veremos mas ade-
lante, el modelo de sustitucion, no necesita el concepto de entorno. Pero cuando pasemos
al paradigma procedural sera muy importante su utilizacion. Por ejemplo, despues de
ejecutar el dene anterior, el entorno quedara como:

Identicador Valor
pi 3 1415

1.2.2. Evaluacion de una expresion

Para evaluar una expresion, Scheme sigue la siguiente regla:

Para evaluar (f oo arg1 . . . argn )

1. Si f oo es una forma especial: aplicar f oo a los argumentos sin evaluar.

Cada forma especial se aplica de una forma distinta.
2. Sino f oo solo puede ser una funcion
a) Evaluar las subexpresiones: f oo, arg1, . . . , argn
b) Aplicar el procedimiento resultante de evaluar f oo a los resultados
de evaluar arg1, . . . , argn

Por ejemplo, para evaluar (+ 2 3), Scheme evalua el 3 (resulta el numero 3), despues
el 2 (resulta el numero 2) y despues el + (resulta el procedimiento suma, que el
interprete representa como "#[...]"). Y por ultimo, aplica el procedimiento suma a 3 y
2, resultando 5.
10 1.2. Introduccion a Scheme

Puede parecer raro eso de que se evalue el +. Que signica eso? Pues 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 parametro o incluso hacer que una funcion devuelva un procedimiento.
Los parentesis signican algo. En Scheme no puedes usar parentesis a menos que vayas
a llamar a una funcion o a una forma especial. Por ejemplo, si tecleas:
(+ ( s q u a r e 2 ) ( 3 ) )

No obtendras 7. Scheme devolvera un error porque 3 no es una funcion.

1.2.3. Denicion de nuevas funciones

Y tambien se usa dene para denir una funcion, con la siguiente sintaxis (que ya veremos
que es azucar sintactico):
( d e f i n e ( < nombrefuncion > <param >)
<c u e r p o >)

Ejemplos:
( define ( square x )
( x x )) ; ; o d e f i n i c i n de una o f u n c i n
( square 5) ; ; l l a m a d a a l a o f u n c i n
( square (+ 2 3)) ; ; o c o m p o s i c i n con f u n c i o n e s d e f i n i d a s

Terminologa: el parametro formal es el nombre del argumento (x); la expresion

argumental real es la expresion utilizada en la llamada ((+ 2 3)); el valor real del argu-
mento es el valor del argumento en la llamada (5). El nombre del argumento viene de la
denicion de la funcion; el valor del argumento viene de la llamada.

1.2.4. Quote
La forma especial quote devuelve el identicador que se le pasa como argumento sin
evaluar, como el mismo identicador:
> ( quote hola )
hola
> hola
hola

La tilde () es una abreviatura de quote. Las dos expresiones anteriores son identicas.
A quote se le puede pasar como argumento un identicador o una expresion:
> ( quote ( + 1 2 ) )
(+ 1 2)
1. Programacion Funcional 11

1.2.5. Algunas funciones de Scheme

Hasta ahora hemos usado unicamente funciones numericas. Vamos a ver algunos ejem-
plos de otras funciones de Scheme.
Una caracterstica fundamental de Scheme es que es muy sencillo extender el lenguaje,
deniendo nuevas primitivas. La version estandar, limpia, de Scheme esta denida en al
R5RS. Pero en clase vamos a usar desde el principio algunas funciones que no estan
denidas en esta version estandar, como first o word. El interprete STk que hemos
puesto en la web, en su version de Windows, ya incorpora estas nuevas primitivas. Si usas
otro interprete de Scheme deberas cargar el chero simply.scm que se encuentra en la
pagina de Apuntes de la web de la asignatura :
(load "/PATH_ABSOLUTO/simply.scm")
Algunos ejemplos:
( f i r s t 274)
( b u t f i r s t 274)
( first hello )
( first hello )
( f i r s t ( bf h e l l o ))
(+ ( f i r s t 2 3 ) ( l a s t 4 5 ) )
( empty ? ( b f h ) )
( and # f # f # t )
( or # f # f # t )

Algunas consideraciones:
Aunque para Scheme un identicador (hello) no es exactamente igual
que un string ("hello"), muchas funciones de las anteriores las conside-
ran iguales
Muchas funciones son polimorcas: pueden usarse con distintos tipos de
objetos.

1.2.6. Otros ejemplos de denicion de funciones

Vamos a denir algunas funciones mas
( d e f i n e ( p l u r a l wd )
( word wd s ) )

Este sencillo plural funciona correctamente (en ingles) para la mayora de las pal-
abras (book, elephant, computer) pero no para las palabras que terminan en y. Vamos a
mejorarlo:
( define ( plural wd )
( i f ( equal ? ( l a s t wd ) y )
( word ( b l wd ) i e s )
( word wd s )))
12 1.3. Programacion Funcional

if es una forma especial que solo evalua una de las alternativas.

(Ejemplo) Pig Latin: Mueve consonantes iniciales al nal de la palabra y anade "ay";
SCHEME se convierte en EMESCHAY.
( d e f i n e ( p i g l wd )
( i f ( pldone ? wd )
( word wd ay )
( p i g l ( word ( b f wd ) ( f i r s t wd ) ) ) ) )

( d e f i n e ( pldone ? wd )
( v o w e l ? ( f i r s t wd ) ) )

( d e f i n e ( vowel ? l e t t e r )
(member ? l e t t e r ( a e i o u ) ) )

Pigl introduce recursion una funcion que se llama a ella misma . Veremos mas sobre
esto en las proximas semanas.
(Otro ejemplo): Sabes jugar a Buzz? Comienzas a contar y si tu numero es divisible
por 7 o tiene el dgito 7 tienes que decir "buzz" en lugar del numero:
( d e f i n e ( buzz n )
( cond ( ( equal ? ( r e m a i n d e r n 7 ) 0 ) buz z )
( ( member ? 7 n ) b u z z )
( else n )))

Esto introduce la forma especial cond para multiples opciones. La forma especial cond
es la gran excepcion a la regla sobre el signicado de los parentesis; las clausulas no son
llamadas.

1.2.7. Resumen
El define es el modo de abstraccion mas 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 sera muy tedioso si
tuviesemos que recordar y repetir sus detalles cada vez que queremos utilizarlos. Ademas,
los programas complejos se generan construyendo, paso a paso, objetos cada vez mas
complejos.
Asociar valores con smbolos y despues reutilizarlos, signica que debe existir algun
tipo de memoria que guarde las parejas nombre-objeto. Ese tipo de memoria se denomina
entorno (y mas concretamente, entorno global). En temas posteriores veremos que una
ejecucion puede involucrar diferentes entornos.

1.3. Programacion Funcional

El primer paradigma de programacion que vamos a ver es el paradigma de la Pro-
gramacion Funcional. En este paradigma, las funciones no tienen memoria y no dejan
1. Programacion Funcional 13

efectos colaterales, y ademas cada funcion siempre devuelve el mismo resultado para un
mismo parametro. Por ejemplo,
( square 2)
4
( square 2)
4

Si le pasamos a square el argumento 2 siempre devolvera 4. Parece algo obvio, sin

embargo en el siguiente ejemplo veras una funcion que no forma parte de la Programacion
Funcional:
( random 1 0 )
4
( random 1 0 )
7

La funcion 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 funcion.
Otro ejemplo donde se viola este principio de la Programacion Funcional. Como to-
dava no hemos visto como se hacen asignaciones en Scheme, lo vamos a escribir en C:
s t a t i c i n t iCount = 0 ;
i n t g e t C o u n t ( i n t i I n c r e m e n t ){
iCount = iCount + iIncrement ;
return iCount ;
}

count = g e t C o u n t ( 1 0 ) ; // devuelve 10
count = g e t C o u n t ( 1 0 ) ; // devuelve 20

Fjate que si llamamos a getCount dos veces se obtienen resultados distintos. Ademas
hay un efecto colateral despues de llamar a getCount: el valor de la variable iCount vara.
Resumiendo, el Paradigma de la Programacion Funcional tiene las siguientes carac-
tersticas:

Una funcion puede tener cualquier numero de argumentos, incluyendo cero, pero
siempre debe devolver un unico valor. (Supongamos que necesitamos dos. Podramos
combinarlos en uno, por ejemplo, una frase). No es una funcion a no ser que siempre
obtengas la misma respuesta para los mismos argumentos

La denicion de funcion proporciona un parametro formal (un nombre) y la llamada

a la funcion proporciona un argumento real (un valor). Estos encajan como en un
rompecabezas. No escribas una funcion que solo funciona para un valor particular
de argumento.

Las funciones no deben tener memoria ni producir efectos colaterales. Despues

de una llamada a una funcion, el sistema tiene que permanecer inalterable.
14 1.4. Modelo de sustitucion

En lugar de secuencias de eventos, tenemos composicion de funciones, como f (g(x))

de las clases de matematicas del instituto. Las representaremos gracamente con
maquinas y diagramas de funciones.

1.4. Modelo de sustitucion

Vamos a ver el primer modelo computacional. Es aplicable al paradigma funcional y
sirve para formalizar como se comportan los programas escritos en este paradigma. Se
trata del modelo de sustitucion o de reescritura.
La regla que dene el modelo de sustitucion para evaluar una expresion es muy sencilla:

Para aplicar un procedimiento compuesto a unos argumentos, se debe evaluar

el cuerpo del procedimiento con cada parametro formal reemplazado por el
correspondiente argumento.

Para ilustrar esta regla, vamos a denir unas funciones:

( d e f i n e ( double x ) (+ x x ))
( define ( square y ) ( y y ))
( d e f i n e ( f z ) (+ square ( double z ) ) 1 ) )

Y ahora vamos a ver que ocurre cuando ejecutamos (f (+ 2 1)) utilizando el modelo
de sustitucion:

1. Evaluamos la expresion: f es un procedimiento; que 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 expresion: + es +, 1 es 1. Que es (square (double 3))?

square es un procedimiento; y que es (double 3)? double es un procedimiento y 3
es 3. As que, una vez hemos evaluado todo, podemos empezar a aplicar los proced-
imientos. Empezamos por double sustituyendo el cuerpo de la funcion: (+ (square
(+ 3 3)) 1)

4. Ahora, que es (+ 3 3)? (+ (square 6) 1)?

5. Ahora se sustituye el cuerpo de square: (+ (* 6 6) 1)

6. Que es (* 6 6)? (+ 36 1)?

7. Y (+ 36 1)? 37
1. Programacion Funcional 15

1.4.1. Orden de evaluacion normal vs. de aplicacion

El ejemplo del modelo de sustitucion que hemos visto se ha hecho utilizando el orden
de aplicacion, donde se evalua primero todos los procedimientos y argumentos antes de
ejecutar la llamada a la funcion.
Otra forma de evaluar expresiones es utilizando el orden normal: expandir completa-
mente los procedimientos hasta que todo esta expresado mediante operaciones primitivas
y autoevaluaciones, y entonces evaluar la expresion.
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 ultimo, expandimos todo los operadores primitivos y autoevaluamos los valores.
Se hace uno por uno
(+ ( (+ 3 (+ 2 1)) (+ (+ 2 1) (+ 2 1))) 1)
(+ ( (+ 3 3) (+ (+ 2 1) (+ 2 1))) 1)
(+ ( (+ 3 3) (+ 3 (+ 2 1))) 1)
(+ ( (+ 3 3) (+ 3 3))) 1)
(+ ( 6 (+ 3 3)) 1)
(+ ( 6 6) 1)
(+ 36 1)
37

Hemos visto las dos formas de evaluacion: con el orden aplicativo, evaluamos comple-
tamente todas las subexpresiones antes de aplicar el procedimiento principal. Mientras
que en el orden normal, primero expandimos completamente los procedimientos hasta
que todo esta expresado mediante operaciones primitivas y autoevaluaciones. Entonces,
en uno y en otro, podemos encontrar la solucion de la expresion.
En programacion funcional, el orden normal y el orden aplicativo siempre devolveran
el mismo resultado.
Vamos a denir una funcion que debera devolver siempre 0:
( d ef i n e ( zero x ) ( x x ) ) ; Esta funcion siempre d eb er i a d ev ol v er 0

Ahora vamos a evaluar (zero (random 10)) con orden aplicativo y con orden normal.
16 1.4. Modelo de sustitucion

Orden aplicativo

( z e r o ( random 1 0 ) )
( random 10) == > 5
( z e r o 5) >
( 5 5) == > 0
0 ; E l o r d e n de a p l i c a c i o n d e v u e l v e 0

Orden normal

( z e r o ( random 1 0 ) )
( z e r o ( random 10)) >
( ( random 1 0 ) ( random 1 0 ) )
( random 10) == > 4
( random 10) == > 8
( 4 8) == > 4
4 ; E l o r d e n norma l no

La regla es que si estas haciendo programacion funcional, obtienes las mismas re-
spuestas sea cual sea el orden de evaluacion. Por que no sucede as en el caso de (zero
(random 10))? Porque no es una funcion. Por que?
Eciencia: intenta computar
( square ( square (+ 2 3)))

en orden normal y de evaluacion. El orden de aplicacion es mas eciente proque solo

suma 2 y 3 una vez, no cuatro. (Pero mas adelante, veremos que esto no es una regla
general, a veces el orden normal es mas eciente).
 Tema 2
Recursion

2.1. Recursion
En este tema vamos a hablar de la recursion. Como disenar un algoritmo recursivo?
El consejo mas importante es el que aparece en el siguiente recuadro:

CONFIA EN LA RECURSION

Esto es, para resolver un problema de forma recursiva debes:

CONFIAR EN LA RECURSION para resolver una version mas simple del problema
Obtener la solucion al problema completo a partir de la solucion de la version mas
simple

Por ejemplo, veamos el problema de saber si un caracter (por ejemplo la a) esta en

una cadena:

1. Quitamos el primer caracter de la cadena.

2. Si el caracter es la "a" devolvemos true.
3. Sino llamamos a la recursion con el resto de la cadena (un problema mas sencillo,
porque es una cadena mas corta) y devolvemos el resultado devuelto por la recursion.

Cuando para el algoritmo? Cuando el problema es lo mas simple posible y ya no se

puede simplicar mas: este es el caso base. Debemos entonces devolver un valor concreto,
la recursion ya ha terminado. En el caso del ejemplo; caso base: cadena vaca; devolvemos
f alse. Esto en Scheme es:
( d e f i n e ( elemento ? x palabra )
( cond
( ( empty ? p a l a b r a ) # f )
( ( equal ? x ( f i r s t p a l a b r a )) # t )
( e l s e ( elemento ? x ( bf palabra ) ) ) ) )

17
18 2.1. Recursion

Otro ejemplo. Veamos el problema de contar el numero de veces que un caracter (por
ejemplo la a) aparece en una cadena:

1. Quitamos el primer caracter de la cadena.

2. Llamamos a la recursion con el resto de la cadena (un problema mas sencillo, porque
es una cadena mas corta). Esta llamada nos dice que en el resto de la cadena hay n
letras a.

3. Si el primer caracter que hemos quitado es una a devolvemos n+1, sino devolvemos
n.

4. Caso base: cadena vaca. En ese caso devolvemos 0.

Esto en Scheme queda como:

( d e f i n e ( v e c e s l wd)
( i f ( empty ? wd )
0
( i f ( equal ? ( f i r s t wd ) l )
(1+ ( v e c e s l ( b f wd ) ) )
( v e c e s l ( b f wd ) ) ) ) )

Otro problema: Pig Latin. Pig Latin es una modicacion del ingles que usan los
ninos para hablar de forma divertida. Se trata de modicar una cadena moviendo todas
las consonantes (hasta la primera vocal) de su comienzo a su nal y anadiendo el sujo
ay. Por ejemplo, en castellano:

Ingles Pig Latin

chaval avalchay
curso ursocay
problema oblemapray

Aqu la solucion recursiva es algo mas complicada. La primera idea sera hacerlo como
los ejemplos anteriores:

1. Si la palabra a modicar empieza por consonante: quitar la consonante, aplicar Pig

Latin al resto de cadena.

2. Conamos en que la recursion nos devuelva el resto de cadena traducida a Pig

Latin y entonces anadimos la consonante al nal.

3. Caso base: si la cadena empieza por vocal devolver la cadena con el sujo ay
anadido.

Funciona bien esta solucion? Veamos un ejemplo. Apliquemos Pig Latin a la palabra
"problema". Nos debera devolver oblemapray. Sin embargo, el algoritmo anterior hara
lo siguiente:
2. Recursion 19

1. La palabra "problema" comienza por consonante. La quitamos y aplicamos Pig

Latin a roblema.

2. Conamos en la recursion y devuelve la palabrama traducida: oblemaray. Movemos

la "p" al nal: oblemarayp. NO ES CORRECTO.

Como habra que plantear la recursion? Si nos jamos en el ejemplo, nos daremos
cuenta de que la "p" debera estar antes del sujo ay. Esto se consigue llamando a la
recursiondespues de haber movido la consonante al nal de la cadena:

1. La palabra "problema" empieza por consonante, la quitamos y la colocamos al nal

de la palabra. Nos queda roblemap.

2. Conamos en la recursion y aplicamos Pig Latin a esta palabra. Devolvera oblemapay.

!!Correcto

La solucion en Scheme:
( d e f i n e ( p i g l wd )
( i f ( v o c a l ? ( f i r s t wd ) )
( word wd ay )
( p i g l ( word ( b f wd ) ( f i r s t wd ) ) ) ) )

Donde esta aqu la regla general? Estamos aplicando la recursion a un caso mas
sencillo? S, ya que la palabra roblemap tiene la primera vocal mas a la izquierda que
problema.
No todas las recursiones siguen este patron. En los ejemplos anteriores en el cuerpo de
la funcion se realiza una unica llamada recursiva. No siempre es as. Por ejemplo, veamos
el calculo de la serie de Fibonacci. Recordemos que la secuencia de numeros de Fibonacci
se dene con la siguiente expresion:

1, si n {0, 1}
f ib(n) =
f ib(n 1) + f ib(n 2), si n > 1
De esta forma, la secuencia de numeros de Fibonacci es: 1, 1, 2, 3, 5, 8, 13, 21, . . . La
funcion recursiva que calcula el numero n-esimo de la serie es la siguiente:
( define ( f ib n)
( cond ( ( = n 0 ) 0 )
((= n 1 ) 1 )
( e l s e (+ ( f i b ( n 1 ) )
( f i b ( n 2 ) ) ) ) ) )

La diferencia con las funciones recursivas vistas hasta ahora es que en el cuerpo de la
funcion se realizan dos llamadas recursivas. Esto genera un proceso recursivo en forma de
arbol, como se comprueba en la siguiente gura, extrada del Abelson & Sussman.
20 2.2. Procesos recursivos e iterativos

Figura 2.1: Calculo de f ib(5)

El ultimo ejemplo de funcion recursiva es el triangulo de Pascal. Cada elemento del

triangulo de Pascal es la suma de los dos numeros que hay sobre el:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
..
.
La funcion Scheme que calcula el numero de Pascal que se encuentra en una determi-
nada la y columna es la siguiente:
( d e f i n e ( p a s c a l row c o l )
( cond ( ( = c o l 0 ) 1 )
((= c o l row ) 1 )
( e l s e ( + ( p a s c a l (1+ row ) (1+ c o l ) )
( p a s c a l (1+ row ) c o l ) ) ) ) )

El proceso que genera esta funcion es un proceso que tambien tiene forma de arbol,
ya que se hacen dos llamadas recursivas dentro del cuerpo de la funcion.

2.2. Procesos recursivos e iterativos

Vamos a hablar ahora de la diferencia entre un proceso recursivo y un proceso iterativo.
Para diferenciar entre ambos tenemos que ocuparnos de describir los procesos que generan
los procedimientos de Scheme. Veamos el siguiente ejemplo:
2. Recursion 21

( d e f i n e ( count s e n t )
( i f ( empty ? s e n t )
0
(1+ ( count ( b f s e n t ) ) ) ) )

Esta funcion cuenta el numero de palabras en un frase. Es una funcion recursiva,

porque se llama a si misma en su cuerpo. Veamos el proceso que genera la funcion. Para
eso, veamos una traza:
( count a b c d e f )
(1+ ( count b c d e f ) )
(1+ (1+ ( count c d e f ) ) )
(1+ (1+ (1+ ( count d e f ) ) ) )
(1+ (1+ (1+ (1+ ( count e f ) ) ) ) )
(1+ (1+ (1+ (1+ (1+ ( count f ) ) ) ) ) )
(1+ (1+ (1+ (1+ (1+ (1+ ( count ) ) ) ) ) ) )
(1+ (1+ (1+ (1+ (1+ (1+ 0))))))
(1+ (1+ (1+ (1+ (1+ 1)))))
(1+ (1+ (1+ (1+ 2))))
(1+ (1+ (1+ 3)))
(1+ (1+ 4))
(1+ 5)
6

El proceso requiere un tiempo O(n), siendo n el numero de caracteres de la cadena.

Tambien requiere un espacio O(n), sin contar el espacio para la frase en si misma, porque
Scheme tiene que mantener el estado de n computaciones pendientes durante el proce-
samiento. Estas computaciones pendientes obligan a guardar el estado del proceso en el
momento en que se hace la llamada recursiva. Este estado se guarda en la llamada pila
de recursion, y se recupera cuando se obtiene el valor de la llamada recursiva.
El esquema muestra la evolucion del proceso generado por la funcion count. Es un
ejemplo de un proceso recursivo lineal. Cuando hemos llegado a la mitad del esquema y
calculamos (count ""), todava no hemos nalizado completamente el problema. Ten-
emos que recordar anadir 1 al resultado ses veces. Cada una de esas tareas recordadas
requiere un espacio en memoria hasta que se termina el proceso.
A continuacion presentamos un programa algo mas complicado que hace lo mismo de
distinta forma.
( d e f i n e ( count s e n t )
( d e f i n e ( i t e r wds r e s u l t )
( i f ( empty ? wds )
result
( i t e r ( b f wds ) ( 1 + r e s u l t ) ) ) )
( i t e r sent 0) )

Esta vez, no dejamos ninguna computacion en espera, no tenemos que recordar tareas
no completas; cuando alcanzamos el caso base de la recursion tenemos la respuesta al
22 2.2. Procesos recursivos e iterativos

problema completo.
( count a b c d e f )
( i t e r abcdef 0)
( i t e r bcdef 1)
( i t e r cdef 2)
( i t e r def 3)
( i t e r ef 4)
( i t e r f 5)
( i t e r 6 )
6

Este es un ejemplo de un proceso iterativo. Cuando un proceso tiene esta estructura,

Scheme no necesita memoria extra para recordar todas las cosas pendientes de terminar
a lo largo de la computacion del proceso. En otros lenguajes de programacion existen
bucles (for, while) para denir procesos iterativos. En un lenguaje funcional no existen
bucles; todo lo tenemos que hacer con llamadas recursivas. Pero en este caso es un tipo
de recursion especial, que no deja llamadas en espera. Esta recursion tambien recibe el
nombre de tail recursion o recursion por la cola.
Ambos algoritmos son equivalentes; incluso es posible construir la funcion con recursion
por la cola automaticamente a partir de la funcion recursiva (no vamos a ver como se hace;
lo dejamos para otras asignaturas).
Otros ejemplos de procesos recursivos y procesos iterativos son los siguientes.

2.2.1. Factorial

; ; f a c t o r i a l proceso re c ur s i v o

( define ( f a c t o r i a l n)
( i f (= n 1)
1
( n ( f a c t o r i a l ( n 1 ) ) ) ) )

; ; f a c t o r i a l proceso i n t e r a t i v o

( define ( f a c t o r i a l n)
( factiter 1 1 n ))

( d e f i n e ( f a c t i t e r p r o d u c t c o u n t e r maxcount )
( i f ( > c o u n t e r maxcount )
product
( f a c t i t e r ( counter product )
(+ c o u n t e r 1 )
maxcount ) ) )
2. Recursion 23

2.2.2. Numeros de Fibonacci

; ; proceso r e c u r si vo

( define ( f ib n)
( cond ( ( = n 0 ) 0 )
((= n 1 ) 1 )
( e l s e (+ ( f i b ( n 1 ) )
( f i b ( n 2 ) ) ) ) ) )

; ; proceso i t e r a t i v o

( define ( f ib n)
( fibiter 1 0 n ))

( d e f i n e ( f i b i t e r a b count )
( i f ( = count 0 )
b
( f i b i t e r ( + a b ) a ( count 1 ) ) ) )
24 2.2. Procesos recursivos e iterativos
 Tema 3
Procedimientos de orden superior

3.1. Funciones como datos de primera clase

La gran idea de esta semana es considerar a las funciones como datos. Es una idea
radical porque cambia completamente la vision mas habitual de los lenguajes de progra-
macion procedurales, donde una funcion es un proceso y hay una clara distincion entre
datos y programa.
La metafora habitual de un proceso es una receta. En esa metafora, la receta te dice
lo que hacer, pero la receta no es un ingrediente. Pero esta semana comprobaremos como
una funcion es un objeto con la misma entidad que un numero o una cadena de texto.
Compara la idea con la derivada en calculo. Es una funcion cuyo dominio y rango son
funciones, no numeros. La funcion derivada trata a funciones ordinarias como a cosas, no
como a procesos.
En la primera semana hemos visto un primer elemento para construir abstracciones:
denir procedimientos. Un procedimiento recoge un conjunto de operaciones sobre unos
argumentos y les da un nombre. Este nombre nos permite tratar al procedimiento como
una unidad y usarlo para construir a su vez otros procedimientos.
Una caracterstica esencial de Scheme y el resto de lenguajes funcionales es que con-
sidera a las funciones como datos de primera clase. Al igual que un entero o un caracter,
una funcion puede pasarse como argumento, asignarse a una variable o devolverse como
resultado de otra funcion. Esto es tan distinto al resto de lenguajes de programacion que
merece ser visto un poco mas despacio. Vamos a ver varios ejemplos y estrategias que nos
van a servir para ir entendiendo este importante concepto.

3.1.1. Funciones como argumentos

El uso de argumentos sirve para generalizar un patron determinado. Por ejemplo,
consideremos las siguientes funciones

25
26 3.1. Funciones como datos de primera clase

( define pi 3.141592654)
( define ( squarearea r ) ( r r ))
( define ( circlearea r ) ( pi r r ))
( define ( spherearea r ) ( 4 pi r r ))
( define ( hexa gon a r ea r ) ( ( s q r t 3 ) 1 . 5 r r ) )

En cada uno de estos procedimientos, estamos obteniendo el area de alguna gura

geometrica multiplicando por una constante el cuadrado de una dimension lineal (radio
o lado). Todas las funciones tienen un unico argumento, la dimension lineal. Es posible
generalizar aun mas este patron? Si nos jamos bien, nos daremos cuenta de que todas
las funciones usan la siguiente regla: elevo al cuadrado el radio (o lado) y lo multiplico
por una constante que depende de la forma de la gura.
De esta manera podemos construir una solucion mas general, deniendo una nueva
funcion area que toma dos argumentos: el radio (o lado) de la forma y el tipo de forma,
representado por un numero constante que se multiplica por el cuadrado del radio (o lado)
para devolver el area.
( define square 1)
( define c i r c l e pi )
( define sphere ( 4 pi ))
( define hexa gon ( ( s q r t 3 ) 1 . 5 ) )

( d e f i n e ( area shape r ) ( shape r r ))

Hemos denido nombres para las formas; cada nombre representa un numero constante
que se multiplica por el cuadrado del radio. Estamos generalizando un patron mediante
el uso de un numero variable en lugar de un numero constante.
Pero tambien podemos genealizar un patron en el que lo que vara es una funcion.
Veamos los dos ejemplos siguientes:
( d e f i n e ( s ums qua re a b )
( i f (> a b)
0
( + ( a a ) ( sumsquare ( 1 + a ) b ) ) ) )

( d e f i n e ( sumcube a b )
( i f (> a b)
0
( + ( a a a ) ( sumcube ( 1 + a ) b ) ) ) )

Cada una de estas funciones calcula la suma de una serie desde un numero inicial (a)
hasta un numero nal (b). Por ejemplo (sumsquare 5 8) calcula 52 + 62 + 72 + 82 . El
proceso de calcular cada termino indvidual, de anadir los terminos, y de saber cuando
parar es el mismo estemos anadiendo cuadrados de numeros o cubos de numeros. La unica
diferencia esta en decidir que funcion aplicar a cada termino. Podemos generalizar este
patron haciendo que la funcion sea un argumento adicional, de la misma forma que el
argumento number en la funcion area:
3. Procedimientos de orden superior 27

( d e f i n e ( sum f n a b )
( i f (> a b)
0
(+ ( f n a ) ( sum f n ( 1 + a ) b ) ) ) )

3.1.2. Listas en Scheme

3.1.3. Filtro sobre elementos de una lista
3.1.4. Funciones sin nombre
3.1.5. Tipos de datos de primera clase
3.1.6. Funciones que devuelven funciones

3.2. Let
Let es una forma especial de Scheme que permite llamar a una expresion (el cuerpo
del let) despues de haber declarado unos valores para unas variables que se usan en esta
expresion. Esta declaracion de valores es local a la ejecucion del let. Una vez que la
expresion del let se evalua, no se conservan esos valores. Su sintaxis es:
( l e t ( ( v a r 1 exp1 )
...
( v a r n expn ) )
)

Para evaluar el let, las expresiones exp1 . . . expn se evaluan y sus valores se asocian a
las variables var1 . . . varn . La expresion se evalua con estos valores asignados. Ejemplos:
> ( let (( x 1)
(y 2))
(+ x y ) )
3

> ( define x 5)
> ( let (( x (+ 2 1))
( y (+ x 3 ) )
(+ x y ) )
11

Dos precauciones:

1. Let no proporciona una sentencia de asignacion tal y como existen en otros lengua-
jes. La asociacion entre los nombres y los valores solo se mantienen mientras que
computamos el cuerpo del let.
28 3.2. Let

2. Si tienes mas de una pareja nombre-valor, como en este ultimo ejemplo, los calculos
no se realizan secuencialmente. Las ultimas asociaciones no dependen de las previas.

Vamos a aclarar esto ultimo explicando como se dene let en terminos de lambda:
( l e t ( ( v a r 1 exp1 )
...
( v a r n expn ) )
)

se traduce a

( ( lambda ( v a r 1 . . . v a r n ) ) exp1 . . . expn )

Esto es, se construye una funcion sin nombre con los mismos argumentos del let y se
llama a esa funcion con el resultado de evaluar las expresiones asociadas a cada argumento.
Por ejemplo:
( let (( x 1)
(y 4))
( x y ))

se traduce a

( ( lambda ( x y )
( x y )) 1 4)