plp-aula-Lisp

Prévia do material em texto

Paradigmas de Linguagens de 
Programação
LISP
2
Tópicos
 Programação funcional.
 LISP → “List Processing”.
 Um programa em LISP define uma ou mais 
funções, chamadas para executar o que se 
deseja. 
 Por isto LISP é um exemplo de liguagem que 
segue a “programação funcional”.
3
Paradigma funcional
 Idéias chave da programação funcional:
 A computação é vista como um conjunto de 
funções matemáticas mapeando entradas e 
saídas;
 Não há variáveis, laços e atribuição.
 Exemplos de linguagens que usam 
programação funcional:
 LISP, Scheme e Haskell.
4
LISP
5
LISP
 Foi criada em 1960 por John McCarthy;
 Linguagem funcional original:
 Não é case-sensitive.
 O padrão Common Lisp, consolidado em 
1990, une vários dialetos de LISP;
 http://www.softwarepreservation.org/proje
cts/LISP/book/LISP%201.5%20Programmers%20
Manual.pdf
 http://www-prod-gif.supelec.fr/docs/cltl/cltl2.ht
ml
6
LISP
 Foi a primeira a adotar um sistema de 
gerenciamento de memória conhecido 
como coleção de lixo (garbage collection).
7
Exemplos LISP
 Cálculo de derivadas Simbólicas:
 LISP usa notação pré-fixa. A função x2 + 3x é 
denotada por:
 (+ (* x x) (* 3 x)).
 Se definirmos uma função DERIV, calculamos 
a derivada chamando:
 (deriv '(+ (* x x) (* 3 x))).
 Resposta:
 (+ (* 2 x) 3)
8
Exemplos LISP
 O Psiquiatra
 ELIZA: primeiro programa de computador a 
passar o Teste de Turing
Um juiz humano conversa em linguagem 
natural com um humano e uma máquina 
criada para ter desempenho indistinguível 
do ser humano, sem saber qual é máquina 
e qual é humano.
 Foi escrito por Joseph Weizenbaum em 1966.
 Existe uma versão dentro do Emacs: M-x M-x 
doctor.doctor.
9
Exemplos LISP
 MYCIN
 Sistema pioneiro para diagnósticos médicos;
 Foi um dos precursores dos sistemas especialistas;
 Representa seu conhecimento sobre os sintomas e 
possíveis diagnósticos como um conjunto de regras 
da seguinte forma:
 SE a infecção é bacteremia primária
 E o local da cultura é um dos locais estéreis
 E suspeita-se que a porta de entrada é o trato 
gastro-intestinal
 ENTÃO há evidência sugerindo (0.7) que a 
infecção é bacteróide.
10
Common Lisp
11
Common Lisp
 Como instalar no Linux:
 sudo apt-get clisp
 Ou pelo Gerenciador de pacotes Synaptic.
 Sintaxe Common Lisp:
 Para usar → $ clisp
 Para usar o help → digite :h
 Para sair digite (quit)
 Usar com arquivo: escreva um arquivo de texto simples 
com as expressões a avaliar, dê a ele extensão .lsp, e 
chame clisp < arquivo.lsp
 Carregar um arquivo: (load “arquivo.lsp”)
12
Tipos Atômicos
 Tipos:
 Só para dados; não para variáveis.
Átomos
Números Símbolos Strings
Inteiros
Razões
Ponto flutuante
Complexos
Nomes de funções:
seqüências de 
caracteres que 
podem incluir letras, 
números e sinais 
especiais, exceto 
brancos e parênteses
13
Pares com Pontos
 Tipos (Pares-com-pontos):
 São estruturas, ou registros, com dois 
componentes: car e cdr.
 Listas: definidas como sendo uma lista vazia 
ou um cons, cujo cdr é uma lista.
 O símbolo NIL é usado para denotar a lista 
vazia. A expressão () é sinônima de NIL.
Pares com Pontos
Listas Não-listas
14
Aritmética
 LISP possui definidos operadores para as quatro 
operações: +, -, *, /
 A função + recebe um número qualquer de 
argumentos e retorna a soma de todos eles;
 A função - subtrai do primeiro argumento todos os 
outros, exceto quando há só um argumento: daí ela 
retorna o oposto dele; 
 A função * recebe um número qualquer de 
argumentos e retorna o produto de todos eles. 
 A função / divide o primeiro argumento 
sucessivamente por cada um dos outros, exceto 
quando há só um argumento: daí ela retorna o 
inverso dele.
15
Aritmética
 Operadores relacionais: 
 >, <, >=, <=, = (igual), /= (diferente)
 eq (IDÊNTICO) → (eq a b): 
 Compara se os argumentos são derivados um do 
outro (não compara listas; 
 equal (EQUIVALENTE) → (equal a b):
 Compara se os argumentos são equivalente (pode 
comparar listas)
 Operadores lógicos:
 and, or, not
16
Representação Gráfica
 Representação Gráfica: caixas
 Colocamos uma caixa com dois 
compartimentos;
 Cada um deles com um apontador para 
uma componente do cons: 
O compartimento esquerdo aponta 
para o car e o direito para o cdr.
17
Representação Gráfica
 Representação Gráfica:
 Representação gráca do par-com-ponto cuja 
representação textual é: 
 ( ( A . 1 ) . ( "ca" . ( x . 10.0 ) ) ).
18
Representação Gráfica
 Representação Gráfica:
 (A . NIL) ou simplesmente (A)
 Lista: (A ( A B) E)
19
CAR, CDR e CONS
 CAR ou FIRST:
 Retorna o primeiro componente de um 
par-com-ponto.
 CDR ou REST:
 Retorna a segunda componente do 
par-com-ponto.
 CONS:
 Recebe dois argumentos e retorna uma nova 
caixa contendo estes argumentos como 
componentes, na ordem dada.
20
Estrutura da Linguagem
 Um programa em LISP define uma ou 
mais funções;
 Dois estilos de escrever códigos em LISP:
– LISP puro;
– Funções com efeitos colaterais.
21
Definindo Funções
 Macro defun.
 Usada para definir funções em LISP;
 Sintaxe básica:
defun nome lista-de-args corpo
 Exemplo:
 Calcular o quadrado entre dois números
 Lembre-se: devemos usar os operadores +, -, * e / 
com notação pré-fixa.
22
Definição de Funções
 Função vs. macro (defun e defmacro):
 Macro apenas expande e não avalia nada;
 Os argumentos de uma função são 
sempre avaliados antes de serem 
passados para ela;
 Argumentos opcionais: têm que ser sempre os 
últimos, e são introduzidos através da chave 
&optional.
 Número variável de argumentos: a chave 
&rest junta todos os argumentos restantes 
numa lista e passa esta lista à função.
23
Condicionais IF e COND
 IF
 Recebe três argumentos:
 if expr1 expr2 expr3.
 Exemplos:
 Comparar dois números e retorna o maior entre eles.
 Calcular as raízes de uma equação do segundo grau.
24
Condicionais IF e COND
 COND
 Como o switch em C, possui um número 
qualquer de argumentos;
 Em cada um deles, o primeiro elemento é um 
teste. Se o teste é verdadeiro, o segundo 
elemento é retornado;
 O resultado é NIL caso nenhum dos testes 
avaliados seja verdadeiro;
 No último teste, é comum usar o símbolo 
especial T (como o default em um case do C)
25
Condicionais IF e COND
 Exemplos:
 Comparar dois números e retornar o maior 
entre eles:
(defun maior (x y) (cond ((> x y) x) (t y)))
 Comparar três números e retornar o maior 
entre eles:
(defun maior3 (x y z) (cond ((and (>= x y) (>= x z)) x) 
 ((and (>= y x) (>= y z)) y) ((and (>= z x) (>= z y)) z)))
26
Variáveis Locais
 LET:
 Esta palavra pode ser traduzida como “seja” em 
português; 
 Numa função, às vezes você gostaria de dizer: “seja x 
igual a ...” e continuar um cálculo baseado em x;
 LET permite que façamos este tipo de construção.
 Exemplo:
 (defun raiz (a b c) (let ((disc (discr a b c))) (/ (+) (- b) (sqrt 
disc)) (* 2 a)))
 (defun discr (a b c) (- (* b b) (* 4 a c)))
27
Atribuindo Valores a Símbolos
 A macro defun atribui um valor como 
função ao símbolo que é o nome da 
função;
 Existe uma macro análoga, para atribuir 
um valor como dado: setf.
 setf nome valor
 Exemplo:
 (setf x 8)
28
Atribuindo Valores a Símbolos
 SETF:
 setf é bastante usado para variáveis globais ou 
vetores;
 setf é muito útil para armazenar expressões grandes 
para testar funções junto ao interpretador;
 No entanto, é importante evitar seu uso 
indiscriminado, por exemplo, em simplestradução de 
construções imperativas (de Pascal, C ou Java) para 
LISP.
29
 Recursão ocorre quando uma função 
chama a si própria, direta ou 
indiretamente. 
 Exemplos:
 Calcular o fatorial de um número n.
 Somar números inteiros de 1 a n.
 Contar quantos inteiros positivos existem em uma lista.
Recursão
30
Recursão – Método do 
Quadradão
 Maneira de raciocinar que pode ser útil 
para escrever a definição de funções 
recursivas em LISP.
31
Recursão – Método do 
Quadradão
 Exemplo: 
 Suponha que queiramos escrever a função my-count, 
que recebe um item e uma lista e retorna o número 
de ocorrências deste item na lista.
 O que significa o sinal de interrogação?
32
Recursão – Método da Cauda
 Loops transformados em funções recursivas 
assim resultam numa forma de recursão 
especial, chamada de recursão de cauda (tail 
recursion);
 É mais eficiente do que outras formas de 
recursão. 
 Ocorre quando o resultado das chamadas 
recursivas é retornado sem modicação pela 
função.
33
Recursão – Método da Cauda
 Exercícios:
 Escreva a função my-last, que recebe uma lista e 
retorna a última caixa desta lista, ou NIL se a lista for 
vazia.
 Exemplo:
(defun soma (n) (somaux n 0 1))
(defun somaux (n soma i) (if (> i n) soma
(somaux n (+ soma i) (1+ i)) ) )
35
Exercício 1
 Escreva uma função para determinar o MDC 
entre dois números, x e y:
36
Exercício 2
 Escreva uma função que retorne o tamanho de 
uma lista:
37
Exercício 3
 Escreva uma função para criar uma lista (ou 
seja, que faça a mesma coisa que a macro list):
38
Exercício 4
 Escreva uma função que retorne o n-ésimo 
elemento de uma lista:
39
Exercício 5
(defun contpos(lista) (if (null lista) 0 (if (> (car lista) 
0) (+ 1 (contpos (cdr lista))) (contpos (cdr lista)))))
Resolva este mesmo exercício usando cond.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39