Lisp

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. Ela é uma linguagem formal matemática.  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: Common Lisp, Scheme e Clojure.

História 
Lisp é uma família de linguagens que possui uma longa história. As primeiras ideias-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. A motivação de McCarthy surgiu da ideia 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.

2000 até o presente 

Depois de ter decaído um pouco nos anos 90, Lisp experimentou um ressurgimento de interesse após 2000. A maioria das novas atividades foi focada em implementações de Common Lisp, Scheme, Emacs Lisp, Clojure, e Racket, e inclui o desenvolvimento de novas bibliotecas e aplicativos portáteis.

Muitos novos programadores de Lisp foram inspirados por escritores como Paul Graham e Eric S. Raymond para buscar uma linguagem que outros consideram antiquada. Os programadores New Lisp frequentemente descrevem a linguagem como uma experiência de abrir os olhos e afirmam ser substancialmente mais produtivos do que em outras linguagens.[28] Esse aumento na consciência pode ser contrastado com o "Inverno da IA" e o breve ganho de Lisp em meados da década de 1990.

Dan Weinreb lista em sua pesquisa de implementações Common Lisp onze implementações de Common Lisp ativamente mantidas. Scieneer Common Lisp é uma nova implementação comercial da CMUCL com um primeiro lançamento em 2002.

A comunidade open-source criou uma nova infra-estrutura de suporte: o CLiki é um wiki que coleta informações relacionadas ao Common Lisp, o Common Lisp lista recursos, o #lisp é um canal IRC popular e permite compartilhar e comentar trechos de código (com suporte do  lisppaste, um bot de IRC escrito em Lisp),  Planet Lisp coleta o conteúdo de vários blogs relacionados a Lisp, no  LispForum usuários discutem tópicos de Lisp,  Lispjobs é um serviço para anunciar ofertas de emprego e há um serviço de notícias semanal,  Weekly Lisp News. Common-lisp.net é um site de hospedagem para projetos Common Lisp de código aberto.  QuickLisp] é um gerenciador de bibliotecas do Common Lisp.

Cinquenta anos de Lisp (1958–2008) foram celebrados em LISP50@OOPSLA. Há reuniões regulares de usuários locais em Boston, Vancouver e Hamburgo. Outros eventos incluem o European Common Lisp Meeting, o European Lisp Symposium e uma Conferênia Internacional de Lisp.

A comunidade Scheme mantém ativamente mais de vinte implementações. Várias novas implementações significativas (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon) foram desenvolvidas nos anos 2000. O Relatório Revisado sobre o Esquema de Linguagem Algorítmica padrão do Scheme foi amplamente aceito na comunidade Scheme. O processo Solicitações de implementação do Scheme criou muitas bibliotecas e extensões quase-padrão para o Scheme. As comunidades de usuários de implementações individuais do Scheme continuam a crescer. Um novo processo de padronização de linguagem foi iniciado em 2003 e levou ao padrão R6RS Scheme em 2007. O uso acadêmico do Scheme para o ensino de informática parece ter diminuído um pouco. Algumas universidades não estão mais usando Scheme em seus cursos introdutórios de ciência da computação; MIT agora usa Python em vez de Scheme para seu programa de ciência da computação e MITx massive open online course.

Existem vários novos dialetos de Lisp: Arc, Hy, Nu, Liskell e LFE (Lisp Flavored Erlang). O analisador para Julia é implementado em Femtolisp, um dialeto de Scheme (Julia é inspirada por Scheme e é frequentemente considerada um Lisp).

Dialetos historicamente significativos
LISP 1 – Primeira Implementação.
LISP 1.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 – Este foi uma sucessora para o LISP 1.5 desenvolvida no Laboratório de IA de Stanford, 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.
MACLISP – Desenvolvido para o Projeto MAC do MIT (Não tem relaçãocom o Macintosh da Apple, nem com McCarthy), descendente direto do LISP 1.5. Rodou em sistemas PDP-10 e Multics. (MACLISP mais tarde começou a ser chamado de Maclisp, e geralmente é citado como MacLisp.)
InterLisp – desenvolvido na BBN Technologies para sistemas PDP-10 rodando o sistema operacional Tenex, mais tarde usado como Lisp "da costa oeste" para as máquinas Xerox Lisp como InterLisp-D Umaversão menor chamada "InterLISP 65" foi produzida para a linha base de computadores 6502 da Família Atari de 8 bits. Por bastante tempo Maclisp e Interlisp foram fortes competidores.
Franz Lisp – originalmente um projeto da Universidade da Califórnia, Berkeleyt; mais tarde desenvolvido por Franz Inc. O nome é uma piada com o nome de "Franz Liszt", e não se refere à Allegro Common Lisp, o dialeto de Common Lisp vendido por Franz Inc., em anos mais recentes.

Aplicabilidades 
Lisp é uma linguagem madura, concebida atenciosamente, altamente portável, linguagem de força industrial. Suas características que mais chamam atenção são:
 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. É 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 
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. 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 
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 
(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 
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 
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

Expressões Lambda 
((lambda (arg) (+ arg 1)) 5)

Resultado: 6

Fatorial 
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 racional
⇒ 245850922/78256779

(* (rationalize pi) (fatorial 40)) ; o resultado é um número racional
⇒ 66864508220128937516859865761265220075208572928000000000/26085593

(- (/ (* (rationalize pi) (fatorial 40))
      (fatorial 40))
   (rationalize pi))
⇒ 0                    ; o resultado da aritmética racional é exato

Ligações externas 
 http://www-formal.stanford.edu/jmc/history/lisp/lisp.html
 http://www-formal.stanford.edu/jmc/lisp20th/lisp20th.html
 http://www.gigamonkeys.com/book/
 http://www.paulgraham.com/onlisp.html
 Linguagem LISP (em Common Lisp)
 Introdução à Linguagem Lisp
 Grupo de usuários no Brasil
 Usando Linguagem AutoLISP (Site em inglês da Autodesk)
https://cdn.knightlab.com/libs/timeline3/latest/embed/index.html?source=1fdIwf92qhQZ6UIPwjwYzwLq_cJ-PEruZtWhGRiQoFlU&font=Default&lang=en&initial_zoom=2&height=650 (timeline da linguagem LISP e suas derivadas)

 
Linguagens de programação funcionais