Lisp

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Lisp
Paradigma multiparadigma: funcional, procedural, orientada a objetos
Surgido em 1958
Criado por John McCarthy
Compiladores internos
Dialetos: Common Lisp, Scheme, Emacs Lisp, Autolisp, Arc, Clojure, Newlisp, Lush, Arc
Influenciou Logo, Smalltalk, Ruby, Dylan

Lisp é uma família de linguagens de programação concebida por John McCarthy em 1958. Num célebre artigo, ele mostra que é possível usar exclusivamente funções matemáticas como estruturas de dados elementares (o que é possível a partir do momento em que há um mecanismo formal para manipular funções: o Cálculo Lambda de Alonzo Church). A linguagem Lisp foi projetada primariamente para o processamento de dados simbólicos.[1] Ela é uma linguagem formal matemática.[1] Durante os anos de 1970 e 1980, Lisp se tornou a principal linguagem da comunidade de inteligência artificial, tendo sido pioneiro em aplicações como administração automática de armazenamento, linguagens interpretadas e programação funcional.

O seu nome vem de LISt Processing (a lista é a estrutura de dados fundamental desta linguagem). Tanto os dados como o programa são representados como listas, o que permite que a linguagem manipule o código fonte como qualquer outro tipo de dados.

Existem diversos dialetos de Lisp, sendo os mais conhecidos o Common Lisp e o Scheme.[2]

História[editar | editar código-fonte]

Lisp é uma família de linguagens que possui uma longa história. As primeiras idéias-chave para a linguagem foram desenvolvidas por John McCarthy em 1956, durante um projeto de pesquisa em inteligência artificial. A primeira implementação da linguagem se dá no inverno de 1958.[3] A motivação de McCarthy surgiu da idéia de desenvolver uma linguagem algébrica para processamento de listas para trabalho em IA (inteligência artificial). Esforços para a implementação de seus primeiros dialetos foram empreendidos no IBM 704, IBM 7090, DEC PDP-1, DEC PDP-6 e DEC PDP-10. O dialeto principal entre 1960 e 1965 foi o Lisp 1.5.No início dos anos 1970, houve outros dois dialetos predominantes, desenvolvidos através de esforços anteriores: MacLisp e Interlisp.

Apesar das primeiras implementações do Lisp terem sido realizados nos IBM 704 e 7090, trabalhos posteriores concentraram-se nos DEC PDP-6 e PDP-10, este último sendo o baluarte do Lisp e das pesquisas em IA (inteligência artificial) em lugares como o MIT (Massachussets Institute of Tecnology) e as Universidades de Stanford e Carnegie-Mellon até metade dos anos 1970. O computador PDP-10 e seu antecessor, o PDP-6 eram por definição, especialmente adequados para o Lisp, por possuirem palavras de 36 bits e endereços de 18 bits. Esta arquitetura permitia um registro de um cons cell (par pontuado) em uma única palavra de memória, em instruções simples extraíam o seu car e cdr. Esses computadores possuíam também poderosas instruções de pilha, que proporcionavam rápida chamada a funções; porém suas limitações em 1973 eram evidentes: suportavam um pequeno número de pesquisadores utilizando o Lisp e seu endereçamento em 18 bits limitava o espaço dos programas. Uma resposta para o problema de endereçamento foi o desenvolvimento do "Lisp Machine",um computador dedicado especialmente à tarefa de trabalhar com a linguagem. Outra solução foi a utilização de computadores de uso geral com maior capacidade de endereçamento, como o DEC VAX e o S1 Mark IIA.

Dialetos historicamente significativos[editar | editar código-fonte]

  • LISP 1[4] – Primeira Implementação.
  • LISP 1.5[5] – Primeira versão amplamente distribuída, desenvolvida por McCarthy e outros do MIT. Assim chamada porque continha várias melhorias no interpretador "LISP 1" original, mas não foi uma grande reestruturação como planejado que fosse ser o LISP 2.
  • Stanford LISP 1.6[6] – Este foi uma sucessora para o LISP 1.5 desenvolvida no Stanford AI Lab, e amplamente distribuída para sistemas PDP-10 rodando o sistema operacional TOPS-10. Se tornou obsoleta com o advento do Maclisp e do InterLisp.

Aplicabilidade[editar | editar código-fonte]

Lisp é uma linguagem madura, concebida atenciosamente, altamente portável, linguagem de força industrial com a qual desenvolvedores em todo o mundo contam para:

  • Ferramenta rápida e altamente personalizável para fazer coisas do dia a dia.
  • Aplicações grandes, complexas e críticas as quais seriam impossíveis desenvolver em outra linguagem.
  • Prototipação rápida e Rapid Application Development (RAD).
  • Aplicações de alta disponibilidade, principalmente aquelas que necessitam de mudanças após a etapa inicial.

A linguagem teve um grande sucesso em software do ramo de negócios, engenharia, processamento de documentos, hipermídia (incluindo a Web), matemática, gráficos e animação (Mirai), inteligência artificial e processamento de linguagem natural. Uma das grandes vantagens de Lisp é que ela trata o programa como dado, possibilitando assim um programa inteiro ser dado como entrada de um outro, coisa que não acontece em outras linguagens como C e Pascal. E usada algumas vezes para definir todos os aspectos de uma aplicação, ou apenas o motor de processamento interno, ou apenas a interface do usuário; e ainda é usada com rotina para prover linguagens de comando interativas, linguagens de macro ou script e linguagens extensoras de sistemas comerciais.

Características Técnicas[editar | editar código-fonte]

A linguagem LISP é interpretada, 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 podemos pensar no LISP como uma calculadora, que ao invés de avaliar expressões aritméticas avalia expressões simbólicas, chamadas de expressões.[7] Cada programa em LISP, é, portanto, uma expressão. As expressões são de tamanho indefinido e tem uma estrutura de árvore binária. A estrutura de utilização da memória disponível é na forma de listas, pois livra o programador da necessidade de alocar espaços diferentes para o programa e para os dados, fazendo com que os dados e os programas sejam homogêneos, característica única da linguagem LISP. Suas principais características são:

  • Tipos de dados: átomo e a lista. É com apenas esses dois tipos de dados que se constroem as expressões-S, as estruturas basilares de LISP.
  • Fraca Tipagem: LISP, em relação a outras linguagens funcionais mais recentes, é fracamente tipado, o que causa complicações, já que operações que acessam as suas estruturas de dados são tratadas como funções.
  • Funções de ordem elevada: Linguagens funcionais tipicamente suportam funções de ordem elevada (exemplo: função de uma função de uma função de uma…).
  • Avaliação Ociosa: É o que ocorre quando uma função aninhada executa uma computação desnecessária para a avaliação da função que a chama, aumentando o tempo de execução.
  • Concorrência (multitarefa): A concorrência nas linguagens imperativas tradicionais é relativamente complexa; o programador é o responsável pela sincronização de todas as tarefas (a multitarefa no paradigma procedural é tão sofisticada quanto um GOTO). Em contraste, as linguagens funcionais intrinsecamente nos oferecem oportunidades para a concorrência: A partir do momento em que uma função tem mais de um parâmetro, estes parâmetros devem em princípio ser avaliados simultaneamente (note que os parâmetros seriam as funções correspondentes às tarefas a serem executadas); A partir deste ponto, a responsabilidade pela sincronização das tarefas passa do programador para o compilador (as modernas linguagens funcionais orientadas a multitarefa dispõe de mecanismos através dos quais o programador pode guiar o compilador). Todavia, as linguagens funcionais orientadas a multitarefa permitem ao programador trabalhar em um nível muito mais elevado do que as linguagens imperativas destinadas a este mesmo fim.
  • Um alto nível de abstração, especialmente quando as funções são utilizadas, suprimindo muitos detalhes da programação e minimizando a probabilidade da ocorrência de muitas classes de erros;
  • A não dependência das operações de atribuição permite aos programas avaliações nas mais diferentes ordens. Esta característica de avaliação independente da ordem torna as linguagens funcionais as mais indicadas para a programação de computadores maciçamente paralelos;
  • A ausência de operações de atribuição torna os programas funcionais muito mais simples para provas e análises matemáticas do que os programas procedurais.

E como desvantagem, destacamos:

  • Uma menor eficiência para resolver problemas que envolvam muitas variáveis (ex. contas de banco) ou muitas atividades seqüenciais são muitas vezes mais fáceis de se trabalhar com programas procedurais ou programas orientados a objeto.

O Common Lisp permite várias representações diferentes de números. Estas representações podem ser divididas em 4 tipos: hexadecimais, octais, binários e decimais. Estes últimos podem ser divididos em 4 categorias: inteiros, racionais, ponto flutuante e complexos.

Implementação das Listas[editar | editar código-fonte]

Originalmente, em Lisp havia duas estruturas de dados fundamentais: o átomo e a lista; o átomo pode ser numérico, ou alfanumérico. Exemplos de átomos: atomo1, a, 12, 54, bola, nil.

O átomo nil representa o valor nulo e ao mesmo tempo representa uma lista vazia. A lista é a associação de átomos ou outras listas (numa lista chamamos de elementos a cada um dos itens) representandos entre parêntesis. Exemplo de lista:

(esta lista contém 5 átomos)

((jose (22 solteiro)) (antonio (15 casado)))

Normalmente a implementação de uma lista é um encadeamento de pares em que o ponteiro à esquerda do par aponta para o elemento correspondente da lista e em que o ponteiro à direita do par aponta para a restante lista.

  [   .   ]
    |   |
    |   +---- ponteiro para a restante lista (quando for o último, aponta para nil)
    +-------- ponteiro para o conteúdo do elemento
  [   .   ] +→[   .   ] +→[   .   ] +→[   .   ] +→[   .   ]
    |   |   |   |   |   |   |   |   |   |   |   |   |   |
    |   +---+   |   +---+   |   +---+   |   +---+   |   +--> nil
   esta        lista      contém        5         átomos

Avaliação dados: os átomos quando avaliados retornam eles mesmos. As listas, quando avaliadas, são funções, onde o primeiro elemento representa o nome da função e os elementos seguintes são os argumentos para esta função. Exemplos de função:

(+ 3 4)
> 7
(* 5 (+ 2 5))
> 35
(car (quote (a b)))
> a

Normalmente, as implementações de Lisp providenciam um ambiente interactivo de avaliação de expressões. Os exemplos acima apresentam a interacção com uma implementação de Lisp. Como pode ser visto também, um programa Lisp pode confundir um programador inexperiente porque requer o uso de muitos parênteses, o que lhe rendeu um trocadilho anglófono para o nome da linguagem: LISP = Lots of Irritating Stupid Parentheses (tradução: Montes de Irritantes Parênteses Estúpidos), ou então LISP = Linguagem Infernal Somente de Parênteses.

Existe o mito de que Lisp é uma linguagem que só funciona com um interpretador. Na realidade, todos os dialetos relevantes de Lisp têm compiladores. Alguns dialetos, o compilador é uma função que se pode invocar a partir de código normal para transformar uma lista (que descreve uma função) numa função invocável. Programas Lisp comerciais são tipicamente compilados por motivos de eficiência, mas a semântica do Lisp permite que o programador possa usar programas interpretados e programas compilados ao mesmo tempo. A maioria dos usos interpretados ocorrem interativamente, para invocar programas compilados a partir de código escrito por um programador. Há exemplos disso acima onde se apresenta o resultado interactivo de invocar funções compiladas.

Exemplos de Funções[editar | editar código-fonte]

(quote expressão)
Retorna a expressão diretamente, sem tentar qualquer forma da avaliação. Ex: (quote jose) retorna jose, e (quote (jose silva)) retorna (jose silva).

'expressão
Significa o mesmo que (quote expressão). Ex: 'jose retorna jose, e '(jose silva) retorna (jose silva).

(eval expressão)
força a avaliar a expressão. Ex: Embora '(+ 3 4) simplesmente retorna (+ 3 4), (eval '(+ 3 4)) força a avaliar o (+ 3 4) e portanto retorna 7.

(car lista)
Retorna o primeiro elemento da lista. Ex: (car '(jose silva)) retorna jose. Entre os vários dialetos de Lisp, há alguns (por exemplo, ISLISP) que permitem o nome first como alternativa para car.

(cdr lista)
Retorna a lista sem o primeiro elemento. Ex: (cdr '(jose da silva)) retorna (da silva). Há dialetos que usam o nome rest como alternativa para cdr.

(cons atomo lista)
Adiciona átomo ao início da lista. Ex: (cons 'jose '(da silva)) retorna (jose da silva).

Funções matemáticas:

+ (Adição)
- (Subtração)
* (Multiplicação)
/ (Divisão)

Macros[editar | editar código-fonte]

O grande diferencial de Lisp são as macros. As macros são completamente diferentes das que se encontram em C, pois estas somente fazem substituição de texto, enquanto que em Lisp as macros são programas que geram programas.

Uso de Lisp[editar | editar código-fonte]

Lisp foi utilizado para desenvolver o primeiro sistema computacional de matemática simbólica, o Macsyma.

Ele também é utilizado como linguagem de extensão do software de CAD AutoCAD, desenvolvido pela AutoDesk. O editor de textos Emacs também utiliza Lisp como linguagem de extensão. Segundo o seu próprio autor, Richard Stallman, Lisp foi o responsável por tornar o Emacs tão popular, pois o fato da linguagem de extensão dele ser tão poderosa permite que ele seja estendido muito além do que se imaginava que ele originalmente poderia fazer.

A ITA software desenvolveu um sistema de reserva de passagens chamado Orbitz em LISP, ele é utilizado por diversas companhias aéreas. A Symbolics criou um sistema de modelagem 3D que depois foi adquirido pela IZWare e atualmente se chama Mirai, ele foi utilizado nos efeitos do filme Senhor dos Anéis.

O LISP foi utilizado pelo Paul Graham para desenvolver o sistema de e-commerce da Viaweb, que posteriormente foi vendido para o Yahoo por US$ 40 milhões, na época da bolha da internet.

Exemplos de código[editar | editar código-fonte]

Expressões Lambda[editar | editar código-fonte]

((lambda (arg) (+ arg 1)) 5)

Resultado: 6

Fatorial[editar | editar código-fonte]

Common Lisp:

(defun fatorial (n)
  (if (= n 0)
      1
      (* n (fatorial (- n 1)))))

Scheme:

(define fatorial
  (lambda (n)
    (if (= n 0)
        1
        (* n (fatorial (- n 1))))))

Embora as definições acima pareçam correctas, para evitar o transbordamento da pilha pode ser preferível usar as seguintes.

Common Lisp:

(defun fatorial (n)
  (do ((i n (- i 1))
       (resultado 1 (* resultado i)))
      ((= i 0) resultado)))

Scheme:

(define fatorial
   (lambda (n)
     (let f ((i n) (resultado 1))
       (if (= i 0)
         resultado
         (f (- i 1) (* resultado i))))))

Na maioria dos dialetos modernos de Lisp usam-se inteiros de precisão numérica indefinida:

(fatorial 40)815915283247897734345611269596115894272000000000
 
(length (write-to-string (fatorial 10000)))35660       ; dígitos no resultado de (fatorial 10000)
 
(/ (fatorial 10000) (fatorial 9998))99990000    ; resultado exato

Naqueles dialetos também usam-se números racionais de precisão numérica indefinida. Por exemplo, no Common Lisp se pode ter esta interacção:

pi
⇒ 3.141592653589793
 
(rationalize pi)        ; aproximação do valor como número racional245850922/78256779
 
(* (rationalize pi) (fatorial 40)) ; o resultado é um número racional66864508220128937516859865761265220075208572928000000000/26085593
 
(- (/ (* (rationalize pi) (fatorial 40))
      (fatorial 40))
   (rationalize pi))0                    ; o resultado da aritmética racional é exato

Referências

  1. a b McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. Lisp 1.5 Programmer´s Manual. Cambridge, Massachusetts: The MIT Press, 1962. 106 pp. p. 1. ISBN 0-262-13011-4.
  2. Friedman, Daniel P.; Felleisen, Matthias. The Little LISPer. New York: Macmillan, 1989. 206 pp. p. xiii. ISBN 0-02-339763-2.
  3. Bergin, Thomas J.; Gibson, Richard G.. History of Programming Languages II. New York: ACM Press, Addison-Wesley, 1996. 864 pp. ISBN 0-201-89502-1.
  4. McCarthy, J; Brayton, R.; Edwards, D. Fox, P.; Luckham, D.; Maling, K.; Park, D.; Russell, S (Março 1960). LISP I Programmers Manual Artificial Intelligence Group, M.I.T. Computation Center and Research Laboratory. Acessado em 11 de maio de 2010.
  5. McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.. In: John. LISP 1.5 Programmer's Manual. [S.l.]: MIT Press, 1962; 2nd Edition, 15th printing, 1985. ISBN 0 262 130 1 1 4.
  6. Quam, Lynn H.; Diffle, Whitfield. In: Lynn H.. Stanford LISP 1.6 Manual. [S.l.: s.n.].
  7. Wexelblat, Richard L.(Editor). History of Programming Languages. New York: Academic Press, 1981. 758 pp. p. 173-197. ISBN 0-12-745040-8.

Ligações externas[editar | editar código-fonte]