Linguagem Lisp

Prévia do material em texto

CENTRO ESTADUAL DE EDUCAÇÃO TECNOLÓGICA
“PAULA SOUZA”
FACULDADE DE TECNOLOGIA DE TAQUARITINGA
CURSO SUPERIOR DE TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS
TÓPICOS ESPECIAIS EM INFORMÁTICA
TEMA: LISP 
PROFESSOR: MSc. JOÃO DE LUCCA FILHO
ALUNOS:
GUILHERME HENRIQUE VALENTIM
 MARÍLIA GOMES RODRIGUES
1º semestre de 2015
INTRODUÇÃO
Este trabalho tem como objetivo aprofundar os conceitos de LISP, LISTAS, FUNÇÕES, COMMON LISP, CLOS, S-EXPRESSIONS E MACROS, SCHEME E LAMBDA. E discorrer sobre a versatilidade da linguagem funcional LISP e suas implementações.
LISP
LISP (LISt Processing) é uma família de linguagens de programação funcional (o método básico de computação é a aplicação de funções e argumentos), criada por John McCarthy em 1958. Durante os anos de 1970 e 1980, LISP se tornou a principal linguagem da comunidade de inteligência artificial, tendo sido pioneira em aplicações como administração automática de armazenamento, linguagens interpretadas e programação funcional. A primeira utilização da tecnologia foi na criação de programas capazes de enfrentar seres humanos em partidas de xadrez.
Historicamente o Lisp é a linguagem da inteligência artificial, por excelência, e assim sendo, diversos projetos em IA (Inteligência Artificial) foram escritos em Lisp.
Foi a primeira a adotar um sistema de gerenciamento de memória conhecido como coleção de lixo (garbage collection), que nada mais é que um processo usado para a automação do gerenciamento de memória. Com ele é possível recuperar uma área de memória inutilizada por um programa, o que pode evitar problemas de vazamento de memória, resultando no esgotamento da memória livre para alocação.
O USO DE LISP
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;
Por ser funcional, se adapta muito bem ao grande desafio dos programadores atuais: a programação paralela;
Usa cartão de crédito? Saiba que Lisp é uma das tecnologias mais utilizadas na detecção de fraudes;
Lisp é a principal linguagem usada em estudos de inteligência artificial.
A linguagem teve um grande sucesso em softwares do ramo de negócios, engenharia, processamento de documentos, hipermídia (incluindo a Web), matemática, gráficos, 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 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.
Há aplicações de LISP nos domínios do processamento simbólico e de conhecimento (IA), e na confecção de programas muito difundidos como editores (EMACS) e CAD (AUTOCAD).
•	O EMACS, um editor de texto, leitor de e-mail, navegador web, agenda de compromissos, e tudo o que você possa imaginar, é quase todo escrito em Emacs Lisp (A parte mais baixo-nível do editor é escrita em C.).
•	O AUTOCAD, um famoso aplicativo de design 3D, usa um dialeto de Lisp como linguagem de script.
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.
LISP é uma linguagem extremamente rica quanto aos tipos de dados que podem ser divididos em três tipos básicos:
•	Símbolos: são dados nomeados, como nomes de funções e variáveis usadas durante o programa. Ex.: aux, cont10, isto_é_uma_variável;
•	Números: abrange todas as categorias de números aceitos pela linguagem: inteiros, ponto flutuante, racionais, complexos, etc;
•	Listas: é um conjunto de dados relacionados delimitados por parênteses. Ex.: (1 2 3 4), (a b (c d) e), (). 
	Em certos exemplos, pode aparecer o caractere aspas simples “ ’ ” precedendo algum símbolo. Isto indica que o respectivo símbolo não deve ser avaliado pelo interpretador, sendo enxergado apenas como uma string, um caractere ou uma constante.
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. 
DEFINIÇÃO DE LISTAS
	LISP foi desenvolvida como uma linguagem de manipulação de listas. Uma lista pode ser considerada uma estrutura de dados privilegiada devido a sua facilidade de manipulação. 
	Delimitados por parênteses, a quantidade de elementos de uma lista pode variar de 0, 1 ou mais elementos (número finito).
Exemplos:
( 1 2 a b “Ana” 5 6 ) - é uma lista de 7 elementos;
( 1 (2 a b c 5 6 ) )	- é uma lista de 2 elementos sendo que o 2º elemento também 			 é uma lista;
( ) - é uma lista vazia.
	De acordo com os exemplos, verifica-se que os elementos de uma lista são separados apenas por um espaço em branco, sem a utilização de qualquer caractere especial como vírgula ou chaves.
DEFINIÇÃO DE FUNÇÕES
	Para se definir uma função, o interpretador LISP precisa de três conhecimentos básicos:
1.	O nome da função;
2.	Os argumentos;
3.	Os procedimentos da função.
	Com a combinação destes três passos, pode-se escrever uma função bem simples chamada de newlikes. 
	defun – este macro permite a definição de uma nova função.
	( defun new likes ( name )
		( setf likes ( cons name likes ) )
		( setf dislikes ( remove name dislikes ) ) )
	Seguindo o exemplo acima, os três passos completos são:
1.	O nome da função: newlikes
2.	O argumento: name
3.	Os procedimentos: adiciona a variável name na lista likes e a remove da lista dislikes.
A chamada da função deve ser da seguinte forma: (newlikes ‘name). Neste exemplo não há preocupação com o conteúdo das listas likes e newlikes uma vez que a prioridade aqui é mostrar o corpo de uma função. 
Existem diversos dialetos de LISP, sendo os mais conhecidos o Common LISP e o Scheme.
LISP: VANTAGENS E DESVANTAGENS
VANTAGENS
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.
DESVANTAGENS
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 trabalhar com programas procedurais ou programas orientados a objeto.
COMMON LISP
Common LISP é uma implementação específica da linguagem de programação LISP, multi-paradigma que suporta programação funcional e procedural. Foi criada por Guy L. Steele nos anos 1980 a partir da linguagem LISP com o intuito de combinar aspectos de diversos dialetos LISP anteriores, incluindoScheme. Foi proposto inicialmente o nome de "Standard LISP" para a linguagem, mas em virtude de um dialeto LISP já existir com este nome, se buscou um nome similar, resultando no nome "Common LISP".
O Common LISP surgiu como uma união das variantes de LISP existentes na década de 1980, e agrega diversas funcionalidades desses dialetos. Nesse sentido, pode-se dizer que a linguagem não é particularmente simples, e de fato, possui uma quantidade notável de dados de precisão arbitrária e um sistema de orientação a objetos notavelmente complexo. 
O Commom LISP é notado como completo, em particular quando comparado com o Scheme. Porém, o fato de a linguagem possuir uma riqueza maior de recursos disponíveis tende a tornar o código mais portável, pois pode-se realizar em uma grande quantidade de tarefas sem a necessidade de bibliotecas externas. Esse é um dos principais problemas práticos com o Scheme, em que qualquer programa de tamanho moderado, acaba usando extensões fornecidas pela implementação e não cobertas pelo padrão da linguagem. 
EXEMPLOS DE CÓDIGOS EM COMMON LISP
Olá mundo:
(defun olá-mundo
	(formatt “Olá mundo”)) 
Entrada e saída:
(defun pergunta (string)
	(format t “ ~% ~%~A” string)
	(read))
(pergunta “Quantos anos você tem? “) 
CLOS
CLOS foi desenvolvido especificamente para o esforço de normalização e foi separadamente escrito no {Common LISP Object System Specification}. No entanto, pequenos detalhes do seu projeto foram ligeiramente mudados. CLOS é a parte do Common LISP responsável pelas características usuais de uma linguagem de programação orientada a objetos como classes, métodos, herança, etc. Para a sua implementação foram criadas macros para definir classes, métodos para criar instâncias.
FUNÇÕES DE PRIMEIRA CLASSE
Em LISP, funções são elementos de primeira classe, isto é, podem ser usadas como qualquer outro valor da linguagem, podendo ser passadas como parâmetro ou retomadas como funções. O Commom LISP usa escopo estático por padrão; se uma função g é retornada por uma função f, g será capaz de acessar as variáveis definidas de f, que são visíveis em seu escopo, mesmo depois de f ter retomado. O uso de tais funções associadas a ambientes, denominadas closures, é bastante comum em Commom LISP. 
SCHEME
Scheme é uma linguagem de programação multiparadigma que suporta programação funcional e procedural. Foi criada por Guy L. Steele e Gerald Jay Sussman em 1975, a partir da linguagem LISP com o intuito de estudar a teoria dos atores de Carl Hewitt. O modelo de Hewitt era orientado a objeto (e influenciado pelo Smalltalk). Os objetos eram chamados atores e as mensagens eram também atores. Sussman e Steele tiveram algum problema no entender algumas das conseqüências do modelo a partir dos artigos de Hewitt e decidiram construir uma implementação de brinquedo de uma linguagem de atores visando experimentá-la. Escreveram um pequeno interpretador LISP e adicionaram os mecanismos necessários para a criação de atores e envio de mensagens. Existem dois padrões que definem a linguagem Scheme: o padrão oficial IEEE e um padrão popular chamado "Revised Report on the Algorithmic Language Scheme", abreviado como RnRS, onde n é o número de revisões.
Scheme adota uma filosofia minimalista, assim sendo, provê o mínimo de noções possíveis, e, na prática, qualquer outra noção pode ser adicionada via bibliotecas, como todos os dialetos do LISP, possui pouca sintaxe comparado à maioria das outras linguagens. Devido à sua sintaxe completamente aninhada, não existem regras de precedência de operadores e sua notação parentizada é usada para todas as chamadas de função, desta forma não há ambigüidades como as que são encontradas nas linguagens de notação infixa. Porém em procedimentos que existam muitos fatores a serem abordados, o programa pode ficar visualmente confuso e necessita ser analisado com mais cuidado.
EXEMPLOS:
(5+3)seria assim: (+ 5 3)
(5+3)*2 seria assim: (* (+ 5 3) 2)
(8/2)seria assim: (/ 8 2)
Exemplo de um procedimento composto:
((lambda (x) (+ x x)) (* 3 4))
Neste caso:
3*4 = 12;
x = 12;
x + x = 12 + 12 = 24;
EXEMPLOS DE CÓDIGOS EM SCHEME
Olá mundo:
(define ola-mundo
	(lambda ()
		(display “Olá mundo!”)
		(newline)))
(ola-mundo)
Ou, simplesmente: 
(display “Olá mundo!”)
S-EXPRESSIONS
Uma importante característica das linguagens da família LISP é o fato de que o código dos programas é representado por estruturas de dados da própria linguagem, coletivamente denominadas S-expressions. Por exemplo, a lista (+2 3) representa a aplicação da função + aos argumentos 2 e 3. + é um símbolo (uma estrutura de dados específica do LISP), 2 e 3 são números e os parênteses são usados para delimitar listas. Quando uma lista representando código é avaliada ou compilada, o primeiro elemento da lista é tratado como uma função a ser aplicada aos argumentos restantes. 
Essa característica dá ao LISP sua sintaxe peculiar, e também é fonte de uma das propriedades mais interessantes da linguagem: pode-se estende-la arbitrariamente com novas construções sintáticas, através de transformações de código realizadas sobre as listas que o compõem. Isso se dá em geral, através da definição de macros, funções que mapeiam árvores de código em novas árvores de código. 
LAMBDA
Projetada por Alonzo Church nos anos 1930, cálculo lambda, também escrito como cálculo-λ, é um sistema formal que estuda funções recursivas computáveis, no que se refere à teoria da computabilidade, e fenômenos relacionados, como variáveis ligadas e substituição. Sua principal característica são as entidades que podem ser utilizadas como argumentos e retornadas como valores de outras funções.
A parte relevante de cálculo lambda para computação ficou conhecida como cálculo lambda não-tipado. O cálculo lambda tipado e o não-tipado têm suas idéias aplicadas nos campos da lógica, teoria da recursão (computabilidade) e linguística, e tem tido um grande papel no desenvolvimento da teoria de linguagens de programação (com a versão não-tipada sendo a inspiração original para programação funcional, em particular LISP, e a versão tipada contribuindo para fundamentar modernos sistemas de tipos e linguagens de programação). 
O cálculo lambda consiste de uma linguagem de termos lambda junto com uma teoria equacional (que pode também ser entendida operacionalmente).
Como os nomes de funções são uma mera conveniência, o cálculo lambda não tem interesse em nomear uma função. Já que todas as funções esperando mais de um argumento podem ser transformadas em funções equivalentes recebendo uma única entrada, o cálculo lambda não tem interesse em criar funções que aceitam mais de um argumento. E como os nomes dos argumentos são irrelevantes, a noção nativa de igualdade entre termos lambda se chama equivalência-alpha e que demonstra este princípio.
DEFINIÇÃO FORMAL DO LAMBDA
Expressões lambda são compostas por:
variáveis v1, v2, …, vn
símbolos abstratos λ (lambda) e . (ponto)
parênteses ( )
Considerando um número infinito de identificadores: {a, b, c, …, x, y, z, x1, x2, …}, o conjunto de todas as expressões do lambda pode então ser descrito pela seguinte gramática:
<expressão> ::= <identificador>
<expressão> ::= (λ<identificador>. <expressão>)
<expressão> ::= (<expressão><expressão>)
Os ajustes de lambda, Λ, podem ser definidas recursivamente:
se x é uma variável, então x ∈ Λ
se x é uma variável e M ∈ Λ, então (λx.M) ∈ Λ
se M, N ∈ Λ, então (M N) ∈ Λ
Instâncias da regra 2 são conhecidas como abstrações e instâncias de regra 3 são conhecidas como aplicações.
CONCLUSÃO
O estudo da LISP é intrigante, pois podemos perceber que a linguagem é mais que uma ferramenta importante em aplicações para Inteligência Artificial, LISP é uma linguagem madura, altamente portável, que desenvolvedores a utilizam em várias áreas de programação, percebe-se que aplicações em LISP são totalmente possíveis, viáveis e factíveis. 
REFERÊNCIAS
Steele, Jr., Guy L. (1990). Common LISP:the language (2nd ed.). Digital Press, Newton,
MA, USA.
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 p. p. 1. 
 Friedman, Daniel P.; Felleisen, Matthias. The Little LISPer. New York: Macmillan, 1989. 206 p. p. xiii.
 Bergin, Thomas J.; Gibson, Richard G.. History of Programming Languages II. New York: ACM Press, Addison-Wesley, 1996. 864 p.  
 McCarthy, J; Brayton, R.; Edwards, D. Fox, P.; Luckham, D.; Maling, K.; Park, D.; Russell, S (Março 1960). LISPI Programmers Manual Artificial Intelligence Group, M.I.T. Computation Center and Research Laboratory. 
2
13