PDF de programación - Curso de Lisp con Golden Common Lisp

Curso de Lisp

con Golden Common Lisp

Dpto. de Álgebra, Computación, Geometría y Topología

José A. Alonso

Universidad de Sevilla

Sevilla, 1990

Contenido

1 El cálculo aritmético

1.1 Los números y sus operaciones . . . . . . . . . . . . . . . . . .
1.2 Nombrar los objetos de cálculo . . . . . . . . . . . . . . . . . .
1.3 Definición de nuevas funciones . . . . . . . . . . . . . . . . . .
1.4 Variables globales y locales . . . . . . . . . . . . . . . . . . . .

1
1
4
6
8

2 El cálculo simbólico

9
2.1 La función QUOTE sobre símbolos . . . . . . . . . . . . . . .
9
2.2 Las expresiones en Lisp . . . . . . . . . . . . . . . . . . . . . . 10
2.3 La función QUOTE sobre listas . . . . . . . . . . . . . . . . . 11
2.4 Funciones de búsqueda en listas . . . . . . . . . . . . . . . . . 11
2.5 Funciones de construcción de listas
. . . . . . . . . . . . . . . 16
2.6 Funciones de modificación física de listas . . . . . . . . . . . . 18

3 El control

19
. . . . . . . . . . . . . . . . . . . . . . . . 19
3.1 Los valores lógicos
3.2 Funciones de comparación de números
. . . . . . . . . . . . . 19
3.3 Funciones de comparación de símbolos y listas . . . . . . . . . 20
3.4 Condicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4.1 La función IF . . . . . . . . . . . . . . . . . . . . . . . 22
3.4.2 La función COND . . . . . . . . . . . . . . . . . . . . 23
3.4.3 Las funciones AND y OR . . . . . . . . . . . . . . . . 26
3.4.4 Las funciones WHEN y UNLESS . . . . . . . . . . . . 27

4 La programación recursiva

28
4.1 Funciones recursivas
. . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Las funciones TRACE y UNTRACE . . . . . . . . . . . . . . 29
4.3 Aritmética entera positiva . . . . . . . . . . . . . . . . . . . . 29
4.4 La aritmética ordinaria del lisp . . . . . . . . . . . . . . . . . 35
. . . . . . . . . . . . . . 36
4.5 Simulación de primitivas sobre listas
4.6 Definición de funciones sobre listas
. . . . . . . . . . . . . . . 39

i

4.7 Funciones sobre árboles . . . . . . . . . . . . . . . . . . . . . . 43
4.8 Funciones sobre conjuntos
. . . . . . . . . . . . . . . . . . . . 44

5 La iteración en Lisp

47
5.1 El grupo PROG, GO, RETURN . . . . . . . . . . . . . . . . . 47
5.2 Las funciones DO y DO* . . . . . . . . . . . . . . . . . . . . . 51
5.3 Las funciones DOTIMES y DOLIST . . . . . . . . . . . . . . 53
5.4 La función MAPCAR . . . . . . . . . . . . . . . . . . . . . . . 56

6 Funciones anónimas

58
6.1 La función LAMBDA . . . . . . . . . . . . . . . . . . . . . . . 58
6.2 Las funciones EVERY y SOME . . . . . . . . . . . . . . . . . 59

7 Las A–listas (listas de asociación)

61
7.1 Pares punteados . . . . . . . . . . . . . . . . . . . . . . . . . . 61
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.2 A–listas

8 Las P–listas (listas de propiedades)

67
8.1 P–listas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.2 Bases de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
8.3 Programación dirigida por los datos . . . . . . . . . . . . . . . 75
8.4 Funciones con memoria . . . . . . . . . . . . . . . . . . . . . . 76

9 Lectura y escritura

81
9.1 Funciones de lectura y escritura . . . . . . . . . . . . . . . . . 81
9.2 Funciones de lectura y escritura sobre ficheros . . . . . . . . . 86

Bibliografía

94

ii

Capítulo 1

El cálculo aritmético

1.1 Los números y sus operaciones

1.1.1 Ejemplo: Primera sesión Lisp:

C> GCLISP
* 5

5
*

1.1.2 Nota: El valor de un número es dicho número.
1.1.3 Ejemplo: Segunda sesión Lisp:

; multiplica 3 por 5

; multiplica 2 por 3 y por 4

; 20 dividido por 5

; (24/3) /2

; 1/0.5

* (* 3 5)
15
* (* 2 3 4)
24
* (/ 20 5)
4.0
* (/ 5 20)
0.25
* (/ 24 3 2)
4.0
* (/ 0.5)
2.0

1.1.4 Notas:

1. Los números pueden combinarse entre sí mediante operaciones aritméticas

usando la notación prefija.

1

2. Para escribir un comentario se utiliza ; y el resto de la línea es ignorado

por el intérprete.

3. La multiplicación se representa por * y la división por /. Pueden tener

un número arbitrario de argumentos.

1.1.5 Ejemplo: Tercera sesión Lisp:

* (* (- 1 2) (+ 4 5))
-9
* (+ (+ 15 5) (- 100 45))
75

1.1.6 Notas:

1. La suma y la resta se representan por + y -, respectivamente.

2. Al efectuar una operación, LISP evalúa primero sus argumentos.

1.1.7 Ejercicio: Calcular

2(4 − 1)6

18

+ (8 − 6)7

Solución:

* (+ (* 2 (- 4 1) (/ 6 18)) (* (- 8 6) 7))
16.0
* (+ (* 2

(- 4 1)
(/ 6 18))

(* (- 8 6)

7))

16.0

1.1.8 Notas:

1. El número de niveles de operaciones puede ser elevado.

2. LISP no devuelve el resultado hasta que se cierran todos los paréntesis.

3. Conviene “formatear” las expresiones LISP para resaltar su estructura

lógica.

1.1.9 Ejemplo: Fin de sesión Lisp:

2

* (EXIT)
C>

1.1.10 Nota: Para entrar al LISP pulsar GCLISP, y para salir (EXIT).
1.1.11 Definición: Funciones numéricas:

(+ n1 n2 ... nN) devuelve el valor de la suma n1+n2+...+nN . Si N = 0,

da 0.

(+)
(+ 3)
(+ 3 7 5)
(+ 32000 32000)
(+ 32000.0 32000)

---> 0
---> 3
---> 15
---> ERROR
---> 64000.0

(1+ n) es equivalente a (+ n 1).
(- n1 n2 ... nN) devuelve el valor de n1 − n2 − ... − nN . Si N = 1, da

−n1.

(- 3)
(- 123 7 5)

---> -3
---> 111

(1- n) es equivalente a (- n 1).

(ABS n) devuelve el valor absoluto de n.

(ABS 3)
(ABS -3.6)

---> 3
---> 3.6

(* n1 n2...nN) devuelve el valor del producto n1.n2...nN . Si N = 0, da 1.

(*)
(* 3)
(* 3 7 5)
(* 32000 32000)
(* 32000.0 32000)

---> 1
---> 3
---> 105
---> ERROR
---> 1.024F+09

(/ n1 n2) devuelve el valor de dividir n1 por n2.

3

(/ 6 2)
(/ 5 2)

---> 3.0
---> 2.5

(/ n) es lo mismo que (/ 1 n); es decir, devuelve el inverso de n.

(/ 2)
(/ 0.5)

0.5
--->
---> 2.0

(MOD n1 n2) devuelve el resto de la división entera de n1 por n2.

(MOD 7 2)

---> 1

(MAX n1 ... nN) devuelve el mayor valor de n1,..., nN.

(MAX 3)
(MAX 1 2 3 4 5 2)
(MAX -2.3 7 0)

---> 3
---> 5
---> 7.0

(MIN n1 ... nN) devuelve el menor valor de n1,..., nN.

(MIN 3)
(MIN 1 2 3 4 5 2)
(MIN -2.3 7 0)

---> 3
---> 1
---> -2.3

1.1.12 Nota: También están definidas las funciones trigonométricas y ex-
ponenciales. No hay diferencia con los otros lenguajes.

1.2 Nombrar los objetos de cálculo

1.2.1 Ejemplo: Sesión con asignaciones:

* (SETQ PRECIO 80)
80
* (SETQ IVA 10)
10
* PRECIO

; PRECIO <--- 80

; IVA <--- 10

4

80
* (/ (* PRECIO IVA) 100)
8.O
* (+ 1 2 X 3)
ERROR:
Unbound variable: X
1> <Control C>
Top-Level
* (SETQ X (* 2 5))
10
* (+ 1 2 X 3 )
16
* (SETQ X 1 Y 2 Z (+ X Y))
3
* (+ X Y Z)
6

1.2.2 Definición: La función SETQ:

(SETQ SIMB-1 EXP-1 ... SIMB-N EXP-N) asigna al símbolo SIMB-
1 el valor de la expresión EXP-1,..., a SIMB-N el valor de EXP-N y
devuelve el valor de EXP-N.

1.2.3 Nota: La función SETQ modifica el entorno de cálculo.
1.2.4 Ejercicio: Calcular el valor de C después de la evaluación de la
expresión

(SETQ A 3 C (+ (SETQ B 4) (+ A B)))

Solución: 11.
1.2.5 Definición: Las funciones INCF y DECF:

(INCF s n) = (SETQ s (+ s n)).
(INCF s)
(DECF s n) = (SETQ s (- s n)).
(DECF s)

= (INCF s 1).

= (DECF s 1).

1.2.6 Ejemplo:

(SETQ X 3) ---> 3
(INCF X)
---> 4
X
---> 4
(DECF X 3) ---> 1
X
---> 1

5

1.3 Definición de nuevas funciones

1.3.1 Ejemplo: Definición de la función CUBO:

* (DEFUN CUBO (N)

(* N N N))

CUBO
* (CUBO 2)
= 8

1.3.2 Nota: La función primitiva para definir funciones es DEFUN. Una
función está determinada por su nombre [en el ej. CUBO], la lista de sus
parámetros [en el ej. N] y su cuerpo [en el ej. (* N N N)]
1.3.3 Ejemplo: Definición de la función SUMA-BINARIA:

* (DEFUN SUMA-BINARIA (X Y)

(+ X Y))
SUMA-BINARIA
* (SUMA-BINARIA 2 3)
5
* (SETQ X -1)
-1
* (SUMA-BINARIA 2 3)
5
* X
-1
* (+ (SUMA-BINARIA 2 3) X)
4
* (* (SUMA-BINARIA (+ 50 50) 1) 3)
303

1.3.4 Ejercicio: Escribir una función P2 que calcule el valor del polinomio
ax2 + bx + c. Por ejemplo,

(P2 4 3 2 2)

---> 24

Solución:

(DEFUN P2 (A B C X)

(+ (* A X X) (* B X) C))

1.3.5 Nota: La lista de parámetros de una función puede ser vacía. Por
ejemplo,

6

* (DEFUN NUMERO ()

(SETQ X (1+ X)))

NUMERO
* (SETQ X 0)
0
* (+ (NUMERO) (NUMERO) (NUMERO))
6
* X
3

; INICIALIZA X

; (+ 1 2 3)

1.3.6 Nota: La función NUMERO tiene “efecto de borde” porque altera
el entorno de cálculo. Al escribir funciones conviene evitar efectos de borde.
1.3.7 Nota: Un problema puede resolverse de forma “descendente” (de-
scomponiéndolo en otros más simples) o de forma “ascendente” (desarrollar
utilidades y combinarlas). Se aconseja la forma descendente.
1.3.8 Ejemplo: (de programación descendente) Definir la función

(MEDIA-CUADRADO X Y)

que devuelva la media de los cuadrados de X e Y.

* (DEFUN MEDIA-CUADRADO (X Y)

(MEDIA (CUADRADO X) (CUADRADO Y)))

MEDIA-CUADRADO
* (DEFUN CUADRADO (X)

(* X X))

CUADRADO
* (CUADRADO 3)
9
* (DEFUN MEDIA (X Y)

(/ (+ X Y) 2))

MEDIA
* (MEDIA 4 8)
6.0
* (MEDIA-CUADRADO 2 4)
10.0

; TEST DE CUADRADO

; TEST DE MEDIA

1.3.9 Ejercicio: Definir CUADRADO-MEDIA tal que (CUADRADO-
MEDIA X Y) sea el cuadrado de la media de X e Y. Por ejemplo,

(CUADRADO-MEDIA 2 4) ---> 9.0

Solución:

(DEFUN CUADRADO-MEDIA (X Y)

(CUADRADO (MEDIA X Y)))

7

1.4 Variables globales y locales

1.4.1 Definición: La función LET:

(LET ((VAR1 VAL1) ... (VARN VALN)) S1 ...SM) asocia a la vari-
able VAR1 el valor VAL1,..., a la variable VARN el valor VALN, calcula
las expresiones S1,..., SM, reconstruye el entorno y devuelve el valor de
SM.

1.4.2 Ejemplo:

(SETQ X 1)
---> 1
(LET ((X 2) (Y 3)) (+ X Y)) ---> 5
---> 1
X

1.4.3 Ejercicio: Definir una función F1 que calcule la media de los cuadra-
dos de las raíces de la ecuación ax2 + bx + c = 0. Por ejemplo,

(F1 1 -5 6) ---> 6.5

Solución:

(DEFUN F1 (A B C)

(LET ((AUX1 (- B))

(AUX2 (SQRT (- (* B B)

(* 4 A C))))

(AUX3 (* 2 A)))

(MEDIA-CUADRADO (/ (+ AUX1 AUX2) AUX3)

(/ (- AUX1 AUX2) AUX3))))

1.4.4 Nota: Una función puede tener el mismo nombre que una variable.
1.4.5 Ejemplo:

* (SETQ DOS 2)
2
* (DEFUN DOS ()