Noções de lisp
Lisp: LISp Processing
J.M.Barreto INE-CTC-UFSC
Qual a razão de conhecer LISP?
• Segundo McDermot e Charniac a razão é a
mesma de aprender francês se vai estudar na
França: é a lingua natural falada pelos
franceses!
• Será isto ainda verdade?
–Nem tanto, mas...
Será a Programação Funcional?
J. M. Barreto UFSC_INE
Razões para usar LISP (1/4)
• LISP é uma linguagem funcional pobre, mas
raros são os profissionais de IA que
escolhem LISP por suas características
funcionais. Exatamente por esta razão ela é
pobre em termos funcionais: juntam-se
outras facilidades que mascaram o estilo
funcional puro!
J. M. Barreto UFSC_INE
Razões para usar LISP (2/4)
• LISP é estensível e se não se gosta de um
interface oferecido é fácil criar outro.
• LISP tem programa e dados com a mesma
estrutura de dados: listas. Logo, um programa
pode facilmente ler a ele mesmo, modificar-se
durante a execução e continuar funcionando
modificado sem interrupção: isto é, torna-se
fácil implementar algoritmos de aprendizado.
J. M. Barreto UFSC_INE
Razões para usar LISP (3/4)
• Estruturas de dados são facilmente
manipuladas em LISP.
• Por exemplo:
– A pilha é a própria lista;
– Existem primitivas para ler, juntar novo
elemento na pilha, etc.
– Árvores são implementadas como listas de
listas., s3endo fácil percorrê-las e modificá-las.
J. M. Barreto UFSC_INE
Razões para usar LISP (4/4)
• É fácil aprender LISP e seu aprendizado
ajuda a desenvolver capacidades mentais.
Foi exatamente acreditando nisto que
Papert, criou no MIT a linguagem LOGO,
subconjunto de LISP, com ênfase gráfica,
para uso do aprendizado de crianças. As
experiências tem sido animadoras.
E como nasceu esta linguagem?
J. M. Barreto UFSC_INE
Lisp: Nota histórica (1/3)
• John McCarthy vinha trabalhando há anos
em uma linguagem que fosse, como
provado por Turing, equivalente à sua
máquina. Em 1960, dando aula no MIT
demonstrou que a função “eval” era capaz
de simular a máquina de Turing, resultado
teórico de grande valor.
J. M. Barreto UFSC_INE
Lisp: Nota histórica (2/3)
• Um dos alunos de John McCarthy, Steve
Russel comentou: “sendo verdade este
teorema, basta implementar “eval” e
teremos a Máquina de Turing”, ao que
McCarthy contestou “Não confunda teoria
com prática, este é um resultado teórico,
para ter valor prático tem de percorrer um
longo caminho”.
J. M. Barreto UFSC_INE
Lisp: Nota histórica (3/3)
• Russel não se satisfez. Implementou “eval” e
algumas outras funções em Máquina IBM704,
apresentou seu trabalho e assim nasceu Lisp,
linguagem fruto do espírito prático de aluno com
grande conhecimento teórico. Guarda ainda hoje
lembranças do passado:
car: “contents of address register;
cdr: “contents of decrement register;
• Símbolos do assembler do IBM704.
J. M. Barreto UFSC_INE
Sintaxe de Lisp
• Vocabulário de Lisp:
• Atomos: elementos indivisíveis, podendo ser:
– Números; ex: 1, 13, 15, -.35, etc.
– Identificadores: sequencias de letras e números; ex:
Lisa, Jane1, fibo, etc.
– Identificadores reservados: +, -, /, *, car, cdr, etc.
• Delimitadores: (,)
J. M. Barreto UFSC_INE
Sintaxe de Lisp
• Linguagem Lisp:
– Lisp* = atom | lista
– Atom = identificador | identificador reservado |
número
– Lista = (atom) | (atom lista)
J. M. Barreto UFSC_INE
Lisp Puro
• Lisp Puro contem as seguintes funções
primitivas:
–
–
–
–
Car primeiro elemento de uma lista;
Cdr: o que sobra de uma lista tirando o 1º elemento
Cons: constroi lista dado um elemento e uma lista;
Eql: retorna T se os dois elementos que se seguem são
iguais, NIL no caso contrario;
– Atom: retorna T se elemento que o segue é atomico,
NIL em caso contrário.
J. M. Barreto UFSC_INE
Semantica operacional de Lisp Puro
Seletores: car, cdr
–
–
–
–
> (car ´(a d f))
>A
> (cdr ´(a s d f g))
> (s d f g)
Construtor:
– > (cons ‘a ‘(s d f g))
– > (a s d f g)
J. M. Barreto UFSC_INE
Predicado atômico:
–
–
–
–
> (atom ‘jane)
>T
> (atom ‘(a s d f g))
> NIL
Predicado egalitário
–
–
–
–
> (eql ‘casa ‘casa)
>T
> (eql 10 20)
> NIL
Assignação e valor de atomo
• (set ‘a 10)
A
• (setq b 20)
B
• B
20
• ‘B
B
• (atom ‘b)
T
• (atom b)
T
J. M. Barreto UFSC_INE
• (setq c ‘(a s d))
C
• C
(a s d)
• (car c)
A
• (cdr c)
(s d)
• (atom c)
NIL
• (atom ‘c)
T
Manipulação de listas; exemplos
• (setq ‘v ‘(e i o u))
V
• (cons ‘a v)
(a e i o u)
• (car ‘(q w e r t))
Q
• (cdr ‘(q w e r t))
(w e r t)
• (cdr (car v))
nil
J. M. Barreto UFSC_INE
• (car (cdr (cdr ‘(a s d f g))))
D
• (caddr ‘(a s d f g))
D
• (atom v)
Nil
• (eql ‘v ‘v)
T
• (eql ‘v v)
nil
Operações aritméticas
• (+ 2 3 4 5)
14
• (+1 2)
3
• (*2 3)
6
• (* 2 3 4 )
24
J. M. Barreto UFSC_INE
• (* (+ 2 3) (+ 1 2 3))
30
• (* 2 (* 5 6 3) 2)
360
• e assim não é
preciso chamar a
calculadora do
computador...
Novas Funções
• (defun nome-da-função (variáveis ligadas)
(corpo da definição))
• Corpos:
– Cond
– Program
– if
J. M. Barreto UFSC_INE
Exemplos de novas funções
• Encontra o segundo elemento de uma lista:
(defun segundo (lista)
(cadr lista))
• Calcula o fatorial de um número:
(defun fat (n)
(cond (( > n 0) (‘Numero negativo não tem fatorial’))
(( = n 0) 1)
(( = n 1) 1)
(T (fat (- n 1)))))
J. M. Barreto UFSC_INE
• Lê uma lista até um elemento dado retornando o
que sobra:
(defun resto (lista elemento)
(cond ((eql (car lista) elemento) cdr lista)
(T (resto ((cdr lista) elemento )))))
J. M. Barreto UFSC_INE
Exercícios
• Escreva 2 funções
Lisp para juntar novos
telefones e consultar
uma lista de nomes e
de telefones.
Sugestão: use como
estrutura de dados
uma lista de pares,
(nome telefone)
J. M. Barreto UFSC_INE
• Sabendo que sua verão
de Lisp usa > e < para
ordem alfabética,
escreva função Lisp
para colocar em ordem
um lista de nomes.
• E se fosse a lista de
endereços do exercício
anterior?
Que faço com isso tudo?
Jogou!
J. M. Barreto UFSC_INE
• Não!
• Não jogue o pobre
cálculo  no lixo!
• Ele é a base das
linguagens funcionais
e de Lisp, que apesar
de todas as suas
impurezas vale o
estudo!