LISP Slides PDF

Inteligência Artificial INTRODUÇÃO  2 O QUE É A INTELIGÊNCIA ARTIFICIAL (IA) ? Muitas definições de Inteligência Aspectos a considerar: Capacidade de resolver problemas Capacidade de usar o conhecimento –...

Inteligência Artificial INTRODUÇÃO  2 O QUE É A INTELIGÊNCIA ARTIFICIAL (IA) ? Muitas definições de Inteligência Aspectos a considerar: Capacidade de resolver problemas Capacidade de usar o conhecimento – raciocínio Capacidade de Aprender Etc. Medida de inteligência: QI (testes de inteligência)… Jogar xadrez denota inteligência? Em 1980 aparentemente a resposta era consensual… Hoje há máquinas que derrotam o campeão do Mundo! Joaquim Filipe  3 DEFINIÇÃO DE TRABALHO Não há uma definição globalmente aceite. Elaine Rich: “Estudo de como fazer os computadores realizarem tarefas em que de momento as pessoas são melhores.” A certa altura as pessoas eram melhores que as máquinas a fazer operações aritméticas! Joaquim Filipe  4 NASCIMENTO DA IA A designação “Inteligência Artificial” foi inventada em 1956 Conferência em “Darthmouth College”, EUA. Por: John McCarthy, … LISP (1959) Marvin Minsky, … Percetrão (et. Seymour Papert) (1969) Allen Newell, … Logic Theorist (1956) Arthur Samuel, … Teoria de Jogos, Damas (1963) Herbert Simon … Racionalidade Limitada (Premio Nobel) Joaquim Filipe LISP Introdução  6 PARADIGMA FUNCIONAL Funções são “entidades de primeira classe” i.e. são tratadas como valores e podem ser argumentos de outra função, i.e. definir funções de “ordem superior” ou podem ser o resultado da invocação de uma função. Isto é raro em linguagens imperativas ou orientadas para objectos, e na maioria dos casos não são suportadas funções de ordem superior. Podem ser usadas em qualquer operação e podem ser criadas em run-time. Características da programação funcional pura: Funções têm um parâmetro e um resultado. Não há efeitos laterais; implica transparência referencial. Imutabilidade dos dados: não se modificam estruturas de dados; se necessário criam-se novas estruturas que são cópias modificadas das anteriores. Não há atribuição de valores a variáveis Não há anomalias sintáticas ou semânticas Principal estrutura de controlo: recursividade tirando partido da possibilidade de se definir funções de ordem superior A programação funcional decorre do cálculo lambda. Mais informação em: https://thesocietea.org/2016/12/core-functional-programming-concepts/ Inteligência Artificial (c) Joaquim Filipe  7 CÁLCULO LAMBDA Sistema formal baseado em lógica matemática usado para exprimir computação com base na abstração de função e sua aplicação usando ligações de variáveis e substituições. -calculus Representa um modelo de computação universal (Turing- complete) x.x2+1 é uma abstração lambda para a função: f(x)=x2+1 Aplicação: f(3)=10 … (x.x2+1) 3 ➔ 10 No cálculo lambda as funções podem ser usadas como valores de input de outras funções. Exemplo: ((x.x2+1) ((x.x-4) 7)) ➔ 10 As funções lambda podem ser etiquetadas (com um nome): f := (x.x2+1) g:= (x.x-4) E agora pode invocar-se (f (g 7)) ➔ 10 Alonzo Church Inteligência Artificial (c) Joaquim Filipe  8 CONCEITOS BÁSICOS É conveniente rever os seguintes conceitos: Compilação vs. Interpretação Características Vantagens e desvantagens Gestão de memória Heap vs. Stack Caracteristicas Vantagens e desvantagens Métodos Tipos de Dados Semântica Tipos Estáticos vs. Dinâmicos Inteligência Artificial (c) Joaquim Filipe  9 COMPILAÇÃO VS. INTERPRETAÇÃO Compilação: conversão para linguagem máquina antes da execução Vantagens: Velocidade, mas dependente da plataforma Permite a deteção de erros na compilação, Debug lento: Teste de novas versões obriga a recompilar o programa Interpretação: REPL Vantagens: Independência da plataforma Reflexão (capacidade para o programa se alterar a si próprio: Assembler, Lisp, etc.) Útil para testes: criação e instanciação de entidades durante a execução. Essencial em metaprogramação: tratar os programas como dados. https://en.wikipedia.org/wiki/Metaprogramming Tipos de dados dinâmicos Late binding / Duck Typing: tipo definido apenas em tempo de execução (não de compilação) https://en.wikipedia.org/wiki/Type_system#Dynamic_type-checking_and_runtime_type_information Tamanho de programa menor Para além disto: As tecnologias de compilação just-in-time permitem que o gap entre linguagens compiladas e interpretadas esteja a estreitar. As linguagens “bytecode” permitem compilar para uma máquina virtual que depois corre o programa de forma eficiente em diferentes plataformas, com vantagens de ambos os paradigmas. Inteligência Artificial (c) Joaquim Filipe  10 CARACTERISTICAS DE UMA LINGUAGEM INTERPRETADA REFLEXIVA Interpretada: baseada num REPL Compilada por partes Permite testes incrementais rápidos, tirando partido do interpretador. Read Ciclo Read-Eval-Print (instrução) Read-Eval-Print Loop(REPL) Print Eval (resultado) (estrutura) Reflexiva: trata dados como se fossem programas Acesso direto ao avaliador Permite construir código em tempo de execução e portanto criar estruturas de dados que são avaliadas. Inteligência Artificial (c) Joaquim Filipe  11 GESTÃO DE MEMÓRIA: STACK VS. HEAP Stack: Segue uma disciplina LIFO, criada em RAM para cada thread, onde são guardadas as instâncias (frames) de invocação de função incluindo o código e variáveis. Serve para variáveis locais, de tamanho fixo e vida limitada. Rápido, pode usar a cache do CPU, mas limitado (sujeito a overflow) Possível problema com recursividade Heap: Também existe em RAM, mas permite alocação dinâmica de memória, sem intervenção do CPU. Serve para variáveis globais, de tamanho variável e vida indefinida. Lento, mas a limitação de memória é a memória total da máquina Interage-se com o heap através de pointers Gestão pode ser baseada em garbage collection (como em Java ou LISP) ou manual (como em C ou C++). Caso seja manual pode originar memory leaks. Inteligência Artificial (c) Joaquim Filipe  12 TIPOS DE DADOS O sistema de tipos de dados de uma linguagem define a semântica e as regras de comportamento do programa. inteiro: 49 ? carater: 1 ? Vantagens: Abstração e Modularidade (interoperabilidade) Documentação (clarifica a intenção do programador) Permite maximizar, na compilação: otimização e segurança. Verificação de dados: Estática (no texto do código fonte) Pode detetar erros durante a compilação Dinâmica (durante a execução do programa) Pode detetar erros durante a execução (e.g. CommonLisp) Inteligência Artificial (c) Joaquim Filipe  13 VARIÁVEIS Características principais de uma variável: Tipo Tempo de vida de uma variável (lifetime) Desde a criação até ao desaparecimento: vide análise de stack vs. heap. Âmbito de uma variável (scope) Léxico – definido pela análise do texto do código fonte: uma variável pode ser referenciada em blocos internos àquele em que foi definida. Este conceito está associado ao de closure Dinâmico – definido pela forma de encadeamento da invocação de funções ao longo da execução do programa. Inteligência Artificial (c) Joaquim Filipe  14 CARACTERÍSTICAS PRINCIPAIS DO LISP Linguagem Funcional Interpretada Reflexiva Tipos de dados dinâmicos (late binding) Âmbito das variáveis definido de forma léxica Estruturas de dados dinâmicas pervasivas, tirando partido extensivo do heap mas em que os pointers são tratados de forma implícita (transparente) através do tipo de dados: “Lista”. Inteligência Artificial (c) Joaquim Filipe  15 GÉNESE LISP = LISt Processing 1958 Inteligência Artificial (John McCarthy) Dialectos principais: Stanford LISP, MacLisp, InterLisp, Franz Lisp, Zeta Lisp, Common Lisp (1984), ANSI Common Lisp (1999), … Ambientes de desenvolvimento: Lispworks,... Inteligência Artificial (c) Joaquim Filipe  16 LISP: UMA LINGUAGEM FUNCIONAL O LISP tem como elemento central a Função. Um programa em LISP é uma função: devolve um valor em vez de produzir efeitos laterais, tais como alteração de objetos ou atribuição de valores a variáveis. Estilo de Programação: “bottom-up” e “top-down” Dividir para conquistar: “top-down” Vantagem: reduz a complexidade Aumentar o vocabulário da linguagem: “bottom-up” Vantagens: torna os programas mais fáceis de ler, promove a reutilização de código e permite descobrir padrões úteis para o domínio de aplicação. A linguagem e o programa evoluem em conjunto. Importante criar abstrações ajustadas ao domínio de aplicação. Inteligência Artificial (c) Joaquim Filipe  17 LISP “PURO” O LISP “puro” é um núcleo central da linguagem baseado exclusivamente no cálculo lambda, a que mais tarde os vários dialectos adicionaram muitas outras funcionalidades acessórias, algumas das quais desvirtuantes do paradigma funcional. Características principais: Variáveis podem mudar de tipo durante a execução Ausência de operação de atribuição Ausência de sequenciação Ausência de estruturas de controlo iterativas (ciclos) Ausência do conceito de “pointer” para manipulação de estruturas de dados dinâmicas Ausência da necessidade de gerir a memória “heap”. Interpretado (compilado por partes) Programas e dados têm a mesma estrutura Acesso direto ao avaliador o que significa que é possível fazer programas que fazem programas Inteligência Artificial (c) Joaquim Filipe  18 ASPETOS BÁSICOS DO AVALIADOR: PROGRAMAS VS. DADOS Invocação de funções Usa-se listas com a seguinte sintaxe: notação prefixa e entre parêntesis (+ 2 3) => 5 Plica serve para evitar avaliar a expressão à direita, tratando-a como dados e não como programa. ‘a => a ‘(a b) => (a b) Non-case-sensitive Pode escrever-se os nomes das funções e variáveis sem diferenciar maiúsculas de minúsculas. Inteligência Artificial (c) Joaquim Filipe  19 TIPOS DE DADOS ELEMENTARES Átomos Listas Simbolos Estruturas de dados Números dinâmicas, usadas para Inteiros dados e programas Fixnums Bignums Reais Etc. Booleanos Caracteres Strings Outros Inteligência Artificial (c) Joaquim Filipe  20 LITERAIS DE: NÚMEROS, BOOLEANOS, CARATERES E STRINGS Exemplos de literais Inteiros: -1 1 2 Fixnum: [most-negative-fixnum, most-positive-fixnum] Bignum: 64646765756756756756752343 Reais: 1.2 5.3 4.1e7 Booleanos: T NIL Caracteres: #\a #\b Strings: “sou uma string” Inteligência Artificial (c) Joaquim Filipe  21 SÍMBOLOS Permitem representar variáveis e funções Estrutura de um símbolo (slots) Nome, função, valor, lista de propriedades, pacote factorial Name: “factorial” Function: (lambda(...)… Value: nil PList: nil Package: default A tabela de símbolos Factorial A B Car Cdr … Inteligência Artificial (c) Joaquim Filipe  22 LISTAS Listas: Estruturas de dados dinâmicas Baseada em células cons https://en.wikipedia.org/wiki/Cons Exercicio1 : representar graficamente a lista (a b c) A B C NIL Exercicio 2: representar graficamente a lista (a (b c) d) Inteligência Artificial (c) Joaquim Filipe  23 TIPO ABSTRATO LISTA Construtor cons ex.: (cons ‘a ‘(b)) => (a b) Selectores: car ex.: (car ‘(a b)) => a cdr ex.: (cdr ‘(a b)) => (b) Exercicio: representar as estruturas de dados dos parâmetros e resultados Há seletores complexos que se aplicam a listas. Exemplo: (cadr ‘(1 b c d)) ➔b (cddr ‘(1 b c d)) ➔ (c d) (caddr ‘(1 b c d)) ➔c (cdddr ‘(1 b c d)) ➔ (d) Inteligência Artificial (c) Joaquim Filipe  24 MACROS Formas especiais do LISP que definem extensões da estrutura sintática da linguagem. Ao contrário de funções, não implicam invocação e utilização do stack. São meras substituições léxicas. Exemplo: (first ‘(a b c d))  (car ‘(a b c d)) ➔ a (rest ‘(a b c d))  (cdr ‘(a b c d)) ➔ (b c d) (second ‘(a b c d))  (cadr ‘(a b c d)) ➔ b (third ‘(a b c d))  (caddr ‘(a b c d)) ➔ c … Inteligência Artificial (c) Joaquim Filipe  25 NOTAÇÃO BNF BNF = Backus-Naur Form Simbolos terminais Pertencem à linguagem que está a ser descrita e permitem construir expressões. Simbolos não terminais Pertencem à meta-linguagem e são instanciados quando se constrói uma expressão. Regras de Produção Definem a estrutura dos símbolos não terminais em termos de outros símbolos não terminais e de símbolos terminais. Simbolos da notação BNF | “alternativa” a|A “delimitadores de símbolos não terminais” ::= “é descrito por:” ::= a | A * “zero ou mais ocorrências” {prmt}* + “uma ou mais ocorrências” {prmt}+ Inteligência Artificial (c) Joaquim Filipe  26 EXEMPLO: DEFINIÇÃO SINTÁTICA DO TIPO LISTA USANDO BNF ::= ( {}* ) | nil < expressão simbólica> ::= | ::= | | | | | Inteligência Artificial (c) Joaquim Filipe  27 TIPO ABSTRATO DE DADOS Modelo matemático Tipo de dados ≠ de Estrutura de dados Especificação de um tipo de dados através de Identificação dos seus possíveis valores e da Identificação e definição das operações que podem ser executadas sobre esses dados. Um tipo abstrato de dados é independente da implementação. Inteligência Artificial (c) Joaquim Filipe  28 TIPO ABSTRATO LISTA: ALGUMAS FUNÇÕES DE MANIPULAÇÃO list ex.: (list ‘a ‘b) => (a b) append ex.: (append ‘(a b) ‘(c d)) => (a b c d) length ex.: (length ‘(a b)) => 2 nth ex.: (nth 1 ‘(a b c d)) => b reverse ex.: (reverse ‘(a b c d)) => (d c b a) concatenate ex.: (concatenate ‘list ‘(a) ‘(b c)) => (a b c) Etc… - Exercicio: - Escrever a sintaxe da invocação da função append em BNF, sabendo que pode ter qualquer número de args do tipo lista. - identificar dez funções de manipulação de listas existentes em LISP e escrever a respectiva sintaxe em BNF Inteligência Artificial (c) Joaquim Filipe  29 TIPOS NUMÉRICOS FUNÇÕES ARITMÉTICAS (+ (- (* (/ Real | (mod Integer (sqrt Real | (abs + / - * Integer (1+ (1- Real | (sin Integer (cos (exp 1- 1+ (expt sin sqrt cos abs (log … (random Inteligência Artificial (c) Joaquim Filipe  30 OPERAÇÕES COM NÚMEROS (/ 3 5) ➔ 3/5 (1+ (/ 3 5)) ➔ 8/5 (/ 3.0 5) ➔ 0.6 (div 3 5) ➔ Error: Undefined operator DIV (mod 5 4) ➔ 1 (mod 5.1 4) ➔ 1.099999 (% 4 5) ➔ Error: Undefined operator % (sqrt 9) ➔ 3.0 (sqr 3) ➔ Error: Undefined operator SQR Inteligência Artificial (c) Joaquim Filipe  31 ALGUMAS FUNÇÕES INTERESSANTES: LOG, EXP E RANDOM (exp ) potência do número de Euler (e) Exemplo: (exp 1) = 2.71828183 (expt ) : elevado a. (log ) Logaritmo neperiano (ou natural): base 2.71828183 ex= n (log 2.71828183) = ? (log 1) = ? (log ) ; a base é um argumento opcional. Logaritmo de base diferente da de Euler Exemplo: (log 8 2) = ? (random ) random aceita um número n e devolve um número aleatório do mesmo tipo (inteiro ou real) entre 0 (inclusive) e n (exclusive). Inteligência Artificial (c) Joaquim Filipe  32 NÚMEROS MUITO GRANDES Tipo inteiro (numérico / lista): BIGNUM (factorial 3) = 6 (factorial 6) = 720 (factorial 1000) = ?? O LISP dá todos os algarismos! Como? … usa listas: Byte 1 Byte 2 … Byte k NIL Inteligência Artificial (c) Joaquim Filipe  33 TIPO BOOLEAN / PREDICADOS (null (atom List | (listp Symbol | Listp Null (symbolp Real | Atom Symbolp Numberp (numberp Integer Zerop Boolean Oddp Evenp … (zerop (oddp (evenp (floatp (integerp (bignump Inteligência Artificial (c) Joaquim Filipe  34 OPERADORES RELACIONAIS (> (< Real | Integer (= (>= < = > Boolean = ( (bignump 987654321) T Inteligência Artificial (c) Joaquim Filipe  37 EXERCÍCIOS Da lista (3 4 “3” T 5) diga quantos são os seus elementos e de que tipo são (átomo/lista). Faça um diagrama da lista. Da lista (3 (4 6) nil () ((5)) ) diga quais são os seus elementos e de que tipo são (átomo/lista). Qual é o quinto elemento? Faça um diagrama da lista. Qual é o resultado da avaliação da expressão (+ 3 (* 7 6) 5 (/ 4 2))? Quais as listas que correspondem às expressões aritméticas (3+5+6+2)-1, (3+5+6)+2-1, 3+5+6+(2-1), 3+2*5, (5-(2-4))/(3*7) ? Qual a cauda da lista (3 4 5)? E da lista ((3) 4 5)? E da lista ((3) (4 5))? E da lista nil? E da lista contendo nil? Inteligência Artificial (c) Joaquim Filipe  38 EXERCICIOS Qual a cabeça da cauda das seguintes listas: (), (3), (3 4), ((3) 4), ((3) (4 5)), ((3) (4 5) (7)) Diga qual o resultado das seguintes expressões: (cons 1 nil), (cons 3 '(5)), (cons '(3) '(2)), (cons '(3) ()), (cons '(3 (5 6)) '((2 4) 6) ) Diga qual a expressão simbólica contendo o número máximo de cons que permite construir a lista (3 (4) 5). E a lista (3 ((4) 6) 5) ? Diga qual a expressão contendo car's e cdr's que permite obter 5 a partir da lista (3 4 5 6). E da lista (3 4 (1 3 (6 5)) (1 2))? Diga qual a diferença entre a avaliação de (car (car '((1) 2))) e de (car '(car ((1) 2))) (cons (+ 1 2) '(3)) e de (cons '(+ 1 2) '(3)) Inteligência Artificial (c) Joaquim Filipe DEFINIÇÃO DE FUNÇÕES E ESTRUTURAS DE CONTROLO  40 DEFINIÇÃO DE FUNÇÕES (defun () “” ) ;;; Exemplo: (defun media (nota1 nota2 nota3) “faz a media aritmética de 3 notas” (/ (+ nota1 nota2 nota3) 3)) ; devolve um número Inteligência Artificial (c) Joaquim Filipe  41 EXEMPLOS Função para calcular o quadrado de um número (defun quadrado (numero) “devolve o quadrado de um número” (* numero numero)) Função para calcular a área de um círculo (defun areaCirculo (raio) “devolve a área de um circulo, dado o raio” (* 3.14159265 (quadrado raio))) ;o pi não está predefinido Inteligência Artificial (c) Joaquim Filipe  42 FUNÇÕES E SÍMBOLOS DE FUNÇÕES Funções com nome. soma3 Name: “soma3” Ex.: (defun soma3 (x) (+ x 3)) Function: (lambda(...) Símbolo “soma3” tem no slot function esta definição. Value: nil PList: nil Funções sem nome. Package: default Ex.: (lambda (x) (+ 3 x)) Não há nenhum símbolo para memorizar esta definição. O que é executável é a definição (lambda) Exemplo de utilização das funções lambda em LISP: ( (lambda(x) (+ 3 x)) 7) => 10 (* 2 ((lambda(x) (+ 3 x)) 7) => 20 Inteligência Artificial (c) Joaquim Filipe  43 DEPURAÇÃO (DEBUG) (trace {}*) – indica os valores dos argumentos e do resultado de cada vez que uma função é invocada. (dribble ) – envia o output para o ecran e para um ficheiro, simultaneamente (describe ) – dá os parâmetros e a documentação se existir Inteligência Artificial (c) Joaquim Filipe  44 ESTRUTURAS DE CONTROLO DO LISP PURO Sequenciação: não tem. Selecção: Cond Repetição: usa a recursividade Inteligência Artificial (c) Joaquim Filipe  45 SELEÇÃO Sintaxe: (cond … ) ::= ( ) Inteligência Artificial (c) Joaquim Filipe  46 COND: EXEMPLOS (cond ((oddp x) ‘impar) ((evenp x) ‘par)) (cond ((oddp x) ‘impar) (t ‘par)) (cond ((= x 0) 1) (t (* x (fact (1- x))))) Inteligência Artificial (c) Joaquim Filipe  47 MACROS if (if ) exemplo: (if (zerop 3) “nulo” “ok”) ➔ “ok” ecase (ecase ( ) …. ( )) exemplo: (ecase b (a 1) (b 2) (c 3)) ➔ 2 Inteligência Artificial (c) Joaquim Filipe  48 EXEMPLOS Definir a função max para devolver o maior de 2 números: (defun max (x y) “devolve o número maior; se os números forem iguais devolve o segundo” (cond ((> x y) x) (t y))) Definir a função max4 para devolver o maior de 4 números: (defun max4 (x y w z) (max x (max y (max w z)))) Inteligência Artificial (c) Joaquim Filipe  49 RECURSIVIDADE Uma função recursiva tem sempre uma estrutura com 2 condições ou mais: Condição de paragem Condição recursiva (1 ou mais) Exemplo: (defun f (n) (cond (( (set-password 'valentine) (if password > (set-secret 'sesame 'my-secret) ➔ “Password errada” “a password já está definida” > (set-secret 'valentine 'my-secret) ➔ MY-SECRET (setf password new-passwd))) > (get-secret 'fubar) ➔ “Querias…” (defun change-password (old-passwd new-passwd) > (get-secret 'valentine) ➔ MY-SECRET (if (eq old-passwd password) > (change-password 'fubar 'new-password) (setf password new-passwd) ➔“Password não alterada” “Password não alterada”)) > (change-password 'valentine 'new-password) (defun set-secret (passwd new-secret) (if (eq passwd password) ➔ NEW-PASSWORD (setf secret new-secret) > (get-secret 'valentine) ➔ “Querias…” “Password errada”)) > Password ➔ Error: unbound variable (defun get-secret (passwd) > Secret ➔ Error: unbound variable (if (eq passwd password) > (setf password 'cheat) secret > (get-secret 'cheat) ➔ “Querias…” “Querias…”))) Inteligência Artificial (c) Joaquim Filipe  66 EXEMPLO 2 O exemplo anterior serve apenas para guardar 1 segredo pois de cada vez que se avalia o LET redefine-se todas as funções (closures). Possível Solução: > (defun make-secret-keeper () (let ((password nil) (secret nil)) #'(lambda (operation &rest arguments) (ecase operation (set-password (let ((new-passwd (first arguments))) (if password “a password já está definida” (setf password new-passwd)))) (change-password (let ((old-passwd (first arguments)) (new-passwd (second arguments))) (if (eq old-passwd password) (setf password new-passwd) “Password não alterada”))) (set-secret (let ((passwd (first arguments)) (new-secret (second arguments))) (if (eq passwd password) (setf secret new-secret) “Password errada”))) (get-secret (let ((passwd (first arguments))) (if (eq passwd password) secret “Querias…”))))))) Inteligência Artificial (c) Joaquim Filipe  67 EXEMPLO 2 (CONT.) > (defparameter secret-1 (make-secret-keeper)) > secret-1 ➔ # > (funcall secret-1 'set-password 'valentine) ➔ VALENTINE > (funcall secret-1 'set-secret 'valentine 'deep-dark) ➔ DEEP-DARK > (defparameter secret-2 (make-secret-keeper)) > (funcall secret-2 'set-password 'bloody) ➔ BLOODY > (funcall secret-2 'set-secret 'bloody 'mysterious) ➔ MYSTERIOUS > (funcall secret-2 'get-secret 'valentine) ➔ “Password errada” > (funcall secret-1 'get-secret 'valentine) ➔ DEEP-DARK Inteligência Artificial (c) Joaquim Filipe  68 EXERCICIOS Defina funções para Rodar uma lista para a esquerda. (roda-esquerda ‘(1 2 3 4)) => (2 3 4 1) Calcular as raizes reais da equação de 2º grau. (fresolvente 1 0 -1)=> (-1 1) Defina as seguintes funções recursivas: Máximo: max(lista de números)=>valor máximo Fibonacci: fib(n) => n-ésimo na sequência de Fib. Binario: bin(n)=(1 0 … 0) que, dado um número inteiro positivo, constrói uma lista de zeros e uns, formando a representação binária do argumento. Hexadecimal: hex(n)=(0 A 3 … F) que, dado um número inteiro positivo, constrói uma lista de símbolos entre 0 e F, formando a representação hexadecimal do argumento. Inteligência Artificial (c) Joaquim Filipe  69 EXERCICIOS Escreva funções para resolver os seguintes problemas: Espelho(L): Recebe uma lista, que pode ter sublistas, e inverter a ordem de todos os elementos, inclusive dentro das sublistas Lista-ate-n(n): Recebe um número e devolve uma lista com todos os inteiros até n ordenada por ordem crescente. Insere(e p L): insere um elemento e na posição p de uma lista. Insere-ordenado(n L-ord): insere um número numa lista que já está ordenada por ordem crescente, de forma a que o resultado continue a ser uma lista ordenada, utilizando o menor número possível de operações (procura binária). Alisa(L): Recebe uma lista com sublistas e devolve uma lista com os elementos pela mesma ordem mas sem sublistas. Inteligência Artificial (c) Joaquim Filipe  70 EXERCICIOS DE CONJUNTOS Presume-se que um conjunto é representado por uma lista de elementos sem repetição. Conjunto(Lista): Recebe uma lista e devolve um conjunto (elimina os repetidos) Intersecao(C1 C2): Recebe dois conjuntos e devolve o conjunto interseção. Reuniao(C1 C2): Recebe dois conjuntos e devolve o conjunto reunião. Diferenca(C1 C2): Recebe dois conjuntos e devolve o conjunto diferença (C1 – C2). Adiciona(e C1): Devolve o conjunto que resulta de adicionar e ao conjunto C1. Subtrai(e C1): Devolve o conjunto que resulta de retirar e ao conjunto C1. Inteligência Artificial (c) Joaquim Filipe FUNÇÕES LAMBDA, PARÂMETROS E META-FUNÇÕES  72 LAMBDA A função lambda é o elemento básico de programação em LISP. Decorre do cálculo lambda Exemplo: Definição de função: (lambda (x y) (+ x y 1)) Invocação: ((lambda (x y) (+ x y 1)) 2 5) ➔ 8 Inteligência Artificial (c) Joaquim Filipe  73 SYNTAXE COMPLETA DOS PARÂMETROS (lambda ({var}* [&optional {var | (var [initform [svar]])}*] [&rest var] [&key {var | ({var | (keyword var)} [initform [svar]])}* [&allow-other-keys]] [&aux {var | (var [initform])}*)] [[{declaration}* | documentation-string]] {form}*) As var e svar têm de ser símbolos Quando se invoca a função as keywords têm de começar pelo caracter : Uma initform pode ser qualquer expressão LISP. Inteligência Artificial (c) Joaquim Filipe  74 EXEMPLOS &rest (defun g (x &rest r)...) (g 1 2 3 4 5)... x=1 r=(2 3 4 5) &optional (defun f (a &optional (b 5)) (+ a b)) (defun f (a &optional (b 5) &rest z) (cons a (cons b z))) Inteligência Artificial (c) Joaquim Filipe  75 EXEMPLOS (CONT.) &key (defun f (x &key y z w)...) (f 1 :w 3 :y 1)... x=1 y=1 z= w=3 (defun f (x &key y (z 0) w)...) (f 1 :w 3 :y 1)... x=1 y=1 z=0 w=3 Inteligência Artificial (c) Joaquim Filipe  76 FUNCIONAIS (META-FUNÇÕES) Acesso direto ao avaliador do Lisp (mesmo que é usado no REPL) (eval ) exemplo: (defun f(n) (eval (cons (nth n ‘(+ - / *)) ‘(2 3)))) (apply ) exemplo: (defun g(n) (apply (nth n ‘(+ - / *)) ‘(2 3))) (funcall ) exemplo: (defun h(n) (funcall (nth n ‘(+ - / *)) 2 3)) Inteligência Artificial (c) Joaquim Filipe  77 FUNÇÕES DE CORRESPONDÊNCIA mapcar function list &rest more-lists maplist function list &rest more-lists mapc function list &rest more-lists -- não acumulam o resultado mapl function list &rest more-lists mapcan function list &rest more-lists -- usam funções destrutivas mapcon function list &rest more-lists Exemplos: (mapcar ‘+ ‘(1 2 3) ‘(6 7 8)) => (7 9 11) ;; função de 2 argumentos (mapcar #'abs '(3 -4 2 -5 -6)) => (3 4 2 5 6) ;; função de 1 argumento (maplist #'(lambda (x) (cons 'foo x)) '(a b c d)) => ((foo a b c d) (foo b c d) (foo c d) (foo d)) Inteligência Artificial (c) Joaquim Filipe  78 EXEMPLO Dada uma lista de tripletes com a seguinte estrutura: ::= ( ) ::= (*) Defina uma função para listar os países das pessoas com mais de 50 anos. (defun maiores50 (pessoas) (apply #’append ;; remove os nils de uma lista de listas (mapcar (lambda (pessoa) (cond ((> (second pessoa) 50) (cddr pessoa))) (t nil) )) pessoas))) ;;; (maiores50 '((antonio 51 PT)(brad 34 UK) (charles 77 FR))) >> (PT FR) Inteligência Artificial (c) Joaquim Filipe  79 DETALHES Apply #‘append … Útil para remover nils de uma lista de listas. (apply #‘append ‘((a) (b) nil (c) nil nil (d))) >> (a b c d) Pormenor: ( (lambda (pessoa) (cond ((> (second lista) 50) (third p))) (t nil)) ‘(c 77 PT) ) >> PT ( (lambda (pessoa) (cond ((> (second lista) 50) (cddr p)) (t nil))) ‘(c 77 PT) ) >> (PT) Inteligência Artificial (c) Joaquim Filipe  80 EXERCICIOS Qual o resultado de cada uma das invocações de funções abaixo? (mapcar #'1+ '(1 2 3 4 5)) (mapcar #'list '(1 2 3 4 5)) (mapcar #'list '(1 2 3 4 5) '(a b c)) Escreva uma função para somar 2 unidades a todos os elementos de uma lista de números dada. Escreva uma função para somar as raízes quadradas de uma lista de números. Versão recursiva Versão usando funções de ordem superior Escrever uma função para contar o número de números ímpares numa lista. Inteligência Artificial (c) Joaquim Filipe  81 EXERCICIOS Defina funções para 1) multiplicar duas matrizes bidimensionais NxM e MxK (defun multimap (m1 m2) 2) transpor uma matriz quadrada (defun transposta (m) O número de linhas e colunas de cada matriz é arbitrário. Use como representação do tipo de dados matriz uma estrutura de dados na forma de lista de listas. ((…) (... )... ) Inteligência Artificial (c) Joaquim Filipe FUNÇÕES DE E/S  83 FUNÇÕES DE E/S Básicas Read Read-line Write-Line Terpri Format … Estas funções têm um argumento opcional que é o ou. T = (*standard-io*) = ecran NIL = string Inteligência Artificial (c) Joaquim Filipe  84 LEITURA READ Argumentos: (&OPTIONAL (STREAM *STANDARD-INPUT*) (EOF-ERROR-P T) EOF-VALUE RECURSIVE-P) Lê o próximo valor no stream (cujo default é *standard- input*) EOF-ERROR-P e EOF-VALUE especificam o que acontece se o programa tentar ler de um stream vazio: Se EOF-ERROR-P tem o valor true então o Lisp gera uma excepção. Caso contrário retorna o EOF-VALUE (default nil). RECURSIVE-P está reservada a funções invocadas pelo Lisp reader. Inteligência Artificial (c) Joaquim Filipe  85 LEITURA (CONT.) READ-LINE Argumentos: (&OPTIONAL (STREAM *STANDARD-INPUT*) (EOF-ERROR-P T) EOF-VALUE RECURSIVE-P) Devolve a linha de texto lida do stream na forma de uma string, descartando o newline. Outras READ-BYTE stream &optional eof-error-p eof-value READ-CHAR &optional stream eof-error-p eof-value recursive-p Inteligência Artificial (c) Joaquim Filipe  86 ESCRITA FORMAT Argumentos: (STREAM CONTROL-STRING &REST FORMAT-ARGUMENTS) Se STREAM= T, o resultado é escrito no *standard- output*, Se é NIL, o resultado é devolvido como uma string. Caso contrário, STREAM geralmente corresponde a um ficheiro. A CONTROL-STRING contém a string a escrever, geralmente com diretivas embutidas, iniciadas com o carater "~". Inteligência Artificial (c) Joaquim Filipe  87 FORMAT DIRETIVAS: ~A or ~nA Escreve um argumento como PRINC ~S or ~nS Escreve um argumento como PRIN1 ~D or ~nD Escreve um argumento como um inteiro ~% TERPRI ~& FRESH-LINE n é a largura do campo em que o valor é escrito Exemplos: Números reais: Números inteiros: (format t "~d" 1000000) (format t "~$" pi) 1000000 3.14 (format t "~:d" 1000000) (format t "~5$" pi) 1,000,000 3.14159 (format t "~@d" 1000000) +1000000 Inteligência Artificial (c) Joaquim Filipe  88 FORMAT (CONT.) Mais exemplos: (format nil "The value is: ~a" 10) "The value is: 10" (format nil "The value is: ~a" "foo") "The value is: foo" (format nil "The value is: ~a" (list 1 2 3)) "The value is: (1 2 3)“ Format Condicional: (format nil "~[zero~;um~;dois~]" 0) ==> "zero" (format nil "~[zero~;um~;dois~]" 1) ==> "um" (format nil "~[zero~;um~;dois~]" 2) ==> "dois" Inteligência Artificial (c) Joaquim Filipe  89 MAIS DIRECTIVAS ~% new line  ~O octal integer ~& fresh line  ~X hexadecimal integer ~| page break  ~bR base-b integer ~T tab stop  ~R spell an integer ~< justification  ~P plural ~> terminate ~<  ~F floating point ~C character  ~E scientific notation ~( case conversion  ~G ~F or ~E, depending ~) terminate ~( upon magnitude ~D decimal integer  ~$ monetary  ~A legibly, without escapes ~B binary integer  ~S Readably, with escapes  ~~ ~ Inteligência Artificial (c) Joaquim Filipe  90 EXERCICIOS Escreva uma função denominada escreve_numero que receba um número e escreva no écran “O numero é...”. Use a função format. Escreva uma função denominada sequencia_numeros que leia uma sequência de números positivos via teclado, por qualquer ordem, terminada por zero, e escreva no écran a sequência de números lida ordenada por ordem crescente, um número em cada linha. Escreva uma função chamada escreve_lista que escreva o conteúdo duma lista no écran. (escreve_lista ‘(1 2 3)) (1 2 3) Redefina a pergunta anterior em escreve_lista1 de forma a poder escrever um elemento da lista por linha. Recomenda-se o uso da função mapc. (escreve_lista1 ‘(1 2 3)) 1 2 3 Inteligência Artificial (c) Joaquim Filipe  91 FICHEIROS open filename &key :direction :element-type :if-exists :if-does-not-exist :external-format (with-open-file ( {keys}*) ) Inteligência Artificial (c) Joaquim Filipe  92 KEYWORDS DE OPEN Keyword Value Stream Direction ---------- :DIRECTION :INPUT input (default) :OUTPUT output :IO input & output :PROBE none Keyword Value Action if File Exists ---------- :IF-EXISTS :ERROR signal an error :NEW-VERSION next version (or error) :RENAME rename existing, create new :SUPERSEDE replace file upon CLOSE :RENAME-AND-DELETE rename and delete existing, create new :OVERWRITE reuse existing file (position at start) :APPEND reuse existing file (position at end) Keyword Value Action if File Does Not Exist ------------ :IF-DOES-NOT-EXIST :ERROR signal an error :CREATE create the file Inteligência Artificial (c) Joaquim Filipe  93 KEYWORDS DE OPEN (CONT.) Keyword Value Element Type ------------- :ELEMENT-TYPE :DEFAULT character (default) 'CHARACTER character 'SIGNED-BYTE signed byte 'UNSIGNED-BYTE unsigned byte other implementation-dependent Keyword Value File Format ---------------- :EXTERNAL-FORMAT :DEFAULT default (default) other implementation-dependent Inteligência Artificial (c) Joaquim Filipe  94 PATHNAME Em diferentes sistemas operativos as funções de acesso ao sistema de ficheiros podem diferir, sendo conveniente um nível intermédio de abstração, mediante o tipo de dados “pathname”: Construtor: make-pathname &key :host :device :directory :name :type :version :defaults :case Seletores: pathname-host pathname pathname-device pathname pathname-directory pathname pathname-name pathname pathname-type pathname pathname-version pathname Acesso especial: user-homedir-pathname &optional host Teste probe-file namestring Conversão para string: namestring pathname Inteligência Artificial (c) Joaquim Filipe  95 EXEMPLO (make-pathname :host "technodrome" :directory '(:absolute "usr" "krang") :name "shredder") => #P"technodrome:/usr/krang/shredder“ Nota: Em Windows, o acesso a “c:\...” é restrito. Preferível colocar os ficheiros de trabalho num diretório abaixo da raiz ou então noutro disco. Inteligência Artificial (c) Joaquim Filipe  96 EXEMPLO Escreva uma função que copia as linhas impares de um ficheiro “.txt” para um novo ficheiro com o mesmo nome e extensão “.odd”. (defun copia-impares (file1) (let ((path1 (make-pathname :host "e" :directory '(:absolute "") :name file1 :type "txt")) (path2 (make-pathname :host "e" :directory '(:absolute "") :name file1 :type "odd"))) (with-open-file (f1 path1 :direction :input) (with-open-file (f2 path2 :direction :output :if-exists :supersede) (copia-linha f1 f2))))) (defun copia-linha (f1 f2) (let ((linha (read-line f1 nil :fim))) (cond ((not (eq linha :fim))(write-line linha f2) (salta-linha f1 f2)) (t (close f2))))) (defun salta-linha (f1 f2) (let ((linha (read-line f1 nil :fim))) (cond ((not (eq linha :fim))(copia-linha f1 f2)) (t (close f2))))) Inteligência Artificial (c) Joaquim Filipe  97 EXERCICIOS Usando a função with-open-file defina uma função escreve_lista_ficheiro que receba uma lista e um nome completo (caminho + nome) de um ficheiro e que escreva o conteúdo dessa lista – com um elemento por linha - nesse ficheiro. Usando a função with-open-file, e a função read defina uma função le_elementos_ficheiro que receba um nome completo de um ficheiro e que leia todos os elementos existentes nesse ficheiro e os escreva no écran elemento a elemento, um em cada linha. Escreva um função chamada conta_se que conte todos os carateres de um ficheiro cujo código ASCII esteja entre um dado limite inferior e um dado limite superior e retorne uma lista de pares em que cada par é constituído pelo código ASCII do carater relevante e o respetivo número de ocorrências no ficheiro. Pode usar as funções: (code-char ) e (char-code ) Escreva uma função denominada transforma_elementos para ler os elementos numéricos de um dado ficheiro de entrada, e aplicar uma função transforma a cada elemento, a qual converte o elemento em hexadecimal, e escreve o resultado da aplicação dessa função num dado ficheiro de saída. Inteligência Artificial (c) Joaquim Filipe PACKAGES  99 O PROBLEMA Objetivo: evitar confundir símbolos que têm o mesmo nome mas existem em módulos de software diferentes. Namespace problem O problema resolve-se ao nível do Reader no REPL (read-eval-print loop). Duas possibilidades principais: Ocorrências de símbolos com o mesmo nome em diferentes módulos devem ser o mesmo. Ocorrências de símbolos com o mesmo nome em diferentes módulos devem ser diferentes. Inteligência Artificial  100 POSSÍVEIS SOLUÇÕES Em módulos diferentes usar prefixos diferentes para os símbolos. Diferentes programadores podem construir diferentes módulos sem interferir um com o outro. Problemas: Gestão de nomes dependente da auto-disciplina do programador. Dificuldade em combinar que um nome é o mesmo símbolo (com o mesmo valor e/ou mesma definição de função) em vários módulos. Inteligência Artificial  101 EXEMPLO CONCRETO Campeonato de um Jogo de 2 jogadores Necessário: Programa para gerir o jogo, invocando a função principal de cada jogador (recebe o estado e devolve a jogada). Programa que determina a jogada do jogador 1. Programa que determina a jogada do jogador 2. O program de gestão do jogo tem de usar símbolos que pertencem a cada um dos outros programas (a função de jogar) Cada um dos programas de cada jogador tem de encapsular todos os outros símbolos para evitar conflitos. Inteligência Artificial  102 EXEMPLO (ESQUEMÁTICO) campeonato jogar1 jogar2 Jogador 1 Jogador 2 Inteligência Artificial  103 A MELHOR SOLUÇÃO: PACKAGES O LISP tem namespaces implementados na forma de packages (pacotes de símbolos) Existem alguns packages pre-definidos. Exemplo: Common-LISP (nickname: CL) Common-LISP-User (nickname: CL-User) O CL-User usa o CL Há uma constante *package* cujo valor é o package de default (CL-User) A definição de packages faz-se com defpackage Inteligência Artificial  104 EXEMPLO SIMPLES DE UTILIZAÇÃO (defpackage :jogador1) (defpackage :jogador2) (load "w:\\j1.lisp") (load "w:\\j2.lisp") Inteligência Artificial  105 PROGRAMA J1.LISP (in-package :jogador1) (defun alfabeta (…) …) (defun sucessores (e) …) (defun jogar (x)...) Inteligência Artificial  106 PROGRAMA J2.LISP (in-package :jogador2) (defun alfabeta (…) …) (defun sucessores (e) …) (defun jogar (x)...) Inteligência Artificial  107 RECOMENDAÇÕES Cada ficheiro deve indicar o package em que os símbolos são definidos com in-package Apenas deve haver um in-package por ficheiro e deverá ser a primeira linha do ficheiro. Para se poder usar o in-package tem de se definir o package antes (defpackage). Inteligência Artificial  108 DEFINIR PACKAGES (defpackage name &rest options) Name = keyword, correspondente ao nome do package options::= (:nicknames nickname*)* | (:documentation string) | (:use package-name*)* | (:shadow {symbol-name}*)* | (:shadowing-import-from package-name {symbol-name}*)* | (:import-from package-name {symbol-name}*)* | (:export {symbol-name}*)* | (:intern {symbol-name}*)* | (:size integer) Inteligência Artificial  109 OPÇÕES PRINCIPAIS :use conjunto de packages de que o package que está a ser definido herda. Por default, caso não seja dado nada, assume um valor dependente da implementação – habitualmente :Common-LISP. :import-from Os símbolos definidos como argumento são importados para o package que está a ser definido :export Os símbolos definidos como argumento são encontrados ou criados no package que está a ser definido e exportados, por forma a ser partilhados com os packages que usem o package que está a ser definido Inteligência Artificial  110 EXPORT E USE-PACKAGE Mecanismo para importar todos os símbolos relevantes de um dado package: Todos os packages mantêm uma lista de símbolos que é suposto serem usados por outros packages, designada por exported symbol list. Para adicionar um simbolo a esta lista usa-se a função export. Para remover um simbolo desta lista usa-se a função unexport. Para importar todos os símbolos exportados por um package usa-se a função use-package. Para desfazer a operação anterior usa-se a função unuse-package. Inteligência Artificial  111 SHADOWING Shadowing symbols list Lista associada a um package que contém os símbolos isentos de “erros de conflito de símbolos” detetados quando outros packages são “:used” :shadow Conjunto de símbolos criados no package que está a ser definido e que passam a pertencer à shadowing symbols list :shadowing-import-from Conjunto de símbolos importados do package indicado para o package que está a ser definido e que passam a pertencer à shadowing symbols list. Caso exista um símbolo com o mesmo nome no package que está a ser definido esse símbolo é removido do package. Inteligência Artificial  112 INTERN / UNINTERN Todos os símbolos que pertencem a um package são “interned”. Os símbolos são interned no package corrente, que por default é o CL-User. As keywords são interned num package especial com o nome KEYWORD. Um simbolo interned num package pode ser uninterned, deixando de estar acessível. Exemplo, se o package corrente tiver o simbolo fatorial: > (unintern ‘fatorial) T Inteligência Artificial  113 LISTA DE SÍMBOLOS DE UM PACKAGE Para obter todos os simbolos definidos num package: do-symbols (var [package [result- form]]) declaration* {tag | statement}* Há 3 macros: DO-SYMBOLS, DO-EXTERNAL-SYMBOLS, DO-ALL-SYMBOLS Exemplo: (do-external-symbols (s (find-package “KEYWORD")) (print s)) Inteligência Artificial  114 EXERCICIOS Considere um jogo de 2 jogadores em que cada jogador tenta obter um número (objetivo) com uma sequência de N lançamentos de um dado com 6 faces. Ganha o jogador que ficar mais próximo do número. Fazer um programa para o jogador 1 jogar. Use o package jogador-1. Fazer um programa para o jogador 2 jogar. Use o package jogador-2. Fazer um programa jogar num package designado por “campeonato” que jogue alternadamente as funções jogar exportadas por cada um dos packages “jogador-1” e “jogador-2”. As funções jogar recebem um estado (na forma de uma lista de 3 elementos: número a atingir, número corrente do próprio jogador e número corrente do adversário) e devolvem uma jogada (na forma de um boolean: t = joga; nil=pára) A função jogar no campeonato lança o dado (gera um número aleatório) que adiciona ao jogador seguinte, parando o jogo quando ambos os jogadores pararem ou quando um deles ultrapassar o objetivo, caso em que perde. Inteligência Artificial PROGRAMAS COMPLETOS  116 TIPOS ABSTRATOS DE DADOS O LISP é uma linguagem extensível: Permite definir uma linguagem mais abstrata, mais adaptada ao domínio de aplicação Vantagens: Compreensibilidade do código Reutilização de código complexo Facilidade de mudança da representação => Abordagem Bottom-Up Inteligência Artificial (c) Joaquim Filipe  117 EXEMPLO 1 Tipo de dados “Turma” Turma é um conjunto de alunos Necessário definir o tipo “Aluno” Construtor do tipo Aluno (Aluno-novo {: }*) é o nome de uma propriedade qualquer o respetivo valor no mínimo é preciso o # de aluno. Seletor do tipo Aluno (Aluno- ) Construtor do tipo Turma (Turma-nova {}) Seletor do tipo Turma (Turma-alunos {: }*) É habitual os tipos abstratos terem ainda operações de: comparação, predicados, leitura, escrita, para além de toda as operações especificas do tipo abstrato. Inteligência Artificial (c) Joaquim Filipe  118 EXERCICIO 1 Fazer um programa para gerir uma pauta de alunos de uma turma: Adicionar alunos a uma turma Por leitura de um ficheiro Interativamente Cada aluno pode ser representado por uma lista com: numero de aluno, nome, nota do projecto 1, nota do projecto 2, nota do exame e média final. Modificar a nota de um aluno Procurar os alunos com notas positivas Procurar os alunos cujo nome começa por uma dada letra Calcular a média e a moda das notas da turma Calcular o histograma baseado em quartis Ordenar a pauta por nota ou por nome Escrever a pauta Num ficheiro No ecran do computador Inteligência Artificial (c) Joaquim Filipe  119 EXEMPLO 2 Jogo dos animais: o computador faz perguntas ao utilizador, para tentar descobrir o animal em que este pensou. Se não descobrir, aprende o animal. Este jogo é baseado num tipo abstrato de dados que é uma árvore de decisão binária. Admita que a base de dados é constituída por uma estrutura recursiva do tipo: ( ) A estrutura de dados inicial poderia ser a seguinte: (“Tem asas” (“Voa” Pardal Avestruz) (“Mamífero” Cão Rã)) Depois da interacção passaria a ser: (“Tem asas” (“Voa” Pardal (“Nada” Pinguim Avestruz)) (“Mamífero” Cão Rã)) Inteligência Artificial (c) Joaquim Filipe  120 EXERCICIO 2 Construa um programa para: 1. ler de um ficheiro “animais.dat” uma estrutura de dados inicial, representando a árvore binária do jogo. 2. Interagir com o utilizador da forma normal para este jogo, 3. Actualizar a estrutura de dados da forma descrita no exemplo, 4. E, no fim do jogo, escrevê-la no mesmo ficheiro. Inteligência Artificial (c) Joaquim Filipe  121 EXERCICIO 2 (IMPLEMENTAÇÃO) É necessário definir e implementar o tipo abstrato de dados “árvore binária” através de um tipo “nó” recursivo de 3 elementos. (defun faz-no (pergunta sim nao) Exemplo de implementação: (list pergunta sim nao)) (defun escrever-arvore (no &optional (g t)) (defun no-pergunta (no) (format g "~A" no)) (first no)) (defun ler-arvore (&optional (f t)) (read f)) (defun no-sim (no) (second no)) (defun no-nao (no) (third no)) (defun no-terminalp (no) (atom no)) Inteligência Artificial (c) Joaquim Filipe