PDF de programación - Un lenguaje que se aprende en 10 minutos - Lisp (y II)

52-56 lisp.qxd 21/11/05 09:10 Página 52

Ciencia e investigación

Un lenguaje que se aprende en 10 minutos

LLiisspp ((yy IIII))
LLiisspp ((yy IIII))

David Arroyo Menéndez, José E. Marchesi

Una de las características más
importantes de Lisp es la
extraordinaria claridad y simpleza de
su especificación.

Introducción

Lisp es uno de los lenguajes de programación más
simples que existen. Unos pocos conceptos, siete u
ocho, abarcan todo el lenguaje. Hablamos de la
especificación base del lenguaje, naturalmente.
Los distintos dialectos han ido extendiendo el len-
guaje y añadiendo nuevas construcciones. Pero, y
esto es tremendamente importante, lo han hecho
siempre utilizando esos mismos conceptos base.
Eso implica que, una vez conocidos los pocos con-
ceptos que constituyen la base del lenguaje, el lec-
tor será capaz de interpretar prácticamente cual-
quier programa Lisp.

Esta circunstancia (ser un lenguaje muy senci-
llo) permite abarcar su estudio desde un punto de
vista bastante original, y extremadamente produc-
tivo. En el aprendizaje de cualquier otro lenguaje
de propósito general se tiende (muy acertadamen-
te) a comenzar impartiendo las características a
nivel de lenguaje como léxico (cómo se escribe una
palabra reservada), sintaxis (en qué consiste una
sentencia, o una expresión) y semántica (cómo
evalúa una expresión aritmética). Una vez conoci-
dos estos aspectos del lenguaje, por lo general se
pasa a exponer las características más específicas
del entorno y, por tanto, de cómo se traducen las
semánticas expresadas en el lenguaje en una eje-
cución (las variables globales en C se inicializan a
0, cosa que no pasa con las variables locales, que
contienen un valor indefinido, por ejemplo).

En el caso de Lisp, vamos a hacerlo al revés: par-
tiendo del conocimiento de cómo funciona (o
cómo “ve el mundo”) un intérprete de Lisp, pasa-
remos a exponer los aspectos más importantes del
lenguaje.
Memoria: ¿qué hay?

Como podemos ver en la figura 1, un intérprete
Lisp mantiene dos regiones en memoria, diferen-
ciadas:

G La memoria de datos (a la derecha, en la figura).
G Un diccionario de términos, que asocia símbolos
con dos punteros (a la izquierda, en la figura).
El intérprete utiliza la memoria de datos para
almacenar todos los datos presentes en un pro-
ceso Lisp. Se trata de una memoria “idealizada”,
en el sentido de que es capaz de almacenar dis-
tintos tipos de datos (conocidos como “átomos”
en Lisp) y cada uno de ellos ocupa una sola posi-
ción. Por ejemplo, un número entero y una cade-
na de caracteres son ambos átomos y, por tanto,
ambos pueden almacenarse en una posición de la
memoria de datos (la cadena de caracteres es
atómica, y no está compuesta de partes).

El contenido de la memoria de datos está suje-
to a recolección de basura. Como veremos más
adelante, existen referencias a los elementos de
la memoria desde el diccionario de símbolos.
Cuando un átomo ya no es referenciado (ni
directa ni indirectamente) es candidato a reco-
lección de basura, y el colector de memoria mar-
cará la posición que ocupa en la memoria como
disponible.

Así pues, la memoria de datos contiene áto-
mos Lisp. Pese a que los tipos de átomos pueden
variar dependiendo del dialecto que se esté utili-
zando (Common Lisp, Emacs Lisp, Scheme, etc.)
existe un conjunto de tipos bastante estandariza-
do que podremos encontrar en cualquiera de
ellos. Veámoslos.
G NNúúmmeerrooss.. Lisp permite almacenar en la
memoria de datos átomos de tipo numérico.
Esto incluye tanto números enteros (2, 4,
32222) como reales (2.0, 4.43, 3.2222). En
forma escrita, los átomos numéricos utilizan el
léxico habitual de dígitos consecutivos, utili-
zando un punto para denotar la coma decimal.
En la figura 1 podemos ver dos átomos numé-
ricos: uno consiste en el número 1 y el otro en
el número 2.

G CCaaddeennaass ddee ccaarraacctteerreess.. En Lisp las cadenas
de caracteres son átomos, y pueden contener
cualquier carácter. En forma escrita, los áto-
mos cadena de caracteres utilizan la represen-
tación habitual de caracteres encerrados entre
comillas dobles. En la figura 1 podemos ver un
átomo de tipo cadena de caracteres en la
memoria de datos, siendo su valor “foo”.

G SSíímmbboollooss.. Los símbolos son nombres. Su
única semántica es que dos símbolos de dis-
tinto nombre se consideran como símbolos

MMUUNNDDOO

nnºº8855Linux

52

http://digital.revistasprofesionales.com

52-56 lisp.qxd 21/11/05 09:10 Página 53

Lisp (y II)

Ciencia e investigación

Figura 1. Memoria de una máquina Lisp.

distintos. En forma escrita, los símbolos
utilizan un léxico similar al de los identi-
ficadores de otros lenguajes de progra-
mación, aunque permiten la inclusión de
muchos caracteres alfanuméricos dada
la particular (y generosa) forma sintácti-
ca de Lisp, como guiones y barras. En la
figura 1 podemos ver dos átomos de tipo
símbolo, siendo sus valores a y c.
Un aspecto importante de la memoria de
datos es que, a diferencia de casi todos los
demás modelos, no contiene variables, sino
valores. Eso significa que las cajas (los áto-
mos) de las que se compone no deben verse
como “contenedores” de valores, sino como
la idealización del valor en sí. Si un progra-
ma Lisp necesita un valor numérico 0,
encontrará dicho valor numérico en una
zona de la memoria de datos. Si necesita un
22, en lugar de “sobreescribir” el valor 0, uti-
lizará el átomo de valor 22 presente en otra
zona de la memoria de datos. Como es natu-
ral, las distintas implementaciones utilizan
varias optimizaciones, ya que no es práctico
tener en la memoria de datos todos los posi-
bles valores numéricos y de cadenas de
caracteres aunque, conceptualmente, puede
considerarse que los contiene.

De esta forma, un proceso Lisp puede
almacenar valores numéricos y de cadena
de caracteres en la memoria de datos. Esto
es suficiente para efectuar operaciones
aritméticas o simbólicas. Sin embargo, es
conveniente y necesario el poder estructu-

http://digital.revistasprofesionales.com

rar los datos. En nuestro caso, necesitamos
alguna forma de construir estructuras
involucrando a átomos almacenados en la
memoria de datos. Para ello, Lisp propor-
ciona una única primitiva de estructura-
ción: los llamados pares o conses (abrevia-
tura de “cons cell”).

Los pares también son átomos Lisp, y por
consiguiente también se almacenan en la
memoria de datos. Consisten en un par de
valores, que son referencias a otros átomos
presentes en la memoria. De esta forma,
podemos construir estructuras de pares. En
la figura 1 hemos representado los conses
por dos cajitas consecutivas (que, ojo, com-
ponen un solo átomo). La primera cajita
está marcada por la palabra “car”, y la
segunda por “cdr”. En un par, el “car” es la
referencia al primer elemento del par, y el
“cdr” es la referencia al segundo elemento
del par (esta nomenclatura tan particular
obedece a motivos históricos, ya que la pri-
mera implementación de Lisp estaba escri-
ta en ensamblador, y “car” y “cdr” eran las
instrucciones ensamblador para recuperar

la primera y la segunda parte del par de la
memoria de la máquina).

Por ejemplo, en la figura 1 podemos ver
un par cuyo primer elemento es el átomo
“foo” y el segundo el átomo c.

La forma escrita de un par o “cons cell”

es la siguiente:
(car . cdr)

Donde car es el átomo referenciado por
la primera parte del par, y cdr el átomo
referenciado por la segunda parte del par.
En nuestro ejemplo (un par con “foo” y c):
(“foo” . c)

También podríamos especificar pares

relacionando dos valores numéricos:
(2 . 3.0)

O una cadena de caracteres y un valor

numérico:
(“Edad” . 25)

Y así podemos estructurar datos en Lisp,
a base de pares. El lector puede pensar:

Figura 2. Una lista compuesta de pares.

MMUUNNDDOO

53

nnºº8855Linux

52-56 lisp.qxd 21/11/05 09:10 Página 54

Ciencia e investigación

“hum, ¿sólo puedo estructurar datos en
pares?, pues vaya castaña”. Pero Lisp está
muy bien diseñado, y realmente los pares
pueden servirnos para construir cualquier
estructura de datos en la memoria. ¿Cómo
es eso posible? Si pensamos un poco en
ello, nos daremos cuenta de que los pares
también son átomos. Y si un par relaciona
dos átomos, eso implica que un par puede
contener otros pares. Luego puedo, perfec-
tamente, especificar algo como:
(“dos y tres” . (2 . 3))

Donde tenemos un par cuyo primer ele-
mento es la cadena “dos y tres” y su segun-
do elemento es otro par, cuyo primer ele-
mento es 2, y el segundo 3. Esta estructu-
ración no tiene límites. Por ejemplo, podría-
mos denotar un árbol binario compuesto de
números de la siguiente forma:
(1 . ((2 . 3) . (4 . 5)))

Donde 1 es la raíz del árbol, y 2, 3, 4 y 5

las hojas divididas en dos subárboles.

Sin embargo, el manejo de pares puede
resultar tedioso, complicado y por tanto
tendente a cometer errores. Todo ello lleva
a la idea de que, pese a ser una primitiva de
estructuración muy conveniente a efectos
de implementación, no resulta muy prácti-
ca desde el punto de vista del programador.
Para solventar este problema, Lisp define
un tipo estructurado que se implementa a
base de pares: la lista, que da nombre al
lenguaje.

Una lista está definida como una anida-
ción de pares, donde los “car” identifican los
elementos de la lista, y los “cdr” referencian al
par que contiene el siguiente elemento. Para
terminar la lista, el último “cdr” referencia a
un átomo especial: nil. La figura 2 muestra
una lista de tres átomos: a, b y c.

La forma escrita de la lista sería la

siguiente:
(a . (b . (c . nil)))

Afortunadamente, Lisp nos proporciona
una notación abreviada, que es la siguiente:
(a b c)

Es importante comp