las raices de lisp

7/22/2019 Las Raices de Lisp

1/13

Las Races de LispPAUL GRAHAM

Borrador, Enero 18, 2002

En 1960, John McCarthy public un notable artculo en el que hizo por la programacin algoparecido a lo que Euclides hizo por la geometra.1 Demostr cmo, dado un puado de

operadores simples y una notacin para funciones, se puede construir un lenguaje deprogramacin. Llam a este lenguaje Lisp, por "List Processing", debido a que una de susprincipales ideas era usar una estructura de datos simple llamada listtanto para el cdigo comopara los datos.

Vale la pena comprender lo que McCarthy descubri, no slo como un hito en la historia de lascomputadoras, sino como un modelo para lo que la programacin tiende a convertirse ennuestro propio tiempo. Me parece que hasta la fecha ha habido dos modelos de programacinlimpios y consistentes: el modelo C y el modelo Lisp. Estos dos se asemejan a puntos elevadossobre el terreno, con tierras bajas pantanosas entre ellos. Conforme las computadoras se hanvuelto ms potentes, los nuevos lenguajes en desarrollo se han estado moviendo de maneracontinua hacia el modelo de Lisp. Una receta popular para los nuevos lenguajes de

programacin en los ltimos 20 aos ha sido la de tomar el modelo C de la informtica yagregarle, poco a poco, partes tomadas del modelo de Lisp, tales como la escritura en tiempo deejecucin y la recoleccin de basura.

En este artculo tratar de explicar en los trminos ms simples posibles lo que McCarthydescubri. La idea no es slo conocer el interesante resultado terico descubierto hace cuarentaaos, sino demostrar hacia dnde se dirigen los lenguajes. Lo inusual de Lisp de hecho, lacaracterstica distintiva de Lisp es que se puede escribir a s mismo. Para comprender lo queMcCarthy quiso decir con esto, volveremos sobre sus pasos, con su notacin matemtica

traducida a cdigo corriente de Common Lisp.

1 Siete Operadores Primarios

Para empezar, definimos una expresin. Una expresin es ya sea un atom, que es una secuenciade letras (por ejemplo: foo) o una lista de cero o ms expresiones, separadas por espacio en

blanco y encerradas por parntesis. Estas son algunas expresiones:

foo

()(foo)(foo bar)(a b (c) d)

La ultima expresin es una lista de cuatro elementos, la tercera de las cuales es en si misma unalista de un elemento.

1Recursive Functions of Symbolic Expressions and Their Computation byMachine, Part I Communications of the ACM3:4, Abril 1960, pp. 184-195.

1


2/13

En aritmtica la expresin 1+1 tiene un valor de 2. Las expresiones de Lisp validas tambintienen valores. Si una expresin e arroja un valorv decimos que e devuelve v.Nuestro siguientepaso es definir qu tipos de expresiones puede haber, y qu valor devuelve cada una.

Si una expresin es una lista, llamamos al primer elemento el operadory a los elementosrestantes los argumentos. Vamos a definir siete operadores primarios (en el sentido de losaxiomas):quote, atom, eq, car, cdr, cons,ycond.

1. (quote x)devuelvex. Por facilidad de lectura abreviaremos(quote x)como x.

>(quote a)

a> aa> (quote (a b c))(a b c)

2. (atom x) devuelve el atomtsi el valor dex es un atom o la listavaca. De lo contrario regresa(). En Lisp por lo general usamos el atomtpara

representar verdadero, y la lista vaca para representar falso.

> (atom a)t>(atom (a b c))()> (atom ())t

Ahora que tenemos un operador cuyo argumento es evaluado podemos mostrar paraqu sirvequote. Al ponerquotea una lista la protegemos de ser evaluada. Unalista sin quoteque se da como argumento a un operador comoatomes tratadacomo cdigo:

> (atom (atom a))t

mientras que una lista a la que se le aplicquotees tratada como una simple lista,en este caso, una lista de dos elementos:

> (atom (atom a))()

Esto es igual a la manera en que usamos las comillas en Ingls. Cambridge es unpueblo en Massachusetts que tiene cerca de 90,000 personas. Cambridge es unapalabra que contiene nueve letras.

2


3/13

Quote puede parecer un concepto extrao, porque muy pocos otroslenguajes tienen algo parecido. Esta estrechamente ligada a una delas caractersticas ms distintivas de Lisp: el cdigo y los datos secomponen de las mismas estructuras de datos, y el operador quotees la manera en que distinguimos entre ellos.

3. (eq x y)devuelvetsi los valores dexyyson el mismo atom o siambos son la lista vaca, de otra manera devuelve ().

> (eq a a)

t> (eq a b)()> (eq () ())t

4. (car x)espera que el valor dex sea una lista, y devuelve su primer elemento

> (car (a b c))

a

5. (cdr x) espera que el valor dexsea una lista, y devuelve tododespus del primer elemento.

> (cdr (a b c))(b c)

6. (cons x y)espera que el valor deysea una lista, y devuelve unalista que contiene el valor dex seguido por los elementos del valor dey.

> (cons 'a '(b c))(a b c)> (cons 'a (cons 'b (cons 'c '())))(a b c)> (car (cons 'a '(b c)))a> (cdr (cons 'a '(b c)))(b c)

7. (cond (p1e1)...(pnen)) es evaluado como sigue. Las expresionesp sonevaluadas en orden hasta que una devuelve t. Cuando se encuentra una, el valor de

la correspondiente expresin e es devuelto como el valor de la totalidad de laexpresincond.

> (cond ((eq 'a 'b) 'first)((atom 'a) 'second))

second

3


4/13

En cinco de nuestros siete operadores primarios, los argumentos son siempre evaluados cuandouna expresin que empieza con ese operador es evaluada.2 Llamaremos a un operador de ese

tipo unafuncin.

2 Denotando Funciones

Enseguida definimos una notacin para describir funciones. Una funcin es expresada como(lambda (p1...pn) e)dondep1...pnson atoms (llamadosparmetros)y e es unaexpresin. A una expresin cuyo primer elemento es tal expresin

((lambda (p1...pn) e) a1...an)

se le denomina llamada a funcin y su valor se calcula de la siguiente manera. Cada expresinai es evaluada. Luego e es evaluada. Durante la evaluacin de e, el valor de cualquierocurrencia de una de laspi es el valor de la ai correspondiente en la ms reciente llamada afuncin.

> ((lambda (x) (cons x '(b))) 'a)

(a b)

> ((lambda (x y) (cons x (cdr y)))

'z

'(a b c))

(z b c)

Si una expresin tiene un atomfcomo su primer elemento que no sea uno de los operadoresprimarios

(f ai...an)

y el valor defes una funcin(lambda (p1...pn) e)entonces el valor de la expresin es

el valor de

((lambda (p1...pn) e) a1...an)

En otras palabras, los parmetros pueden ser usados como operadores en expresiones lo mismoque como argumentos:

> ((lambda (f) (f '(b c)))

'(lambda (x) (cons 'a x)))

(a b c)

Hay otra notacin para funciones que habilita la funcin para referirse a si misma, dndonospor lo tanto una manera conveniente para definir funciones recursivas.3

2Las expresiones que empiezan con los otros dos operadores, quote y cond, son evaluados de manera diferente. Cuandouna expresin quote es evaluada, su argumento no es evaluado, sino que slo es devuelto como el valor total de laexpresin quote. Y en una expresin cond valida, solo una ruta de subexpresiones en forma de L ser evaluada.3Lgicamente, no necesitamos definir una nueva notacin para esto. Podemos definir funciones recursivas en nuestranotacin existente utilizando una funcin de las funciones denominada el combinador Y. Puede que McCarthy no supiera

del combinador Y cuando escribi este documento; de cualquier manera, la notacin label es ms fcil de leer.

4


5/13

La notacin

(label f (lambda (p1...pn) e))

denota una funcin que se comporta como(lambda (p1...pn) e), con la propiedad

adicional que una ocurrencia defdentro de e evaluara a la expresin label, como siffuera unparmetro de la funcin.

Supn que queremos definir una funcin(subst x y z), que toma una expresinx, un atomy, y una listaz, y devuelve una lista comozpero con cada instancia dey (a cualquier nivel deanidamiento) enzreemplazada porx.

>(subst 'm 'b '(a b (a b c) d))

(a m (a m c) d)

Podemos denotar esta funcin como

(label subst (lambda (x y z)

(cond ((atom z)

(cond ((eq z y) x)

('t z)))

('t (cons (subst x y (car z))

(subst x y (cdr z)))))))

Abreviaremosf=(label f (lambda (p1...pn) e))como

(defun f (p1...pn) e)

por tanto

(defun subst (x y z)

(cond ((atom z)

(cond ((eq z y) x)

('t z)))

('t (cons (subst x y (car z))

(subst x y (cdr z))))))

Incidentalmente, aqu vemos como obtener una clusula por defecto en una expresincond.

Una clusula cuyo primer elemento estsiempre tendr xito. As

(cond (x y) (t z))

es equivalente a lo que podramos escribir en un lenguaje con sintaxis como

if x then y else z

3 Algunas Funciones

Ahora que tenemos una manera de expresar funciones, definimos unas nuevas en funcin denuestros siete operadores primarios. Primero ser conveniente introducir algunas abreviaciones

5


6/13

para patrones comunes. Usaremoscxr, dondexes una secuencia deas ods, como unaabreviacin para la correspondiente composicin decar ycdr. As por ejemplo (cadr e)es una abreviacin para(car (cdr e)), que devuelve el segundo elemento dee.

> (cadr '((a b) (c d) e))

(c d)

> (caddr '((a b) (c d) e))

e

> (cdar '((a b) (c d) e))

(b)

Asimismo, utilizaremos (list e1...en)para

(cons e1 ... (cons en()) ... ).

> (cons 'a (cons 'b (cons 'c '())))

(a b c)

> (list 'a 'b 'c)

(a b c)

Ahora definimos algunas funciones nuevas. Cambi los nombres de estas funciones agregandopuntos al final. Esto distingue las funciones primarias de aquellas definidas en funcin de estas,y tambin evita conflictos con funciones existentes de Common Lisp.

1.(null. x) comprueba si su argumento es la lista vaca.

(defun null. (x)

(eq x '()))

> (null. 'a)

()

> (null. '())t

2.(and. xy)devuelve t si ambos de sus argumentos lo hacen y de lo contrario ().

(defun and. (x y)(cond (x (cond (y 't) ('t '())))

('t '())))

> (and. (atom 'a) (eq 'a 'a))t> (and. (atom 'a) (eq 'a 'b))()

3.(not. x)devuelvetsi su argumento regresa(), y ()si su argumento devuelve

t.

6


7/13

(defun not. (x)

(cond (x '())

('t 't)))

> (not. (eq 'a 'a))

()

> (not. (eq 'a 'b))

t

4.(append. x y)toma dos listas y devuelve su concatenacin.

(defun append. (x y)(cond ((null. x) y)

('t (cons (car x) (append. (cdr x) y)))))

> (append. '(a b) '(c d))

(a b c d)

> (append. '() '(c d))

(c d)

5.(pair. x y)toma dos listas de la misma longitud y devuelve una lista de listas dedos elementos que contienen pares sucesivos de un elemento de cada una.

(defun pair. (x y)

(cond ((and. (null. x) (null. y)) '())

((and. (not. (atom x)) (not. (atom y)))

(cons (list (car x) (car y))

(pair. (cdr) (cdr y))))))

> (pair. '(x y z) '(a b c))((x a) (y b) (z c))

6.(assoc. x y)toma un atomxy una listayde la forma creada porpair., y

devuelve el segundo elemento de la primera lista enycuyo primer elemento esx.

(defun assoc. (x y)

(cond ((eq (caar y) x) (cadar y))

('t (assoc. x (cdr y)))))

> (assoc. 'x '((x a) (y b)))

a

> (assoc. 'x '((x new) (x a) (y b)))

new

7


8/13

4 La Sorpresa

Por tanto podemos definir funciones que concatenan listas, substituyen una expresin por otra,

etc. Una notacin elegante, tal vez, pero y qu? Ahora viene la sorpresa. Resulta que tambinpodemos escribir una funcin que funciona como interprete para nuestro lenguaje: una funcinque toma como argumento cualquier expresin Lisp, y devuelve su valor. Aqu esta:

(defun eval. (e a)

(cond

((atom e) (assoc. e a))

((atom (car e))

(cond

((eq (car e) 'quote) (cadr e))((eq (car e) 'atom) (atom (eval. (cadr e) a)))

((eq (car e) 'eq) (eq (eval. (cadr e) a)

(eval. (caddr e) a)))

((eq (car e) 'car) (car (eval. (cadr e) a)))

((eq (car e) 'cdr) (cdr (eval. (cadr e) a)))

((eq (car e) 'cons) (cons (eval. (cadr e) a)

(eval. (caddr e) a)))

((eq (car e) 'cond) (evcon. (cdr e) a))

('t (eval. (cons (assoc. (car e) a)

(cdr e))

a))))

((eq (caar e) 'label)

(eval. (cons (caddar e) (cdr e))

(cons (list (cadar e) (car e)) a)))

((eq (caar e) 'lambda)

(eval. (caddar e)

(append. (pair. (cadar e) (evlis. (cdr e) a))

a)))))

(defun evcon. (c a)

(cond ((eval. (caar c) a)

(eval. (cadar c) a))

('t (evcon. (cdr c) a))))

(defun evlis. (m a)

(cond ((null. m) '())

('t (cons (eval. (car m) a)

(evlis. (cdr m) a)))))

La definicin deeval. es ms larga que cualquiera de las otras que hemos visto antes.

Analicemos como funciona cada parte.

La funcin toma dos argumentos: e, la expresin a ser evaluada, y a, una lista que representa

los valores que se le han dado a los atoms al aparecer como parmetros en las llamadas afuncin.

8


9/13

A esta lista se le llama el entorno y es del tipo creada porpair..Fue con la intencin de

construir y buscar estas listas que escribimos pair. yassoc..

La espina dorsal deeval.es una expresincondcon cuatro clusulas. Cmo evaluamos

una expresin depende de que tipo sea. La primera clusula maneja atoms. Si e es un atom,

buscamos su valor en el entorno:

> (eval. 'x '((x a) (y b)))

a

La segunda clusula deeval.es otracondpara manejar expresiones de la forma(a),

donde aes un atom. Esta incluye todos los usos de los operadores primarios, y hay unaclusula para cada uno.

> (eval. '(eq 'a a) '())

t

> (eval. '(cons x '(b c))

'((x a) (y b)))

(a b c)

Todos estos (exceptoquote) llaman aeval.para encontrar el valor de los argumentos.

Las ltimas dos clusulas son ms complicadas. Para evaluar una expresincondllamamos a

una funcin auxiliar denominada evcon., que se abre camino a travs de las clusulas

recursivamente, buscando una en la que el primer elemento devuelvat. Cuando encuentra tal

clusula devuelve el valor del segundo elemento.

> (eval. '(cond ((atom x) 'atom)

('t 'list))

'((x '(a b))))

list

La ltima parte de la segunda clusula deeval. maneja llamadas a funcin que han sido

pasadas como parmetros. Funciona reemplazando al atom con su valor (que debe ser una

expresin lambdao label) y evaluando la expresin resultante. Entonces

(eval. '(f '(b c))

'((f (lambda (x) (cons 'a x)))))

se convierte a

(eval. '((lambda (x) (cons 'a x)) '(b c))

'((f (lambda (x) (cons 'a x)))))

que devuelve (a b c).

Las ltimas dos clusulas eneval. manejan llamadas a funcin en las que el primer elemento

es de hecho una expresinlambdaolabel. Una expresinlabeles evaluada al forzar

9


10/13

una lista del nombre de la funcin y la funcin en si misma al entorno, y llamando luego a

eval. en una expresin con la expresin interiorlambdasustituida por la expresin

label. Es decir,

(eval. '((label firstatom (lambda (x)

(cond ((atom x) x)

('t (firstatom (car x))))))

y)

'((y ((a b) (c d)))))

se convierte en

(eval. '((lambda (x)

(cond ((atom x) x)

('t (firstatom (car x)))))

y)

'((firstatom

(label firstatom (lambda (x)

(cond ((atom x) x)

('t (firstatom (car x)))))))

(y ((a b) (c d)))))

que eventualmente devuelvea.

Finalmente, una expresin de la forma((lambda (p1...pn) e) a1...an) es evaluada

llamando en primer lugarevlis. para obtener una lista de valores(v1 ... vn)de los

argumentosa1...an, y evaluando luego e con (p1v1) ... (pn vn) aadido al frente del

entorno. Entonces

(eval. '((lambda (x y) (cons x (cdr y)))

'a

'(b c d))

'())

se convierte en

(eval. '(cons x (cdr y))

'((x a) (y (b c d))))

que eventualmente devuelve(a c d).

5 Repercusiones

Ahora que entendemos como funcionaeval, demos un paso atrs y consideremos lo que

significa. Lo que tenemos aqu es un extraordinariamente elegante modelo de computacin.Utilizando slo quote, atom, eq, car, cdr, cons, ycond, podemos definir una funcin,

eval., que en realidad implementa nuestro lenguaje, y luego utilizando eso podemos definir cualquier

funcin adicional que queramos.

10


11/13

Ya haba modelos de computacin, por supuesto el ms notable la Maquina de Turing. Peroleer los programas de la Maquina de Turing no es muy edificante. Si quieres un lenguaje paradescribir algoritmos, puede que desees algo ms abstracto, y esa fue una de las metas deMcCarthy al definir Lisp.

El lenguaje que defini en 1960 careca de mucho. No tiene efectos secundarios, no tieneejecucin secuencial (que de cualquier manera slo es til con efectos secundarios), no tienenmeros prcticos4 ni mbito dinmico. Pero sorprendentemente estas limitaciones pueden serremediadas con muy poco cdigo adicional. Steele y Sussman muestran como hacerlo en unfamoso articulo llamado The Art of the Interpreter.5

Si comprendes el eval de McCarthy, comprendes ms que slo una etapa en la historia de los

lenguajes. Estas ideas son todavia el ncleo semntico de Lisp hoy en da. As que estudiar el

articulo original de McCarthy nos muestra, en cierto sentido, lo que Lisp es realmente. No estanto algo que McCarthy diseara como algo que descubri. No es intrnsecamente un lenguaje

para IA o prototipado rpido, o cualquier otra tarea de ese nivel. Es lo que obtienes (o una cosaque obtienes) cuando tratas de axiomatizar la computacin.

Con el tiempo, el lenguaje promedio, queriendo decir con esto el lenguaje utilizado por elprogramador promedio, ha crecido consistentemente hasta acercarse a Lisp. As que alcomprenderevalestas comprendiendo lo que probablemente ser el principal modelo de

computacin en el futuro.

4Es posible hacer aritmtica en el Lisp de 1960 de McCarthy utilizando por ejemplo una lista de n atoms para representar elnumero n.5Guy Lewis Steele, Jr. y Gerald Jay Sussman, The Art of the Interpreter, o the Modularity Complex (Partes Cero, Una y

Dos), MIT AI Lab Memo 453, Mayo 1978.

11


12/13

Notas

Al traducir las notaciones de McCarthy a cdigo funcional he tratado de cambiar lo menos

posible. Estuve tentado a hacer el cdigo ms fcil de leer, pero quise conservar el sabor deloriginal.

En el articulo de McCarthy falso es representado porf, no por la lista vaca. Utilice() para

representar falso para que los ejemplos funcionaran en Common Lisp. En ningn lugar elcdigo depende en que ocurra falso para que tambin sea la lista vaca; nada esta nunca encontra sobre el resultado devuelto por un predicado.

Me salt el construir listas a partir de pares de puntos, porque no los necesitas para comprender

eval.Tambin me salt mencionarapply, aunque fueapply (una forma muy temprana

de ella, cuyo propsito principal era aplicar comillas a los argumentos) lo que McCarthy llamoen 1960 la funcin universal; evalera entonces solo una subrutina queapplyllamaba para

realizar todo el trabajo.

Defin alisty loscxrs como abreviaciones porque as es como McCarthy lo hizo. De

hecho los cxrs podan haber sido todos definidos como funciones ordinarias. Iguallistsi

modificbamoseval, lo que podramos hacer fcilmente, para permitir que las funciones

tomaran cualquier cantidad de argumentos.

El articulo de McCarthy slo tenia cinco operadores primarios. Utilizcondyquotepero

pudo haber pensado en ellos como parte de su metalenguaje. De igual forma no defini losoperadores lgicos andynot, pero esto no es tanto problema porque las versiones adecuadas

pueden ser definidas como funciones.

Al definireval.llamamos otras funciones comopair.yassoc., pero cualquier llamada

a alguna de las funciones que definimos en funcin de los operadores primarios puede ser

reemplazada por una llamada a eval.. Es decir,

(assoc. (car e) a)

pudo haber sido escrita como

(eval. '((label assoc.

(lambda (x y)

(cond ((eq (caar y) x) (cadar y))

('t (assoc. x (cdr y))))))

(car e)

a)

(cons (list 'e e) (cons (list 'a a) a)))

Haba un pequeo error en eleval.de McCarthy. La lnea 16 era (equivalente a)

(evlis. (cdr e) a)en lugar de slo(cdr e), lo que provocaba que los argumentos

en una llamada a funcin nombrada fuera evaluada dos veces. Lo cual sugiere que esta

12


13/13

descripcin de eval. todava no haba sido implementada en el lenguaje de maquina IBM

704 cuando el articulo fue enviado. Tambin demuestra lo difcil que es estar seguro de lalongitud correcta de cualquier programa sin ejecutarlo primero.

Encontr otro problema en el cdigo de McCarthy. Despus de dar la definicin deevalpasaa dar algunos ejemplos de funciones de orden superiorfunciones que toman otras funciones

como argumentos. l definemaplist:

(label maplist

(lambda (x f)

(cond ((null x) '())

('t (cons (f x) (maplist (cdr x) f))))))

luego lo utiliza para escribir una sencilla funcindiffpara diferenciacin simblica. Perodiffpasa amaplistuna funcin que utilizaxcomo un parmetro, y la referencia a este es capturada por

el parmetro xdentro demaplist.6

Es un elocuente testimonio a los peligros del mbito dinmico que incluso ya el primer ejemplo defunciones Lisp de orden superior estaba roto debido a ello. Puede ser que McCarthy no estuvieracompletamente consciente de las implicaciones del mbito dinmico en 1960. El mbito dinmicopermaneci en implementaciones Lisp por un periodo sorprendentemente largohasta que Sussman ySteele desarrollaron Scheme en 1975. El mbito lxico no complica mucho la definicin de eval, pero

puede hacer ms difcil escribir compiladores.

6Los programadores Lisp de hoy da usaran mapcar aqu en lugar de maplist. Este ejemplo clarifica un misterio: porque

maplist esta en Lisp para empezar. Era la funcin de mapeo original, y mapcar una adicin posterior.

Traducido de The Roots of Lisp por Paul Graham. Traduccin: Armando Alvarez con la colaboracin de Alonso Soto yHanedi Salas

13

las raices de lisp

Documents