As raízes de Lisp

As raízes de Lisp, adaptação pessoal do artigo de Paul Graham -- The roots of LISP

Em 1960 John McCarthy publicou um artigo espantoso no qual fez para a programação o mesmo que Euclides fez para a geometria (Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, Communications of the ACM 3:4, April 1960, pp. 184-195). Mostrou como construir, dado uma mão cheia de operadores simples e uma notação para funções, uma linguagem de programação completa. Denominou-a de Lisp, abreviatura de List Processing, porque a ideia principal era usar uma estrutura simples para os dados e para o código, uma lista.

Neste texto¹ tentarei explicar de uma maneira simples o que McCarthy descobriu. O objectivo não é só o de aprender um resultado teórico importante que alguém descobriu à quarenta anos atrás, mas mostrar em como aprendendo LISP se aprende também muito do que se faz em muitas outras linguagens de programação desenolvidas hoje. A coisa pouco usual do Lisp — de facto, a qualidade que o define — é que se escreve a si mesmo. Para se entender o que McCarthy quer dizer com isto, vamos repetir os seus passos, traduzindo a sua notação matemática, embora a matemática nunca esteja muito longe, em código Common Lisp.

Sete operadores primitivos

Para começar, definimos o que se entende por expressão. Uma expressão é um átomo, que é uma sequência de letras (por exemplo: foo), ou uma lista de zero ou mais expressões, separadas por espaços em branco e enquadradas por parêntesis. De seguida mostram-se várias expressões:

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

A última expressão é uma lista de quatro elementos, o terceiro dos quais é uma lista de um elemento.

Em aritmética a expressão 1+1 tem o valor 2. Uma expressão válida de Lisp também tem um valor. Se uma expressão e tem o valor v dizemos que e return v. O passo seguinte é definir que tipo de expressões podem existir e que tipo de valor têm.

Se uma expressão é uma lista, chamamos ao primeiro elemento da lista operador, e os restantes elementos argumentos. Vamos, no que se segue, definir sete operadores primitivos (no sentido de axiomas): quote, atom, eq, car, cdr, cons, e cond.

quote

(quote x ) retorna x. Para uma leitura mais simples abreviamos (quote x) por 'x.

> (quote a)
a
> 'a
a
> (quote (a b c))
(a b c)

atom

(atom x) retorna o átomo t se o valor de x é um átomo ou a lista vazia (). Em Lisp convenciona-se usar o átomo t como representando o valor lógico verdade, e a lista vazia como o valor lógico falso.

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

Agora que temos um operador cujo argumento é avaliado podemos mostrar para que é que quote serve. Através de quoting (Nota do tradutor: não vou traduzir quote por citação de modo a que não se perca o sentido em Inglês da frase) uma lista protegemo-la de ser avaliada. Uma lista unquoted como argumento de um operador, como por exemplo atom, é tratada como código:

> (atom (atom ' a))
> t

enquanto uma lista quoted é tratada como uma mera lista, neste caso uma lista de dois elementos

> (atom '(atom 'a))
()

Isto corresponde à maneira de usar citações em Inglês (Nota do tradutor: ver o que se passa em PT). Cambridge é uma cidade de Massachusetts que contém cerca de 90.000 habitantes. "Cambridge" é uma palavra de nove letras.

quote pode parecer um conceito estranho, não há muitas línguas com coisa semelhante. Está intimamente ligado a uma das características distintivas de Lisp: o código e os dados são feitos de uma mesma estrutura, e o operador quote é uma maneira de distinguir os dois.

eq

(eq x y) retorna t se os valores de x e y são o mesmo átomo ou ambos uma lista vazia, e () caso contrário.

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

car

(car x) espera que o valor de x seja uma lista, e retorna o seu primeiro elemento.

> (car '(a b c))
a

cdr

(cdr x ) espera que o valor de x seja uma lista, e retorna o resto da lista a seguir do primeiro elemento.

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

cons

(cons x y) espera que o valor de y seja uma lista, e retorna uma lista contendo o valor de x seguido dos elementos valor de y.

> (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)

cond

(cond (p1 e1) ... (pn en)) é avaliado da seguinte forma. As expressões p são avaliadas até que uma retorna t. Quando uma é encontrada, o valor correspondente da expressão e é retornado como o valor total da expressão cond.

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

Os argumentos de cinco dos sete operadores primitivos anteriores são avaliados quando uma expressão com esse operador é avaliado. Chamaremos a esses operadores funções.

Denotando funções

De seguida definimos a notação para a descrição de funções.

Uma função é representada por ((lambda (p1 ... pn) e) a1 ... an), onde p1 ... pn são átomos (chamados parâmetros) e e é uma expressão. Uma expressão cujo primeiro elemento é uma expressão

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

é chamada de função e o seu valor é calculado da seguinte forma. Cada expressão ai é avaliada. Depois e é avaliada. Durante a avaliação de e, o valor de qualquer ocorrência de qualquer um dos pi é o valor do ai correspondente na mais recente chamada da função.

> ((lambda (x) (cons x '(b))) 'a)
(a b)
> ((lambda (x y) (cons x (cdr y))) 'z '(a b c))
(z b c)

Se uma expressão tem como primeiro elemento um átomo f que não é um dos operadores primitivos (f a1 ... an) e o valor de f é uma função (lambda (p1 ... pn)e) então o valor da expressão é o valor de ((lambda( p1 ... pn)e) a1 ... an).

Por outras palavras, os parâmetros podem ser usados com expressões assim como argumentos

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

Existe outra notação para funções que permite que uma função se chame a si própria, permitindo assim de uma forma conveniente definir funções recursivas (definidas por recorrência) (não é necessário definir uma nova notação para isto. Poderia-mos definir funções recursivas com nossa notação através de do construtor Y. McCarthy poderia não conhecer o Y construtor na altura em que escreveu o artigo; de qualquer modo, a notação label é de leitura mais simples).

A notação label f (lambda (p1 ... pn) e) denota a função que se comporta como lambda (p1 ... pn) e), com a propriedade adicional que uma ocorrência de f dentro de e avaliará a expressões label, como se f fosse um parâmetro da função.

Suponhamos que queremos construir uma função subst(x y z), que toma uma expressão x, um átomo y e uma lista z, e retorna uma lista tipo z onde cada instância y (em qualquer nível) é substituída em z por x.

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

Podemos escrever esta função 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)))))))

Vamos abreviar f (label f (lambda (p1 ... pn)e)) por (defun f(p1 ... pn e)) e logo ficamos com

(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))))))

Acidentalmente, podemos ver que uma condição definida por omissão numa expressão cond. Uma condição cujo primeiro elemento é 't é sempre executada. Assim (cond (x y) ('t z)) é equivalente aquilo que se poderia escrever numa outra linguagem com sintaxe if x then y else z.

Algumas funções

Agora que temos uma maneira de expressar funções, podemos definir novas em termos dos nossos sete operadores primitivos. Em primeiro lugar é conveniente introduzir algumas abreviaturas. Vamos usar cxr, como uma sequência de a ou d, correspondendo a composição de car e cdr. Por exemplo (cadr e) é uma abreviatura de (car (cdr e)), que retorna o segundo elemento de e.

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

Vamos também usar (list e1 ... en) para significar (cons e1 (cons e2 (...(cons en'())))).

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

Vamos definir, no que se segue, novas funções. De modo a distingui-las daquelas que já estão definidas em Commnon Lisp alterou-se os nomes das funções que se seguem introduzindo um ponto o fim.

null

(null. x) testa se o seu argumento é uma lista vazia.

(defun null. (x)
  (eq x '()))

> (null. 'a)
()
> (null. '())
t

and

(and. x y) retorna t se ambos os argumentos o são, () caso contrário.

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

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

not

(not. x) retorna t se o seu argumento é (), e () se o seu argumento é t.

(defun not. (x)
  (cond (x '())
        ('t 't)))

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

append

(append. x y) toma duas listas e retorna a sua concatenação.

(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)

pair

(pair. x y) toma duas listas com o mesmo comprimento e retorna uma lista de listas de dois elementos, com pares de formados com elementos de cada uma das listas iniciais.

(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 x) (cdr y))))))

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

assoc

(assoc. x y) toma um átomo x e uma lista y da forma criada por pair., e retorna o segundo elemento da primeira lista de y que contém x como primeiro elemento.

(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

A surpresa

Assim conseguimos definir funções que concatenam listas, substituem uma expressão por outra, etc. Talvez seja apenas uma notação elegante, e depois? Agora chega a surpresa. Podemos também escrever uma função que funciona como um interpretador da nossa linguagem: uma função que tem como argumento uma expressão de Lisp, retornando o seu valor. Aqui está ela:

(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)))))

A definição de eval. é bastante maior do que as definições que vimos anteriormente. Vamos estuda-la em mais detalhe e por partes.

A função tem dois argumentos: e, a expressão a ser avaliada, e a, uma lista que representa os valores que os átomos que aparecem como parâmetros das chamadas das funções. Esta última lista é chamada de ambiente, e é da forma da listas criadas por pair. e assoc..

A parte principal da função eval. é a expressão cond. que tem quatro condições (clausulas). A avaliação de uma expressão depende de qual é usada. A primeira clausula trata de átomos. Se e é um átomo, procuramos o seu valor no ambiente:

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

A segunda clausula de eval. é um outro cond que trata de expressões da forma (a ...), onde a é um átomo. Estas incluem todos os tipos de operadores primitivos, e há uma clausula para cada um deles.

> (eval. '(eq 'a 'a) '())
t
> (eval. '(cons x '(b c))
         '((x a ) (y b)))
(a b c)

Todos eles (excepto quote) chamam eval. para determinar o valor dos seus argumentos.

As duas últimas clausulas são mais complicadas. Para avaliar uma expressão cond chamamos uma função subsidiária evcon., que percorre as clausulas de uma forma recursiva, procurando o primeiro elemento que retorna t. Quando o encontra tal clausula retorna o valor do segundo elemento.

> (eval. '(cond ((atom x) 'atom)
                 ('t 'list))
         '((x '(a b))))
list

A parte final da segunda clausula de eval. trata das chamadas das funções que são passadas como parâmetros. Funciona substituindo o átomo pelos seu valor (que deverá ser uma expressão lambda ou label)) avaliando o resultado da expressão. Assim

(eval. '(f '(b c))
       '((f lambda (x) (cons 'a x))))
passa a ser

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

que retorna (a b c).

As duas últimas clausulas de eval. tratam de chamadas de funções para as quais o primeiro elemento da lista é uma expressão lambda ou label. Uma função label é avaliada empurrando o nome da função e a própria função para o ambiente, e depois chamando eval. numa expressão onde a expressão lambda interior é substituída pela expressão label. Isto é,

(eval. '((label firstatom (lambda (x)
                            (cond ((atom x) x)
                                  ('t (firstatom (car x))))))
         y)
       '((y ((a b) (c d)))))

fica

(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 no fim retorna a.

Finalmente, uma expressão da forma ((lambda (p1 ... pn) e) a_1 ... a_n), é avaliada chamando em primeiro lugar evlis. de modo a obter uma lista de valores ( v_1 ... v_n) dos argumentos (a_1 ... a_n), avaliando e com (p1 v1) ... (pn vn) appended ao ambiente. Assim

(eval. '((lambda (x y) (cons x (cdr y)))
         'a
         '(b c d))
       '())

fica

(eval. '(cons x (cdr y))
       '((x a) (y (b c d))))

que no fim retorna (a c d).

Conclusão

As considerações anteriores mostram bem como é que eval funciona, voltemos atrás para perceber qual é o seu significado. O que aqui temos é um modelo muito elegante para computação. Usando apenas quote, atom, car, cdr, cons e cond, podemos definir a função eval., que implementa a nossa linguagem de programação, usando-a depois para construir qualquer outra função que queiramos.

A linguagem definida em 1960 tinha muitas omissões. Não tinhas side-effects, nem execução sequencial (que apenas é útil com o anterior), sem números (é possível fazer cálculos de aritmética no Lisp de 1960 de McCarthy, usando, por exemplo, uma lista de n átomos para representar um número n) e dynamic scope. Todas estas limitações podem ser remediadas, surpreendentemente, com um pouco de código adicional. Isto mesmo foi mostrado por Steele e Sussman num famoso artigo² intitulado "The Art of the Interpreter" (Guy Lewis Steele, Jr. and Gerald Jay Sussman, "The Art of the Interpreter, or the Modularity Complex (Part Zero, One and Two)", MIT AI Lab Memo 453, May 1978.

O entendimento do eval de McCarthy não consiste só em perceber e subir um degrau na história das linguagens de programação. Estas ideias são ainda hoje parte do núcleo semântico do LISP. Não é tanto o que McCarthy desenhou ou o que descobriu, não é uma linguagem intrinsecamente para a IA ou para qualquer outra tarefa é o que se obtém quando tentamos axiomatizar a computação.

1. É de facto uma adaptação do texto de Paul Graham para português.

2. The Original 'Lambda Papers' by Guy Steele and Gerald Sussman

(/ 10000 365)

Palavras chave/keywords: Lisp, tradução, adaptação, Paul Graham

Criado/Created: NaN

Última actualização/Last updated: 10-10-2022 [14:26]

Voltar à página inicial.