Lisp (linguagem de programação) - Lisp (programming language)

Lisp
Lisp logo.svg
Paradigma Multi-paradigma : funcional , procedimental , reflexivo , meta
Projetado por John McCarthy
Desenvolvedor Steve Russell , Timothy P. Hart e Mike Levin
Apareceu pela primeira vez 1958 ; 63 anos atrás ( 1958 )
Disciplina de digitação Dinâmico , forte
Dialetos
Influenciado por
IPL
Influenciado

Lisp (historicamente LISP ) é uma família de linguagens de programação com uma longa história e uma notação de prefixo distinta, totalmente entre parênteses . Especificado originalmente em 1958, Lisp é a segunda linguagem de programação de alto nível mais antiga . Apenas Fortran é mais velho, em um ano. Lisp mudou desde seus primeiros dias, e muitos dialetos existiram ao longo de sua história. Hoje, os dialetos Lisp de uso geral mais conhecidos são Racket , Common Lisp , Scheme e Clojure .

Lisp foi originalmente criado como uma prática notação matemática para programas de computador , influenciados pelo (embora não originalmente derivados) a notação de Alonzo Church 's cálculo lambda . Rapidamente se tornou a linguagem de programação preferida para pesquisas em inteligência artificial (IA). Como uma das primeiras linguagens de programação, Lisp foi pioneira em muitas idéias na ciência da computação , incluindo estruturas de dados em árvore , gerenciamento de armazenamento automático , tipagem dinâmica , condicionais , funções de ordem superior , recursão , o compilador de auto-hospedagem e o read – eval – print loop .

O nome LISP deriva de "LISt Processor". Listas vinculadas são uma das principais estruturas de dados do Lisp , e o código-fonte do Lisp é feito de listas. Assim, os programas Lisp podem manipular o código-fonte como uma estrutura de dados, dando origem aos sistemas de macro que permitem aos programadores criar uma nova sintaxe ou novas linguagens específicas de domínio embutidas no Lisp.

A intercambiabilidade de código e dados dá ao Lisp sua sintaxe instantaneamente reconhecível. Todo o código do programa é escrito como expressões S ou listas entre parênteses. Uma chamada de função ou forma sintática é escrita como uma lista com o nome da função ou do operador primeiro e os argumentos a seguir; por exemplo, uma função fque recebe três argumentos seria chamada de . (f arg1 arg2 arg3)

História

John McCarthy desenvolveu o Lisp em 1958 enquanto estava no Massachusetts Institute of Technology (MIT). McCarthy publicou seu projeto em um artigo na Communications of the ACM em 1960, intitulado "Funções recursivas de expressões simbólicas e sua computação por máquina, parte I". Ele mostrou que com alguns operadores simples e uma notação para funções anônimas emprestadas de Church, pode-se construir uma linguagem de Turing-completa para algoritmos.

Information Processing Language foi a primeira linguagem de IA , de 1955 ou 1956, e já incluía muitos dos conceitos, como processamento de lista e recursão, que passaram a ser usados ​​no Lisp.

Notação original de McCarthy usou colchetes " M-expressões " que seriam traduzidos para o S-expressões . Como um exemplo, o M-expressão car[cons[A,B]]é equivalente à de S-expressão . Depois que o Lisp foi implementado, os programadores rapidamente escolheram usar as expressões S e as expressões M foram abandonadas. Expressões M surgiram novamente com tentativas de curta duração de MLisp por Horace Enea e CGOL por Vaughan Pratt . (car (cons A B))

Lisp foi implementado pela primeira vez por Steve Russell em um computador IBM 704 usando cartões perfurados . Russell leu o artigo de McCarthy e percebeu (para surpresa de McCarthy) que a função eval Lisp poderia ser implementada em código de máquina . O resultado foi um interpretador Lisp funcional que poderia ser usado para executar programas Lisp, ou mais apropriadamente, "avaliar expressões Lisp".

Duas macros de linguagem assembly para o IBM 704 tornaram-se as operações primitivas para listas de decomposição: car( Conteúdo da parte Endereço do número do Registro ) e cdr( Conteúdo da parte Decremento do número do Registro ), onde "registro" se refere aos registros do processamento central do computador unidade (CPU). Dialetos lisp ainda usar care cdr( / k ɑr / e / k ʊ d ər / ) para as operações que retornam do primeiro item de uma lista e o resto da lista, respectivamente.

O primeiro compilador Lisp completo, escrito em Lisp, foi implementado em 1962 por Tim Hart e Mike Levin no MIT. Este compilador introduziu o modelo Lisp de compilação incremental, no qual funções compiladas e interpretadas podem se misturar livremente. A linguagem usada no memorando de Hart e Levin é muito mais próxima do estilo Lisp moderno do que o código anterior de McCarthy.

As primeiras rotinas de coleta de lixo foram desenvolvidas pelo estudante de graduação do MIT Daniel Edwards .

Durante as décadas de 1980 e 1990, um grande esforço foi feito para unificar o trabalho em novos dialetos Lisp (principalmente sucessores de Maclisp , como ZetaLisp e NIL (Nova Implementação de Lisp) em um único idioma. A nova linguagem, Common Lisp , era um tanto compatível com os dialetos que substituiu (o livro Common Lisp the Language observa a compatibilidade de várias construções). Em 1994, ANSI publicou o padrão Common Lisp, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp".

Linha do tempo

Conexão com inteligência artificial

Desde o início, Lisp esteve intimamente conectado com a comunidade de pesquisa de inteligência artificial , especialmente em sistemas PDP-10 . Lisp foi usado como a implementação da linguagem de programação Micro Planner , que foi usada no famoso sistema AI SHRDLU . Na década de 1970, quando a pesquisa de IA gerou ramificações comerciais, o desempenho dos sistemas Lisp existentes tornou-se um problema crescente.

Genealogia e variantes

Ao longo de seus sessenta anos de história, Lisp gerou muitas variações sobre o tema central de uma linguagem de expressão S. Além disso, cada dialeto dado pode ter várias implementações - por exemplo, há mais de uma dúzia de implementações de Common Lisp .

As diferenças entre os dialetos podem ser bastante visíveis - por exemplo, Common Lisp usa a palavra defun- chave para nomear uma função, mas Scheme usa define. Dentro de um dialeto que é padronizado, no entanto, as implementações em conformidade suportam a mesma linguagem central, mas com extensões e bibliotecas diferentes.

Dialetos historicamente significativos

  • LISP 1 - Primeira implementação.
  • LISP 1.5 - Primeira versão amplamente distribuída, desenvolvida por McCarthy e outros no MIT. Assim chamado porque continha várias melhorias no intérprete "LISP 1" original, mas não era uma grande reestruturação como o LISP 2 planejado seria.
  • Stanford LISP 1.6 - Este foi um sucessor do LISP 1.5 desenvolvido no Stanford AI Lab e amplamente distribuído para sistemas PDP-10 executando o sistema operacional TOPS-10 . Foi tornado obsoleto por Maclisp e InterLisp.
  • MACLISP - desenvolvido para o Projeto MAC do MIT , o MACLISP é um descendente direto do LISP 1.5. Ele funcionou nos sistemas PDP-10 e Multics . MACLISP viria a ser mais tarde chamado de Maclisp e é frequentemente referido como MacLisp. O "MAC" no MACLISP não está relacionado nem ao Macintosh da Apple nem ao McCarthy .
  • Interlisp - desenvolvido na BBN Technologies para sistemas PDP-10 rodando o sistema operacional TENEX , posteriormente adotado como um Lisp "West coast" para as máquinas Xerox Lisp como InterLisp-D . Uma pequena versão chamada "InterLISP 65" foi publicada para a linha de computadores da família Atari de 8 bits baseada em 6502 . Por algum tempo, Maclisp e InterLisp foram concorrentes fortes.
  • Franz Lisp - originalmente um projeto da Universidade da Califórnia, Berkeley ; posteriormente desenvolvido por Franz Inc. O nome é uma deformação humorística do nome " Franz Liszt " e não se refere a Allegro Common Lisp , o dialeto de Common Lisp vendido pela Franz Inc., nos anos mais recentes.
  • XLISP , no qual o AutoLISP foi baseado.
  • Standard Lisp e Portable Standard Lisp foram amplamente utilizados e portados, especialmente com o Computer Algebra System REDUCE.
  • ZetaLisp , também denominado Lisp Machine Lisp - usado nas máquinas Lisp , descendente direto de Maclisp. ZetaLisp teve uma grande influência no Common Lisp.
  • LeLisp é um dialeto Lisp francês. Um dos primeiros construtores de interface (chamado SOS Interface) foi escrito em LeLisp.
  • Scheme (1975).
  • Common Lisp (1984), conforme descrito por Common Lisp the Language - uma consolidação de várias tentativas divergentes (ZetaLisp, Spice Lisp , NIL e S-1 Lisp ) para criar dialetos sucessores para Maclisp, com influências substantivas do dialeto Scheme também . Esta versão do Common Lisp estava disponível para plataformas abrangentes e foi aceita por muitos como um padrão de fato até a publicação do ANSI Common Lisp (ANSI X3.226-1994). Entre os sub-dialetos mais difundidos do Common Lisp estão Steel Bank Common Lisp (SBCL), CMU Common Lisp (CMU-CL), Clozure OpenMCL (não deve ser confundido com Clojure!), GNU CLisp e versões posteriores de Franz Lisp; todos eles aderem ao padrão ANSI CL posterior (veja abaixo).
  • Dylan foi em sua primeira versão uma mistura de Scheme com o Common Lisp Object System.
  • EuLisp - tentativa de desenvolver um novo Lisp eficiente e limpo.
  • ISLISP - tentativa de desenvolver um novo Lisp eficiente e limpo. Padronizado como ISO / IEC 13816: 1997 e posteriormente revisado como ISO / IEC 13816: 2007: Tecnologia da informação - Linguagens de programação, seus ambientes e interfaces de software de sistema - Linguagem de programação ISLISP .
  • Esquema IEEE - padrão IEEE, 1178–1990 (R1995).
  • ANSI Common Lisp - um American National Standards Institute (ANSI) padrão para Lisp comum, criado por subcomissão X3J13 , fretado para começar Lisp comum: a linguagem como um documento de base e de trabalho através de um público consenso processo para encontrar soluções para problemas comuns de portabilidade de programas e compatibilidade de implementações Common Lisp. Embora formalmente um padrão ANSI, a implementação, venda, uso e influência do ANSI Common Lisp foi e continua a ser visto em todo o mundo.
  • ACL2 ou "A Computational Logic for Applicative Common Lisp", uma variante do aplicativo Common LISP (sem efeitos colaterais). ACL2 é uma linguagem de programação que pode modelar sistemas de computador e uma ferramenta para ajudar a provar as propriedades desses modelos.
  • Clojure , um dialeto recente do Lisp que compila para a máquina virtual Java e tem um foco particular na simultaneidade .
  • Game Oriented Assembly Lisp (ou GOAL) é uma linguagem de programação de videogame desenvolvida por Andy Gavin e a equipe Jak and Daxter da Naughty Dog . Ele foi escrito usando Allegro Common Lisp e usado no desenvolvimento de toda a série de jogos Jak and Daxter .
  • Chialisp, um dialeto de alto nível compilado para CLVM, o ambiente de programação on-chain no blockchain Chia

2000 até o presente

Depois de ter diminuído um pouco na década de 1990, 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 portáteis e aplicativos.

Muitos novos programadores Lisp foram inspirados por escritores como Paul Graham e Eric S. Raymond a buscar uma linguagem que outros consideravam antiquada. Os novos programadores Lisp freqüentemente descrevem a linguagem como uma experiência reveladora e afirmam ser substancialmente mais produtiva do que em outras linguagens. Este aumento de consciência pode ser contrastado com o " inverno AI " e o breve ganho de Lisp em meados da década de 1990.

Em 2010, havia onze implementações Common Lisp mantidas ativamente. Scieneer Common Lisp é uma nova implementação comercial bifurcada do CMUCL com um primeiro lançamento em 2002.

A comunidade de código aberto criou uma nova infraestrutura de suporte: CLiki é um wiki que coleta informações relacionadas ao Common Lisp, o diretório Common Lisp lista recursos, #lisp é um canal IRC popular e permite o compartilhamento e comentários de trechos de código (com suporte de lisppaste , um bot IRC escrito em Lisp), Planet Lisp recolhe conteúdos de vários blogues relacionados com Lisp, em LispForum os utilizadores discutem tópicos Lisp, Lispjobs é um serviço de anúncio de ofertas de emprego e existe um serviço de notícias semanais, Weekly Lisp News . Common-lisp.net é um site de hospedagem para projetos de código aberto Common Lisp. Quicklisp é um gerenciador de biblioteca para Common Lisp.

Cinquenta anos de Lisp (1958–2008) foram celebrados no LISP50 @ OOPSLA. Existem 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 International Lisp Conference.

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 na década de 2000 (década). O Relatório Revisado 5 sobre o padrão Algorithmic Language Scheme do Scheme foi amplamente aceito na comunidade Scheme. O processo Scheme Requests for Implementation criou muitas bibliotecas e extensões quase padronizadas para o Scheme. 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 R 6 RS Scheme em 2007. O uso acadêmico do Scheme para o ensino de ciência da computação parece ter diminuído um pouco. Algumas universidades não estão mais usando o Scheme em seus cursos introdutórios de ciência da computação; O MIT agora usa Python em vez do Scheme para seu programa de graduação em ciência da computação e o massivo curso online aberto do MITx.

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

Em outubro de 2019, Paul Graham lançou uma especificação para Bel , "um novo dialeto do Lisp".

Dialetos principais

Common Lisp e Scheme representam dois fluxos principais de desenvolvimento Lisp. Essas linguagens incorporam escolhas de design significativamente diferentes.

Common Lisp é um sucessor do Maclisp . As principais influências foram Lisp Machine Lisp , Maclisp, NIL , S-1 Lisp , Spice Lisp e Scheme. Ele tem muitos dos recursos do Lisp Machine Lisp (um grande dialeto Lisp usado para programar máquinas Lisp ), mas foi projetado para ser implementado com eficiência em qualquer computador pessoal ou estação de trabalho. Common Lisp é uma linguagem de programação de propósito geral e, portanto, possui um grande padrão de linguagem, incluindo muitos tipos de dados integrados, funções, macros e outros elementos de linguagem, e um sistema de objetos ( Common Lisp Object System ). O Common Lisp também emprestou certos recursos do Scheme, como escopo lexical e fechamentos lexicais . Implementações do Common Lisp estão disponíveis para diferentes plataformas como LLVM , Java virtual machine , x86-64, PowerPC, Alpha, ARM, Motorola 68000 e MIPS, e sistemas operacionais como Windows, macOS, Linux, Solaris, FreeBSD, NetBSD, OpenBSD, Dragonfly BSD e Heroku.

Scheme é um dialeto com escopo estático e apropriadamente recursivo de cauda da linguagem de programação Lisp inventada por Guy L. Steele, Jr. e Gerald Jay Sussman . Ele foi projetado para ter uma semântica excepcionalmente clara e simples e poucas maneiras diferentes de formar expressões. Projetado cerca de uma década antes do Common Lisp, Scheme é um design mais minimalista. Ele tem um conjunto muito menor de recursos padrão, mas com certos recursos de implementação (como otimização de chamada final e continuações completas ) não especificados no Common Lisp. Uma ampla variedade de paradigmas de programação, incluindo estilos imperativos, funcionais e de transmissão de mensagens, encontram expressão conveniente no Scheme. O esquema continua a evoluir com uma série de padrões ( Relatório n revisado sobre o esquema de linguagem do algoritmo) e uma série de solicitações de esquema para implementação .

Clojure é um dialeto recente do Lisp que visa principalmente a máquina virtual Java e o Common Language Runtime (CLR), o Python VM, o Ruby VM YARV e a compilação para JavaScript . Ele foi projetado para ser uma linguagem pragmática de propósito geral. Clojure extrai influências consideráveis ​​de Haskell e coloca uma ênfase muito forte na imutabilidade. Clojure fornece acesso a bibliotecas e estruturas Java, com dicas de tipo opcionais e inferência de tipo , para que chamadas para Java possam evitar reflexão e permitir operações primitivas rápidas. Clojure não foi projetado para ser compatível com outros dialetos Lisp.

Além disso, os dialetos Lisp são usados ​​como linguagens de script em muitas aplicações, com a mais conhecida sendo Emacs Lisp no editor Emacs , AutoLISP e posterior Visual Lisp no AutoCAD , Nyquist no Audacity e Scheme no LilyPond . O potencial pequeno tamanho de um interpretador de Scheme útil o torna particularmente popular para scripts integrados. Os exemplos incluem SIOD e TinyScheme , ambos integrados com sucesso no processador de imagem GIMP sob o nome genérico "Script-fu". LIBREP, um interpretador Lisp de John Harper originalmente baseado na linguagem Emacs Lisp , foi embutido no gerenciador de janelas Sawfish .

Dialetos padronizados

Lisp tem dialetos oficialmente padronizados: Esquema R6RS , Esquema R7RS , Esquema IEEE, ANSI Common Lisp e ISO ISLISP .

Inovações de linguagem

Lisp foi a primeira linguagem em que a estrutura do código do programa é representada fiel e diretamente em uma estrutura de dados padrão - uma qualidade muito posteriormente apelidada de " homoiconicidade ". Assim, as funções Lisp podem ser manipuladas, alteradas ou mesmo criadas dentro de um programa Lisp sem manipulações de nível inferior. Isso geralmente é considerado uma das principais vantagens da linguagem no que diz respeito ao seu poder expressivo, e torna a linguagem adequada para macros sintáticas e avaliação metacircular .

Uma condicional usando uma sintaxe if – then – else foi inventada por McCarthy em um contexto Fortran. Ele propôs sua inclusão no ALGOL , mas não fazia parte da especificação Algol 58 . Para Lisp, McCarthy usou a cond- estrutura mais geral . Algol 60 adotou o if-then-else e o popularizou.

Lisp influenciou profundamente Alan Kay , o líder da equipe de pesquisa que desenvolveu Smalltalk no Xerox PARC ; e, por sua vez, o Lisp foi influenciado por Smalltalk, com dialetos posteriores adotando recursos de programação orientada a objetos (classes de herança, encapsulamento de instâncias, passagem de mensagens, etc.) na década de 1970. O sistema de objetos Flavors introduziu o conceito de herança múltipla e o mixin . O Common Lisp Object System fornece herança múltipla, métodos multimétodos com despacho múltiplo e funções genéricas de primeira classe , produzindo uma forma flexível e poderosa de despacho dinâmico . Ele serviu como modelo para muitos sistemas de objeto Lisp subsequentes (incluindo Scheme ), que são frequentemente implementados por meio de um protocolo de metaobjeto , um design metacircular reflexivo no qual o sistema de objeto é definido em termos de si mesmo: Lisp era apenas a segunda linguagem depois de Smalltalk (e ainda é uma das poucas linguagens) possuir tal sistema de metaobjetos. Muitos anos depois, Alan Kay sugeriu que, como resultado da confluência desses recursos, apenas Smalltalk e Lisp poderiam ser considerados sistemas de programação orientada a objetos concebidos adequadamente.

Lisp introduziu o conceito de coleta de lixo automática , em que o sistema percorre o heap em busca de memória não utilizada. O progresso em algoritmos de coleta de lixo sofisticados e modernos, como coleta de lixo geracional, foi estimulado por seu uso em Lisp.

Edsger W. Dijkstra, em sua palestra sobre o Prêmio Turing de 1972 , disse:

"Com alguns princípios básicos em sua fundação, ele [LISP] mostrou uma estabilidade notável. Além disso, LISP tem sido o portador de um número considerável de nossos aplicativos de computador mais sofisticados. LISP jocosamente foi descrito como“ a maneira mais inteligente de fazer mau uso de um computador. ”Acho essa descrição um grande elogio porque transmite todo o sabor da liberação: ajudou vários de nossos mais talentosos companheiros humanos a terem pensamentos antes impossíveis”.

Em grande parte por causa de seus requisitos de recursos com relação aos primeiros hardwares de computação (incluindo os primeiros microprocessadores), Lisp não se tornou tão popular fora da comunidade de IA como Fortran e a linguagem C descendente de ALGOL . Devido à sua adequação a aplicações complexas e dinâmicas, Lisp está desfrutando de certo ressurgimento do interesse popular nos anos 2010.

Sintaxe e semântica

Observação : os exemplos deste artigo são escritos em Common Lisp (embora a maioria também seja válida em Scheme ).

Expressões simbólicas (expressões S)

Lisp é uma linguagem orientada a expressões . Ao contrário da maioria das outras linguagens, nenhuma distinção é feita entre "expressões" e "declarações" ; todos os códigos e dados são escritos como expressões. Quando uma expressão é avaliada , ela produz um valor (em Common Lisp, possivelmente vários valores), que pode então ser embutido em outras expressões. Cada valor pode ser qualquer tipo de dados.

O artigo de McCarthy de 1958 introduziu dois tipos de sintaxe: Expressões simbólicas ( expressões S , sexps), que refletem a representação interna de código e dados; e expressões meta ( expressões M ), que expressam funções de expressões S. Expressões M nunca foram favorecidas, e quase todos os Lisps hoje usam expressões S para manipular código e dados.

O uso de parênteses é a diferença mais óbvia do Lisp em relação a outras famílias de linguagens de programação. Como resultado, os alunos há muito dão apelidos de Lisp, como Perdido em parênteses estúpidos ou Muitos parênteses supérfluos irritantes . No entanto, a sintaxe da expressão S também é responsável por grande parte do poder do Lisp: a sintaxe é extremamente regular, o que facilita a manipulação por computador. No entanto, a sintaxe do Lisp não se limita à notação tradicional entre parênteses. Ele pode ser estendido para incluir notações alternativas. Por exemplo, XMLisp é uma extensão Common Lisp que emprega o protocolo de metaobjeto para integrar expressões S com Extensible Markup Language ( XML ).

A dependência de expressões dá grande flexibilidade à linguagem. Como as funções Lisp são escritas como listas, elas podem ser processadas exatamente como dados. Isso permite escrever facilmente programas que manipulam outros programas ( metaprogramação ). Muitos dialetos Lisp exploram esse recurso usando sistemas de macro, o que permite a extensão da linguagem quase sem limites.

Listas

Uma lista Lisp é escrita com seus elementos separados por espaços em branco e entre parênteses. Por exemplo, é uma lista cujos elementos são os três átomos , e . Esses valores são digitados implicitamente: eles são, respectivamente, dois inteiros e um tipo de dados específico do Lisp denominado "símbolo" e não precisam ser declarados como tal. (1 2 foo) 12foo

A lista vazia ()também é representada como o átomo especial nil. Esta é a única entidade em Lisp que é um átomo e uma lista.

As expressões são escritas como listas, usando notação de prefixo . O primeiro elemento da lista é o nome de uma função, o nome de uma macro, uma expressão lambda ou o nome de um "operador especial" (veja abaixo). O restante da lista são os argumentos. Por exemplo, a função listretorna seus argumentos como uma lista, então a expressão

 (list 1 2 (quote foo))

avalia para a lista . A "citação" antes de no exemplo anterior é um "operador especial" que retorna seu argumento sem avaliá-lo. Quaisquer expressões sem aspas são avaliadas recursivamente antes que a expressão envolvente seja avaliada. Por exemplo, (1 2 foo)foo

 (list 1 2 (list 3 4))

avalia para a lista . Observe que o terceiro argumento é uma lista; as listas podem ser aninhadas. (1 2 (3 4))

Operadores

Os operadores aritméticos são tratados de forma semelhante. A expressão

 (+ 1 2 3 4)

avalia como 10. O equivalente na notação de infixo seria " ". 1 + 2 + 3 + 4

Lisp não tem noção de operadores implementados em linguagens derivadas de Algol. Operadores aritméticos em Lisp são funções variáveis (ou n-árias ), capazes de receber qualquer número de argumentos. Um operador de incremento '++' no estilo C às vezes é implementado com o nome que incfdá a sintaxe

 (incf x)

equivalente a (setq x (+ x 1)), retornando o novo valor de x.

"Operadores especiais" (às vezes chamados de "formas especiais") fornecem a estrutura de controle do Lisp. Por exemplo, o operador especial ifleva três argumentos. Se o primeiro argumento não for nulo, ele será avaliado como o segundo argumento; caso contrário, ele avalia o terceiro argumento. Assim, a expressão

 (if nil
     (list 1 2 "foo")
     (list 3 4 "bar"))

avalia para . Claro, isso seria mais útil se uma expressão não trivial tivesse sido substituída por . (3 4 "bar")nil

Lisp também fornece operadores lógicos and , or and not . Os operadores e e ou fazem avaliação de curto-circuito e retornarão seu primeiro argumento nulo e não nulo, respectivamente.

 (or (and "zero" nil "never") "James" 'task 'time)

será avaliado como "James".

Expressões lambda e definição de função

Outro operador especial,, lambdaé usado para vincular variáveis ​​a valores que são avaliados em uma expressão. Este operador também é usado para criar funções: os argumentos para lambdasão uma lista de argumentos e a expressão ou expressões avaliadas pela função (o valor retornado é o valor da última expressão avaliada). A expressão

 (lambda (arg) (+ arg 1))

avalia para uma função que, quando aplicada, recebe um argumento, vincula-o arge retorna o número um maior do que esse argumento. As expressões lambda não são tratadas de maneira diferente das funções nomeadas; eles são invocados da mesma maneira. Portanto, a expressão

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

avalia para 6. Aqui, estamos fazendo uma aplicação de função: executamos a função anônima passando para ela o valor 5.

Funções nomeadas são criadas armazenando uma expressão lambda em um símbolo usando a macro defun .

 (defun foo (a b c d) (+ a b c d))

(defun f (a) b...)define uma nova função nomeada fno ambiente global. É conceitualmente semelhante à expressão:

 (setf (fdefinition 'f) #'(lambda (a) (block f b...)))

onde setfé uma macro usada para definir o valor do primeiro argumento para um novo objeto de função. é uma definição de função global para a função nomeada . é uma abreviatura de operador especial, retornando um objeto de função. fdefinition 'ffdefinitionf#'function

Átomos

No LISP original, havia dois tipos de dados fundamentais : átomos e listas. Uma lista era uma sequência ordenada finita de elementos, em que cada elemento é um átomo ou uma lista, e um átomo era um número ou símbolo. Um símbolo era essencialmente um item com nome exclusivo, escrito como uma string alfanumérica no código-fonte e usado como um nome de variável ou como um item de dados no processamento simbólico . Por exemplo, a lista contém três elementos: o símbolo , a lista e o número 2. (FOO (BAR 1) 2)FOO(BAR 1)

A diferença essencial entre átomos e listas era que os átomos eram imutáveis ​​e únicos. Dois átomos que apareceram em lugares diferentes no código-fonte, mas foram escritos exatamente da mesma maneira, representavam o mesmo objeto, enquanto cada lista era um objeto separado que poderia ser alterado independentemente de outras listas e poderia ser distinguido de outras listas por operadores de comparação.

À medida que mais tipos de dados foram introduzidos em dialetos Lisp posteriores e estilos de programação evoluíram, o conceito de átomo perdeu importância. Muitos dialetos ainda retêm o átomo predicado para compatibilidade de legado , definindo-o verdadeiro para qualquer objeto que não seja um contra.

Conses e listas

Diagrama de caixa e ponteiro para a lista (42 69 613)

Uma lista Lisp é implementada como uma lista vinculada individualmente . Cada célula dessa lista é chamada de cons (no Scheme, um par ) e é composta de dois ponteiros , chamados de carro e cdr . Eles são respectivamente equivalentes aos campos datae nextdiscutidos na lista vinculada do artigo .

Das muitas estruturas de dados que podem ser construídas a partir de células cons, uma das mais básicas é chamada de lista adequada . Uma lista adequada é o nilsímbolo especial (lista vazia) ou um contras em que caraponta para um dado (que pode ser outra estrutura de cons, como uma lista) e cdraponta para outra lista adequada.

Se um dado contra for considerado o topo de uma lista encadeada, então seu carro aponta para o primeiro elemento da lista e seu cdr aponta para o resto da lista. Por esse motivo, as funções care cdrtambém são chamadas firste restquando se referem a conses que fazem parte de uma lista vinculada (em vez de, digamos, uma árvore).

Assim, uma lista Lisp não é um objeto atômico, como seria uma instância de uma classe de contêiner em C ++ ou Java. Uma lista nada mais é do que um agregado de contras vinculadas. Uma variável que se refere a uma determinada lista é simplesmente um ponteiro para os primeiros contras na lista. O desvio de uma lista pode ser feito baixando a lista; isto é, pegar cdrs sucessivos para visitar cada contras da lista; ou usando qualquer uma das várias funções de ordem superior para mapear uma função em uma lista.

Porque conses e listas são tão universais em sistemas Lisp, é um equívoco comum que eles sejam as únicas estruturas de dados Lisp. Na verdade, todos, exceto os Lisps mais simplistas, têm outras estruturas de dados, como vetores ( matrizes ), tabelas de hash , estruturas e assim por diante.

Expressões S representam listas

Expressões S entre parênteses representam estruturas de listas encadeadas. Existem várias maneiras de representar a mesma lista como uma expressão S. Um contras pode ser escrito em notação de par pontilhado como , onde está o carro e o cdr. Uma lista adequada mais longa pode ser escrita em notação de pares pontilhados. Isso é convencionalmente abreviado como na notação de lista . Uma lista imprópria pode ser escrita em uma combinação das duas - como para a lista de três conses cujo último cdr é (isto é, a lista na forma totalmente especificada). (a . b)ab(a . (b . (c . (d . nil))))(a b c d)(a b c . d)d(a . (b . (c . d)))

Procedimentos de processamento de lista

Lisp fornece muitos procedimentos integrados para acessar e controlar listas. As listas podem ser criadas diretamente com o listprocedimento, que recebe qualquer número de argumentos e retorna a lista desses argumentos.

 (list 1 2 'a 3)
 ;Output: (1 2 a 3)
 (list 1 '(2 3) 4)
 ;Output: (1 (2 3) 4)

Por causa da maneira como as listas são construídas a partir de pares contras , o consprocedimento pode ser usado para adicionar um elemento ao início de uma lista. Observe que o consprocedimento é assimétrico em como trata os argumentos da lista, devido à forma como as listas são construídas.

 (cons 1 '(2 3))
 ;Output: (1 2 3)
 (cons '(1 2) '(3 4))
 ;Output: ((1 2) 3 4)

O appendprocedimento anexa duas (ou mais) listas uma à outra. Como as listas Lisp são listas vinculadas, anexar duas listas tem complexidade de tempo assintótica

 (append '(1 2) '(3 4))
 ;Output: (1 2 3 4)
 (append '(1 2 3) '() '(a) '(5 6))
 ;Output: (1 2 3 a 5 6)

Estrutura compartilhada

As listas Lisp, sendo listas vinculadas simples, podem compartilhar estruturas umas com as outras. Ou seja, duas listas podem ter a mesma cauda , ou seqüência final de contras. Por exemplo, após a execução do seguinte código Common Lisp:

(setf foo (list 'a 'b 'c))
(setf bar (cons 'x (cdr foo)))

as listas fooe barsão e respectivamente. No entanto, a cauda é a mesma estrutura em ambas as listas. Não é uma cópia; as células contras apontando para e estão nas mesmas localizações de memória para ambas as listas. (a b c)(x b c)(b c)bc

Compartilhar a estrutura em vez de copiar pode proporcionar uma melhoria dramática no desempenho. No entanto, essa técnica pode interagir de maneiras indesejadas com funções que alteram listas passadas a eles como argumentos. Alterar uma lista, como substituir o cpor um goose, afetará a outra:

 (setf (third foo) 'goose)

Isso muda foopara , mas também muda para - um resultado possivelmente inesperado. Isso pode ser uma fonte de bugs, e funções que alteram seus argumentos são documentadas como destrutivas por esse motivo. (a b goose)bar(x b goose)

Aficionados de programação funcional evitam funções destrutivas. No dialeto Scheme, que favorece o estilo funcional, os nomes das funções destrutivas são marcados com um ponto de exclamação de advertência, ou "bang" - como set-car!(leia-se set car bang ), que substitui o carro de um contras. No dialeto Common Lisp, funções destrutivas são comuns; o equivalente de set-car!é nomeado rplacapara "substituir carro". Esta função raramente é vista, entretanto, como Common Lisp inclui um recurso especial,, setfpara tornar mais fácil definir e usar funções destrutivas. Um estilo frequente no Common Lisp é escrever código funcionalmente (sem chamadas destrutivas) durante a prototipagem e, em seguida, adicionar chamadas destrutivas como uma otimização onde for seguro fazê-lo.

Formulários de autoavaliação e citações

Lisp avalia expressões que são inseridas pelo usuário. Símbolos e listas avaliam para alguma outra expressão (geralmente, mais simples) - por exemplo, um símbolo avalia o valor da variável que ele nomeia; avalia para . No entanto, a maioria das outras formas avaliam a si mesmas: se entrar no Lisp, ela retorna . (+ 2 3)555

Qualquer expressão também pode ser marcada para evitar que seja avaliada (como é necessário para símbolos e listas). Essa é a função do quoteoperador especial, ou sua abreviatura '(uma aspa). Por exemplo, normalmente se inserir o símbolo foo, ele retorna o valor da variável correspondente (ou um erro, se não houver tal variável). Para se referir ao símbolo literal, digite ou, geralmente ,. (quote foo)'foo

Ambos Common Lisp e Scheme também suportam o operador de crase (denominado quasiquote em Scheme), inserido com o `caractere ( acento grave ). Isso é quase o mesmo que a citação simples, exceto que permite expressões a serem avaliadas e seus valores interpolados em uma lista citada com a vírgula , unquote e vírgula na ,@ emenda operadores. Se a variável snuetiver o valor, então avalia para , enquanto avalia para . O crase é usado com mais frequência na definição de expansões de macro. (bar baz)`(foo ,snue)(foo (bar baz))`(foo ,@snue)(foo bar baz)

Formulários de autoavaliação e formulários entre aspas são equivalentes de Lisp aos literais. Pode ser possível modificar os valores de literais (mutáveis) no código do programa. Por exemplo, se uma função retorna um formulário entre aspas e o código que chama a função modifica o formulário, isso pode alterar o comportamento da função em invocações subsequentes.

(defun should-be-constant ()
  '(one two three))

(let ((stuff (should-be-constant)))
  (setf (third stuff) 'bizarre))   ; bad!

(should-be-constant)   ; returns (one two bizarre)

Modificar uma forma citada como esta geralmente é considerado um estilo ruim e é definido pelo ANSI Common Lisp como errôneo (resultando em comportamento "indefinido" em arquivos compilados, porque o compilador de arquivos pode aglutinar constantes semelhantes, colocá-las em memória protegida contra gravação, etc.).

A formalização da citação de Lisp foi observada por Douglas Hofstadter (em Gödel, Escher, Bach ) e outros como um exemplo da ideia filosófica de auto-referência .

Escopo e fechamento

A família Lisp se divide sobre o uso de escopo dinâmico ou estático (também conhecido como léxico) . Clojure, Common Lisp e Scheme fazem uso de escopo estático por padrão, enquanto newLISP , Picolisp e as linguagens embutidas em Emacs e AutoCAD usam escopo dinâmico. Desde a versão 24.1, o Emacs usa escopo dinâmico e léxico.

Estrutura de lista do código do programa; exploração por macros e compiladores

Uma distinção fundamental entre Lisp e outras linguagens é que em Lisp, a representação textual de um programa é simplesmente uma descrição legível por humanos das mesmas estruturas de dados internas (listas vinculadas, símbolos, número, caracteres, etc.) que seriam usadas por o sistema Lisp subjacente.

Lisp usa isso para implementar um sistema de macro muito poderoso. Como outras linguagens de macro, como C , uma macro retorna código que pode então ser compilado. No entanto, ao contrário das macros C, as macros são funções Lisp e, portanto, podem explorar todo o poder do Lisp.

Além disso, como o código Lisp tem a mesma estrutura das listas, as macros podem ser construídas com qualquer uma das funções de processamento de lista na linguagem. Resumindo, tudo o que o Lisp pode fazer para uma estrutura de dados, as macros do Lisp podem fazer para o código. Em contraste, na maioria das outras linguagens, a saída do analisador é puramente interna à implementação da linguagem e não pode ser manipulada pelo programador.

Esse recurso facilita o desenvolvimento de linguagens eficientes dentro de outras linguagens. Por exemplo, o Common Lisp Object System pode ser implementado de forma limpa como uma extensão de linguagem usando macros. Isso significa que se um aplicativo precisa de um mecanismo de herança diferente, ele pode usar um sistema de objetos diferente. Isso está em total contraste com a maioria das outras línguas; por exemplo, Java não oferece suporte a herança múltipla e não há uma maneira razoável de adicioná-la.

Em implementações simples do Lisp, essa estrutura de lista é interpretada diretamente para executar o programa; uma função é literalmente um pedaço de estrutura de lista que é percorrida pelo interpretador ao executá-la. No entanto, a maioria dos sistemas Lisp substanciais também incluem um compilador. O compilador traduz a estrutura da lista em código de máquina ou bytecode para execução. Este código pode ser executado tão rápido quanto o código compilado em linguagens convencionais como C.

As macros se expandem antes da etapa de compilação e, portanto, oferecem algumas opções interessantes. Se um programa precisar de uma tabela pré-computada, uma macro pode criar a tabela em tempo de compilação, de modo que o compilador precisa apenas produzir a tabela e não precisa chamar o código para criar a tabela em tempo de execução. Algumas implementações Lisp até possuem um mecanismo,, eval-whenque permite que o código esteja presente durante o tempo de compilação (quando uma macro precisa dele), mas não presente no módulo emitido.

Avaliação e loop de leitura-avaliação-impressão

As linguagens Lisp são freqüentemente usadas com uma linha de comando interativa , que pode ser combinada com um ambiente de desenvolvimento integrado (IDE). O usuário digita expressões na linha de comando ou direciona o IDE para transmiti-las ao sistema Lisp. Lisp as expressões inseridas, avalia -as e imprime o resultado. Por esta razão, a linha de comando Lisp é chamada de loop read – eval – print ( REPL ).

A operação básica do REPL é a seguinte. Esta é uma descrição simplista que omite muitos elementos de um Lisp real, como citações e macros.

A readfunção aceita expressões S textuais como entrada e as analisa em uma estrutura de dados interna. Por exemplo, se você digitar o texto no prompt, traduz isso em uma lista vinculada com três elementos: o símbolo , o número 1 e o número 2. Acontece que esta lista também é uma parte válida do código Lisp; ou seja, pode ser avaliado. Isso ocorre porque o carro da lista nomeia uma função - a operação de adição. (+ 1 2)read+

Observe que a fooserá lido como um único símbolo. 123será lido como o número cento e vinte e três. "123"será lido como a string "123".

A evalfunção avalia os dados, retornando zero ou mais outros dados Lisp como resultado. Avaliação não precisa significar interpretação; alguns sistemas Lisp compilam todas as expressões em código de máquina nativo. No entanto, é simples descrever a avaliação como interpretação: para avaliar uma lista cujo carro nomeia uma função, evalprimeiro avalia cada um dos argumentos fornecidos em seu cdr e, em seguida, aplica a função aos argumentos. Nesse caso, a função é adição e aplicá-la à lista de argumentos produz a resposta . Este é o resultado da avaliação. (1 2)3

O símbolo fooavalia o valor do símbolo foo. Dados como a string "123" são avaliados como a mesma string. A lista avalia a lista (1 2 3). (quote (1 2 3))

É tarefa da printfunção representar a saída para o usuário. Para um resultado simples como 3este é trivial. Uma expressão avaliada como uma parte da estrutura de lista exigiria que printpercorresse a lista e a imprimisse como uma expressão S.

Para implementar um REPL Lisp, é necessário apenas implementar essas três funções e uma função de loop infinito. (Naturalmente, a implementação de evalserá complexa, uma vez que também deve implementar todos os operadores especiais, como ifou lambda.) Isto feito, um REPL básica é uma linha de código: . (loop (print (eval (read))))

O Lisp REPL normalmente também fornece edição de entrada, um histórico de entrada, tratamento de erros e uma interface para o depurador.

Lisp geralmente é avaliado com atenção . No Common Lisp , os argumentos são avaliados na ordem do aplicativo ('leftmost interior'), enquanto no Scheme a ordem dos argumentos é indefinida, deixando espaço para otimização por um compilador.

Estruturas de controle

Lisp originalmente tinha muito poucas estruturas de controle, mas muitas mais foram adicionadas durante a evolução da linguagem. (O operador condicional original do Lisp,, condé o precursor das if-then-elseestruturas posteriores .)

Os programadores no dialeto Scheme freqüentemente expressam loops usando recursão de cauda . A semelhança de Scheme na ciência da computação acadêmica levou alguns alunos a acreditar que a recursão de cauda é a única, ou a mais comum, maneira de escrever iterações em Lisp, mas isso é incorreto. Todos os dialetos Lisp frequentemente vistos têm construções de iteração de estilo imperativo, desde o doloop de Scheme até as expressões complexas de Common Lisploop . Além disso, a principal questão que torna esta questão mais objetiva do que subjetiva é que o Scheme faz requisitos específicos para o tratamento de chamadas de cauda e, portanto, a razão pela qual o uso de recursão de cauda é geralmente encorajado para Scheme é que a prática é expressamente apoiada por a definição da linguagem. Por outro lado, o ANSI Common Lisp não requer a otimização comumente chamada de eliminação de chamada final. Assim, o fato de que o estilo recursivo de cauda como um substituto casual para o uso de construções de iteração mais tradicionais (como do, dolistou loop) é desencorajado no Common Lisp não é apenas uma questão de preferência estilística, mas potencialmente de eficiência (uma vez que uma cauda aparente chamada em Common Lisp pode não ser compilada como um salto simples ) e correção do programa (uma vez que a recursão final pode aumentar o uso da pilha em Common Lisp, arriscando o estouro da pilha ).

Algumas estruturas de controle Lisp são operadores especiais , equivalentes às palavras-chave sintáticas de outras linguagens. As expressões que usam esses operadores têm a mesma aparência de superfície que as chamadas de função, mas diferem porque os argumentos não são necessariamente avaliados - ou, no caso de uma expressão de iteração, podem ser avaliados mais de uma vez.

Em contraste com a maioria das outras linguagens de programação principais, Lisp permite implementar estruturas de controle usando a linguagem. Várias estruturas de controle são implementadas como macros Lisp, e podem até ser macro-expandidas pelo programador que deseja saber como elas funcionam.

Ambos Common Lisp e Scheme têm operadores para fluxo de controle não local. As diferenças entre esses operadores são algumas das diferenças mais profundas entre os dois dialetos. O esquema suporta continuações reentrantes usando o call/ccprocedimento, que permite a um programa salvar (e posteriormente restaurar) um local específico em execução. Common Lisp não suporta continuações reentrantes, mas suporta várias maneiras de lidar com continuações de escape.

Freqüentemente, o mesmo algoritmo pode ser expresso em Lisp em um estilo imperativo ou funcional. Como observado acima, o Scheme tende a favorecer o estilo funcional, usando recursão de cauda e continuações para expressar o fluxo de controle. No entanto, o estilo imperativo ainda é possível. O estilo preferido por muitos programadores de Common Lisp pode parecer mais familiar para programadores acostumados a linguagens estruturadas como C, enquanto o preferido por Schemers se assemelha mais a linguagens puramente funcionais como Haskell .

Por causa da herança inicial do Lisp no processamento de listas, ele possui uma ampla gama de funções de ordem superior relacionadas à iteração em sequências. Em muitos casos em que um loop explícito seria necessário em outras linguagens (como um forloop em C) em Lisp, a mesma tarefa pode ser realizada com uma função de ordem superior. (O mesmo é verdade para muitas linguagens de programação funcionais.)

Um bom exemplo é uma função que em Scheme é chamada mape em Common Lisp é chamada mapcar. Dada uma função e uma ou mais listas, mapcaraplica a função sucessivamente aos elementos das listas em ordem, coletando os resultados em uma nova lista:

 (mapcar #'+ '(1 2 3 4 5) '(10 20 30 40 50))

Isso aplica a +função a cada par correspondente de elementos da lista, produzindo o resultado . (11 22 33 44 55)

Exemplos

Aqui estão alguns exemplos de código Common Lisp.

O programa básico " Hello, World! ":

(print "Hello, World!")

A sintaxe Lisp se presta naturalmente à recursão. Problemas matemáticos, como a enumeração de conjuntos definidos recursivamente, são simples de expressar nesta notação. Por exemplo, para avaliar o fatorial de um número :

(defun factorial (n)
    (if (zerop n) 1
        (* n (factorial (1- n)))))

Uma implementação alternativa ocupa menos espaço na pilha do que a versão anterior se o sistema Lisp subjacente otimizar a recursão de cauda :

(defun factorial (n &optional (acc 1))
    (if (zerop n) acc
        (factorial (1- n) (* acc n))))

Compare os exemplos acima com uma versão iterativa que usa a macro do Common Lisploop :

(defun factorial (n)
    (loop for i from 1 to n
        for fac = 1 then (* fac i)
        finally (return fac)))

A função a seguir inverte uma lista. (A função reversa integrada do Lisp faz a mesma coisa.)

(defun -reverse (list)
    (let ((return-value))
      (dolist (e list) (push e return-value))
      return-value))

Sistemas de objetos

Vários sistemas de objetos e modelos foram construídos em cima, ao lado ou no Lisp, incluindo:

Veja também

Referências

Leitura adicional

links externos

História
Associações e reuniões
Livros e tutoriais
Entrevistas
Recursos