Lisp

Origem: Wikipédia, a enciclopédia livre.

Lisp
Paradigma:	multi-paradigma: funcional, procedural, orientada a objetos
Surgido em:	1958
Última versão:	{{{ultima_versao}}} ()
Criado por:	John McCarthy
Estilo de tipagem:
Compiladores:	internos
Dialetos:	Common Lisp, Scheme, Emacs Lisp
Influenciada por:
Influenciou:	Logo, Smalltalk, Ruby, Dylan
Licença:	{{{licença}}}
Website:	{{{website}}}

A linguagem de programação Lisp (do inglês, ``LISt Processing, processamento de listas) foi criada em 1958 por John McCarthy, o que a torna a segunda mais antiga linguagem de programação de alto nível, mais recente apenas que a linguagem FORTRAN [McC78]. A linguagem, inspirada na linguagem IPL de Newell [NT60], foi inicialmente implementada em um computador IBM 704 pelo Grupo de Inteligência Artificial do Massachusetts Institute of Technology (MIT).

A principal motivação para o desenvolvimento da linguagem Lisp foi facilitar os experimentos com o sistema ``Advice Taker, um sistema desenvolvido com a missão de apresentar um certo ``bom senso ao seguir instruções recebidas sob a forma de sentenças declarativas e imperativas. O principal requisito exigido da linguagem era a possibilidade de manipular expressões representando sentenças lógicas, isto é, a linguagem deveria permitir manipulação simbólica .

Devido à sua origem acadêmica, a linguagem Lisp se desenvolveu de maneira desregulada: cada grupo, que se interessava pelas idéias contidas na proposta da linguagem, implementava sua própria versão, cujos detalhes e ambientes de programação variavam de lugar para lugar. Este desenvolvimento anárquico gerou diversos dialetos de Lisp, por exemplo, Interlisp, Franzlisp, Maclisp, Zetalisp, Scheme, Le_Lisp, entre outros. Esta situação foi contornada em 1984, com a publicação do livro Common Lisp: The Language [SJ84]. Este livro é o resultado de um esforço de padronização que reuniu em um único dialeto as características mais interessantes dos dialetos mais utilizados (principalmente Maclisp, Zetalisp, Scheme e Interlisp). O padrão Common Lisp foi adotado e atualmente existem diversas implementações, tanto comerciais como de domínio público (por exemplo, Clisp, disponível por FTP no endereço Internet ma2s2.mathematik.uni-karlsruhe.de: /pub/lisp), que seguem sua especificação.

Expressões simbólicas

A primeira observação sobre a linguagem Lisp diz respeito à maneira de utilizá-la: Lisp é uma linguagem interpretada, isto é, a interface usuário-sistema consiste em um programa interpretador que sustenta um diálogo, onde o usuário digita expressões em uma linguagem formal definida e recebe de volta a avaliação de sua expressão. Deste ponto de vista, pode-se pensar no Lisp como uma calculadora que, em vez de avaliar expressões aritméticas, avalia expressões simbólicas , chamadas s-expressões.

O próximo passo é definir s-expressão. Usaremos uma definição recursiva na forma de uma gramática:1

  Figure: S-expressões  

onde, representa um número na sintaxe usual das linguagens de programação e é uma seqüência de caracteres não totalmente numéricos. As expressões geradas por esta linguagem podem ser representadas através da árvore recursiva apresentada na figura 1. Nesta árvore, cada ponto preto representa, conforme indicado pela seta, uma nova cópia da árvore. Qualquer lista sempre poderá ser associada a uma árvore gerada a partir da árvore recursiva da figura, onde as folhas corresponderão aos átomos da lista.

  Figure: Árvore associada à s-expressão  

Exemplo: A árvore associada à lista (a ((b))(c d)) é mostrada na figura 2.

As expressões passíveis de avaliação pelo interpretador Lisp devem pertencer à linguagem das s-expressões, o que significa que qualquer programa ou dado na linguagem Lisp deve ser uma expressão desta linguagem.

Exemplo: Alguns exemplos de s-expressões são:

() A

• uma-variavel-global*

1+ 123.4 (a b c) (* 1 2) (a1 (b2 c2 (d3 3) e2) f1 g1 111) (((((0)))))

A analogia entre Lisp e uma calculadora é mais do que uma analogia, pois a linguagem das expressões aritméticas está contida na linguagem das s-expressões. A notação utilizada, para seguir a sintaxe das s-expressões, é a forma pré-fixada, onde o operador é colocado antes dos operandos.

Exemplo:

2 + 3 é escrito (+ 2 3).

5 * 2 + 1 é escrito (+ (* 5 2) 1), observe que a precedência entre operadores torna-se explícita na notação pré-fixada.

3.142 é escrito (expt 3.14 2).

O conceito de recursividade, isto é, a definição de uma entidade fazendo uso de sua própria definição, é fundamental para a linguagem Lisp. Sua origem funcional e a forma recursiva de definição de seus dados e programas fazem da recursividade o regime de processamento por excelência da linguagem. A avaliação, também um processo recursivo, é baseada nas seguintes regras:

A avaliação de um número é o próprio número.

A avaliação de um símbolo é o valor do símbolo.

A avaliação da lista vazia, ``() ou NIL, é a própria lista vazia.

A avaliação de uma lista não vazia se dá em dois passos: inicialmente todos os elementos da lista, exceto o primeiro, são avaliados. Em seguida o primeiro elemento é interpretado como uma função e é aplicado sobre o resultado da avaliação dos demais, isto é, estes resultados são usados como argumentos da função.

O resultado da avaliação pelo interpretador Lisp de expressões aritméticas, devidamente representadas na forma de s-expressões, é exatamente o que se esperaria, isto é, o valor numérico correspondente à expressão.

Exemplo: Considere o seguinte diálogo entre um usuário e o interpretador Lisp (as linhas iniciadas por ``> são entradas do usuário):

> (+ 2 3) 5

> (+ (* 5 2) 1) 11

O exemplo acima esclarece parcialmente o significado das regras de avaliação apresentadas. Em particular, fica claro que o sistema Lisp contém funções pré-definidas, por exemplo as funções aritméticas usuais. Resta saber que outras funções estão disponíveis e, principalmente, como é possível definir novas funções. Vamos começar pela segunda questão.

Funções

Um requisito fundamental para definir uma função é o conceito de condição. Dado um domínio finito , qualquer função sobre pode ser representada pela seguinte expressão:

A primeira função primitiva do Lisp, a função ``cond, implementa exatamente este tipo de representação. Sua sintaxe é a seguinte:

A função ``cond é avaliada da seguinte maneira: inicialmente as sucessivas s-expressões `` são avaliadas, estas expressões podem ser interpretadas como condições que selecionam subconjuntos do domínio da função. O primeiro resultado diferente de NIL leva à seleção do resultado da avaliação da expressão associada `` como o resultado da função ``cond. Esta regra de avaliação pode ser representada pelo seguinte procedimento:

Em Lisp, qualquer s-expressão diferente de NIL é interpretada como tendo o valor booleano verdadeiro , deixando o valor booleano falso como característica exclusiva do símbolo NIL. No entanto, existe um símbolo para representar o valor booleano verdadeiro, o símbolo T, cujo valor, analogamente ao símbolo NIL, é ele próprio.

Exemplo: A função , que retorna a soma da raiz quadrada de um número com outro número, poderia ser implementada da seguinte maneira:

(cond ((< x 0) NIL)

     (T (+ (sqrt x) y)))

A primeira condição da função ``cond, (< x 0), seleciona os elementos do domínio para os quais a função não é definida e tem como resultado associado o símbolo NIL. A segunda condição - o símbolo T, logo, sempre verdadeira - seleciona os valores para os quais a função deve ser efetivamente calculada, o que é feito através da avaliação de seu resultado associado: (+ (sqrt x) y). Esta expressão, contudo, apresenta um problema: as variáveis x e y são livres na expressão, isto é, não existem valores associados a estas variáveis, logo a expressão não pode ser avaliada.

Para transformar a expressão do exemplo acima em uma função é necessário dizer quais são os argumentos da função. Uma notação para resolver este problema foi introduzida por Church na sua teoria sobre o cálculo lambda .

Exemplo: A expressão acima, , quando convertida para a forma de função é representada por:

e sua aplicação sobre um par de número é realizada através da seguinte regra de execução:

Esta notação foi adotada por McCarthy, e a expressão acima pode ser submetida ao interpretador Lisp na seguinte forma:

> ( (lambda (x y)

     (cond ((< x 0) NIL)
           (T (+ (sqrt x) y))))
   4 5)

7

> ( (lambda (x y)

     (cond ((< x 0) NIL)
           (T (+ (sqrt x) y))))
   -9 5)

NIL

Manipulação simbólica

Para descrever o funcionamento da capacidade de manipulação simbólica no Lisp é interessante considerar o programa interpretador como uma máquina abstrata construída especificamente para a manipulação de símbolos.

  Figure: Máquina abstrata  

Esta máquina é formada por duas estruturas de dados: uma tabela de símbolos e um saco de células, cada uma contendo um par de posições. A tabela de símbolos contém três colunas onde são armazenadas as seguintes informações: (i) nome do símbolo, (ii) valor do símbolo, e (iii) definição do símbolo como função (ver figura 3).

Já vimos que a primitiva ``defun pode ser utilizada para associar uma definição de função a um símbolo. Para associar um valor qualquer a um símbolo existe a função primitiva ``set. Sua sintaxe é a seguinte:

Caso a avaliação do primeiro argumento resulte em um símbolo, a função retorna simplesmente o resultado da avaliação de . A função, no entanto, tem um importante efeito colateral: depois de sua execução, o interpretador passará a substituir o símbolo que resulta da avaliação de pelo resultado da avaliação de . O fato de a função ``set avaliar seu primeiro parâmetro leva à necessidade de um mecanismo para ``parar o processo de avaliação, de maneira que possamos informar ao interpretador qual o nome do símbolo que desejamos associado a um dado valor. Isto se faz, como quase tudo em Lisp, através de uma função: o resultado da avaliação de é simplesmente .

Exemplo: Utilização da função primitiva ``set.

> a Error: The variable A is unbound. > (set (quote a) 7) 7 > a 7

A função ``set é tão freqüentemente utilizada que foi introduzido um ``açúcar sintático na forma da função ``setq, que tem o mesmo comportamento da função ``set exceto o fato de não avaliar o primeiro argumento. Pelo mesmo motivo, a função ``quote pode ser abreviada simplesmente pelo caractere ' (chamado ``quote em inglês).

Exemplo: Atribuição de um símbolo como valor de um outro símbolo utilizando a primitiva ``setq.

> (setq b ' a) a > b a > a 7

Observe que a avaliação de um símbolo não é recursiva: o fato de ``a ter valor 7 (devido ao comando do exemplo anterior) não faz com que o valor de ``b - isto é, ``a - passe a ser 7.

O próximo passo consiste em descrever como as células do saco são utilizadas para a construção de representações de listas. A função primitiva ``cons tem esta função: ela recebe como entrada dois argumentos, isto é, duas s-expressões, e retorna um ponteiro para uma nova célula do saco, onde a parte esquerda contém o resultado da avaliação do primeiro parâmetro, e a parte direita contém o resultado da avaliação do segundo parâmetro. Este ponteiro pode então ser armazenado na coluna valor de uma entrada da tabela de símbolos, através da primitiva ``setq, significando que o símbolo em questão passa a ser associado à nova célula. Uma célula é representada em Lisp pela seguinte notação, chamada em inglês ``dotted-pair: .

A interpretação deste par é uma lista onde é um ponteiro para o primeiro elemento e um ponteiro para o resto da lista.

Exemplo: Utilização da função primitiva ``cons.

> (cons 1 2) (1 . 2)

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

> a (b . c)

A função ``cons permite ainda a construção de listas arbitrárias:

> (cons 'x (cons 'b (cons 'z nil))) (x . (b . (z . NIL)))

> (cons (cons 'x nil) (cons 'b (cons 'z nil))) ((x . nil) (b . (z . NIL)))

Interpretador

Para completar a descrição da máquina abstrata resta discutir a utilização, pelo programa interpretador, das estruturas de dados definidas acima. Isto pode ser feito através da definição formal do programa interpretador, o que paradoxalmente pode ser realizado através da definição em Lisp das funções ``eval e ``apply que formam o núcleo do interpretador. Antes de definir estas funções é necessário introduzir mais algumas primitivas, pois até agora dispomos apenas de funções para construir listas e associar valores ou funções a símbolos. Para escrever as funções ``eval e ``apply é necessário dispor de primitivas que permitam a análise de s-expressões recebidas como argumentos. Estas primitivas são de dois tipos: predicados e funções de manipulação.

Os predicados são os seguintes:

se a coluna valor da entrada da tabela de símbolos contiver um ponteiro, então retorna T; se não retorna NIL.

se e forem ponteiros para o mesmo destino, então retorna T; se não retorna NIL.

se e forem iguais, então retorna T; se não retorna NIL. É interessante notar que duas listas podem ser iguais e, no entanto, serem representadas por células diferentes e, logo, serem identificadas por ponteiros diferentes.

se é um átomo, então retorna T; se não retorna NIL.

se é um número, então retorna T; se não retorna NIL.

As descrições de funções Lisp acima se referem aos argumentos como sendo números, átomos, ponteiros, etc. Deve-se lembrar que está implícito que estes argumentos foram avaliados e que é ao resultado desta avaliação que as descrições se referem. As primitivas de manipulação são as seguintes:

se é uma célula, então retorna o conteúdo da parte esquerda da célula; se não retorna erro.

se é uma célula, então retorna o conteúdo da parte direita da célula; se não retorna erro.

retorna uma lista contendo os resultados da aplicação de a cada um dos elementos de . Opcionalmente pode existir mais de uma lista; neste caso a função é aplicada a cada conjunto de elementos com a mesma posição em cada lista.

Se , então retorna o resultado da avaliação de onde todas as ocorrências de xi foram substituídas pelo respectivo vi.

Os nomes das primitivas ``car e ``cdr têm origem histórica. Na primeira implementação do Lisp, em um IBM 704, as funções ``car e ``cdr foram construídas de tal maneira que seus resultados eram armazenados, respectivamente, na parte endereço e na parte decremento do acumulador (observe que a implementação foi realizada em ``assembler). Sendo assim, ``car é um mnemônico para ``Contents of the Address part of Register e ``cdr um mnemônico para ``Contents of the Decrement part of Register [McC78]. Uma vantagem da notação ``car e ``cdr é que composições destas funções podem ser expressas por abreviações, tais como:

De todo modo, as funções ``first e ``rest existem em Common Lisp e são sinônimos para ``car e ``cdr respectivamente.

Além de facilitar a manipulação iterativa de todos os elementos de uma lista, a função ``mapcar apresenta uma característica típica da linguagem Lisp: ela recebe como parâmetro um nome (ou uma forma lambda) de função e é capaz de aplicar esta função nos elementos da lista. A possibilidade de passar funções como parâmetro, ou mesmo construir s-expressões e depois executá-las, é uma característica própria das linguagens funcionais que, no caso do Lisp, é tornada possível pelo fato de as funções de avaliação - ``eval - e de aplicação de funções - ``apply - estarem disponíveis ao usuário.

Utilizando estas novas primitivas, podemos agora definir as funções ``eval e ``apply:

(defun eval (s-expression)

 (cond
   ((numberp s-expression) s-expression)
   ((atom s-expression)
    (cond ((boundp s-expression)
           (VALOR s-expression))
          (t (ERRO))))
   ((eql (car s-expression) 'quote)
    (cadr s-expression))
   ((functionp (car s-expression))
    (apply (car s-expression)
           (mapcar (quote eval) (cdr s-expression))))
   (t (ERRO))))

onde a função (VALOR retorna o conteúdo da coluna valor da tabela de símbolos na entrada correspondente a , e a função (ERRO) coloca o interpretador em estado de erro.

A estrutura da função ``eval corresponde às regras de avaliação apresentadas no início da seção, onde a tarefa de aplicar uma função em uma lista de argumentos, presente na última regra, é delegada à função ``apply. É interessante observar o caráter excepcional da função ``quote: como seu resultado é exatamente a não avaliação de seu parâmetro, ela é tratada diretamente pela função ``eval, não sendo passada para a função ``apply como todas as demais funções.

(defun apply (fun lista-par)

 (cond
   ((eql fun 'car) (CAR lista-par))
   ((eql fun 'cdr) (CDR lista-par))
   ((eql fun 'cons) (CONS lista-par))
   ((eql fun 'zerop) (ZEROP lista-par))
   (t (eval (sublis (mapcar '(lambda (par val)
                               (cons par val))
                            (cadr (FUNCTION fun))
                            lista-par)
                    (caddr (FUNCTION fun)))))))

A função ``apply, como indica seu nome, é utilizada para aplicar uma função em uma lista de argumentos previamente avaliados. Inicialmente, é verificado se a função em questão é uma primitiva da linguagem; neste caso é chamada uma função específica que realiza a operação necessária na máquina abstrata. Caso a função tenha sido definida pelo usuário (opção T, no programa), então o resultado de (FUNCTION fun), o conteúdo da coluna função da tabela de símbolos, na entrada correspondente ao símbolo ``fun, será algo da forma:

Bibliografia

HD89 T. Hasemer and J. Domingue. Common Lisp Programming for Artificial Intelligence. Addison-Wesley Publishing Company, Reading, MA, 1989.

McC60 J. McCarthy. Recursive functions of symbolic expressions and their computation by machine, part i. Communications of the ACM, 3(4):184-195, 1960.

McC78 J. McCarthy. History of lisp. ACM SIGPLAN Notices, 13(8), August 1978.

NT60 A. Newell and F.M. Tongue. An introduction to information processing language v. Communications of ACM, 3(4):205-211, 1960.

SJ84 G.L. Steele Jr. Common LISP, the Language. Digital Press, Burlington, 1984.

WH84 P.H. Winston and B.K.P. Horn. Lisp (2nd Edition). Addison-Wesley Publishing Company, Reading, MA, 1984.