Como comparar em prolog o valos de x

Programa¸c˜ ao em Prolog ´ UMA ABORDAGEM PRATICA

Eloi L. Favero Departamento de Inform´atica CCEN - UFPA (Vers˜ao 2006) [email protected]

´cnicas de Programac ˜o • Parte I: Fundamentos e Te ¸a – Hist´ orico e Teoria do Prolog ∗ Listas e Estruturas de Dados ∗ Fluxo de Controle e Aritm´etica – T´ ecnicas de Programa¸c˜ ao: ∗ Anima¸c˜ao de Programas ∗ Classifica¸c˜ao e Ordena¸c˜ao • Parte II: A Linguagem Prolog – O Prolog Padr˜ ao ISO – Ambiente de Depura¸c˜ ao ˜ es • Parte III: Estudos de Casos e Aplicac ¸o – Programa¸c˜ ao de Gram´ aticas: Autˆomatos e Gram´aticas Regulares, Gram´aticas Livres de Contexto, Gram´aticas de Atributos; An´alise L´exica, Sint´atica e Semˆantica – Linguagens Formais e Compiladores – Processamento de Linguagem Natural: L´exico/Morfologia, Sintaxe, Gera¸c˜ao de Linguagem Natural – Inteligˆ encia Artificial: KNN, Bayes, Kmeans – Ngramas: Bigramas e Trigramas

Eloi L. Favero Departamento de Inform´atica [email protected] c 2006 Copyright

2006 Para minha companheira Flori e nossos filhos, Emmanuel, Ayun e Thiago pelo amor e a inspira¸c˜ ao. Pref´acio N´os acreditamos que programa¸c˜ao pode ser, e deve ser, uma atividade intelectual recompensadora; e que uma boa linguagem de programa¸c˜ao ´e uma poderosa ferramenta conceitual — uma ferramenta para organizar, expressar, experimentar com, e ainda comunicar nossos pensamentos; ... The Art of Prolog de L. Sterling e E. Shapiro [16]. Objetivos do livro O objetivo deste livro-texto ´e servir como material did´atico na l´ıngua portuguesa para ensino de programa¸c˜ao em Prolog, visando: 1) atender diferentes p´ublicos, de cursos de gradua¸c˜ao at´e cursos de p´os-gradua¸c˜ao, nas ´areas da Ciˆencia da Computa¸c˜ao e correlatas (por exemplo, Sistemas de Informa¸c˜ao); 2) servir de material de apoio para cursos com diferentes cargas hor´arias, de 20 horas at´e 60 horas; e 3) servir como material de referˆencia para usu´arios da linguagem Prolog (adotamos o padr˜ao definido pela norma ISO). Dependendo da dura¸c˜ao do curso, e do p´ublico-alvo, diferentes cap´ıtulos e se¸c˜oes do livro s˜ao usados. No final deste pref´acio sugerimos algumas seq¨uˆencias de cap´ıtulos para alguns usos do livro. A linguagem de programa¸c˜ao Prolog tem sido usada principalmente em disciplinas relacionadas com a ´area de Inteligˆencia Artificial (IA). O Prolog1 , tamb´em, traz bons resultados quando ´e usado nas atividades de programa¸c˜ao de disciplinas tais como: Programa¸c˜ao em L´ogica (a parte pr´atica), Linguagens Formais, Compiladores, Linguagens de Programa¸c˜ao (paradigma l´ogico), entre outras. A abordagem do livro ´e essencialmente pr´atica, em oposi¸c˜ao ao enfoque te´orico da Programa¸c˜ao em L´ogica que destaca assuntos, tais como estrat´egias de resolu¸c˜ao e computabilidade de um programa. O objetivo de um curso pr´atico de Prolog ´e ensinar as t´ecnicas necess´arias para se desenvolver, de forma clara, elegante e concisa, programas que expressam a solu¸c˜ao de problemas reais. Em uma perspectiva complementar, o subt´ıtulo do livro Uma abordagem pr´ atica est´a relacionado ao ditado que diz: o talento nasce da pr´atica fiel. A habilidade de desenvolver programas pensando em Prolog nasce de atividades pr´aticas de programa¸c˜ao. Para isso, apresentamos in´umeros exerc´ıcios associados a cada novo assunto apresentado. Por outro lado, em especial na terceira parte do livro, apresentamos estudos de casos baseados em problemas coletados em diversas 1 Usamos dois termos como sinˆ onimos: “A linguagem Prolog”e “O Prolog”como um sistema que executa a linguagem Prolog. vii viii ´areas da Ciˆencia da Computa¸c˜ao, incluindo: Linguagens Formais, Compiladores, Processamento de Linguagem Natural, Inteligˆencia Artificial e Minera¸c˜ao de Dados. O poder de expressividade do Prolog Desde o surgimento, in´ıcio dos anos 70, o Prolog mant´em sua popularidade devido `a combina¸c˜ao de diversas caracter´ısticas que definem o seu poder expressivo como linguagem de programa¸c˜ao: • Prolog implementa um paradigma de programa¸c˜ ao declarativa (em contraste com o paradigma imperativo de C, Pascal) em que se descreve o que fazer e n˜ao como fazer. Em Prolog, o conhecimento computacional (fatos e regras de inferˆencia) ´e expresso numa forma declarativa de alto n´ıvel; • Prolog trabalha com estruturas de dados de alto n´ıvel. Estruturas de dados complexas, tais como listas, ´arvores, grafos, etc. s˜ao naturalmente representadas e manipuladas em Prolog. Assim sendo, Prolog possibilita prototipa¸c˜ ao r´ apida, por exemplo, para valida¸c˜ao de especifica¸c˜oes de sistemas de software; • Prolog implementa um sistema de resolu¸c˜ao para a l´ogica de cl´ausulas definidas, que ´e um subconjunto significativo da l´ogica de primeira ordem. Apesar desta fundamenta¸c˜ao l´ogica, n˜ao ´e necess´ario ter forma¸c˜ao pr´evia em l´ogica para programar pensando em Prolog; • Prolog vem com um sistema de processamento de regras gramaticais chamado Definite Clause Grammar (DCG), que ´e essencial para o desenvolvimento de aplica¸c˜oes (ou prot´otipos) nas ´areas de Linguagens Formais, Compiladores e Processamento em Linguagem Natural (PLN) — o primeiro Prolog foi desenvolvido para PLN; • Prolog permite metaprograma¸c˜ ao, isto ´e, um programa pode se examinar e se automodificar. Metaprograma¸c˜ao ´e sinˆonimo de linguagens de alta ordem (n˜ao primeira ordem), as quais permitem e facilitam o desenvolvimento de ferramentas para outras linguagens, por exemplo, interpretadores para sistemas de regras para IA. Vale citar, tamb´em, que o Prolog possui uma sintaxe simples, que se mant´em est´avel desde o surgimento do Prolog padr˜ao Edimburgo, em 1977. O padr˜ao ISO Prolog (1996) [10], 19 anos depois, veio afirmar a sintaxe do Prolog Edimburgo como padr˜ao, apenas apresentando um conjunto adicional de predicados predefinidos. Nesse sentido, observa-se que a maior parte dos programas encontrados em livros da d´ecada de 80 rodam sem altera¸c˜oes (ou quase sem) nos interpretadores atuais (por exemplo, os programas do livro Programming in Prolog de Clocksin & Mellish [5], de 1981). Neste texto, sempre que poss´ıvel, adotamos o padr˜ao ISO Prolog; eventuais diferen¸cas s˜ao apontadas. Disciplina de Programa¸c˜ ao Como professor, tenho observado que a pr´atica em Prolog desenvolve algumas habilidades positivas de programa¸c˜ao, que, uma vez adquiridas como talentos, s˜ao levadas para outros ambientes de programa¸c˜ao, tais como C++ e Java. Estas habilidades s˜ao: • Abstra¸c˜ ao: c´odigo de especifica¸c˜ao de alto n´ıvel; ix • Limpeza: c´odigo-fonte limpo, conciso, sem redundˆancias; • Ordem: c´odigo bem estruturado e organizado; • Reusabilidade: em especial, no reuso de predicados revers´ıveis; • Refinamento de programas e Refatora¸c˜ ao de c´ odigo: rescrita de c´odigo quando j´a est´a funcionando visando a generaliza¸c˜ao, a limpeza, a simplicidade, a ordem, o reuso; o uso do interpretador facilita esta atividade (Just In Time Programming). Programas Prolog s˜ao compactos e bem particionados. Em Prolog ´e mais f´acil identificar possibilidades de fatorar c´odigo, removendo predicados redundantes. E, ao mesmo tempo, ´e f´acil identificar possibilidades de reuso de predicados. Por exemplo, o predicado append (para concatenar listas) ´e reus´avel em v´arios outros algoritmos. Isto se deve, em parte, porque em Prolog um procedimento pode assumir mais de um papel: o append, definido inicialmente para concatenar duas listas, pode ser usado para dividir uma lista em duas, a partir de um dado elemento. O Prolog ´e baseado num sistema de resolu¸c˜ao associado a um processo de unifica¸c˜ao. Enquanto um programa procedural ´e baseado em dados+controle (como fazer), um programa em Prolog ´e baseado em fatos+regras (o que fazer). O controle em um programa Prolog est´a impl´ıcito em regras condicionais de alto n´ıvel. Estruturas de dados com tipagem fraca, unifica¸c˜ao e resolu¸c˜ao fazem de um programa Prolog um texto mais pr´oximo de uma especifica¸c˜ao abstrata de um problema e, ao mesmo tempo, execut´avel. O desenvolvimento por refinamentos sucessivos ´e uma t´ecnica de engenharia de software para programa¸c˜ao. O Prolog, quando comparado com as linguagens imperativas, oferece algumas vantagens para trabalharmos com refinamento de programas: nota¸c˜ao concisa e fundamentada em l´ogica; nota¸c˜ao declarativa; procedimentos revers´ıveis; usa somente vari´aveis locais; etc. Estas caracter´ısticas facilitam a escrita de duas vers˜oes equivalentes de um programa, sendo uma vers˜ao um refinamento da outra. Estas habilidades de certa forma est˜ao relacionadas ao poder expressivo da linguagem Prolog, que permite a codifica¸c˜ao de programas altamente concisos, para tratar de problemas relativamente complexos. Por exemplo, um compilador ´e um programa relativamente complexo, at´e mesmo para minilinguagem. Em Prolog podemos implementar um compilador para uma minilinguagem em algumas p´aginas de c´odigo-fonte (como exemplificamos num dos cap´ıtulos do livro). Usos para o Livro O livro ´e constitu´ıdo de 21 cap´ıtulos organizados em trˆes partes. A parte I, cap´ıtulos 1 at´e 8, apresenta os fundamentos e t´ecnicas da programa¸c˜ao Prolog. A parte II, cap´ıtulos 9 e 10, apresenta um guia de referˆencia r´apida da sintaxe do Prolog ISO e o uso do depurador. A parte III explora alguns t´opicos mostrando como programar solu¸c˜oes para problemas complexos: os cap´ıtulos 11 at´e 16 envolvem principalmente programa¸c˜ao de gram´aticas e os cap´ıtulos de 17 a 21 s˜ao t´opicos de IA (aprendizagem de m´aquina e minera¸c˜ao de dados). Pela escolha de uma determinada seq¨uˆencia de cap´ıtulos, o livro-texto pode ser usado tanto em cursos r´apidos de Prolog para estudantes sem experiˆencia em programa¸c˜ao, por exemplo, para estudantes de Ling¨u´ıstica interessados em PLN, como para cursos semestrais avan¸cados para estudantes de p´os-gradua¸c˜ao em Ciˆencia da Computa¸c˜ao. Seguem algumas sugest˜oes de usos para o livro-texto: • Curso r´ apido de Prolog (30 horas). S˜ao recomendados os primeiros quatro cap´ıtulos da Parte I, podem ser vistos s´o superficialmente os cap´ıtulos 5, 6, 7 e 8. x • Programa¸c˜ ao em L´ ogica e Prolog (60 horas). O livro ´e indicado para a parte da linguagem Prolog. Todos os cap´ıtulos da Parte I, mais alguns da Parte III. • Fundamentos de programa¸c˜ ao para IA (60 horas). Come¸cando com Curso r´apido de Prolog. Mais alguns t´opicos da parte III. • Fundamentos de Prolog para Linguagens Formais e Compiladores (entre 20 e 60 horas). Ou para o desenvolvimento de processadores de linguagens. Come¸cando com o Curso r´apido de Prolog, mais os cap´ıtulos sobre Programa¸c˜ao de Gram´aticas e PLN. • Paradigma L´ ogico dentro de uma disciplina de Linguagens de Programa¸c˜ao (10 horas). Os primeiros quatro cap´ıtulos da Parte I, ou apenas o cap´ıtulo 1 e parte do cap´ıtulo 2 (s´o duas horas-aula). Sobre o autor O autor ´e Bacharel em Ciˆencias da Computa¸c˜ao pela UFRGS (1983-1987), Mestre em Ciˆencias da Computa¸c˜ao pela UFRGS (1987-1990) e ´e Doutor em Ciˆencias da Computa¸c˜ao com ˆenfase em Computa¸c˜ao Inteligente pela UFPE (1996-2000). Professor e pesquisador do Departamento de Inform´atica da UFPA desde 1991, atua tamb´em nos cursos de Mestrado e Doutorado do Programa de P´os-Gradu¸c˜ao em Engenharia El´etrica e Computa¸c˜ao (PPGEEC) da UFPA, na sub´area de Computa¸c˜ao Aplicada. O autor vem desenvolvendo pesquisa em algumas sub´areas da Inteligˆencia Artificial (IA): IA Simb´olica, Processamento de Linguagem Natural e Agentes Inteligentes para Web. Sum´ario I Fundamentos e T´ ecnicas de Programa¸c˜ ao em Prolog 1 Introdu¸c˜ ao ao Prolog 1.1 Hist´orico . . . . . . . . . . . . . . . . . . . 1.2 Programa = regras + fatos . . . . . . . . . 1.2.1 Regras e fatos em Prolog . . . . . 1.2.2 Termos e predicados . . . . . . . . . 1.2.3 Conven¸c˜oes para leitura de cl´ausulas 1.2.4 Perguntas . . . . . . . . . . . . . . 1.3 Revis˜ao . . . . . . . . . . . . . . . . . . . . 1.4 SWI-Polog . . . . . . . . . . . . . . . . . . 1.4.1 Entrando no SWI-Prolog . . . . . . . 1.4.2 Rodando um programa . . . . . . . 1.5 Erros de sintaxe . . . . . . . . . . . . . . . 1 . . . . . . . . . . . 3 4 5 5 6 7 8 9 10 10 11 13 . . . . . . . . . . . . . . 15 16 18 20 21 22 23 24 25 27 28 28 29 30 31 3 Programa¸c˜ ao com Listas 3.1 Opera¸c˜oes sobre o tipo lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 O tipo de dados lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 34 34 . . . . . . . . . . . . . . . . . . . . . . 2 Teoria da Programa¸c˜ ao em L´ ogica 2.1 L´ogica proposicional . . . . . . . . . . . . . . . 2.2 L´ogica de cl´ausulas (para proposi¸c˜oes) . . . . . 2.2.1 Provas por refuta¸c˜ao (para proposi¸c˜oes) 2.3 L´ogica de primeira ordem (ou predicados) . . . . 2.3.1 Cl´ausulas de Horn com predicados . . . . 2.3.2 O significado de um programa . . . . . . 2.3.3 Universo de Herbrand . . . . . . . . . . 2.4 O procedimento de resolu¸c˜ao . . . . . . . . . . 2.4.1 Estrat´egias de resolu¸c˜ao . . . . . . . . 2.5 F´ormulas l´ogicas x Cl´ausulas . . . . . . . . . . . 2.5.1 Transforma¸c˜ao de f´ormulas em cl´ausulas 2.5.2 Transforma¸c˜oes para cl´ausulas . . . . . . 2.6 Conclus˜ao . . . . . . . . . . . . . . . . . . . . 2.6.1 Transforma¸c˜oes para cl´ausulas . . . . . . xi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Programa¸c˜ao recursiva . . . . . . . . . . . . . . 3.3.1 Usando um acumulador . . . . . . . . . 3.4 Sele¸c˜ao em Listas . . . . . . . . . . . . . . . . 3.4.1 Membros de uma lista . . . . . . . . . 3.4.2 Explorando o significado de um predicado 3.5 Constru¸c˜ao de listas . . . . . . . . . . . . . . . 3.6 Trabalhando com ordem . . . . . . . . . . . . . 3.6.1 Ordem alfanum´erica . . . . . . . . . . . 3.7 Listas para teoria dos conjuntos . . . . . . . . . 3.8 Refatora¸c˜ao: Otimiza¸c˜ao de predicados . . . . . 3.9 Predicados para listas do SWI-Prolog . . . . . . 3.10 *Programa¸c˜ao procedural vs l´ogica (Opcional) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 37 39 39 40 41 44 45 46 48 51 52 4 Programando o fluxo de controle 4.1 Interpreta¸c˜ao procedimental para cl´ausulas . . 4.2 Predicados de controle . . . . . . . . . . . . 4.2.1 Os predicados fail/0, true/0 e repeat/0 4.2.2 O operador de corte (!) . . . . . . . . 4.2.3 If-then-else ( −> ; ) . . . . . . . 4.2.4 Nega¸c˜ao por falha . . . . . . . . . . . 4.2.5 Meta chamada e resposta u´nica . . . . 4.3 Recursividade com entrada e sa´ıda . . . . . . 4.3.1 Mudando a ordem de predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 56 57 57 58 61 61 63 64 65 5 Programa¸c˜ ao aritm´ etica 5.1 Avaliando express˜oes aritm´eticas . . . . . 5.2 Processamento aritm´etico . . . . . . . . 5.3 Recursividade e itera¸c˜ao . . . . . . . . . 5.3.1 Somando os ´ımpares . . . . . . . 5.3.2 Valores aleat´orios (randˆomicos) . 5.4 Refinamento de programas . . . . . . . . 5.4.1 Criptografia aritm´etica . . . . . . 5.4.2 Vers˜ao inicial . . . . . . . . . . . 5.4.3 Uma solu¸c˜ao mais eficiente . . . 5.5 Gerar histograma para dados estat´ısticos 5.5.1 Conclus˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 67 68 69 70 71 71 71 72 73 75 78 Estruturas de Dados 6.1 Manipula¸c˜ao de Dados . . . . . . . . . . . . . 6.1.1 Metapredicados . . . . . . . . . . . . . 6.1.2 Incluindo e excluindo fatos e regras . . . ´ 6.2 Arvores bin´arias . . . . . . . . . . . . . . . . . 6.2.1 Mais sobre representa¸c˜ao de informa¸c˜ao . 6.2.2 Percurso em ´arvores bin´arias . . . . . . ´ 6.3 Arvore de busca . . . . . . . . . . . . . . . . . 6.3.1 Busca . . . . . . . . . . . . . . . . . . 6.3.2 Inser¸c˜ao . . . . . . . . . . . . . . . . . 6.3.3 Remo¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 79 81 83 84 86 86 90 91 91 93 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 6.5 Manipula¸c˜ao de grafos . . . . . . . . . . . . . 6.4.1 Usando um custo em cada nodo . . . . 6.4.2 Trabalhando com uma lista de arcos . **Diferen¸ca de listas (t´opico avan¸cado) . . . . 6.5.1 Concatenar diferen¸cas de listas . . . . 6.5.2 Usando diferen¸cas de listas no percurso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . de ´arvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 . 95 . 96 . 98 . 99 . 101 7 Anima¸c˜ ao de programas 7.1 Torres de Hanoi . . . . . . . . . . . . . . . . . . . . 7.1.1 Salvando e atualizando o estado das hastes . . 7.2 Jogo-da-Velha . . . . . . . . . . . . . . . . . . . . . 7.2.1 Estrat´egia de jogo para vencer (ou n˜ao perder) 7.2.2 O jogo do advers´ario do computador . . . . . 7.2.3 Desenhar o tabuleiro . . . . . . . . . . . . . . 7.2.4 A listagem do programa todo . . . . . . . . . 7.2.5 Falando sobre testes . . . . . . . . . . . . . . 7.3 Projetos: Utilizando estrat´egias de jogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 103 105 108 110 111 112 113 115 117 8 Classifica¸c˜ ao e ordena¸c˜ ao 8.1 Ordena¸c˜ao por permuta¸c˜ao . . . . . . . . . 8.2 Inser¸c˜ao direta . . . . . . . . . . . . . . . . 8.3 Ordena¸c˜ao por sele¸c˜ao . . . . . . . . . . . 8.4 Ordena¸c˜ao por troca (bublle sort) . . . . . 8.5 Ordena¸c˜ao por intercala¸c˜ao . . . . . . . . . 8.6 Ordena¸c˜ao por intercala¸c˜ao (otimizada) . . . 8.7 Ordena¸c˜ao por parti¸c˜ao e troca (Quick sort) 8.8 Medindo a performance de programas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 120 120 122 122 123 123 125 126 II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ambientes de Programa¸c˜ ao e Sintaxe do Prolog ISO 9 Depura¸c˜ ao de Programas 9.1 O modelo de execu¸c˜ao de Byrd . . . . . 9.2 Controle do n´ıvel de espionagem . . . . . 9.3 Modos de depura¸c˜ao: trace ou debugging 9.4 Interagindo com o trace . . . . . . . . . 131 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 134 136 137 137 10 O padr˜ ao ISO Prolog 10.1 Cl´ausulas e Termos . . . . . . . . . . . . . . . . . . . . . . . . 10.1.1 Tipos de dados . . . . . . . . . . . . . . . . . . . . . . . 10.1.2 Termo composto . . . . . . . . . . . . . . . . . . . . . . 10.1.3 Dados vs programa = s´ımbolos funcionais vs predicativos 10.1.4 Coment´arios . . . . . . . . . . . . . . . . . . . . . . . . 10.2 Operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 10.2.1 Operadores vs Arvore sint´atica . . . . . . . . . . . . . . 10.3 Express˜oes aritm´eticas . . . . . . . . . . . . . . . . . . . . . . . 10.3.1 Functores aritm´eticos embutidos no Prolog . . . . . . . . 10.4 Construindo e decompondo termos . . . . . . . . . . . . . . . . 10.5 Base de fatos e regras (cl´ausulas e predicados) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 142 142 144 145 145 146 148 149 151 152 153 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.5.1 Encontrando m´ultiplas solu¸c˜oes . . . . . . . . . . . . 10.6 Entrada e sa´ıda . . . . . . . . . . . . . . . . . . . . . . . . 10.6.1 Entrada e sa´ıda em arquivos (padr˜ao Edimburgo) . . 10.6.2 Trabalhando com arquivos-texto no padr˜ao Edimburgo 10.6.3 Entrada e sa´ıda no Prolog ISO . . . . . . . . . . . . 10.6.4 Leitura de fitas . . . . . . . . . . . . . . . . . . . . . 10.6.5 Trabalhando com arquivos no Prolog ISO . . . . . . . 10.6.6 Arquivos bin´arios . . . . . . . . . . . . . . . . . . . . III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Estudos de Casos e Aplica¸c˜ oes 154 154 154 156 157 157 158 159 163 11 Programa¸c˜ ao de Gram´ aticas 11.1 N´ıveis ling¨u´ısticos . . . . . . . . . . . . . . . . . . . 11.2 Gram´aticas em Prolog: DCG . . . . . . . . . . . . . 11.2.1 Gram´atica regular . . . . . . . . . . . . . . . 11.2.2 Gram´atica livre de contexto . . . . . . . . . . 11.2.3 Gram´atica sens´ıvel ao contexto . . . . . . . . 11.3 Gram´aticas de Atributos . . . . . . . . . . . . . . . . 11.4 Avaliar express˜oes aritm´eticas . . . . . . . . . . . . . 11.4.1 Programando a GLC como DCG . . . . . . . 11.4.2 Calculando o valor com equa¸c˜oes semˆanticas . 11.4.3 O problema da associatividade `a esquerda para 11.5 Gerando nota¸c˜ao polonesa com a¸c˜oes semˆanticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . LL(k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 165 166 166 167 168 169 172 173 173 174 174 12 Romanos para decimais e Decimais por extenso 177 12.1 Romanos para decimais e vice versa . . . . . . . . . . . . . . . . . . . . . . . . . 177 12.2 Traduzindo decimais por extenso e vice-versa . . . . . . . . . . . . . . . . . . . . 179 13 Tokens para express˜ oes aritm´ eticas 181 13.1 Testando o programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 14 Calcular express˜ oes aritm´ eticas com vari´ aveis 185 15 Um compilador: tradutor e interpretador 15.1 A minilinguagem . . . . . . . . . . . . . . . . 15.2 O scanner: an´alise l´exica . . . . . . . . . . . . . 15.3 O analisador de express˜oes baseado em tabela . 15.4 O tradutor: analise sint´atica e gera¸c˜ao de c´odigo 15.4.1 Gram´atica da minilinguagem . . . . . . . 15.4.2 Testes para o tradutor . . . . . . . . . . 15.5 O interpretador: an´alise semˆantica . . . . . . . . . . . . . . 189 190 190 194 196 197 198 199 . . . . . 203 203 204 204 205 207 16 Processamento de Linguagem Natural com DCG 16.1 Introdu¸c˜ao ao PLN . . . . . . . . . . . . . . . . 16.2 L´exico – Morfologia . . . . . . . . . . . . . . . 16.2.1 Flex˜ao em gˆenero . . . . . . . . . . . . 16.3 Um exemplo de minilinguagem . . . . . . . . . ´ 16.4 Arvore sint´atica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16.5 Incluindo regras para concordˆancia . . . . . . . . . . . . . . . . . . . . . . . . . 208 16.6 Gerando uma ´arvore sint´atica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 16.7 Semˆantica para linguagem natural . . . . . . . . . . . . . . . . . . . . . . . . . . 211 17 IA: Classifica¸c˜ ao KNN 17.1 KNN: K vizinhos mais pr´oximos . . . . . . . . . . . . . . . . . . . . . . . . . . . 17.2 Base de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17.3 O algoritmo KNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 215 216 217 18 IA: Agrega¸c˜ ao Kmeans 219 18.1 Medidas de similaridade e distˆancia . . . . . . . . . . . . . . . . . . . . . . . . . 219 18.2 Criando uma popula¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 18.3 Kmeans: Agrupamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 19 IA: Classifica¸c˜ ao Naive Bayes 229 19.1 Os conjuntos de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 19.2 A inferˆencia Bayesiana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 20 IA: Similaridade via nGramas 235 20.1 O programa de testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 21 IA: Teoria da Informa¸c˜ ao 21.1 Bits e quantidade de informa¸c˜ao . . . . . 21.2 Entropia e Entropia conjunta . . . . . . 21.3 Entropia condicional e Informa¸c˜ao m´utua 21.4 Escolha de atributos . . . . . . . . . . . 21.5 Indu¸c˜ao de ´arvore para classifica¸c˜ao: Id3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 243 246 247 247 250 Lista de Figuras 1.1 1.2 O ambiente do SWI-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O interpretador de comandos do SWI-Prolog . . . . . . . . . . . . . . . . . . . . 11 12 9.1 O modelo de caixa e portas de Byrd . . . . . . . . . . . . . . . . . . . . . . . . . 134 10.1 Operadores predefinidos conforme o Prolog ISO . . . . . . . . . . . . . . . . . . 146 10.2 Fun¸c˜oes aritm´eticas do Prolog ISO . . . . . . . . . . . . . . . . . . . . . . . . . 151 ´ 11.1 Arvore sint´atica com atributos sintetizados (S-GA), para contar os a(s). . . . . . . 170 ´ 11.2 Arvore para a senten¸ca ”bbb”, da gram´atica L-GA, com atributos herdados (descem) e sintetizados (sobem) para contar os (b)s. . . . . . . . . . . . . . . . . . . . . . 171 13.1 Autˆomato finito para tokens de express˜oes aritm´eticas. . . . . . . . . . . . . . . . 182 xvii Parte I Fundamentos e T´ ecnicas de Programa¸c˜ ao em Prolog 1 CAP´ITULO 1 Introdu¸c˜ ao ao Prolog Alan Robinson (1965) ˜o e unificac ˜o Resoluc ¸a ¸a R. Kowalski (1972) ˜o procedural Interpretac ¸a Alain Colmerauer (1973) Primeiro Prolog David Warren (1977) Prolog Edimburgo Inicialmente apresentamos um hist´orico do Prolog. Em seguida, uma introdu¸c˜ao `a linguagem Prolog, definindo a nomenclatura b´asica, que inclui os conceitos de fato, regra, pergunta, cl´ausula, predicado, procedimento e programa. Os conceitos de programa¸c˜ao introduzidos aqui s˜ao detalhados e exemplificados nos demais cap´ıtulos da primeira parte do livro. Maiores detalhes sobre a sintaxe do Prolog s˜ao encontrados na segunda parte deste livro-texto. 3 4 1. Introdu¸c˜ ao ao Prolog 1.1 Hist´ orico Um programa Prolog ´e uma cole¸c˜ao de fatos e de regras que definem rela¸c˜oes entre os objetos do discurso do problema. Uma computa¸c˜ao em Prolog envolve a dedu¸c˜ao de conseq¨uˆencias a partir das regras e fatos. O significado do programa ´e o conjunto de todas as conseq¨uˆencias deduz´ıveis pela iterativa aplica¸c˜ao das regras sobre os fatos iniciais e os novos fatos gerados. Portanto, Prolog ´e uma linguagem com uma fundamenta¸c˜ao l´ogica, em teoria da prova. A linguagem de programa¸c˜ao Prolog se originou a partir de trabalhos de pesquisa em procedimentos de resolu¸c˜ao para l´ogica de primeira ordem. Mais precisamente, o nascimento do Prolog aconteceu por volta de 1965, quando Alan Robinson desenvolveu os dois componentes-chave de um provador de teoremas para l´ogica de cl´ausulas (equivalente `a l´ogica de primeira ordem): • o procedimento de resolu¸c˜ao; • o algoritmo de unifica¸c˜ao. A partir do resultado te´orico de 1965, v´arias tentativas foram feitas para desenvolver uma m´aquina de computa¸c˜ao baseada no princ´ıpio de resolu¸c˜ao, o que s´o aconteceu na d´ecada de 70. Por um lado, R. Kowalski [12], em 1972, formulou uma interpreta¸c˜ao procedimental para as cl´ausulas de Horn (uma vers˜ao restrita da l´ogica de cl´ausulas, para a qual Robinson desenvolveu a resolu¸c˜ao). Ele mostrou que uma cl´ausula l´ogica, tal como A if B1 and B2, que equivale `a implica¸c˜ao l´ogica (B1 and B2) -> A, pode ser lida e executada como um procedimento em uma linguagem de programa¸c˜ao recursiva, na qual o A ´e a cabe¸ca do procedimento e os B1 and B2 s˜ao o seu corpo. Assim, o programa prog if ler(Dado) and calcular(Dado, Result) and impr(Result) ´e lido como: para executar prog executa-se ler(Dado) e depois executa-se calcular(Dado, Result) e ent˜ao executa-se impr(Result). Esta leitura equivale a um procedimento imperativo: procedure prog; begin ler(Dado); calcular(Dado, Result); impr(Result); end; Esta interpreta¸c˜ao de cl´ausulas ´e consistente com o processo de resolu¸c˜ao, no qual a unifica¸c˜ao ´e quem faz a manipula¸c˜ao dos dados: atribui¸c˜ao de valores, constru¸c˜ao de estruturas de dados, sele¸c˜ao de dados e passagem de parˆametros. Assim, o surgimento da Programa¸c˜ao em L´ogica (PL), em 1972, resultou da integra¸c˜ao destes trˆes conceitos: resolu¸c˜ao, unifica¸c˜ao e cl´ausulas de Horn. Prolog vem de PROgramming in LOGic. Em 1973, Alain Colmerauer [6] na Universidade de Aix-Marseille desenvolveu um provador de teoremas para implementar sistemas de Processamento de Linguagem Natural, chamado Prolog (Programation et Logique), que empregava a interpreta¸c˜ao de Kowalski. Em 1974, David Warren [17] esteve dois meses em Marseille, onde conheceu a linguagem Prolog e escreveu um programa chamado Warplan, que resolvia um problema de planejamento (busca de uma lista de a¸c˜oes, para, a partir de um estado inicial, chegar a um estado final). De volta a Edimburgo e pensando em um t´opico para sua tese, Warren estava estudando a id´eia de construir um compilador para Prolog a fim de resolver o problema da fraca performance 1.2. Programa = regras + fatos 5 dos interpretadores de Prolog, pois, nesta ´epoca, havia um consenso de que sistemas provadores de teoremas baseados em l´ogica eram irremediavelmente ineficientes. Em 1977, na Universidade de Edimburgo (na Esc´ocia), David Warren conseguiu desenvolver o primeiro compilador para Prolog, chamado de Prolog-10, tamb´em conhecido como Prolog padr˜ao Edimburgo [15]. Este compilador e outros desenvolvidos nesta ´epoca ainda n˜ao satisfaziam o requisito de performance. Em 1983, Warren publicou um trabalho definindo as instru¸c˜oes para uma m´aquina abstrata de Prolog, hoje conhecida como WAM (Warren abstract machine) [2] que ´e a base de todas as implementa¸c˜oes comerciais e acadˆemicas hoje dispon´ıveis. Com rela¸c˜ao aos compiladores anteriores, uma WAM apresentava as seguintes t´ecnicas de otimiza¸c˜ao: pontos de escolha separados dos ambientes dos predicados; passagem de argumentos por registradores (em vez da pilha); e escolha de cl´ausulas usando ´ındices. Programa¸c˜ ao em L´ ogica vs. Prolog Programa¸c˜ao em L´ogica (PL) n˜ao ´e sinˆonimo de Prolog. Inicialmente, em PL temos duas grandes classes de programas: cl´ausulas definidas (ou Horn) e n˜ao definidas (estudadas no pr´oximo cap´ıtulo). Prolog ´e um sistema que executa programas para cl´ausulas definidas. Por outro lado, muitos programas em Prolog n˜ao tˆem uma representa¸c˜ao em PL pura, como veremos nos pr´oximos cap´ıtulos. Na pr´atica, a PL, como disciplina de fundamentos te´oricos da computa¸c˜ao, deve seu sucesso ao Prolog. Na seq¨uˆencia, apresentamos uma introdu¸c˜ao ao Prolog. PL ´e retomada no pr´oximo cap´ıtulo. 1.2 Programa = regras + fatos Um programa Prolog ´e uma cole¸c˜ao de fatos e de regras que definem rela¸c˜oes entre os objetos do discurso do problema. Uma computa¸c˜ao em Prolog envolve a dedu¸c˜ao de conseq¨uˆencias a partir das regras e fatos. O significado de um programa ´e o conjunto de todas as conseq¨uˆencias deduz´ıveis pela iterativa aplica¸c˜ao das regras sobre os fatos iniciais e os novos fatos gerados. 1 2 3 4 5 6 7 8 9 10 11 12 %% programa da familia pai(tare, abraao). %1 pai(tare, nacor). %2 pai(tare, aran). %3 pai(aran, lot). %4 /* 7 fatos */ pai(aran, melca). %5 pai(aran, jesca). %6 mae(sara, isaac). %7 %% fem(X):-mae(X,Y). %1 irmao(X,Y):-pai(P,X),pai(P,Y), X\==Y. %2 tio(T,X):-pai(P,X),irmao(P,T). %3 1.2.1 /* 3 regras */ Regras e fatos em Prolog Um programa em Prolog ´e uma cole¸c˜ao de unidades l´ogicas chamadas de predicados. Cada predicado ´e uma cole¸c˜ao de cl´ausulas. Uma cl´ ausula ´e uma regra ou um fato. 6 1. Introdu¸c˜ ao ao Prolog O programa da fam´ılia, em Prolog, apresenta a ´arvore geneal´ogica da fam´ılia b´ıblica de Abra˜ao. O programa descreve um conjunto de rela¸c˜oes l´ogicas envolvendo os objetos do dom´ınio do problema, que s˜ao as pessoas da fam´ılia b´ıblica identificadas pelos seus nomes. Estas rela¸c˜oes l´ogicas s˜ao estabelecidas atrav´es das cl´ausulas do programa. Como conven¸c˜ao nos textos-fonte dos programas n˜ao usamos a acentua¸c˜ao nas palavras e nomes, como est´a exemplificado no programa mencionado. Segue uma descri¸c˜ao sint´atica dos elementos presentes no programa da fam´ılia b´ıblica. 1.2.2 Termos e predicados Em um programa em Prolog: • Uma vari´ avel representa um elemento n˜ao especificado do dom´ınio. Sintaticamente, uma vari´avel sempre inicia com letra mai´uscula; • Uma constante representa um elemento espec´ıfico do dom´ınio. Pode ser num´erica ou uma cadeia de caracteres (tipicamente, iniciando com letra min´uscula). No programa da fam´ılia b´ıblica, s˜ao constantes todos os nomes das pessoas: tare, abraao, nacor, sara, ...; e, s˜ao vari´aveis: X, Y, T, P. Regras e fatos, em Prolog, s˜ao representados por cl´ausulas (no programa da fam´ılia b´ıblica, temos uma regra ou fato em cada linha). Assim, em Prolog, um programa ´e um conjunto de cl´ausulas; cada cl´ausula corresponde a uma f´ormula l´ogica. Cl´ ausulas s˜ao agrupadas em predicados. Um predicado ´e definido por um conjunto de regras e fatos com o mesmo nome (por exemplo, pai no programa da fam´ılia b´ıblica). Revisando o programa da fam´ılia b´ıblica, podemos identificar duas partes, a primeira descrita por fatos, definidos pelas rela¸c˜oes pai/2 e mae/2; e a segunda pelas regras irmao/2, fem(inina)/1 e tio/2. pai/2 denota o predicado pai com dois argumentos, enquanto fem/1 denota o predicado fem com um argumento. O predicado pai/2 ´e definido por seis fatos. Em resumo, o programa da fam´ılia b´ıblica ´e descrito por sete fatos e trˆes regras que definem cinco predicados. Mais formalmente, cl´ausulas s˜ao f´ormulas l´ogicas constru´ıdas a partir de f´ormulas atˆomicas: • Se P ´e uma f´ormula atˆomica, ent˜ao a sua nega¸c˜ao tamb´em ´e uma f´ormula, representada em Prolog por \+ P. • Se P e Q s˜ao f´ormulas, ent˜ao tamb´em a conjun¸c˜ao (P,Q), a disjun¸c˜ao (P;Q) e a condicional (P:-Q) s˜ao f´ormulas, n˜ao atˆomicas. F´ormulas n˜ao atˆomicas s˜ao formadas por operadores l´ogicos (, ; :- \+), respectivamente (e, ou, condicional, nega¸c˜ao). O s´ımbolo :- representa uma implica¸c˜ao l´ogica invertida, chamada de condicional. Assim, P:-Q ´e equivalente a Q → P , como veremos no pr´oximo cap´ıtulo. Um fato, por exemplo, pai(tare,nacor) tamb´em representa uma regra condicional: true → pai(tare,nacor). F´ormulas atˆomicas s˜ao constru´ıdas a partir de termos. No programa da fam´ılia b´ıblica, s˜ao exemplos de f´ormulas: pai(tare, nacor), fem(X), pai(P,X), ... Termos s˜ao constru´ıdos a partir de vari´aveis e constantes. Como segue: • Toda constante ´e um termo e toda vari´avel ´e um termo; • Se t1 , .., tn s˜ao termos e f ´e um s´ımbolo funcional, ent˜ao f (t1 , .., tn ) tamb´em ´e um termo; 1.2. Programa = regras + fatos 7 • Se t1 , .., tn s˜ao termos e p ´e um s´ımbolo predicativo, ent˜ao p(t1 , .., tn ) tamb´em ´e um termo, que corresponde a um predicado. Assim, um termo ´e um s´ımbolo seguidos de n argumentos: t(t1 , .., tn ). Nesta representa¸c˜ao t ´e chamado de functor. Um functor pode ser um s´ımbolo funcional ou um s´ımbolo predicativo. Quando n = 0 temos dois casos: se o s´ımbolo ´e funcional temos uma constante que ´e um termo; e se o s´ımbolo for predicativo temos uma constante l´ogica que ´e uma f´ormula atˆomica, por exemplo, true ou false. Functores com um ou dois argumentos podem tamb´em ser escritos na forma de operadores. Por exemplo, 1+2 corresponde a +(1,2), -1 corresponde a -(1); e 1=2 corresponde a =(1,2). O uso de operadores em Prolog tem como objetivo tornar a escrita de termos e predicados mais econˆomica e f´acil, utilizando menos parˆenteses e v´ırgulas. Compare: +(1,2) com 1+2 , o primeiro utiliza trˆes caracteres a mais, dois parˆenteses e uma v´ırgula. Representa¸c˜ ao de conhecimento Prolog ´e uma linguagem declarativa, na qual a computa¸c˜ao ´e baseada na representa¸c˜ao do conhecimento do dom´ınio do problema. Nesta representa¸c˜ao devemos considerar todos os objetos sobre os quais queremos falar, as propriedades de cada objeto e as rela¸c˜oes entre objetos. Termos definidos por s´ımbolos funcionais, por exemplo, idade(X), representam fun¸c˜oes que retornam valores que s˜ao constantes no dom´ınio do problema. Por exemplo, idade(joao) retornando 25, sexo(joao) retornando masculino. Idade e sexo s˜ao atributos ou qualidades de um indiv´ıduo. Termos definidos por s´ımbolos predicativos s˜ao predicados. Eles representam regras e fatos do Prolog. Um predicado representa uma rela¸c˜ao l´ogica (verdadeira ou falsa) entre indiv´ıduos, por exemplo, pai(Joao,Maria) e irmao(X,Y). Formalmente, um predicado representa uma f´ormula que ´e um objeto l´ogico, isto ´e, retorna sempre um valor l´ogico (verdadeiro ou falso). Em linguagem natural, existe tamb´em uma diferen¸ca semˆantica entre um s´ımbolo funcional e um s´ımbolo predicativo. O primeiro representa uma ora¸c˜ao incompleta, ou um nominal, por exemplo, idade(X), idade(joao) pode ser lido como A idade de X ... , A idade de Jo˜ao.... O segundo representa sempre uma ora¸c˜ao completa, por exemplo, o predicado idade(joao,23) ´e lido como A idade de Jo˜ao ´e 23; e o predicado forte(joao) ´e lido como Jo˜ao ´e forte. No programa da fam´ılia b´ıblica temos a codifica¸c˜ao do conhecimento nas cl´ausulas em duas formas: • expl´ıcito: indiv´ıduos (constantes) e fatos (ou rela¸c˜oes) entre os indiv´ıduos, pai/2 e mae/2; • impl´ıcito: as regras fem/1, tio/2 e irmao/2, que geram novos fatos a partir dos fatos iniciais. 1.2.3 Conven¸c˜ oes para leitura de cl´ ausulas Para um fato com 2 parˆametros podemos ter duas leituras trocando-se de ordem os parˆametros. Para o fato pai(tare,abraao) temos duas leituras: Tar´e ´e pai de Abra˜ao ou Abra˜ao ´e pai de Tar´e. Preferimos a primeira forma, por´em em Prolog n˜ao existe uma conven¸c˜ao padr˜ao, fica a crit´erio do programador. Numa regra cabeca:-corpo, o corpo pode ser constitu´ıdo de uma lista de predicados, ligados por v´ırgula, denotando uma conjun¸c˜ao l´ogica. A regra fem(X):-mae(X,Y) ´e lida como uma f´ormula condicional: (X ´e feminino) se (X ´e m˜ae de Y). E a regra tio(T,X):-pai(P,X), 8 1. Introdu¸c˜ ao ao Prolog irmao(P,T) ´e lida como uma f´ormula condicional: (T ´e tio de X) se (P ´e pai de X) e (P ´e irm˜ao de T). Abaixo, segue uma lista de exemplos de leitura de cl´ausulas: pai(tare, abraao). leia-se Tare ´e pai de Abra˜ao mae(sara, isaac). leia-se Sara ´e m˜ae de Isaac fem(X) :mae(X,Y). leia-se (X ´e feminina) se (X ´e m˜ae de Y ) irmao(X,Y) :pai(P,X),pai(P,Y),X\==Y. leia-se (X ´e irm˜ao de Y) se (P ´e pai de X) e (P ´e pai de Y) e (X ´e diferente de Y) 1.2.4 Perguntas O significado de um programa ´e o conjunto de conseq¨uˆencias que s˜ao deduzidas a partir dos fatos e regras. Assim sendo, um sistema Prolog (isto ´e, um sistema que executa um programa Prolog) pode ser visto como um interpretador de perguntas. Para sabermos se um fato arbitr´ario ´e conseq¨uˆencia do programa, perguntamos ao sistema, que responde Sim (Yes) se for verdade e N˜ao (No) caso contr´ario. ?- fem(sara). Yes. ?- fem(aran). No ?- fem(X). X=sara Yes ?- irmao(melca, lot). Yes ?- irmao(lot,X). X=melca; X=jesca Yes ?- tio(nacor,jesca). Yes Acima, temos uma lista de perguntas que podemos fazer ao interpretador quando est´a executando o programa da fam´ılia b´ıblica. Na primeira pergunta, ?-fem(sara) (Sara ´e feminina?), o sistema respondeu Yes. Para deduzir a resposta, o sistema usou a regra 1 e o fato 7, como segue: mae(sara, isaac) fem(X):-mae(X,Y) ———————— fem(sara) Sara ´e m˜ae de Isaac (X ´e feminina) se (X ´e m˜ae de Y) ———————————— Sara ´e feminina Este mesmo esquema responde `a pergunta ?-fem(X) (Quem ´e feminina?). O fato deduzido fem(sara) ´e comparado com o predicado fem(X) onde se deduz que X=sara. De forma similar, buscando conseq¨uˆencias l´ogicas, o interpretador responde todas as perguntas apresentadas acima. A segunda pergunta ´e: Aran ´e feminino?. A resposta ´e N˜ao, pois n˜ao existem 1.3. Revis˜ ao 9 fatos do tipo mae(Aron,X). Para esta dedu¸c˜ao o Prolog assume a hip´ otese do mundo fechado: tudo o que n˜ao est´a descrito nos fatos ou n˜ao ´e deduz´ıvel dos fatos ´e falso. A terceira pergunta ´e: Quem ´e feminina?. O sistema retorna X=sara, dizendo que Sara ´e quem ´e feminina. Mais adiante, pergunta-se Quem ´e irm˜ao de Lot? irmao(lot,X) — o sistema d´a duas respostas: Melca e Jesca. Ambos valores podem ser deduzidos para a vari´avel X. E assim por diante. 1.3 Revis˜ ao Exerc´ıcio 1.1 Com base nos esquemas abaixo e no texto do cap´ıtulo, defina os conceitos solicitados. Seja breve, utilize no m´aximo 20 palavras, incluindo pelo menos um exemplo. %% fatos & regras pai(tare, abraao). fatos pai(tare, nacor). %%  corpo  z cabeca }| { z }| { regras irmao(X, Y) : − pai(P, X), pai(P, Y), X\ == Y .  fem(X) : −mae(X, Y). %% predicados & cl´ ausulas pai(tare, nacor). }cl´ausula predicado }cl´ausula  pai(tare, aran). }cl´ausula  fem(ana). fem(X) : − \ + masc(X). }cl´ausula predicado  fem(X) : − mae(X, Y). }cl´ausula 1. Cl´ausula e predicado. 2. Regra, fato e pergunta. Exerc´ıcio 1.2 Idem, defina os termos abaixo. %%f o´rmulas fˆ ormula n˜ ao atˆ omica z }| atˆ omica z { n˜ ao atˆ omica atˆ omica }| atˆ omica { z }| { z }| { z }| { irmao(X, Y) : − pai(P, X), pai(P, Y) . %% termos simples & compostos termo composto z }| { termo composto termo/const z }| { termo/const z }| { z }| { pessoa( joao − silva, ender( rua − abc, 2700 ), | {z } | {z } functor termo/var z}|{ CIC ). argumentos 1. Vari´avel. Solu¸c˜ ao: Uma vari´avel representa um elemento n˜ao especificado do dom´ınio do problema, inicia por letra mai´uscula, por exemplo, X, Maior. 10 1. Introdu¸c˜ ao ao Prolog 2. Constante. 3. Termo simples e termo composto. 4. Functor. Solu¸c˜ ao: Um functor ´e o s´ımbolo que precede os argumentos num termo composto, por exemplo, em pai(joao, ana), o functor ´e pai. 5. Argumento. 6. Operador. 7. F´ormula atˆomica e n˜ao atˆomica. Exerc´ıcio 1.3 Idem, defina os termos abaixo. 1. S´ımbolo funcional e s´ımbolo predicativo. 2. Ora¸c˜ao completa e ora¸c˜ao incompleta. 3. Rela¸c˜ao l´ogica entre indiv´ıduos. 1.4 SWI-Polog Neste livro, a partir deste cap´ıtulo, assumimos que o leitor tem dispon´ıvel um sistema Prolog para rodar os programas e fazer os exerc´ıcios de programa¸c˜ao. Recomendamos o uso do SWIProlog, por´em existem dezenas de sistemas Prolog dispon´ıveis no mercado (sistemas comerciais ou acadˆemicos): Amzi!tm , ALStm , Aritytm , Eclipsetm , LPAtm , Quintustm , SICStustm , SWItm , XBStm . Praticamente todos estes sistemas rodam nas duas principais plataformas de sistemas operacionais: Windowstm e Linuxtm . O SWI-Prolog ´e desenvolvido pela Universidade de Amsterd˜a, ´e um software com distribui¸c˜ao livre para ensino e pesquisa. Ele usa poucos recursos da m´aquina, ´e r´apido para compila¸c˜ao e possui documenta¸c˜ao on-line (http://www.swi-prolog.org/). Ele implementa uma vers˜ao do Prolog ISO, que ´e o padr˜ao adotado pelo livro, o que significa que os exemplos do livro podem ser executados neste Prolog sem necessidade de ajustes. Na Figura 1.1 vemos um uso t´ıpico do SWI-Prolog. Ele ´e integrado a um editor compat´ıvel com o Emacs (editor UNIX), o qual s´o ´e recomend´avel para programadores que conhecem os comandos do Emacs. Programas Prolog s˜ao geralmente pequenos, podendo ser editados em qualquer editor ´ necess´ario que o editor enumere as linhas para de programas, como mostrado na Figura 1.1. E identificar um erro ap´os uma compila¸c˜ao. Ap´os instalado, o sistema SWI-Prolog, por default, se associa com todos os arquivos com extens˜ao ’.pl’. Assim, basta um duplo clique sobre um arquivo ’.pl’ para rodar o SWI-Prolog. 1.4.1 Entrando no SWI-Prolog Podemos rodar o SWI-Prolog pelo modo usual, caminhando pelos menus, por exemplo: Iniciar > Programas > SWI-Prolog. N´ os preferimos duplo clique sobre um arquivo de programa ’.pl’ pois o interpretador reconhece o caminho at´ e o local onde est´ a o arquivo; caso contr´ario ´e necess´ario indicar todo o caminho. 1.4. SWI-Polog 11 Figura 1.1: O SWI-Prolog: um editor e o interpretador de perguntas. Num sistema Prolog, a maneira usual de rodar um programa ´e fazendo perguntas ao interpretador de comandos. Por exemplo, podemos perguntar se a=a e o sistema deve responder Sim (Yes). E, se perguntarmos se a=b, o sistema deve responder N˜ao (No). Podemos tamb´em escrever o cl´assico: write(’Alo mundo’),nl. ?-a=b. No ?-a=a. Yes ?-write(’Alo mundo’),nl. Alo mundo Yes No fim de cada pergunta devemos digitar um ponto final, seguido de enter. Para cada pergunta o interpretador sempre responde com Yes ou No. 1.4.2 Rodando um programa O pr´oximo passo ´e rodar um programa, isto ´e, carregar um conjunto de fatos e regras na mem´oria para podermos perguntar sobre eles. Conven¸c˜ ao. Adotamos a seguinte conven¸c˜ao nos cap´ıtulos do livro: (1) Quando um texto em fonte courier (para programas) aparece dentro de uma caixa com os quatro lados, estaremos fazendo referˆencia ao uso de um interpretador Prolog. Neste caso devem aparecer perguntas que iniciam com ?- (veja acima um exemplo). (2) Quando um texto em fonte courier aparecer delimitado por uma caixa sem as laterais e com as linhas enumeradas, se trata de um programa. Propositalmente, estes textos de programas, em fonte courier, n˜ao s˜ao acentuados. Existem duas formas de carregar um programa fonte: duplo clique sobre o arquivo com extens˜ao ’.pl’ ou usando o predicado consult. Com estas explica¸c˜oes, j´a estamos em condi¸c˜oes de carregar o primeiro programa e em seguida fazer as primeiras perguntas. Digite em qualquer editor o programa que segue e salve-o como ’pai.pl’. 12 1 2 3 1. Introdu¸c˜ ao ao Prolog %% pai.pl pai(pedro, maria). pai(pedro, ana). Figura 1.2: O interpretador de comandos do SWI-Prolog: o programa pai.pl est´a sendo consultado. A Figura 1.2 mostra o interpretador de perguntas rodando (foi ativado clicando-se sobre o programa ’pai.pl’). Um duplo clique sobre um arquivo de programa faz duas coisas: entra no Prolog e carrega o arquivo clicado. Se j´a estamos dentro do Prolog, carregamos um programa perguntando ?-consult( arquivo). Este comando pode tamb´em ser simplificado na forma: ?-[arquivo]. Assim, para carregar o arquivo ’pai.pl’ pergunta-se: ?-consult(pai) ou ?-[pai] (No final de cada pergunta ou cl´ ausula de programa devemos sempre digitar um ponto final.). Agora podemos fazer perguntas sobre o programa j´a carregado. Por exemplo, perguntando ?-pai(pedro, ana) o sistema responde Yes; e perguntando ?-pai(X,Y) o sistema d´a duas respostas. Para obter a segunda resposta digita-se ponto e virgula (;) depois da primeira resposta. ?- consult(pai). % pai compiled 0.00 sec, 0 bytes Yes 2 ?- [pai]. %% mesmo que consult() % pai compiled 0.00 sec, 0 bytes Yes 3 ?- listing(pai). %% lista o predicado pai pai(pedro, maria). pai(pedro, ana). Yes 4 ?- pai(pedro,maria). Yes 1.5. Erros de sintaxe 13 5 ?- pai(X,Y). X = pedro, Y = maria ; %% digite (;) X = pedro, Y = ana ; No O processo de programa¸c˜ao consiste em criar ou modificar o texto de um programa, salv´alo e, a seguir, reconsult´a-lo. No SWI-Prolog uma reconsulta ´e feita repetindo-se a pergunta ?-consult(aquivo). Em alguns sistemas s´o a primeira vez carregamos com consult, nas outras vezes devemos usar reconsult. Em resumo, trabalha-se com o editor de programas em uma janela e o SWI-Prolog em outra(s), repetindo o ciclo: editar, salvar, reconsultar e perguntar. Uma parte trabalhosa da programa¸c˜ao em Prolog ´e a digita¸c˜ao das perguntas. Para facilitar o trabalho, o SWI-Prolog guarda um hist´orico das perguntas que podem ser reexecutadas sem serem redigitadas, basta caminhar com as setas up/down para resgat´ a-las. 1.5 Erros de sintaxe O Prolog possui uma sintaxe bem simples. Por´em, para um principiante o diagn´ostico sobre os erros de sintaxe ´e um tanto vago. Segue uma lista comentada de erros comuns. Falta de ponto final Um erro comum ´e a falta do ponto final, depois de uma pergunta; ou, num arquivo de programa, depois de uma cl´ausula. Usar sempre ap´ ostrofo com nomes de arquivos Um dos primeiros erros ´e tentar usar aspas no lugar de ap´ostrofos nos comandos de consult e reconsult ou [’arquivo.pl’]1 . A extens˜ao .pl ´e opcional: basta escrever [arquivo]. Se o nome do arquivo ´e uma palavra que inicia com letra min´uscula e sem extens˜ao, n˜ao ´e necess´ario usar ap´ostrofos. Usar aspas causa um problema, porque um conjunto de caracteres entre aspas corresponde a uma lista dos c´odigos ASCII dos caracteres, por exemplo, ?- "abc"= [97,98,99] Portanto, consult("abc") ´e o mesmo que consult([97,98,99]). Sempre devemos usar ap´ostrofos: ?- [’abc’]. ?-consult(’abc’). Para especificar um caminho para um arquivo tamb´em use ap´ostrofos, por exemplo, ?- consult(’C:/ prolog/ pai.pl’). Vari´ aveis iniciam por mai´ uscula e nomes de predicados por min´ usculas Para um iniciante ´e comum escrever vari´aveis come¸cando com letra min´uscula. Estes erros n˜ao s˜ao sint´aticos. Por exemplo, se perguntarmos ?-pai(x,y) o sistema responde No. Por outro lado, se escrevermos o nome de predicado come¸cando em mai´uscula, o SWI-Prolog mostra um erro. Note que aqui o erro n˜ao ´e indicado na posi¸c˜ao correta - in´ıcio do functor ”Pai”. ?- Pai(X,Y). ERROR: Syntax error: Operator expected ERROR: Pai(X,Y 1 Em alguns sistemas Prolog a extens˜ao ´e ”.pro”; ou tamb´em podemos escolher a extens˜ao default associada ao Prolog. 14 1. Introdu¸c˜ ao ao Prolog ERROR: ** here ** ERROR: ). N˜ ao deixar brancos entre o nome do predicado e o abre parˆ enteses O nome do predicado deve ser colado ao abre parˆenteses. Note que, tamb´em, aqui o erro n˜ao ´e indicado na posi¸c˜ao correta. ?- pai ERROR: ERROR: ERROR: ERROR: (X,Y) . Syntax error: Operator expected pai (X,Y ** here ** ) . Tentar definir um predicado predefinido Se tentarmos carregar um programa que tem um predicado que ´e do sistema, por exemplo, um arquivo chamado mm.pl com member(a,[a]). O sistema acusa o erro abaixo: ?- [mm]. ERROR: (c:/prolog/mm.pl:3): No permission to modify static_procedure ‘member/2’ % pai compiled 0.00 sec, 16 bytes Muitos dos predicados vistos neste livro-texto s˜ao predefinidos no SWI-Prolog, tais como: append, member, select, etc. Para us´a-los devemos adicionar um sufixo, por exemplo, um d´ıgito inteiro: append1. Avaliar uma express˜ ao aritm´ etica com vari´ aveis livres Uma express˜ao aritm´etica, para ser avaliada, deve ter suas vari´aveis fechadas. ?- X is 1+ B. %% B n~ ao est´ a instanciado ERROR: Arguments are not sufficiently instantiated Usar operadores n˜ ao definidos Por exemplo, a opera¸c˜ao de divis˜ao inteira, para o ISO Prolog, n˜ao ´e div, mas sim // (no entanto, div ´e padr˜ao no Prolog Edimburgo). Na tentativa de usar div, o SWI-Prolog responde como ilustrado abaixo. ?- X is 10 div 2. ERROR: Syntax error: Operator expected ERROR: X is 10 ERROR: ** here ** ERROR: div 2 . No pr´oximo cap´ıtulo, apresentamos uma fundamenta¸c˜ao te´orica para este tipo de racioc´ınio computacional baseado em dedu¸c˜oes l´ogicas. CAP´ITULO 2 Teoria da Programa¸c˜ ao em L´ ogica Neste cap´ıtulo, apresentamos uma vis˜ao geral dos fundamentos te´oricos da Linguagem Prolog, isto ´e, a teoria l´ogica subjacente ao Prolog. Partindo da l´ogica de proposi¸c˜oes, chega-se ao procedimento de resolu¸c˜ao com unifica¸c˜ao. A apresenta¸c˜ao ´e informal, sem provas de teoremas. Para um estudo detalhado deste tema s˜ao indicadas algumas referˆencias no final do cap´ıtulo. Este cap´ıtulo ´e opcional para cursos r´apidos. Isto ´e, pode-se alcan¸car uma proficiˆencia aceit´avel em Prolog, sem conhecer os seus fundamentos te´oricos. No entanto, quanto mais o aluno domina os conceitos deste cap´ıtulo mais seguran¸ca e firmeza ter´a no desenvolvimento de programas em Prolog. Em computa¸c˜ao estudamos dois principais sistemas l´ogicos. A l´ogica de proposi¸c˜ oes (ou sentencial) estuda f´ormulas do tipo A ∨ ¬B → C e a l´ogica de predicados (ou l´ogica de primeira ordem) estuda f´ormulas com ocorrˆencias dos quantificadores universal e existencial, por exemplo: ∀X∀Y ∃P (pai(P, X) ∧ pai(P, Y ) ∧ (X 6= Y ) → irmao(X, Y )). O Prolog implementa um modelo l´ogico chamado de l´ogica de cl´ausulas definidas que est´a entre a l´ogica das proposi¸c˜oes e a l´ogica dos predicados. 15 16 2. Teoria da Programa¸c˜ ao em L´ ogica 2.1 L´ ogica proposicional O formalismo l´ogico mais simples ´e a l´ogica proposicional (tamb´em conhecida como c´alculo proposicional ou ´algebra Booleana). Uma mulher n˜ao pode voar. On¸ca Pequena n˜ao pode voar. Portanto, On¸ca Pequena ´e uma mulher. Argumento I Um p´assaro pode voar. Sabi´a Pequeno ´e um p´assaro. Portanto, Sabi´a Pequeno pode voar. Argumento II Ora¸c˜oes completas podem ser traduzidas para f´ormulas da l´ogica proposicional. Em linguagem natural podemos escrever argumentos como uma seq¨uˆencia de proposi¸c˜oes, na qual a u´ltima proposi¸c˜ao ´e a conclus˜ao e as outras s˜ao as premissas. Como exemplos, temos os argumentos I e II acima. Mesmo sem conhecer um modelo no mundo real (Quem ´e On¸ca Pequena e Sabi´a Pequeno?), podemos ver que a partir das duas premissas n˜ao d´a para deduzir logicamente que On¸ca Pequena ´e uma mulher. Este argumento pode ser representado1 com um esquema de prova na l´ogica de proposi¸c˜oes, como segue: {A → ¬B, C → ¬B} ` C → A sendo A=uma mulher; B=pode voar; C=On¸ca Pequena; e, o s´ımbolo ` denota uma dedu¸c˜ao ou prova. Por outro lado, a conclus˜ao sobre o Sabi´a Pequeno ´e v´alida (pela regra modus ponens). Esta argumenta¸c˜ao pode ser representada como uma prova: {A → B, C → A} ` C → B sendo A=um p´assaro; B=pode voar; C=Sabi´a Pequeno. O estudo da l´ogica de proposi¸c˜oes visa ao desenvolvimento de sistemas de prova formal para validar mecanicamente argumentos como I e II. Estes sistemas de prova para proposi¸c˜oes s˜ao tamb´em conhecidos como c´alculo para proposi¸c˜oes2 . Elementos da l´ ogica proposicional As unidades b´asicas da l´ogica proposicional s˜ao as constantes (true, false) e os identificadores (letras mai´usculas) que denotam proposi¸c˜oes (ora¸c˜oes completas) que s˜ao verdadeiras ou falsas. As unidades b´asicas s˜ao combinadas em f´ormulas pelos operadores l´ogicos; seguem os principais operadores l´ogicos: conjun¸c˜ao (∧, &), disjun¸c˜ao (∨, v), nega¸c˜ao (¬, ~), implica¸c˜ao (→, ->) e o condicional (←, B true true true false true true false true Uma interpreta¸c˜ ao define um valor para cada um dos identificadores de uma f´ormula. Por exemplo, a f´ormula A & B ´e verdadeira para a interpreta¸c˜ao { A=true, B=true }, mas ´e falsa para todas as outras interpreta¸c˜oes. Algumas f´ormulas s˜ao v´alidas para qualquer interpreta¸c˜ao, por exemplo, A v ~A. E outras nunca s˜ao v´alidas, por exemplo, A & ~A. Existem duas principais abordagens para se validar uma f´ormula: • o uso de tabelas-verdade; • um sistema de c´alculo ou dedu¸c˜ao; Para Programa¸c˜ao em L´ogica (PL), interessa-nos a segunda abordagem, na qual s˜ao usadas regras de igualdade e dedu¸c˜ao para se reduzir algebricamente uma f´ormula num valor verdade. Em PL uma destas regras se destaca pelo seu papel num sistema de resolu¸c˜ao (para l´ogica dos predicados). Esta regra ´e a regra de elimina¸c˜ ao, que pode ser enunciada como (A v B) & (~A v C) ` (B v C) ou como (A & (~A v B)) ` B ou como (A & (A -> B)) ` B sendo que o s´ımbolo ` denota uma dedu¸c˜ao ou prova. Esta regra ´e chamada regra de elimina¸c˜ao porque, combinando duas subf´ormulas, ela elimina o termo comum, que nestes enunciados ´e o A. Exerc´ıcio 2.1 Usando a regra de elimina¸c˜ao prove que K ´e verdadeiro, a partir do conjunto de f´ormulas dado abaixo: {F, H->I, H->J, J->K, F->G, F->H} Exerc´ıcio 2.2 Usando a regra de elimina¸c˜ao prove que L ´e verdadeiro, a partir do conjunto de f´ormulas dado abaixo: {F, H->I, H->J, H & J->L, F->G, F->H} Uma dedu¸c˜ao acontece em um metan´ıvel da linguagem. Nos exerc´ıcios acima, o A e o B da regra de elimina¸c˜ao (A & (A -> B)) ` B s˜ao substitu´ıdos por identificadores das f´ormulas: F,G,H,I,J,K,L. 18 2. Teoria da Programa¸c˜ ao em L´ ogica 2.2 L´ ogica de cl´ ausulas (para proposi¸c˜ oes) Os exemplos de argumenta¸c˜ao I e II s˜ao descritos como trˆes ora¸c˜oes: duas premissas e uma conclus˜ao. Cada um destes argumentos pode ser representado numa u´nica f´ormula l´ogica: as premissas s˜ao ligadas por uma conjun¸c˜ao; e entre as premissas e a conclus˜ao pode-se usar uma implica¸c˜ao. Com isso, temos que uma argumenta¸c˜ao ´e v´alida se a sua f´ormula ´e verdadeira. Pelas leis da l´ogica de proposi¸c˜oes, toda f´ormula pode ser transformada numa forma normal conjuntiva que ´e uma conjun¸c˜ao de um conjunto de cl´ausulas. Cada cl´ausula ´e uma disjun¸c˜ao formada por identificadores com ou sem nega¸c˜ao, tamb´em chamados de literais positivos e negativos, respectivamente. Segue um exemplo de rescrita de uma f´ormula como um conjunto de cl´ausulas na forma normal conjuntiva: 1 2 3 4 5 6 7 8 9 10 11 12 ((A v B) & (~A v C)) -> D ~((A v B) & (~A v C)) v D (~( A v B) v ~(~A v C)) v D ((~A & ~B) v (A & ~C)) v D (~A v A v D) & (~A v ~C v D) & (~B v A v D) & (~B v ~C v D) = (A v D v ~A ) & ( D v ~A v ~C) & (A v D v ~B ) & ( D v ~B v ~C) = = = = %% defini¸ c~ ao de -> %% leis de morgam %% " %% distribui¸ c~ ao v %% forma %% normal Como resultado, a f´ormula original ´e equivalente a quatro cl´ ausulas ligadas por conjun¸c˜oes. Cada cl´ausula ´e uma disjun¸c˜ao com literais positivos e negativos. Se cada f´ormula da l´ogica de proposi¸c˜oes pode ser representada por uma ou mais cl´ausulas da l´ogica de cl´ausulas, ent˜ao temos uma equivalˆencia entre estes dois formalismos l´ogicos. Tudo o que pode ser expresso em l´ogica de proposi¸c˜oes pode tamb´em ser expresso em l´ogica de cl´ausulas e vice-versa. Uma forma de nota¸c˜ ao abreviada para cl´ausulas (na forma normal conjuntiva) foi proposta por Kowalski, como segue: A1 ∨ ... ∨ Am ∨ ¬B1 ∨ ... ∨ ¬Bn ´e representada como A1 , ..., Am ← B1 , ...Bn Nesta nota¸c˜ao abreviada, temos uma leitura mais simples: removeram-se todas as nega¸c˜oes, os operadores de conjun¸c˜ao e disjun¸c˜ao; no lugar usam-se v´ırgulas. Dada esta nota¸c˜ao abreviada, temos a seguinte classifica¸c˜ao para cl´ausulas: • se m>1 — A1,A2,... []. fator --> [X],{integer(X)},{write(X), write(’ enter’), nl}. fator --> [’(’], expr, [’)’]. O efeito das a¸c˜oes semˆanticas ´e escrever uma seq¨uˆencia de passos a serem executados numa calculadora do tipo HP. Esta nota¸c˜ao para representar express˜oes sem parˆenteses ´e tamb´em chamada de nota¸c˜ao polonesa, como segue: ?- expr([10,+,20,*,33],[]). 10 enter 20 enter 11.5. Gerando nota¸c˜ ao polonesa com a¸c˜ oes semˆ anticas 175 33 enter mult some ?- expr([1,-,2,+,4,-,3],[]). 1 enter 2 enter 4 enter 3 enter subt some subt Exerc´ıcio 11.8 Desenhe uma ´arvore sint´atica decorada com as a¸c˜oes semˆanticas para a gram´atica vers˜ao fatorada que gera a nota¸c˜ao polonesa, para a senten¸ca 1+2*3. CAP´ITULO 12 Romanos para decimais e Decimais por extenso Neste cap´ıtulo mostramos dois exemplos de programas com gram´aticas DCG. O prop´osito dos exemplos ´e did´atico: mostrar como funciona internamente a DCG, como um programa DCG pode ser convertido para cl´ausulas. 12.1 Romanos para decimais e vice versa Uma defini¸c˜ao simples para n´umeros romanos ´e valida para valores no intervalo de 1 at´e 3999. N˜ao ´e poss´ıvel expressar o zero em romanos. Seguem dois exemplos de convers˜ao de decimal para romano e vice-versa. ?- romano_(1947,V). V = ’MCMXLVII’ ?- decimal_(’MCMXLVII’,V), Vo is V. V = 1000+ (900+ (40+ (5+ (1+ (1+0))))) Vo = 1947 O programa abaixo faz a convers˜ao de romanos para decimais e vice-versa. O conjunto de regras serve para os dois predicados, por´em eles em si variam um pouco. O programa todo n˜ao pode ser revers´ıvel pois envolve opera¸c˜oes aritm´eticas que em princ´ıpio n˜ao s˜ao revers´ıveis. As regras devem ser executas de cima para baixo. Note que ´e uma gram´atica n˜ao LL(1): por exemplo, existem trˆes regras em que o corpo inicia com ’C’. Poderiam ser fatoradas, mas o exemplo serve para mostrar que as DCGs trabalham com gram´aticas LL(k). 1 2 3 %% file:romano.pl %% romano para valor r(V)-->romam(V1),r(V2),{V = V1+V2}. 177 178 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 12. Romanos para decimais e Decimais por extenso r(0)-->[]. decimal_(X,V):-atom_chars(X,L),r(V,L,[]),!. romam(1000)-->[’M’]. romam(900)-->[’C’],[’M’]. romam(500)-->[’D’]. romam(400)-->[’C’],[’D’]. romam(100)-->[’C’]. romam(90)-->[’X’],[’C’]. romam(50)-->[’L’]. romam(40)-->[’X’],[’L’]. romam(10)-->[’X’]. romam(9)-->[’I’],[’X’]. romam(5)-->[’V’]. romam(4)-->[’I’],[’V’]. romam(1)-->[’I’]. %% valor para romano romano_(V,R):-xr(V,L,[]),!,atom_chars(R,L). xr(V) --> romam(V1),{V1= []. Para entendermos um pouco mais sobre DCGs, vamos mostrar como codificar este programa em cl´ausulas, isto ´e, sem usar o recurso gramatical DCG. Segue o c´odigo. Para economizar espa¸co n˜ao reescrevemos todas as regras. Deixamos para o leitor completar as regras bem como o predicado roman_, a partir da vers˜ao anterior. Existe uma correspondˆencia de uma linha para uma linha entre a vers˜ao DCG e esta vers˜ao em cl´ausulas. Em cada cl´ausula s˜ao acrescidos dois parˆametros, as fitas de entrada e sa´ıda. 1 2 3 4 5 6 7 8 9 10 11 12 %% romano para valor decimal_(X,V):-atom_chars(X,L),r(V,L,[]),!. r(V,I,O):-romam(V1,I,I1),r(V2,I1,O),V = V1+V2. r(0,I,I). %% ?- decimal_(’MCMII’,V), Vo is V. romam(1000,I,O):-tok(’M’,I,O). romam(900,I,O):-tok(’C’,I,I1),tok(’M’,I1,O). romam(500,I,O):-tok(’D’,I,O). romam(400,I,O):-tok(’C’,I,I1),tok(’D’,I2,O). romam(100,I,O):-tok(’C’,I,O). romam(1,I,O) :-tok(’I’,I,O). tok(X,I,O) :-I=[X|O]. Agora, abaixo, podemos ver como s˜ao traduzidas as regras DCG para cl´ausulas pelo tradutor do Prolog. O c´odigo abaixo ´e da vers˜ao DCG do programa. Em rela¸c˜ao a vers˜ao anterior, o Prolog substitui o tk(X,I,O) por I=[X|O] na cabe¸ca das cl´ausulas. ?- [romano]. ?- listing(romam). romam(1000, [’M’|A], A). romam(900, [’C’|A], B) :- A=[’M’|B]. romam(500, [’D’|A], A). romam(400, [’C’|A], B) :- A=[’D’|B]. 12.2. Traduzindo decimais por extenso e vice-versa romam(100, [’C’|A], A). romam(90, [’X’|A], B) :romam(50, [’L’|A], A). romam(40, [’X’|A], B) :romam(10, [’X’|A], A). romam(9, [’I’|A], B) :romam(5, [’V’|A], A). romam(4, [’I’|A], B) :romam(1, [’I’|A], A). 179 A=[’C’|B]. A=[’L’|B]. A=[’X’|B]. A=[’V’|B]. Por fim, devemos dizer que ´e poss´ıvel codificar uma vers˜ao do programa com tok/3 para uma linguagem imperativa. Primeiro reescrevemos as cl´ausulas removendo os valores inteiros da cabe¸ca de cada cl´ausula para o seu corpo, como segue: 1 2 3 4 5 6 7 romam(X,I,O):-tok(’M’,I,O), {X=1000}. romam(X,I,O):-tok(’C’,I,I1),tok(’M’,I1,O),{X=900}. romam(X,I,O):-tok(’D’,I,O), {X=500}. romam(X,I,O):-tok(’C’,I,I1),tok(’D’,I2,O),{X=400}. romam(X,I,O):-tok(’C’,I,O), {X=100}. romam(X,I,O):-tok(’I’,I,O), {X=1}. tok(X,I,O):-I=[X|O]. Agora o predicado romam pode ser visto como uma fun¸c˜ao booleana, numa linguagem imperativa, como segue: 1 2 3 4 5 6 7 8 function romam(var V:int; I:int; var O:int):bool; begin roman := tok(’M’,I,O) and attr(X,1000) or tok(’C’,I,I1) and tok(’M’,I1,O) and attr(X,900) or ... tok(’I’,I,O) and attr(X,1); end; function tok(T:char; I:int; var O:int):bool; begin tok:= (fita[I]=T) and attr(O,I+1); end; function attr(var X:int; V:int):bool; begin X:=V; attr:=true;end; Desse jeito se traduz um programa em DCG (Prolog) para um programa Prolog-like em Pascal. Depois que algu´em passa anos programando em Prolog acaba fazendo este tipo de programa at´e nas linguagens imperativas. Esta tradu¸c˜ao vale tamb´em para Java e outras linguagens imperativas. Para completar o estudo de gram´aticas, veremos outro exemplo pedag´ogico na se¸c˜ao que segue. Exerc´ıcio 12.1 Este programa procedural opera com retrocesso? E´ um programa LL(2)? Justifique. 12.2 Traduzindo decimais por extenso e vice-versa ´ um programa revers´ıvel: as O programa abaixo traduz decimais por extenso e vice-versa. E mesmas regras podem gerar o valor decimal ou o valor por extenso, depende de qual parˆametro ´e fornecido na pergunta, como segue: 180 12. Romanos para decimais e Decimais por extenso ?- dx([cento,e,trinta,e,um],V,[]). V = [1, 3, 1] ?- dx(C,[3,1,2,3],[]), dx(C,L,[]). C = [tres, mil, e, cento, e, vinte, e, tres] L = [3, 1, 2, 3] Segue o programa, com um predicado para unidades, dezenas, centenas e milhar. Apresentamos somente parte das regras, deixando indica¸c˜oes de como complet´a-lo. Completando-se as dezenas, centenas, ... este programa funciona para valores at´e 9999. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 dx(X)-->dddd(X);ddd(X);dd(X);d(X). d([zero])-->[0]. d([um])-->[1]. d([dois])-->[2]. d([tres])-->[3]. %%.. dd([dez])-->[1,0]. dd([onze])-->[1,1]. %%.. dd([vinte])-->[2,0]. dd([vinte,e|D])-->[2],d(D). dd([trinta])-->[3,0]. dd([trinta,e|D] )-->[3],d(D). %%.. ddd([cem])-->[1,0,0]. ddd([cento,e|DD])-->[1],dd(DD). ddd([duzentos])--->[2,0,0]. ddd([duzentos,e|DD])-->[2],dd(DD). %%... dddd([mil])-->[1,0,0,0]. dddd([mil, e|DDD])-->[1],ddd(DDD). dddd([D, mil, e|DDD])-->d([D]),ddd(DDD). Exerc´ıcio 12.2 Programe uma vers˜ao deste programa numa linguagem imperativa, tipo Pascal, C++ ou Java. Numa linguagem imperativa s˜ao necess´arias duas vers˜oes, pois as fun¸c˜oes n˜ao ser˜ao revers´ıveis: uma gera o extenso e a outra reconhece o extenso gerando o decimal. CAP´ITULO 13 Tokens para express˜ oes aritm´ eticas Uma tarefa comum para processadores de linguagens ´e transformar uma linha de texto em uma lista de tokens. Por exemplo, abaixo temos um predicado tokens que transforma um string em uma lista de tokens. ?- tokens(L,"11 +3*(23)",[]). L = [int(11), simb(+), int(3), simb(*), simb(’(’), int(23), simb(’)’)] Yes Neste exemplo temos dois tipos de tokens: inteiros e s´ımbolos. Os inteiros s˜ao seq¨uˆencias de d´ıgitos (11, 3 e 23); os s´ımbolos gr´aficos de dois tipos: operadores e separadores. Exemplos de operadores s˜ao (+ *). Os separadores s˜ao os parˆentese e tamb´em os caracteres n˜ao-vis´ıveis (e.g., espa¸cos em branco). A gram´atica resultante, ver abaixo, possui sete n˜ao-terminais com 13 produ¸c˜oes. Um token (tok) ´e um inteiro ou um s´ımbolo. Uma fita de tokens ´e uma seq¨uˆencia de tokens, que podem estar separados por uma seq¨uˆencia de brancos(br). Os tokens s˜ao escritos na sa´ıda e os brancos s˜ao desprezados. Na Figura 13.1, temos um autˆomato equivalente. Na passagem da gram´atica para o autˆomato, alguns n˜ao-terminais n˜ao s˜ao representados como estados: temos sete n˜ao-terminais e apenas quatro estados – n˜ao temos os estados int, br e tok. Estes estados podem ser criados com uma transi¸c˜ao vazia partindo do estado toks – portanto tamb´em podem ser eliminados, excluindo-se as trˆes transi¸c˜oes vazias. 1 2 3 4 5 6 7 8 9 tokens tokens rtokens rtokens rtokens tok tok %% branco --> --> --> --> --> --> --> tok, rtokens. br, rtokens. tok, rtokens. br, rtokens. []. int. simbolo. --> [C],{C --> --> --> --> --> dig, rint. dig, rint. []. branco, rbr. branco, rbr. []. %% [32]; [8]; [10]; [13]. 181 182 10 11 13. Tokens para express˜ oes aritm´ eticas dig( C ) --> [C],{C>47, C [D],{member(D, "*+/-()")}. Esta gram´atica na nota¸c˜ao DCG do Prolog ´e execut´avel. As trˆes u´ltimas regras (dig, simbolo e branco) possuem a¸c˜oes semˆanticas que verificam restri¸c˜oes sobre os caracteres da fita de entrada. Na defini¸c˜ao destas produ¸c˜oes, assumimos que fita de entrada ´e uma cadeia de c´odigos Ascii. A maneira mais econˆomica de escrever cadeias de c´odigos Ascii ´e usando aspas: ?- ”0123 89”=X. X= [48, 49, 50, 51, 32, 56, 57] Em "0"=[48], o valor Ascii do zero ´e 48. No Prolog ISO vale tamb´em a nota¸c˜ao 0’0=48. Todos os d´ıgitos est˜ao entre os valores Ascii 48 e 57, o que resulta na produ¸c˜ao dig(C)-->[C],{C>47, C dig(C),!, rint(W). rint([C|W]) --> dig(C),!, rint(W). rint( []) --> []. br --> branco,!, rbr. rbr --> branco,!, rbr. rbr --> []. tokens([H|T]) --> tok(H),!,rtokens(T). tokens( T ) --> br, !,rtokens(T). rtokens([H|T]) --> tok(H),!,rtokens(T). rtokens( T ) --> br, !,rtokens(T). rtokens( []) --> []. tok(int(T)) --> int(L),!,{name(T,L)}. Figura 13.1: Autˆomato finito para tokens de express˜oes aritm´eticas. 13.1. Testando o programa 13 14 15 16 tok(simb(T)) branco dig( C ) simbolo([D]) --> --> --> --> 183 simbolo(L),!,{name(T,L)}. [C],{C47, C [let], decVars(Ti/T1), [in], expr(T1,V). decVars(Ti/To) --> decVar(Ti/T1), [’,’], decVars(T1/To). decVars(Ti/To) --> decVar(Ti/To). decVar(Ti/To) --> [L],{isLetra(L)}, [=], expr(Ti,E), {insert(par(L,E),Ti/To)}. expr(TAB,E)--> let(TAB,E). expr(TAB,E)--> termo(TAB,T),[+],expr(TAB,Eo),{E = (T+Eo)}. expr(TAB,E)--> termo(TAB,E). termo(TAB,T)--> fator(TAB,F),[*],termo(TAB,To),{T = (F*To)}. termo(TAB,F)--> fator(TAB,F). fator(TAB,X)--> [X],{integer(X)}. fator(TAB,E)--> [’(’],expr(TAB,E), [’)’]. fator(TAB,V)--> [X],{member(X,[a,b,c,d,e,f,g,h,i,x,y,z])}, {lookUp(par(X,V),TAB), write((look:X:V)),nl}. %% vars %% ?- teste(1,LET),let([],V,LET,RESTO), VAL is V. teste(1, [let, a,=,4,+,5,’,’,b,=,8,+,2, in, a, +, b]). teste(2, [let, c,=,let, a,=,4,+,5,’,’,b,=,8,+,2, in, a, +, b,’,’, d,=,8,+,2, in, ’(’, c, +, d,’)’, *, c, +, d ]). No final do programa dois testes foram codificados como predicados a fim de facilitar a digita¸c˜ao das express˜oes LET aninhadas. Segue a execu¸c˜ao destes dois testes. No programa inclu´ımos dois write(s) para ver o que acontece com a tabela de s´ımbolos. ?- teste(1,LET),let([],V,LET,RESTO),VX is V. tab:[par(a, 4+5)] tab:[par(b, 8+2), par(a, 4+5)] tab:[par(b, 8), par(a, 4+5)] tab:[par(b, 8+2), par(a, 4+5)] look:a:4+5 look:a:4+5 look:b:8+2 look:b:8+2 look:b:8+2 look:b:8+2 LET = [let, a, =, 4, +, 5, (’,’), b, =|...] V = 4+5+ (8+2) RESTO = [] VX = 19 ?- teste(2,LET),let([],V,LET,RESTO), VX is V. 187 tab:[par(d, 8+2), par(c, 4+5+ (8+2))] look:c:4+5+ (8+2) look:d:8+2 LET = [let, c, =, let, a, =, 4, +, 5|...] V = (4+5+ (8+2)+ (8+2))* (4+5+ (8+2))+ (8+2) RESTO = [] VX = 561 Exerc´ıcio 14.1 Fatore o programa da gram´atica. Lembre que depois de fatorar ´e necess´ario ajustar as equa¸c˜oes semˆanticas. Inclua corte, onde for necess´ario, para que ele trabalhe de forma determin´ıstica. Veja exemplo no cap´ıtulo sobre gram´aticas. Exerc´ıcio 14.2 Implemente uma t´ecnica de diagn´ostico para erros sint´aticos, que mostra at´e onde o programa reconheceu a fita de entrada. Trabalhe sobre uma vers˜ao fatorada do problema. Exerc´ıcio 14.3 Implemente um diagn´ostico para erros semˆanticos. As vari´aveis declaradas em vars numa express˜ao let vars in expr s´o podem ser usadas num contexto mais interno in expr. Seguem abaixo dicas para diagn´ostico de erros semˆanticos: let a=b+5, b=8-2 /** em a=b+5 a vari´ avel b ainda n~ ao foi declarada **/ in let c=a+b, d=a+a+3 in (c+d)*(c+d)/2 let a=b1+5, b=let k=2+3 in k+k in (b+c+k) /** em b+c+k a vari´ avel k j´ a n~ ao existe **/ /** ela ´ e local ao outro let **/ let a=5, b=8-2 in let a=a+1 in a+b /** esta express~ ao ´ e v´ alida e o aqui o a=6 **/ /** vale a declara¸ c~ ao mais interna, j´ a funciona **/ Por fim, modifique o predicado do lookUp para dar o diagn´ostico. Como mostrado nos exemplos. CAP´ITULO 15 Um compilador: tradutor e interpretador Neste cap´ıtulo, apresentamos um estudo de caso de um tradutor para uma minilinguagem baseada na linguagem Pascal. O c´odigo gerado, uma ´arvore sint´atica abstrata, ´e executado por um interpretador. A id´eia ´e explorar t´ecnicas das disciplinas de compiladores e linguagens formais: como implementar um l´exico (scanner), um analisador sint´atico e um interpretador. O analisador sint´atico ´e bem poderoso: ele faz uso de analisador de precedˆencia de operadores guiado por tabela (a especifica¸c˜ao ´e na forma de uma tabela). Todos os componentes fazem uso de DCG, mostrando o poder expressivo das gram´aticas DCG para implementar processadores de linguagens (ferramentas para processar linguagens). A constru¸c˜ao de um compilador ´e uma tarefa complexa, por isso ´e usualmente decomposta em trˆes principais subtarefas: • an´alise l´exica; • an´alise sint´atica; • an´alise semˆantica e gera¸c˜ao de c´odigo. Estes trˆes n´ıveis s˜ao apresentados neste estudo de caso. A an´alise l´exica ´e feita por um componente (programa); a an´alise sint´atica ´e feita por dois componentes: um s´o para tratar express˜oes e o outro para os comandos em si. A gera¸c˜ao de c´odigo est´a integrada aos componentes sint´aticos, ´e guiada pela an´alise sint´atica. Por fim, o c´odigo gerado (´arvore sint´atica) ´e interpretado, como se fosse por uma m´aquina abstrata. Sugerimos dois livros como material complementar, o primeiro ´e um livro cl´assico sobre compiladores e o segundo ´e um livro sobre Prolog com um cap´ıtulo sobre compiladores: (1) A. Aho, R. Seti. e J. Ulmman. [1] Compilers — Principles, Techniques, Tools; (2) L. Sterling e E. Shapiro, [16] The Art of Prolog. 189 190 15.1 15. Um compilador: tradutor e interpretador A minilinguagem Abaixo, apresentamos um programa exemplo da minilinguagem: calcula o fatorial. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 program fatorial; var fat, valor; begin write(’Calcula o fatorial’); nl; write(’ valor=’);, read(valor); fat := 1; while valor > 0 do begin fat := fat * valor; valor := valor - 1; end; write(’o fatorial eh:’, fat); nl; write(’FIM’); end. A minilinguagem tem trˆes tipos de dados: inteiros, booleanos e strings. Todas as vari´aveis declaradas s˜ao assumidas do tipo inteiro. Express˜oes booleanas s˜ao usadas nos comandos if e while, n˜ao em declara¸c˜oes. Strings s˜ao usados nos comandos read e write, n˜ao em declara¸c˜oes. Ao lado direito do comando de atribui¸c˜ao podemos ter express˜oes aritm´eticas complexas, que s˜ao analisadas pelo parser que verifica a precedˆencia e a associatividade dos operadores. Temos um comando read que lˆe valores para uma ou mais vari´aveis inteiras; um comando write que escreve uma lista de strings e/ou inteiros; e, um comando nl que escreve o fim de linha (como no Prolog). 15.2 O scanner: an´ alise l´ exica Al´em de n´umeros inteiros, delimitadores e palavras reservadas, o tokenizer deve processar os identificadores que, para a linguagem Pascal, iniciam com uma letra opcionalmente seguida de letras ou d´ıgitos, por exemplo aa123bb. A partir de um arquivo fonte, o scanner gera a lista de tokens para o programa, como a lista exemplificada abaixo (armazenada no fato teste/2). As palavras reservadas s˜ao representadas como r(prog) e r(const); os identificadores como id(fatorial) e id(valor); os n´umeros como num(105); os operadores e os parˆenteses como: ’:=’, ’)’, etc. 1 2 3 4 5 6 7 8 9 10 11 teste(fat, [r(prog),id(fatorial),;, r(var), id(valor),’,’,id(fat),;, r(begin), r(write),’(’,str(’Calcula o fatorial’),’)’,;,r(nl),;, r(write),’(’,str(’ valor=’),’)’,;, r(read),’(’,id(valor),’)’,;, id(fat),:=,num(1),;, r(while),id(valor),>,num(0),r(do), r(begin), id(fat),:=,id(fat),*,id(valor),;, 15.2. O scanner: an´ alise l´ exica 12 13 14 15 16 191 id(valor),:=,id(valor),-,num(1),;, r(end),;, r(write),’(’,str(’o fatorial eh:’),’,’,id(fat), ’)’,;,r(nl),;, r(write),’(’,str(’FIM’),’)’,;, r(end),’.’]). O scanner pode tamb´em gerar o n´umero de linha associado a cada token, como no segundo exemplo abaixo. Este n´umero serve para indicar a posi¸c˜ao de um erro. ?- l1. 1, [r(program), id(fatorial), (;)] 2, [r(var), id(fat), (’,’), id(valor), (;)] 3, [r(begin)] ... ?- l2. 66:[ (1, r(program)), (1, id(fatorial)), (1, (;)), (2, r(var)), (2, id(fat)), (2, ’,’), (2, id(valor)), (2, (;)), (3, r(begin)), (4, r(write)), ... ?- l3. 66:[r(program), id(fatorial), (;), r(var), id(fat), (’,’), id(valor), (;), r(begin), r(write), ’(’, str(’Calcula o fatorial’), ’)’, (;), r(nl), (;), r(write), ’(’, str(’ valor=’), ’)’, (;), r(read), ’(’, id(valor), ’)’, (;), ... Segue abaixo o c´odigo do programa scanner, o readln-elf. Ele ´e inspirado no c´odigo do predicado readln do SWI-Prolog, que lˆe os tokens de uma fita de entrada, ver exemplo abaixo. Em rela¸c˜ao `a vers˜ao citada n´os acrescentamos reconhecimento de strings (com ap´ostrofos e com aspas) e de s´ımbolos tais como Arg1 = [10]; Arg1 = StopChars), ( var(WordChars)-> Arg2 = "01234567890_"; Arg2 = WordChars ), ( var(Case ) -> Arg3 = lowercase; Arg3 = Case ), rl_readln_(LN, P, EOF, Arg1, Arg2, Arg3). rl_readln_(LN, P, EOF, StopChars, WordChars, Case) :rl_blanks(LN, LL), rl_words(P, options(WordChars, Case), LL, []), !. rl_words([W|Ws], Opts) --> rl_word(W, Opts),!,rl_blanks, rl_words(Ws, Opts). rl_words([], _) --> rl_blanks, !. rl_words([], _) --> []. rl_word(str(W),Opts)--> [0’’], rl_pair(C1, 0’’), !, rl_pairs(Rest, 0’’),([0’’],!; []), {name(W, [C1|Rest])}. rl_word(str(W),Opts)--> [0’"],rl_pair(C1, 0’’), !, rl_pairs(Rest, 0’’),([0’"],!; []), {name(W, [C1|Rest])}. %% two chars symbs rl_word(W, _, [0’, 0’=]). rl_word(W, _, [0’*,0’*|S0], S0) :- name(W, [0’*, 0’*]). rl_word(W, _, [0’:,0’=|S0], S0) :- name(W, [0’:, 0’=]). %% rl_word(num(N), _) --> [0’.], rl_num(N1), !, rl_nums(Rest, dot), {name(N,[0’0 , 0’. , N1|Rest])}. 15.2. O scanner: an´ alise l´ exica 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 193 rl_word(num(N), _) --> rl_num(N1),!, rl_nums(Rest, _), {name(N,[N1|Rest])}. rl_word(Wo, Opts) --> rl_char(C1, Opts), !, rl_chars(Rest, Opts), {name(W, [C1|Rest]), (res(W)-> Wo=r(W); Wo=id(W))}. rl_word(P,_) --> [C], {name(P, [C])}, !. rl_chars([A|As], Opts) --> rl_char(A, Opts), !, rl_chars(As, Opts). rl_chars([], _)-->[]. rl_pairs([A|As], Opts) --> rl_pair(A, Opts), !, rl_pairs(As, Opts). rl_pairs([], _)--> []. rl_pair(C1, Opts)--> [C1],{Opts\=C1}. rl_nums([46,N|As], Dot)--> [46], {var(Dot)}, rl_num(N),!, rl_nums(As, dot). rl_nums([A|As], Dot)--> rl_num(A),!, rl_nums(As, Dot). rl_nums([], _) --> []. rl_blanks --> rl_blank, !, rl_blanks. rl_blanks --> []. %% Basic Char types rl_char(A, options(WChars, Case),[C|S],S):- rl_lc(C, A, WChars, Case). rl_num(N, [N|R], R) :- code_type(N, digit). rl_blank( [X|R], R) :- code_type(X, space). rl_lc(X, X1, _,Case):- code_type(X, upper),!,rl_fix_case(Case,X,X1). rl_lc(X, X, _, _) :code_type(X, lower). rl_lc(X, X, WordChars, _) :- memberchk(X, WordChars). rl_fix_case(lowercase,U,L):- !,code_type(L,lower(U)). rl_fix_case(_, C, C). O predicado principal ´e o readln_. Seguem dois testes para ele. No primeiro teste ´e passada a lista de caracteres que podem ocorrer dentro dos identificadores; a op¸c˜ao lowercase for¸ca tudo em min´uscula; strings n˜ao s˜ao afetados. No segundo teste, os identificadores s˜ao mantidos case sensitive (como aparecem no texto). ?-readln_("IOLE1a ’SS10.1’ temp", P, L, [10],"_01213456789",lowercase). P = [id(iole1a), str(’SS10.1’), id(temp)] ?-readln_("IOLE1a ’SS10.1’ temp", P, L, _,_, case). P = [id(’IOLE1a’), str(’SS10.1’), id(temp)]

O predicado readln chama um predicado rl_words que lˆe as palavras. Palavras s˜ao separadas por brancos rl_blanks. Uma palavra pode ser id(), str(), num() ou um s´ımbolo com um ou mais caracteres xx(num(X)), rTerm(PP,0,num(X)/To). term(PP,To) --> xx(’(’), term(1200,T), xx(’)’),rTerm(PP,0,(T)/To). term(PP,To) --> xx(OP), {prefix(P, FX,OP,PR),P= xx(OP),{infix(P,YFX,OP,PL,PR),P=[(P,X)],!. %% , { write((’@[email protected]’,P,X)),nl}. xx(X)-->[X]. %% , { write((’@[email protected]’,X)),nl}.

Segue a execu¸c˜ao de alguns exemplos. O terceiro teste mostra um erro pois o (!) n˜ao foi definido como operador. ?-tt. [num(1), -, -, num(1)], , @[email protected]:-(num(1), -(num(1))) [num(1), +, num(1), *, id(a), *, id(a), +, id(a), -, num(1)], , @[email protected]:-(+(+(num(1), *(*(num(1), id(a)), id(a))), id(a)), num(1)) [num(1), !, !, *, +, (, +, (, +, (, num(1), ), ), )], , @ERRO [email protected] :[!, !, *, +, (, +, (, +, (, num(1), ), ), )], num(1)

15.4 O tradutor: analise sint´ atica e gera¸c˜ ao de c´ odigo O programa tradutor tem trˆes principais partes: a tabela de s´ımbolos, a gram´atica em si e um conjunto de testes. O programa inicia com a tabela de s´ımbolos, que pode ter dois tipos de informa¸c˜ao: vari´aveis e constantes. Abaixo, ilustramos um exemplo de tabela com duas vari´aveis e uma constante. ?- wTab. tab(var, fat, 0) tab(var, valor, 0) tab(const, zero, 0) O predicado initTab inicializa a tabela como vazia, removendo poss´ıveis entradas e declarando o predicado como dinˆamico para poder ser alterado durante a execu¸c˜ao. O predicado mk/3 ´e usado para incluir uma nova entrada na tabela. J´a o predicado wTab ´e usado para escrever a tabela com prop´osito de teste e depura¸c˜ao. Os erros semˆanticos s˜ao tratados com as informa¸c˜oes da tabela de s´ımbolos. S˜ao tratados com dois tipos de testes: (1) na parte de declara¸c˜oes, para verificar se uma vari´avel (ou constante) n˜ao est´a sendo declarada duas vezes; e (2) no corpo do programa, para verificar se uma vari´avel foi declarada. Gera-se duas mensagens de erros semˆanticos: vari´avel n˜ao declarada e vari´avel j´a declarada. 1 2 3 4 5 6 7 8 9 %% file: tradutor.pl :-[’expr-pl’]. %%-----------TABELA DE SIMBOLOS--------------------:-dynamic(tab/3). initTab :- abolish(tab/3),dynamic(tab/3). mk(C,X,V) :-tab(C,X,V),!;assert(tab(C,X,V)). wTab :-tab(CV,ID,N), nl, write(tab(CV,ID,N)), fail. wTab. errDECL(ID) :-tab(VC,ID,_),!, write(’ERRO: Ja Declarada ’:VC:ID),nl. errNDECL(ID):- \+tab(_,ID,_),!, write(’ERRO: Nao declarada’:ID),nl. 15.4. O tradutor: analise sint´ atica e gera¸c˜ ao de c´ odigo 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 197 %%-------GRAMATICA---------------------------------const --> xx(r(const)),!,rConst,xx(;). const --> []. rConst --> cDecl,rrConst. rrConst--> xx(;),cDecl,rrConst. rrConst--> []. cDecl --> xx(id(ID)),xx(=),xx(num(N)), {errDECL(ID),!;mk(const,ID,N)} . var --> xx(r(var)),!,rVar,xx(’;’). var --> []. rVar --> xx(id(ID)),{errDECL(ID),!;mk(var,ID,0)},rrVar. rrVar --> xx(’,’),xx(id(ID)),{errDECL(ID),!;mk(var,ID,0)},rrVar. rrVar --> []. prog(prog(X,B)) --> xx(r(program)),!,xx(id(X)),xx(;),block1(B),xx(.). block1(B) --> const, var, beStmt(B). beStmt(be(S)) --> xx(r(begin)),!, stmtSeq(S), xx(r(end)). stmtSeq([S|Ss]) --> stmt(S), rStmt(Ss). stmtSeq([]) --> []. rStmt([S|Ss]) --> xx(;),stmt(S), rStmt(Ss). rStmt([]) --> xx(;). rStmt([]) --> []. stmt(S) --> beStmt(S). stmt(attr(ID,E)) --> xx(id(ID)),xx(:=),{tab(var,ID,V);errNDECL(ID)},exp(E). stmt(if(C,T)) --> xx(r(if)),!, cond(C),xx(r(then)),stmt(T). stmt(wh(C,S)) --> xx(r(while)),!,cond(C), xx(r(do)),stmt(S). stmt(read(S)) --> xx(r(read )),!,xx(’(’), idSeq(S), xx(’)’). stmt(write(S)) --> xx(r(write)),!,xx(’(’), wrtSeq(S), xx(’)’). stmt(nl) --> xx(r(nl)),!. idSeq([ID|Ss]) --> xx(id(ID)),{tab(var,ID,V);errNDECL(ID)}, rIdSeq(Ss). rIdSeq(S) --> xx(’,’),idSeq(S). rIdSeq([]) --> []. wrtSeq([E|Es]) --> exp(E),rWrtSeq(Es). wrtSeq([str(ID)|Ss]) --> xx(str(ID)),rWrtSeq(Ss). rWrtSeq(S) --> xx(’,’),wrtSeq(S). rWrtSeq([]) --> []. 45 46 47 exp(T) --> term(1201,T). %%,{nl,display(T),nl}. cond(T) --> term(1201,T). %%,{nl,display(T),nl}. A gram´atica ´e parte central do tradutor. Como j´a falamos, uma gram´atica DCG ´e uma gram´atica do tipo LL(K), que funciona por retrocesso. 15.4.1 Gram´ atica da minilinguagem Um programa inicia pela declara¸c˜ao de constantes e vari´aveis. Num programa, podemos ter uma lista de constantes, por exemplo, const zero=0; mil=1000;. Cada declara¸c˜ao de constante, regra const, termina por um ponto-e-v´ırgula. Acrescentamos a regra, const-->[], pois a declara¸c˜ao de constantes ´e opcional. A regra rCont define a lista de declara¸c˜oes de constantes. Em cada declara¸c˜ao de constantes, temos uma a¸c˜ao semˆantica que verifica se a vari´avel sendo declarada j´a est´a na tabela, em caso afirmativo ´e erro, caso contr´ario, o predicado mk/3 inclui uma 198 15. Um compilador: tradutor e interpretador entrada na tabela. Vari´aveis tamb´em s˜ao opcionais. Por exemplo, |program vazio; begin end| ´e um programa v´alido sem declara¸c˜ao de vari´aveis nem de constantes. Um programa na minilinguagem ´e formado pela declara¸c˜ao de constantes, seguida da declara¸c˜ao de vari´aveis e do bloco de comandos. O bloco de comandos come¸ca com a palavra reservada begin e termina com end. O conte´udo do bloco ´e uma lista de comandos, podendo conter outros comandos do tipo begin end. Al´em do comando composto s˜ao implementados outros cinco comandos: o de atribui¸c˜ao, :=; dois condicionais, if e while; o de leitura, read, e o de escrita, write. ´ dif´ıcil desenvolver uma gram´atica do tipo LL(k) para express˜oes aritm´eticas e express˜oes E booleanas que trate dos problemas de precedˆencia e associatividade. Por isso, foi criado o componente j´a descrito onde as express˜oes s˜ao especificadas por um conjunto de operadores definidos numa tabela. Este componente ´e chamado em duas produ¸c˜oes: exp(T) --> term(1201,T) . %% ,{nl,display(T),nl}. cond(T) --> term(1201,T). %% ,{nl,display(T),nl}. 15.4.2 Testes para o tradutor Segue abaixo o texto que faz parte do programa tradutor, mas que cont´em apenas os testes. Para programas complexos, como um compilador (tradutor), ´e necess´ario definir estrat´egias para fazer testes sistem´aticos de todas as produ¸c˜oes da linguagem. Uma possibilidade ´e testar pequenos grupos de produ¸c˜oes que executam determinadas funcionalidades, por exemplo, a declara¸c˜ao de vari´aveis. Aqui, os predicados do/2 e do2/2 foram definidos para testar produ¸c˜oes isoladamente. Com eles se definem testes espec´ıficos para declara¸c˜ao de constantes c1 e vari´aveis v1, v2. Por exemplo, o teste v1 declara trˆes vari´aveis (que s˜ao inclu´ıdas na tabela de s´ımbolos) e o teste v2 tenta declarar duas vezes a mesma vari´avel. Segue a execu¸c˜ao do teste v2. ?- v2. [r(var),id(valor),(,),id(valor),(;)] : >>> ERRO: Ja Declarada : var : valor sobrou : [] tab(var,valor,0) De forma similar tamb´em existem testes para as express˜oes aritm´eticas e2, e3 e condicionais co1, co2. ´ importante deixar registrados os testes a serem executados, pois quando modificamos uma E parte da gram´atica rapidamente podemos testar apenas aquele fragmento. Al´em disso, fica registrado como documenta¸c˜ao para lembrarmos depois como se faz o teste. Temos tamb´em testes mais completos, baseados na fita do programa fatorial, codificada em teste/2, que s˜ao p, pcv, terro e tfat. Por fim, temos os testes com os arquivos de entrada p1 e t1. 1 2 3 4 5 6 7 do(P,X):-initTab, DO=..[P,X,R],call(DO),write(’sobrou’: R),nl,wTab. do2(P,X):-initTab, DO=..[P,T,X,R],call(DO),write(T:’\nsobrou’: R),nl,wTab. c1:-do(const,[r(const),id(zero),=,num(0),;,;,id(tres2),=,num(3),;]). v1:-do(var,[r(var), id(valor),’,’,id(maior),’,’,id(tot),;]). v2:-do(var,[r(var), id(valor),’,’,id(valor),;]). e1:-assert(tab(var,tot,_)),do2(exp,[num(1), ,id(tot)]). e2:-assert(tab(var,tot,_)),do2(exp,[id(l1), ,id(tot)]). 15.5. O interpretador: an´ alise semˆ antica 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 199 e3:-assert(tab(var,valor,_)),do2(exp,[num(1),*,id(valor),-,num(3),*,num(4)]). co1:-assert(tab(var,valor,_)),do2(cond,[id(valor), , id(zero)]). co2:-assert(tab(var,valor,_)),do2(cond,[id(valor), , num(1), *, id(abc)]). %----------------------------------------------------------------% fitas de um programa p:-prog(T,[r(program),id(test),;,r(begin), r(end),’.’],X),write(T:X),nl. pcv:-initTab, prog(T,[r(program),id(test),;, r(const),id(zero),=,num(0),;, r(var), id(valor),’,’,id(maior),’,’,id(total),;, r(begin), r(end),’.’],X),write(T:X),wTab,nl. teste(erro, [r(program),;, r(var), id(valor),’,’,id(fat),;,r(end),’.’]). teste(fat, [r(program),id(fatorial),;, r(var), id(valor),’,’,id(fat),;, r(begin), r(write),’(’,str(’Calcula o fatorial’),’)’,;,r(nl),;, r(write),’(’,str(’ valor=’),’)’,;, r(read),’(’,id(valor),’)’,;, id(fat),:=,num(1),;, r(while),id(valor), > ,num(0),r(do), r(begin), id(fat),:=,id(fat),*,id(valor),;, id(valor),:=,id(valor),-,num(1),;, r(end),;, r(write),’(’,str(’o fatorial eh:’),’,’,id(fat), ’)’,;,r(nl),;, r(write),’(’,str(’FIM’),’)’,;, r(end),’.’]). stdout(F,CALL):-tell(F),call(CALL),told. tfat :- teste(fat, P),initTab,prog(Po,P,R),nl,writeq(Po:R), nl. terro :- teste(erro,P),initTab,prog(Po,P,R),nl,writeq(Po),nl, writeq(er:R). %% usinf files %% ?- t1. ?- p1. t1:- callComp(’fat.pas’). p1:- callComp(’prog.pas’). callComp(F):- file_to_tokens(F,L), wfile(L), zipper_dl(L,Lo/[]),!, writeq(M:Lo), Lo=P,initTab,prog(Po,P,R),!, nl,writeq(Po),nl,writeq(sobrou:R). Comparando-se o tamanho da gram´atica com o tamanho do arquivo de testes, vemos que s˜ao do mesmo tamanho. Isto mostra que devemos nos preocupar com os testes, principalmente em programas complexos como um compilador. 15.5 O interpretador: an´ alise semˆ antica O interpretador roda sobre o c´odigo gerado pelo tradutor, logo, ele inicia carregando o tradutor. O tradutor ´e ativado pelo predicado prog/3 que retorna a ´arvore sint´atica para ser interpretada. A entrada do tradutor ´e `a sa´ıda do l´exico, que ´e ativado pelo predicado file_to_tokens. Temos tamb´em, abaixo, um teste que n˜ao depende destes dois componentes, mas apenas de uma ´arvore sint´atica codificada como o fato testeInt/2. Isto ´e bom, pois, `as vezes n˜ao queremos 200 15. Um compilador: tradutor e interpretador

depender dos outros componentes para trabalhar com o interpretador. Segue um exemplo de execu¸c˜ao do programa fatorial. ?- tfati. executando..fatorial Calcula o fatorial valor=entre com o valor:valor | 5. valor=0 [email protected]@ valor=5 fat=0 [email protected]@ fat=1 fat=1 [email protected]@ fat=5 valor=5 [email protected]@ valor=4 fat=5 [email protected]@ fat=20 valor=4 [email protected]@ valor=3 fat=20 [email protected]@ fat=60 valor=3 [email protected]@ valor=2 fat=60 [email protected]@ fat=120 valor=2 [email protected]@ valor=1 fat=120 [email protected]@ fat=120 valor=1 [email protected]@ valor=0 o fatorial eh:120 FIM

O interpretador ´e codificado como uma fun¸c˜ao recursiva com um predicado para cada tipo de constru¸c˜ao do programa. Temos um predicado aval que chama avalif, avalwh, avalwrL para respectivamente os comandos if, while e write. Depois temos o predicado avalExp que tem uma regra (linha) para cada operador, se chama recursivamente para cada operando. A recursividade termina quando ´e encontrado um identificador ou uma constante. O valor de um identificador ´e buscado na tabela de s´ımbolos. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 %% file:inter.pl :-[’tradutor’]. callCompInt(F):- file_to_tokens(F,L), % wfile(L), zipper_dl(L,Lo/[]),length(Lo,M),writeq(M:Lo),!,Lo=P, initTab,prog(Po,P,R), % nl,writeq(Po),nl,writeq(Po), !,aval(Po). t1i:- callCompInt(’fat.pas’). p1i:- callCompInt(’prog.pas’). %% EXEMPLO DE A´RVORE SINTATICA ABSTRATA DO FAT tint :- initTab, testeInt(fat,P),aval(P). testeInt(fat, prog(fatorial, be([write([str(’Calcula o fatorial’)]), nl, write([str(’ valor=’)]), attr(valor, num(5)), attr(fat, num(1)), wh(id(valor)>num(0), be([attr(fat, id(fat)*id(valor)), attr(valor, id(valor)-num(1))])), write([str(’o fatorial eh:’), id(fat)]), nl, write([str(’FIM’)])])) ). %% testa os exemplos do tradutor tprogi :- teste(prog,P),initTab,prog(Po,P,[]),nl,writeq(Po),nl, !,aval(Po). tfati :- teste(fat, P),initTab,prog(Po,P,[]),nl,writeq(Po),nl,!,aval(Po). %% ?- avalExp( id(valor)>id(maior)+id(total),X). 15.5. O interpretador: an´ alise semˆ antica 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 201

%%------------------------------------------------------------aval([]). aval(prog(ID,B)):-nl,write(’executando..’),write(ID),nl,aval(B). aval(be(X)):-!,aval(X). aval(if(C,B)):-!,avalif(C,B). avalif(C,B):-avalExp(C,Co),Co=true,!,aval(B). avalif(C,B). aval(wh(C,B)):-!,avalwh(C,B). avalwh(C,B):-avalExp(C,Co),Co=true,!,aval(B),avalwh(C,B). avalwh(C,B). aval([X|Xs]):-aval(X),aval(Xs). aval(read([X])):- write(’entre com o valor’:X),nl,!, read(Xo),!,save(tab(_,X,Xo)). aval(write(X)):-!,avalwrL(X). avalwrL([X|Xs]):-!,avalExp(X,Xo),write(Xo),avalwrL(Xs). avalwrL([]). aval(nl):-nl. aval(attr(X,E)):-avalExp(E,Eo),save(tab(_,X,Eo)). avalExp(str(X),X). avalExp(id(X),Y):-tab(_,X,Y). avalExp(num(X),X). avalExp(Yo, V=true,!;V=false)). avalExp(>(X,Y),V):-avalExp(X,Xo),avalExp(Y,Yo),!, ((Xo>Yo, V=true,!;V=false)). avalExp( (X,Y),V):-avalExp(X,Xo),avalExp(Y,Yo),!, ((Xo\=Yo, V=true,!;V=false)). avalExp(+(X,Y),V):-avalExp(X,Xo),avalExp(Y,Yo), (V is Xo+Yo). avalExp(-(X,Y),V):-avalExp(X,Xo),avalExp(Y,Yo), (V is Xo-Yo). avalExp(*(X,Y),V):-avalExp(X,Xo),avalExp(Y,Yo), (V is Xo*Yo). avalExp(/(X,Y),V):-avalExp(X,Xo),avalExp(Y,Yo), (V is Xo/Yo). save(tab(X,Y,Z)):-tab(X,Y,Vi), asserta(tab(X,Y,Z)), write(Y=Vi),write(’ [email protected]@ ’),write(Y=Z),nl,!. save(tab(X,Y,Z)):-asserta(tab(X,Y,Z)),write(’ [email protected]@@ ’),write(Y=Z),nl,!.

Como foi visto, em Prolog, podemos codificar um sistema complexo como um compilador em componentes modulares, que podem ser testados isoladamente. Cada componente tem menos de uma centena de linhas de c´odigo fonte, assim fica f´acil domin´a-lo mentalmente. Aqui termina nosso estudo de caso sobre compiladores. Restam v´arios desafios para os alunos. Por um lado, como estender o l´exico para trabalhar com n´umeros de ponto flutuante e outros tipos de inteiros (bin´arios e hexa) como os da linguagem Java; como incluir declara¸c˜oes vari´aveis destes diferentes tipos: bool, char, etc; como incluir outros comandos: if-then-else, for, etc; como incluir vetores; como incluir fun¸c˜oes tipo Java; etc; Por outro lado, como gerar assembler para a ´arvore sint´atica, apenas substituindo o interpretador. Bom estudo e bom trabalho. CAP´ITULO 16 Processamento de Linguagem Natural com DCG Neste cap´ıtulo apresentamos alguns conceitos de Processamento de Linguagem Natural (PLN) fazendo uso da nota¸c˜ao gramatical DCG do Prolog. O material deste cap´ıtulo pode ser aprofundado em livros, tais como, M. A. Covington, [8] Natural Language Processing for Prolog Programmers, Prentice Hall, New Jersey, 1994. 16.1 Introdu¸c˜ ao ao PLN Processamento de Linguagem Natural ´e uma sub´area da Inteligˆencia Artificial que estuda o uso do computador para processar linguagens usadas na comunica¸c˜ao entre seres humanos, tais como portuguˆes e inglˆes. Exemplos de aplica¸c˜oes em PLN incluem: Tradu¸c˜ao autom´atica; Extra¸c˜ao autom´atica de conhecimento a partir de textos; Reconhecimento de voz; Dicion´arios eletrˆonicos e Corretores ortogr´aficos; etc. Estas aplica¸c˜oes, no estado da arte atual, ainda deixam muito a desejar, por exemplo, para um tradutor, a qualidade da tradu¸c˜ao ainda ´e bem pobre. Do ponto de vista da Ling¨u´ıstica (ciˆencia que estuda as linguagens naturais), a estrutura de uma linguagem natural ´e classificada em cinco n´ıveis: Fonologia (som); Morfologia (forma¸c˜ao das palavras); Sintaxe (estrutura das frases); Semˆantica (significado das frases) e Pragm´atica (uso da linguagem num contexto). Em uma perspectiva ortogonal `a Ling¨u´ıstica, o estudo de linguagens em computa¸c˜ao faz referˆencia `a ´area da computa¸c˜ao conhecida como linguagens formais (de computador). Uma linguagem formal ´e descrita e processada em trˆes n´ıveis de conhecimento: L´exico (ou morfol´ogico) trata dos tokens e palavras; Sint´atico trata das senten¸cas (erros de gram´atica); Semˆantico trata do significado das senten¸cas ou tradu¸c˜ao. Neste cap´ıtulo, apresentamos no¸c˜oes de PLN, enfocando as ´areas de morfologia, sintaxe e semˆantica. A tecnologia desenvolvida para linguagens formais de computador ´e usada em PLN, principalmente em aplica¸c˜oes sobre linguagem escrita. 203 204 16.2 16. Processamento de Linguagem Natural com DCG L´ exico – Morfologia A morfologia estuda a forma¸c˜ao das palavras. Uma linguagem tem dois principais tipos de forma¸c˜ao de palavras: (1) Inflex˜ao: dada a raiz de uma palavra geram-se v´arias formas, e.g., mesa, mesas; canto, canta, cantas, cantem; (2) Deriva¸c˜ao: juntar palavras existentes para formar outras, e.g., guarda-chuva. Palavras s˜ao formadas por caracteres. O Prolog possui um conjunto de facilidades para se trabalhar com caracteres formando palavras. Um s´ımbolo atˆomico, ou palavra b´asica do Prolog, pode ser decomposto em uma lista de c´odigos Ascii. Cada c´odigo Ascii representa um caractere. A maioria dos caracteres ´e vis´ıvel na tela e possui um significado simb´olico. Existem tamb´em caracteres de controle, por exemplo, caracteres de nova linha e de tabula¸c˜ao. O Prolog possui o predicado name(ATOMO, LISTA_CHAR) que converte um ´atomo numa lista de c´odigos Ascii, onde cada caractere ´e representado por um c´odigo. Seguem dois exemplos: ?- name(’ABC’,X). X = [65,66,67] ?- name(’abc’,X). X = [97,98,99]

No Prolog tamb´em podemos escrever a lista dos valores Ascii de um ´atomo, colocando-o entre aspas. Na primeira pergunta, abaixo, vemos que os caracteres ”AZaz”valem [65,90,97,122], o que significa que o conjunto das letras mai´usculas(”AZ”) est´a no intervalo entre 65 e 90, o conjunto das min´usculas (”az”) est´a no intervalo entre 97 e 122, e que temos 26 letras, incluindo o Y e W. Na segunda pergunta, temos os valores para os d´ıgitos decimais que est˜ao entre 48 e 57. Na terceira pergunta, temos uma lista de s´ımbolos gr´aficos normalmente usados no Prolog para programa¸c˜ao. O espa¸co em branco ´e o valor 32. ?- "AZaz"=X. X = [65,90,97,122] ?- "0123456789" = Y. Y = [48,49,50,51,52,53,54,55,56,57] ?- " [email protected]$%$^&*()-+" = Z. Z = [32,33,64,36,37,36,94,38,42,40,41,45,43]

16.2.1 Flex˜ ao em gˆ enero Um tipo de processamento morfol´ogico (que manipula palavras) ´e a flex˜ao em gˆenero: dada a forma no masculino, gerar a forma correspondente no feminino. Trabalha-se no n´ıvel dos caracteres, por exemplo, na palavra menino, como substituir o ”o”por um ”a”para gerar a palavra menina. Decompomos a palavra numa lista de caracteres, usando name/2, trocamos o u´ltimo caractere por um ”a”, como segue: ?- Z=menina, name(Z,NZ),append(X,[97],NZ), append(X,[111],NZ1), name(Z1,NZ1). Z = menina , NZ = [109,101,110,105,110,97] , X = [109,101,110,105,110] , NZ1 = [109,101,110,105,110,111] , Z1 = menino 16.3. Um exemplo de minilinguagem 205 O valor Ascii do ”o”´e 111 e do ”a”´e 97. Para usar o predicado name, temos que codificar os valores Ascii dos caracteres nas regras. O append tem dois usos, um para separar o ”o”da palavra menino (”menin”+”o”) e outro para juntar o ”a”formando menina (”menin”+”a”). Para evitar a manipula¸c˜ao de valores Ascii, que s˜ao um tanto obscuros, fazemos dois predicados: separa e junta. Estes predicados, escondendo o trabalho com os valores Ascii, permitem ´atomos nos seus parˆametros, como segue. 1 2 3 4 5 6 junta(X,Y,Z):-nonvar(X),nonvar(Y),name(X,NX),name(Y,NY), append(NX,NY,NZ),name(Z,NZ),!. separa(X,Y,Z):-nonvar(Z),name(Z,NZ), append(NX,NY,NZ),name(Y,NY),name(X,NX),!. genero(LEMA,LEX):- var(LEX ),separa(RAIZ,o,LEMA),junta(RAIZ,a,LEX ). genero(LEMA,LEX):- var(LEMA),separa(RAIZ,a,LEX ),junta(RAIZ,o,LEMA). O junta exige os dois primeiros parˆametros instanciados; o separa exige o u´ltimo parˆametro instanciado. A partir dos predicados junta e separa ´e codificada uma regra que faz a convers˜ao entre genero: se damos a forma feminina ela devolve a masculina e vice-versa. Seguem alguns exemplos: ?- separa(M,o,menino). M = menin ?-junta(menin,o,M). M = menino ?- genero(menino, X). X = menina ?- genero(X, menina). X = menino 16.3 Um exemplo de minilinguagem Para mostrar como podemos trabalhar com a sintaxe de uma linguagem natural, devemos focalizar a aplica¸c˜ao num dom´ınio bem restrito. Assumimos o dom´ınio de um pequeno ambiente para uma fam´ılia de c˜aes, gatos e ratos. Neste dom´ınio podemos fazer frases tais como: • O gato persegue o Mikey. • As gatas comem o queijo do Mikey. • Ele persegue o gato. Ele come uns ratos. • Bidu persegue Mimi. Bidu dorme. Abaixo, apresentamos algumas regras gramaticais para gerar frases como as exemplificadas, com at´e dois participantes. Uma ora¸c˜ao (ou senten¸ca) ´e formada por uma frase nominal (fraseNom)1 seguida de uma frase verbal (fraseVerbal). Uma frase nominal ´e um nome opcionalmente precedido por um artigo ou um pronome. Uma frase verbal ´e um verbo seguido de uma frase nominal. 1´ E comum em Portuguˆes usar o termo sintagma nominal. N´os preferimos usar o termo frase em vez de sintagma. Frase ´e uma seq¨ uˆencia de palavras que forma um sentido completo (por exemplo: exclama¸c˜ao, ora¸c˜ao simples, ora¸c˜ao complexa). Sintagma ´e uma seq¨ uˆencia de palavras que forma um constituinte. Uma ora¸c˜ao tamb´em ´e um constituinte gramatical. 206 1 2 3 4 5 6 7 8 9 10 11 12 16. Processamento de Linguagem Natural com DCG sent --> fraseNom, fraseVerbal. fraseNom --> artigo, nome. fraseNom --> nome. fraseNom --> pronome. fraseVerbal --> verbo, fraseNom. fraseVerbal --> verbo. %% nome --> [bidu] ; [mimi] ; [mikey]. nome --> [cao] ; [gato] ; [gata] ; [gatas] ; [rato] ; [queijo]. pronome--> [ele] ; [ela]. verbo --> [late] ; [persegue] ; [come]; [comem]; [dorme]. artigo --> [A], {member(A,[a,as,o,os,um,uns,uma,umas])}. A segunda parte do c´odigo da gram´atica define um l´exico para o dom´ınio do problema. Neste l´exico, todas as palavras usadas nas senten¸cas devem ser classificadas em categorias l´exicas, que incluem nomes pr´oprios (Bidu, Mikey), nomes comuns (gato, rato, queijo), pronomes (ele), verbos (persegue, dorme) e artigos (o, os). Para testar as regras, criamos uma base de testes e um predicado que chama cada um dos testes (run). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 teste([o, gato, dorme]). teste([o, gato,persegue,mikey]). teste([o, gato,come,o,queijo,do,mikey]). teste([a, gata,come,o,queijo]). teste([o, gatas,come,umas,queijo]). teste([ela, persegue, o, rato]). teste([ele, persegue, um, mikey]). teste([ele, persegue, o, mikey]). teste([eles, come, um, rato]). teste([ele, come, uns, rato]). teste([o,ele,come,o,rato]). %% wOK(R,T):-R=[]-> write((’ ok’:T)); write((erro1:T:sobrou:R)). wErro(T):-write((erro2:T)). run(T):-sent(T,R)-> wOK(R,T); wErro(T ). run. Cada produ¸c˜ao codificada como uma regra gramatical DCG, quando executada, retorna um dos trˆes estados: • falhou completamente, n˜ao reconhecendo nada (erro2); • reconheceu uma parte da senten¸ca, retornando, no segundo parˆametro, `a parte n˜ao reconhecida (erro1); • reconheceu a senten¸ca toda, retornando, no segundo parˆametro, a lista vazia (ok). Estas regras est˜ao codificadas no predicado run/1. O predicado run/0, por retrocesso, chama o teste para todas as entradas da base de testes. Segue o resultado dos testes. Podemos ver que a gram´atica apresenta v´arios problemas, incluindo falta de tratamento para a concordˆancia nominal e verbal, por exemplo, /*o gatas /*eles come /*um Mikey/. Estes problemas s˜ao analisados a seguir. ´ 16.4. Arvore sint´ atica ?- run. ok : ok : erro1 : ok : ok : ok : ok : ok : ok : ok : erro2 : yes 16.4 207 [o,gato,dorme] [o,gato,persegue,mikey] [o,gato,come,o,queijo,do,mikey] : sobrou : [do,mikey] [a,gata,come,o,queijo] [o,gatas,come,umas,queijo] [ela,persegue,o,rato] [ele,persegue,um,mikey] [ele,persegue,o,mikey] [eles,come,um,rato] [ele,come,uns,rato] [o,ele,come,o,rato] ´ Arvore sint´ atica Alguns conceitos sobre sintaxe est˜ao diretamente relacionados `a constru¸c˜ao de ´arvores sint´aticas para senten¸cas. Abaixo, temos uma ´arvore sint´atica para a frase Ele come o queijo. A raiz da ´arvore ´e o n´o sent; na fronteira da ´arvore, temos os n´os folhas (e.g., ele, come); internamente na ´arvore temos os n´os fn e fv, que denotam frase nominal e verbal, respectivamente. Estes n´os s˜ao tamb´em chamados de constituintes gramaticais. Para cada constituinte temos uma frase associada, por exemplo, o fn mais interno ´e associado `a frase o queijo. Cada palavra ´e classificada numa das categorias l´exicas: pron(ome), verbo, art(igo) e nome comum. fn -- pron -- ele / sent verbo -- come \ / fv art -- o \ / fn \ comum -- queijo sent(fn(pron(ele)),fv(verbo(come),fn(art(o),comum(queijo)))) A ´arvore possui tamb´em uma representa¸c˜ao na forma de termo, como ´e mostrado acima. Esta representa¸c˜ao na forma de termo ´e facilmente gerada a partir das regras DCG da gram´atica. Cada n´o interno da ´arvore ´e uma regra DCG. Se o n´o tem dois filhos, ent˜ao no corpo da regra temos uma chamada para duas sub-regras. Abaixo, apresentamos uma vers˜ao da gram´atica que gera ´arvores sint´aticas. Acrescentamos um sufixo (_) em cada predicado para diferenci´a-los da vers˜ao anterior. As regras para nome, pronome e verbo, aqui, s˜ao codificadas com uso do member, como hav´ıamos codificado a regra-artigo na vers˜ao anterior. 1 2 3 sent_(sent(FN,FV) ) --> fraseNom_(FN), fraseVerbal_(FV). fraseNom_(fn(A,N) ) --> artigo_(A), nome_(N). fraseNom_(fn(N) ) --> nome_(N). 208 4 5 6 7 8 9 10 11 12 16. Processamento de Linguagem Natural com DCG fraseNom_(fn(P) ) --> fraseVerbal_(fv(V,FN)) --> fraseVerbal_(fv(V) ) --> %% nome_(propr(N)) --> [N], nome_(comum(N)) --> [N], pronome_(pron(P)) --> [P], verbo_(verbo(V))--> [V], artigo_( art(A)) --> [A], pronome_(P). verbo_(V), fraseNom_(FN). verbo_(V). {member(N, {member(N, {member(P, {member(V, {member(A, [bidu,mimi,mikey])}. [cao, gato, rato, queijo])}. [ele,ela])}. [late, persegue, come])}. [a,as,o,os,um,uns,uma,umas])}. Podemos testar os diferentes constituintes isoladamente. Por exemplo, perguntar sobre o nome pr´oprio Mikey: ?-nome_(N,[mikey],[]). O resultado ´e N=propr(mikey). Uma pergunta sobre uma frase nominal ´e ?- fraseNom (A, [o, cao],[]), que resulta em A=fn(art(o), comum(cao)). Uma regra DCG, quando traduzida para uma cl´ausula, ´e acrescida de dois parˆametros (os dois mais `a direita): (1) lista de entrada e (2) lista de sa´ıda. Quando a gram´atica reconhece todos os tokens da lista de entrada, a lista de sa´ıda ´e vazia. A ´arvore ´e retornada no primeiro dos trˆes parˆametros. Seguem algumas perguntas sobre ´arvores sint´aticas: ?- fraseNom_(A, [mikey],[]). A = fn(propr(mikey)) ?- fraseNom_(A, [o, cao],[]). A = fn(art(o),comum(cao)) ?- sent_(A, [o, cao, late],[]). A = sent(fn(art(o),comum(cao)),fv(verbo(late))) ?- sent_(A, [ele, come, o, queijo],[]). A = sent(fn(pron(ele)),fv(verbo(come),fn(art(o),comum(queijo)))) Na gera¸c˜ao de ´arvores, fizemos somente testes que s˜ao v´alidos, pois quando uma pergunta falha n˜ao retorna valores nas vari´aveis. 16.5 Incluindo regras para concordˆ ancia A concordˆancia pode acontecer em diversos n´ıveis, por exemplo, nas frases /*eles compra livro /*Mimi perseguir Mikey/ temos problemas de concordˆancia verbal. E nas frases /*o livros /*a livros/ temos problemas concordˆancia nominal. Para trabalhar com concordˆancia ´e necess´ario estender as regras gramaticais com parˆametros associados aos tra¸cos das palavras de cada frase. Tra¸cos ling¨u´ısticos s˜ao informa¸c˜oes ling¨u´ısticas que caracterizam uma palavra. Seguem alguns tra¸cos para as palavras, c˜ao, ele, Bidu: • c˜ao – nome comum, gˆenero masculino e n´umero singular; • ele – pronome pessoal, gˆenero masculino e n´umero singular, na terceira pessoa; • Bidu – nome pr´oprio (um c˜ao), gˆenero masculino. Os tra¸cos de uma palavra s˜ao representados num fato. Por exemplo, para a palavra ele o fato ´e tracos(ele, t(pronome, masc/sing, s3)). Um ou mais valores de tra¸cos s˜ao passados como parˆametros entre as regras gramaticais para verificar as regras de concordˆancia. 16.5. Incluindo regras para concordˆ ancia 209 Abaixo, na regra sent1, temos em T os valores dos tra¸cos da frase nominal (fraseNom(T)). Verificamos que estes mesmos valores acontecem na frase verbal (fraseVerbal(T)). Numa frase nominal, devemos garantir (ou estabelecer) a concordˆancia entre gˆenero e n´umero. A concordˆancia em gˆenero ´e estabelecida pela vari´avel MF, resolvendo erros do tipo /*a gato /*o gata/. Ao mesmo tempo, a concordˆancia em n´umero ´e estabelecida pela vari´avel SP, resolvendo erros do tipo: /*o gatos /*os gato/. Al´em disso, um artigo indefinido deve preceder um nome comum, resolvendo erros do tipo: /*um Mikey/. Um nome pr´oprio ou um pronome, tamb´em, s˜ao frases nominais. Numa frase verbal, temos apenas o verbo ou o verbo seguido de uma frase verbal. Nesta gram´atica, na frase verbal, n˜ao existe concordˆancia entre o verbo e o objeto. Tipicamente, o verbo s´o concorda com o sujeito. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 sent1 --> fraseNom(T), fraseVerbal(T). fraseNom(t(_, MF/SP,P)) --> artigo(t(_,MF/SP,_)), nome(t(comum,MF/SP,P)). fraseNom(t(_, MF/SP,P)) --> artigo(t(_,MF/SP,def)), nome(t(propr,MF/SP,P)). fraseNom(t(_, MF/SP,s3)) --> nome(t(C,MF/SP,_)), {C=propr; C=pronome}. fraseVerbal(T) --> verbo(T), fraseNom(_). fraseVerbal(T) --> verbo(T). %% nome(t(propr, MF/SP,_)) --> [X],{tracos(X,t(propr, MF/SP,_)) }. nome(t(comum, MF/SP,_)) --> [X],{tracos(X,t(comum, MF/SP,_)) }. nome(t(pronome,MF/SP,_)) --> [X],{tracos(X,t(pronome,MF/SP,_)) }. verbo(t(_, MF/SP,P)) --> [X],{tracos(X,t(verbo, MF/SP,P)) }. artigo(t(_, MF/SP,P)) --> [X],{tracos(X,t(artigo, MF/SP,P)) }. %% do(S,T):- CALL=..[S,T,R], CALL-> wOK(R,T); wErro(T). do1:-teste(T),do(sent1,T),nl,fail. do1. Para esta vers˜ao da gram´atica, o l´exico ´e codificado como uma tabela de palavras associadas a tra¸cos ling¨u´ısticos. Todas as palavras usadas numa frase devem constar no l´exico. Para aplica¸c˜oes n˜ao-triviais, o l´exico ´e uma fonte de conhecimento grande e dispendiosa, portanto a codifica¸c˜ao manual de um l´exico ´e uma atividade tediosa. Seguem os fatos do l´exico: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 tracos0(cao, t(comum, masc/sing, _)). tracos0(gato, t(comum, masc/sing, _)). tracos0(gata, t(comum, fem/sing, _)). tracos0(rato, t(comum, masc/sing, _)). tracos0(queijo, t(comum, masc/sing, _)). %% tracos0(ele, t(pronome, masc/sing, s3)). tracos0(eles, t(pronome, masc/plur, p3)). tracos0(ela, t(pronome, fem/sing, s3)). %% tracos0(come, t(verbo, _/sing, s3)). tracos0(persegue, t(verbo, _/sing, s3)). tracos0(comem, t(verbo, _/plur, p3)). %% tracos0(bidu, t(propr, masc/_, _)). tracos0(mikey, t(propr, masc/_, _)). 210 17 18 19 20 21 22 23 24 25 26 27 28 16. Processamento de Linguagem Natural com DCG tracos0(mimi, t(propr, fem/_, _)). %% tracos0(o, t(artigo, masc/sing, def)). tracos0(os, t(artigo, masc/plur, def)). tracos0(um, t(artigo, masc/sing, ind)). tracos0(uns, t(artigo, masc/plur, ind)). tracos0(a, t(artigo, fem/sing, def)). tracos0(as, t(artigo, fem/plur, def)). tracos0(uma, t(artigo, fem/sing, ind)). tracos0(umas, t(artigo, fem/plur, ind)). %% tracos(P, T) :- tracos0(P, T),!. Abaixo, temos os testes executados para a gram´atica sent1, que verifica tamb´em as regras de concordˆancia. Foram identificados v´arios novos erros, os de concordˆancia: /*o gatas /*um Mikey /*eles come /*uns rato/. ?- do1. do1. ok : ok : erro1 : ok : erro2 : ok : erro1 : ok : erro2 : erro1 : erro2 : yes [o,gato,dorme] [o,gato,persegue,mikey] [o,gato,come,o,queijo,do,mikey] : sobrou : [do,mikey] [a,gata,come,o,queijo] [o,gatas,come,umas,queijo] [ela,persegue,o,rato] [ele,persegue,um,mikey] : sobrou : [um,mikey] [ele,persegue,o,mikey] [eles,come,um,rato] [ele,come,uns,rato] : sobrou : [uns,rato] [o,ele,come,o,rato] Na pr´atica, esta gram´atica sint´atica pode ser vista como uma esp´ecie de corretor gramatical, que verifica erros comparando os tra¸cos das palavras que comp˜oem as senten¸cas. 16.6 Gerando uma ´ arvore sint´ atica Aqui, vemos como juntar o c´odigo que gera uma ´arvore (sent_) ao c´odigo que faz a concordˆancia (sent1). Basicamente, ´e s´o acrescentar um parˆametro em cada n˜ao-terminal da gram´atica sent1, como segue. 1 2 3 4 5 6 7 8 sent2(sent(FN,FV) ) --> fraseNom(FN,T), fraseVerbal(FV,T). fraseNom(fn(A,N),t(_,MF/SP,P))-->artigo(A,t(_,MF/SP,_)),nome(N,t(comum,MF/SP,P)). fraseNom(fn(A,N),t(_,MF/SP,P))-->artigo(A,t(_,MF/SP,def)),nome(N,t(propr,MF/SP,P)). fraseNom(fn(N), t(_, MF/SP,s3)) --> nome(N,t(C,MF/SP,_)), {C=propr; C=pronome}. fraseVerbal(fv(V,FN),T) --> verbo(V,T), fraseNom(FN,_). fraseVerbal(fv(V),T) --> verbo(V,T). %% nome(propr(X), t(propr, MF/SP,_)) --> [X],{tracos(X,t(propr, MF/SP,_)) }. 16.7. Semˆ antica para linguagem natural 9 10 11 12 13 14 15 nome(comum(X), t(comum, MF/SP,_)) --> [X],{tracos(X,t(comum, MF/SP,_)) nome( pron(X), t(pronome,MF/SP,_)) --> [X],{tracos(X,t(pronome,MF/SP,_)) verbo(verbo(X),t(_, MF/SP,P)) --> [X],{tracos(X,t(verbo, MF/SP,P)) artigo(art(X), t(_, MF/SP,P)) --> [X],{tracos(X,t(artigo, MF/SP,P)) %% do2(S,T,A):- CALL=..[S,A,T,R], CALL-> wOK(R,T); wErro(T). do2:-teste(T),do2(sent2,T,A),nl,write((arvor:A)),nl,fail. do2. 211 }. }. }. }. Abaixo, temos uma lista de testes para a gram´atica sent2/1. Num erro do tipo erro1, uma ´arvore parcial ´e gerada, por´em, num erro do tipo erro2, nada ´e gerado para a vari´avel da ´arvore sint´atica. ?-do2. ok : arvor : ok : arvor : erro1 : arvor : ok : arvor : erro2 : arvor : ok : arvor : erro1 : arvor : ... erro2 : arvor : yes [o,gato,dorme] sent(fn(art(o),comum(gato)),fv(verbo(dorme))) [o,gato,persegue,mikey] sent(fn(art(o),comum(gato)),fv(verbo(persegue),fn(propr(mikey)))) [o,gato,come,o,queijo,do,mikey] : sobrou : [do,mikey] sent(fn(art(o),comum(gato)),fv(verbo(come),fn(art(o),comum(queijo)))) [a,gata,come,o,queijo] sent(fn(art(a),comum(gata)),fv(verbo(come),fn(art(o),comum(queijo)))) [o,gatas,come,umas,queijo] _00074A42 [ela,persegue,o,rato] sent(fn(pron(ela)),fv(verbo(persegue),fn(art(o),comum(rato)))) [ele,persegue,um,mikey] : sobrou : [um,mikey] sent(fn(pron(ele)),fv(verbo(persegue))) [o,ele,come,o,rato] _00074A42 Exerc´ıcio 16.1 Assuma uma frase com dois participantes. Fa¸ca uma regra para gerar a forma passiva dada a forma na ativa. Por exemplo, dada a frase Ele persegue Mimi deve ser gerada a frase Mimi ´e perseguida por ele. 16.7 Semˆ antica para linguagem natural O n´ıvel semˆantico trabalha com o significado de uma frase. Podemos pensar numa aplica¸c˜ao que usa uma representa¸c˜ao l´ogica (ou pr´oxima de) para frases. Estamos falando de l´ogica dos predicados (ou de primeira ordem). O vocabul´ario da l´ogica dos predicados consiste em predicados, em quantificadores (existencial e universal) e em vari´aveis (ver cap´ıtulo 2). Seguem alguns exemplos de frases, cada uma com uma poss´ıvel representa¸c˜ao l´ogica: • Um c˜ao late. [existe(x), cao(x), [late(x)]] • Bidu persegue Mikey. [existe(x), x=bidu, [existe(y), y=mikey, persegue(x, y)]] 212 16. Processamento de Linguagem Natural com DCG • Bidu persegue todo gato. [existe(x), x=bidu, [todo(y), gato(y), persegue(x, y)]] • Todo gato persegue todo rato. [todo(x), gato(x), [todo(y), rato(y), persegue(x, y)]] • Todo rato come um queijo. [todo(x), rato(x), [existe(y), queijo(y), come(x, y)]] • Algum c˜ao late. [existe(x), cao(x), [late(x)]] Nesta aplica¸c˜ao, o estudo da semˆantica de linguagem natural consiste na tradu¸c˜ao de frases para f´ormulas l´ogicas. V´arias frases podem ter uma mesma representa¸c˜ao l´ogica, por exemplo, as frases /O c˜ao late /Um c˜ao late /Algum c˜ao late/ s˜ao traduzidas para [existe(x), cao(x), [late(x)]]. Abaixo, temos uma vers˜ao de uma gram´atica que descreve a tradu¸c˜ao de frases para formas l´ogicas, como exemplificado. Quando temos um nominal composto por um nome pr´oprio, por exemplo, Bidu, geramos [existe(x), x=bidu, [fv/x]]. Aqui, vf/x significa que temos uma frase verbal incompleta pela falta de um valor x. Na representa¸c˜ao de uma frase nominal, usamos o esquema FN/X/V, onde X ´e a vari´avel que faz a liga¸c˜ao entre a frase nominal e uma frase verbal (V). Dentro da frase nominal o V ocupa a u´ltima posi¸c˜ao da lista. Por exemplo, FN/X/V = [existe(X), cao(X), V]/X/V se temos a frase verbal V/X=[late(X)], juntando as duas temos [existe(X), cao(X), [late(X)]]. Um esquema similar de programa tamb´em ´e usado para tratar verbos transitivos, isto ´e, com dois argumentos. Na gram´atica sent3, o operador (=..) ´e usado para criar um termo parametrizado com uma vari´avel, por exemplo, cao(X)=..[cao,X]. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 sent3(FN) --> fraseNom3(FN/X/FV), fraseVerbal3(FV/X). fraseNom3([existe(X),X=N, V]/X/V ) --> artigo3(A), nome3(proprio(N)). fraseNom3([existe(X), NX, V]/X/V ) --> artigo3(A), nome3(comum(N)),{NX=..[N,X]}. fraseNom3([ todo(X), NX, V]/X/V )--> quant3(todo(X)), nome3(comum(N)),{NX=..[N,X]}. fraseNom3([ existe(X),NX, V]/X/V ) --> quant3(algum(X)), nome3(comum(N)),{NX=..[N,X]}. fraseNom3([existe(X),X=N, V]/X/V ) --> nome3(proprio(N)). fraseVerbal3(FN/X) --> verbo_dois3(V), fraseNom3(FN/Y/VXY), {VXY=..[V,X,Y]}. fraseVerbal3([VX]/X) --> verbo_um3(V),{VX=..[V,X]}. %% quant3(todo(X)) --> [todo]. quant3(todo(X)) --> [qualquer]. quant3(algum(X)) --> [algum]. nome3(proprio(N)) --> [N], {member(N, [bidu,mimi,mikey])}. nome3(comum(N)) --> [N], {member(N, [cao, gato, rato, queijo])}. verbo_dois3(V) --> [V], {member(V, [late, persegue, come])}. verbo_um3(V) --> [V], {member(V, [late])}. artigo3(art(A)) --> [A], {member(A, [a,o,um,uma])}. Segue uma base de testes para a gram´atica acima. Assumimos, neste exemplo, que as entradas s˜ao sintaticamente corretas. 16.7. Semˆ antica para linguagem natural 1 2 3 4 5 6 213 teste3([um, cao, late]). teste3([bidu, persegue, mikey]). teste3([bidu, persegue, todo, gato]). teste3([todo, gato, persegue, todo, rato]). teste3([todo,rato, come, um, queijo]). teste3([algum, cao, late]). Podemos testar uma senten¸ca isoladamente. Seguem os testes para duas senten¸cas. Nos sistemas Prolog, ´e usual mostrar as vari´aveis com nomes pouco leg´ıveis, como _G476 e _G529. ?- sent3(A, [todo,rato, come, um, queijo],[]). A = [todo(_G476), rato(_G476), [existe(_G529), queijo(_G529), come(_G476, _G529)]] Yes ?- sent3(A, [todo,rato, come, um, queijo],[]), limpa(A). A = [todo(x), rato(x), [existe(y), queijo(y), come(x, y)]] Yes Para as formas l´ogicas, fizemos um predicado limpa/1, que substitui cada vari´avel por uma constante, letras min´usculas (x,y,z...). Este predicado faz uso do predicado free_variables, que retorna todas as vari´aveis livres de um termo. Por exemplo: ?- free_variables(t(X,Y,Z),V). X = _G297, Y = _G298, Z = _G299 V = [_G297, _G298, _G299] Segue o c´odigo para o predicado limpa. O predicado escolhe_xyz seleciona uma constante para cada uma das vari´aveis livres. 1 2 3 4 limpa(A):-free_variables(A,F), escolhe_xyz(F,[x,y,z]). escolhe_xyz([X|Xs],XYZ):-select(X,XYZ,XYZ1),!,escolhe_xyz(Xs,XYZ1). escolhe_xyz([],_). %% A partir do predicado limpa, fizemos a vers˜ao do3a, que gera as formas l´ogicas, j´a limpas, como segue: ?-do3a. ok:[um, cao, late] forma:[existe(x), cao(x), [late(x)]] ok:[bidu, persegue, mikey] forma:[existe(x), x=bidu, [existe(y), y=mikey, persegue(x, y)]] ok:[bidu, persegue, todo, gato] forma:[existe(x), x=bidu, [todo(y), gato(y), persegue(x, y)]] ok:[todo, gato, persegue, todo, rato] forma:[todo(x), gato(x), [todo(y), rato(y), persegue(x, y)]] ok:[todo, rato, come, um, queijo] forma:[todo(x), rato(x), [existe(y), queijo(y), come(x, y)]] ok:[algum, cao, late] forma:[existe(x), cao(x), [late(x)]] Yes PLN compreende processamento em trˆes principais n´ıveis: L´exico, sint´atico e semˆantico. Usando os recursos do Prolog principalmente DCG ´e f´acil trabalhar nestes trˆes n´ıveis. CAP´ITULO 17 IA: Classifica¸c˜ ao KNN Em muitos cursos de Inteligˆencia Artificial (IA) os alunos apenas utilizam simuladores e/ou softwares de aprendizagem de m´aquina onde os algoritmos s˜ao caixas pretas. O objetivo deste e dos pr´oximos cap´ıtulos e desmistificar algumas destas caixas pretas mostrando o interior de alguns m´etodos de aprendizagem de m´aquina. A partir deste cap´ıtulo temos uma seq¨uˆencia de estudos de casos em IA. O objetivo ´e explorar a programa¸c˜ao de t´ecnicas das disciplinas de IA e Minera¸c˜ao de Dados. Ser˜ao programados os algoritmos de: 1) classifica¸c˜ao via KNN e Bayes; 2) classifica¸c˜ao via indu¸c˜ao de regras; 3)agrupamento (kmeans) e 4)ngramas para compara¸c˜ao. Nestes cap´ıtulos n˜ao apresentamos uma teoria para cada um destes m´etodos, o leitor deve procurar estud´a-los em livros especializados de IA ou de Minera¸c˜ao de Dados. Al´em de explorarmos as facilidades do Prolog para codificar as solu¸c˜oes em si, exploramos tamb´em trˆes formas alternativas de representar os dados de entrada para estes algoritmos: como fatos, como listas de instˆancias ou uma forma que combina estas duas. Ainda, nestes cap´ıtulos s˜ao explorados os diferentes tipos de dados utilizados em algoritmos de aprendizagem e minera¸c˜ao: dados discretos e dados cont´ınuos. S˜ao apresentadas diferentes m´etricas de distˆancia e similaridade para ambos os tipos de dados. Por fim, s˜ao apresentadas tamb´em m´etricas relacionadas com quantidade de informa¸c˜ao e entropia. 17.1 KNN: K vizinhos mais pr´ oximos O nome KNN vem do termo inglˆes K Nearest Neighbors que pode ser traduzido para K vizinhos mais pr´oximos. A id´eia do algoritmo ´e classificar uma determinada instˆancia (ou exemplo) a partir de uma base de instˆancias (exemplos) de treinamento. Assim, a entrada do algoritmo ´e um conjunto de instˆancias de treinamento e uma instˆancia de teste. A sa´ıda ´e a classifica¸c˜ao para a instˆancia de teste. 215 216 17.2 17. IA: Classifica¸c˜ ao KNN Base de dados Para se fazer m´ultiplos testes com o algoritmo, a entrada ´e uma base de exemplos, que ´e dividida em duas parti¸c˜oes, uma para treinamento e outra para testes. Uma forma de particionar a base ´e 2/3 treinamento e 1/3 para testes. A cada vez que se roda o algoritmo um dos exemplos dos testes ´e avaliado. Segue abaixo uma pequena base para ilustrar o funcionamento do algoritmo. Para cada instˆancia temos uma lista de pares atributo=valor e uma classifica¸c˜ao: approve ou reject (cr´edito aprovado ou rejeitado). Cada exemplo ´e enumerado com um identificador u´nico. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 %% ia-dados.pl /* data set 2/3 - 1/3 split */ /* training set */ example(1, approve, [emp=yes, buy=comp, sex=f, married=no]). example(2, reject, [emp=no, buy=comp, sex=f, married=yes]). example(3, approve, [emp=yes, buy=comp, sex=m, married=no]). example(4, approve, [emp=yes, buy=car, sex=f, married=yes]). example(6, approve, [emp=yes, buy=comp, sex=f, married=yes]). example(7, approve, [emp=yes, buy=comp, sex=f, married=no]). example(8, approve, [emp=yes, buy=comp, sex=m, married=no]). example(11, reject, [emp=no, buy=comp, sex=m, married=yes]). /* test set */ test(5, reject, [emp=yes, buy=car, sex=f, married=no]). test(9, approve, [emp=yes, buy=comp, sex=m, married=yes]). test(10, approve, [emp=yes, buy=comp, sex=m, married=yes]). test(12, reject, [emp=no, buy=car, sex=f, married=yes]). Um classificador KNN tem como objetivo inferir a classifica¸c˜ao de um dos exemplos de testes a partir da base de treinamento. Para um dado valor K e uma instˆancia teste, ele busca encontrar os K vizinhos mais similares `a instˆancia de teste; a classe inferida ´e a classe que mais ocorre entre os k vizinhos. Assim o knn/3 tem como parˆametros uma instˆancia e o valor de K, retornando a classe inferida. Para saber quem s˜ao os k vizinhos mais similares (neighbors) precisamos de um predicado que mede a distˆancia (dist) ou a similaridade; quanto maior a distˆancia menor ´e a similaridade. Para atributos discretos uma forma simples de calcular a distˆancia ´e contar o n´umero de atributos com valor diferente entre duas instˆancias. Seguem alguns testes para os predicados knn, dist e neighbors. ?- knn([emp=yes, buy=car, sex=f, married=no], 3,X). X = approve ?- neighbors([emp=yes, buy=car, sex=f, married=no], 3,X). X = [1-approve, 1-approve, 1-approve] ?- dist( [emp=yes, buy=car, sex=f], [emp=yes, buy=comp, sex=m],X). X = 2 A base de teste ´e para validar o resultado do KNN: saber em quantos testes ele acerta e em quantos ele erra: para K=3 o teste 9 acerta e o teste 5 falha, ver abaixo. ?- test(5,C,X),knn(X,3,C1). C = reject ... C1 = approve 17.3. O algoritmo KNN 217 ?- test(9,C,X),knn(X,3,C1). C = approve ... C1 = approve ?- test(9,_,X),neighbors(X,3,L). X = [emp=yes, buy=comp, sex=m, married=yes] L = [1-approve, 1-approve, 1-approve] ?- test(5,C,X),example(N,P,Y),dist(X,Y,D),write(N:[D-P]),nl,fail. 1:[1-approve] 2:[3-reject] 3:[2-approve] 4:[1-approve] 6:[2-approve] 7:[1-approve] 8:[2-approve] 11:[4-reject] Existem duas formas de inferir a classe a partir dos K vizinhos: 1) simplesmente pegar a classe mais freq¨uente (moda) ou 2)considerar tamb´em a distˆancia como um peso, pois a distˆancia varia de 0 a 4 (de todos iguais `a todos diferentes). Fizemos duas vers˜oes do KNN, numa delas a distˆancia ´e considerada: calcula-se o somat´orio do peso de cada classe 1/(1 + (Di )2 ), i : 1..K ; quanto maior a distˆancia menor ´e o peso. Para calcular a freq¨uˆencia de cada classe nos K vizinhos usamos o predicado selClass/4 que seleciona uma lista com os pares Dist-Classe. A freq¨uˆencia de cada classe ´e calculada pelo predicado sumClass que retorna uma lista de pares Soma-Classe; n˜ao confundi-los com os pares Dist-Classe retornados pelos outros predicados. Para o knn simples o sumClass apenas pega o tamanho da lista de cada classe, pois a distˆancia ´e ignorada. J´a para para o knnW com peso, usando o predicado maplist, aplicamos o peso para cada distˆancia e depois somamos os valores. Assim, o sumClassW devolve um valor ponderado pela distˆancia de cada instˆancia. Veja abaixo exemplos de execu¸c˜ao destes predicados. ?- maplist(funcw,[1,2,5,7],X),sumlist(X,S). X = [1/ (1+1*1), 1/ (1+2*2), 1/ (1+5*5), 1/ (1+7*7)] S = 0.758462 ?- sumClass([1-approve, 2-approve, 2-approve, 3-reject, 4-reject],S). S = [3-approve, 2-reject] ?- selClass(approve,[2-approve, 2-approve, 1-reject, 4-reject],S,Lo). S = [2-approve, 2-approve] Lo = [1-reject, 4-reject] ?- test(5,C,X),neighbors(X,6,L),sumClassW(L,S). C = reject X = ... L = [1-approve, 1-approve, 1-approve, 2-approve, 2-approve, 2-approve] S = [2.1-approve] ?- sumClassW([1-approve, 2-approve, 2-approve, 3-reject, 4-reject],S). S = [0.9-approve, 0.158824-reject] 17.3 O algoritmo KNN Segue abaixo o programa principal. Os predicados knn e knnw foram comentados acima. O programa em si ´e pequeno, aproximadamente 30 linhas, mostrando que o Prolog ´e uma linguagem compacta e expressiva. Para rodar o programa ´e necess´ario carregar tamb´em o arquivo de dados (ia-dados.pl). 218 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 17. IA: Classifica¸c˜ ao KNN %% ia-knn.pl %% Vers~ ao adaptada do original de Zdravko Markov :- [ia-dados.pl]. knn(Instance,K,Class) :neighbors(Instance,K,Neighbors), sumClass(Neighbors,Sum),max(Sum,_-Class). knnW(Instance,K,Class) :neighbors(Instance,K,Neighbors), sumClassW(Neighbors,Sum), max(Sum,_-Class). neighbors(Instance,K,Neighbors) :findall(D-C,(example(_,C,E),dist(Instance,E,D)),Ds), keysort(Ds,L), first(K,L,Neighbors). %% dist([],[],0). %% nro de A=V diferentes dist([X|Xs],[X|Ys],N) :- !,dist(Xs,Ys,N). dist([_|Xs],[_|Ys],N) :dist(Xs,Ys,M), N is M+1. sumClass([],[]). sumClass([N-C|Ls],[S-C|R]) :- sumOneClass(C,[N-C|Ls],Lo,S), sumClass(Lo,R). sumOneClass(C,Li,Lo,S):-selClass(C,Li,Co,Lo),zipper(Co,Ns,Cs),length(Ns,S). selClass(X,L,[No-X|Co],Lo) :-select(No-X,L,L1),selClass(X,L1,Co,Lo). selClass(X,L,[],L). sumClassW([],[]). sumClassW([N-C|Ls],[S-C|R]) :- sumOneClassW(C,[N-C|Ls],Lo,S), sumClassW(Lo,R). sumOneClassW(C,Li,Lo,S):-selClass(C,Li,Co,Lo),zipper(Co,Ns,Cs), maplist(funcw,Ns,Nsw),sumlist(Nsw,S). funcw(X, 1/(1+X*X) ). %% zipper([(X-Y)|XYs],[X|Xs],[Y|Ys]):-!,zipper(XYs,Xs,Ys). zipper([],[],[]). max(L,M):-msort(L,Lo),last(Lo,M). first(K,L,KL):-length(KL,K),append(KL,_,L). A partir deste c´odigo podem-se fazer v´arios projetos interessantes, alguns est˜ao nos exerc´ıcios que seguem. Exerc´ıcio 17.1 Adaptar o algoritmo para trabalhar com dados discretos e cont´ınuos usando m´etricas de distˆancia para dados cont´ınuos, as quais s˜ao apresentadas nos pr´oximos cap´ıtulos. Exerc´ıcio 17.2 Ler um arquivo de testes do software para minera¸c˜ao de dados do Weka[18] e process´a-lo gerando as mesmas sa´ıdas que o Weka. Use o formato do Weka: ARFF. Exerc´ıcio 17.3 Dada uma base de testes, permitir a sele¸c˜ao autom´atica do melhor K para uma faixa de valores. Ele deve fazer uma avalia¸c˜ao sistem´atica do seu treinamento. Exerc´ıcio 17.4 Na sele¸c˜ao autom´atica do melhor K, implementar o m´etodo de testes N-fold crossvalidation descrito abaixo. O N ´e um parˆametro. N-fold Cross Validation: divida os dados em N parti¸c˜oes; rode N itera¸c˜oes de treinamenos+testes; cada itera¸c˜ao usa N-1 parti¸c˜oes para treinamento e uma para teste. A performance do classificador ´e medida pela m´edia dos resultados das N itera¸c˜oes. Um caso especial deste m´etodo ´e chamado de Leave-one-out cross-validation: divide um conjunto com M dados em M parti¸c˜oes. CAP´ITULO 18 IA: Agrega¸c˜ ao Kmeans Iniciamos apresentando uma biblioteca de fun¸c˜oes utilit´arias; depois falamos sobre como criar uma popula¸c˜ao para testes e por fim mostramos o algoritmo de agrupamento kmeans. 18.1 Medidas de similaridade e distˆ ancia Neste cap´ıtulo vamos trabalhar com dados do tipo cont´ınuo. Para trabalhar com estes dados usam-se fun¸c˜oes da ´area de estat´ıstica, tais como m´edia, desvio padr˜ao, correla¸c˜ao, etc. Al´em disso, usa-se outras que s˜ao da matem´atica, tais como coseno entre dois ˆangulos num espa¸co vetorial de dimens˜ao N. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 %% ia-similar.pl sum([X|Xs],S):-sum(Xs,Sx),S is Sx+X. sum([],0). medv(V,M):-sum(V,S),length(V,L),M is S/L. sumDifXY([X|Xs],[Y|Ys], S):- sumDifXY(Xs,Ys, Ss), S is abs(X-Y)+Ss. sumDifXY([],[],0). prodX([X|Xs], S):- prodX(Xs, Ss), S is (X*X)+Ss. prodX([],0). prodXY([X|Xs],[Y|Ys], S):- prodXY(Xs,Ys, Ss), S is (X*Y)+Ss. prodXY([],[],0). prodDifXY([X|Xs],[Y|Ys], S):- prodDifXY(Xs,Ys, Ss), S is (X-Y)*(X-Y)+Ss. prodDifXY([],[],0). prodDifMXY([X|Xs],[Y|Ys],Mx,My,S):prodDifMXY(Xs,Ys,Mx,My, Ss), S is (X-Mx)*(Y-My)+Ss. prodDifMXY([],[],_,_,0). prodDifMX([X|Xs],Mx, S):- prodDifMX(Xs,Mx, Ss), S is (X-Mx)*(X-Mx)+Ss. prodDifMX([],_,0). prodMinkXY([X|Xs],[Y|Ys],P, S):- prodMinkXY(Xs,Ys,P, Ss), S is abs(X-Y)^P+Ss. prodMinkXY([],[],P,0). cut0([X|Xs],[Y|Ys], Xo,Yo):- 219 220 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 18. IA: Agrega¸c˜ ao Kmeans (X\==0, Y\==0,!,Xo=[X|Xso],Yo=[Y|Yso];Xo=Xso,Yo=Yso),cut0(Xs,Ys,Xso,Yso). cut0([],[],[],[]). %%--------------------------------------------------%% estatistica var(X,V):- medv(X,Mx),prodDifMX(X,Mx,Sx),length(X,N),V is Sx/N. std(X,D):-var(X,V),D is sqrt(V). covar(X,Y,V):- medv(X,Mx),medv(Y,My),prodDifMXY(X,Y,Mx,My,Sxy), length(X,N),V is Sxy/(N-1). covar2(X,Y,V):- medv(X,Mx),medv(Y,My),prodXY(X,Y,Sxy), length(X,N),V is (Sxy/N)-(Mx*My). %% regress~ ao beta(X,Y,Mx,My,B):- prodDifMXY(X,Y,Mx,My,Sxy),prodDifMX(X,Mx,Sx),B is Sxy/Sx. alfa(X,Y,Mx,My,A):- beta(X,Y,Mx,My,B), A is My - B*Mx. regress(X,Y,A,B):- medv(X,Mx),medv(Y,My),beta(X,Y,Mx,My,B),alfa(X,Y,Mx,My,A). %%--------------------------------------------------%% dist^ ancia & similaridade distEu(X,Y,D):- prodDifXY(X,Y,P), D is sqrt(P). distMink(X,Y,D,P):-prodMinkXY(X,Y,P,DP),D is DP^(1/P). coseno(X,Y,P):- prodXY(X,Y,Sxy),prodX(X,Sx),prodX(Y,Sy), P is Sxy/(sqrt(Sx)*sqrt(Sy)). pearsMed(X,Y,Mx,My,P):- prodDifMXY(X,Y,Mx,My,Sxy),sumDifX(X,Mx,Sx), prodDifMX(Y,My,Sy),P is Sxy/(sqrt(Sx)*sqrt(Sy)). pearson(X,Y,C):-length(X,N),sum(X,Sx), sum(Y,Sy),prodXY(X,Y,Sxy), prodX(X,Sxx),prodX(Y,Syy), C is (N*Sxy-Sx*Sy)/(sqrt(N*Sxx-Sx*Sx)*sqrt(N*Syy-Sy*Sy)). pearson0(X,Y,P):- cut0(X,Y,X0,Y0),pearson(X0,Y0,P). coseno0(X,Y,P):- cut0(X,Y,X0,Y0),pearson(X0,Y0,P). d1Mink(X,Y,P):- distMink(X,Y,P,1). d2Mink(X,Y,P):- distMink(X,Y,P,2). d3Mink(X,Y,P):- distMink(X,Y,P,3). zipper([(X,Y)|XYs],[X|Xs],[Y|Ys]):-!,zipper(XYs,Xs,Ys). zipper([(X-Y)|XYs],[X|Xs],[Y|Ys]):-!,zipper(XYs,Xs,Ys). zipper([],[],[]). %%--------------------------------------------------%% base de testes v1([1,0,6, 4,3,1, 2,0,0,2]). v2([1,5,6, 3,2,1, 2,1,3,0]). %vet(Med,NM, [ABC, DEF GHIJ]) vet(_,luis, [1,0,0, 2,1,7, 0,0,2,3]). vet(_,edu, [5,1,2, 2,1,7, 1,0,6,5]). vet(_,mari, [1,5,6, 4,3,1, 2,0,0,2]). vet(_,mara, [4,2,2, 0,0,6, 1,6,0,6]). vet(_,lau, [6,5,4, 1,2,0, 0,5,0,3]). % cos(X,Y,C):- vet(_,X,Vx),vet(_,Y,Vy),coseno(Vx,Vy,C). dds(D):-member(D,[d1Mink, d2Mink, d3Mink, distEu, coseno, pearson]). %% compara todos do(D,Y):- bagof(X,X^V^vet(_,X,V),CAB),tab(10),writeln(CAB), bagof((V,X),(X^C^Vx^Vy^(vet(_,X,Vx),vet(_,Y,Vy), C=..[D,Vx,Vy,V],C)),M),write((D,Y:’ ’)),wl(M). wl(M):-zipper(M,M1,M2),wl0(M1). 18.1. Medidas de similaridade e distˆ ancia 72 73 221 wl0([X|Xs]):-format(’~2f|’,X),wl0(Xs). wl0([]):-nl. O c´odigo acima inicia com v´arias fun¸c˜oes do tipo somat´orio que s˜ao auxiliares para codificar as fun¸c˜oes estat´ısticas, como a variˆancia, o desvio padr˜ao, a correla¸c˜ao, etc. O leitor pode testar cada uma delas isoladamente, passando um ou dois vetores conforme for o caso. Abaixo mostramos a execu¸c˜ao de alguns predicados estat´ısticos. ????- var([40,56,38, 38,63,59, 52,49,46],V). std([40,56,38, 38,63,59, 52,49,46],D). covar([1,2,3,4,5,6],[6,5,4,3,2,1],V). covar2([1,2,3,4,5,6],[6,5,4,3,2,1],V). V = 76.2222 D= 8.73053 V = -3.5 V = -2.91667 Temos tamb´em a fun¸c˜ao de regress˜ao linear simples. Basicamente codifica-se as f´ormulas: Y=a+bX, a=my-b(mx) e b=sum((x-mx) *(Y-my)) / sum((x-mx) *(x-mx)). Onde sum ´e somat´orio, mx e my s˜ao as medias dos vetores X e Y. Segue abaixo um exemplo de teste, onde s˜ao retornados os valores A e B com os quais podemos montar a equa¸c˜ao: Y = 23.209 + 3.53748*X. ?- regress([3,8,9, 13,3,6, 11,21,1,16], [30,57,64, 72,36,43, 59,90,20,83],A,B). A = 23.209, B = 3.53748 Ainda temos duas medidas de similaridade: correla¸c˜ao e coseno. A correla¸c˜ ao de Person (ou s´o correla¸c˜ao) entre dois vetores retorna um valor entre 0 e 1. Se for 1, eles est˜ao fortemente correlacionados, isto ´e, os valores de um vetor podem predizer os valores do outro. Se for 0, n˜ao existe correla¸c˜ao. E se for -1, existe uma correla¸c˜ao inversamente proporcional. O coseno ´e similar `a correla¸c˜ao devolvendo valores entre 0 e 1. Ele mede o ˆangulo entre dois vetores num espa¸co vetorial. Quanto mais pr´oximo de 1 for o valor, mais similares s˜ao os dois vetores. Ao comparar dois vetores com a correla¸c˜ao ´e bom excluir os itens com zeros em um dos vetores, pois os zeros afetam bastante a correla¸c˜ao. Para isso, usa-se o predicado cut0/3. Diferente da correla¸c˜ao, o coseno n˜ao ´e t˜ao sens´ıvel `a presen¸ca de zeros. Depois, temos as medidas de distˆancia. Quanto menor `a distˆancia mais similares s˜ao dois objetos. As medidas de distˆancia num espa¸co de dimens˜ao N, podem ser generalizadas pela medida de Minkowski, onde um parˆametro ´e o valor da potˆencia; com potˆencia de dois corresponde `a distˆancia Euclidiana. Seguem alguns testes para estas medidas de similaridade e distˆancia. Os dois u´ltimos testes comparam coseno e pearson com e sem os zeros. ???????- pearson([1,2,3],[3,2,1],X). X = -1.0 pearson([1,2,3],[1,2,3],X). X = 1.0 coseno([1,2,3],[1,2,3],X). X = 1.0 coseno([1,2,3],[3,2,1],X). X = 0.714286 d2Mink([1,2,3],[1,2,3],X). X=0.0 v1(X),v2(Y),d2Mink(X,Y,P). P = 6.40312 v1(X),v2(Y),cut0(X,Y,Xo,Yo),coseno(X,Y,P),coseno(Xo,Yo,Po),write(P:Po),nl. 0.750587 : 0.988399 ?- v1(X),v2(Y),cut0(X,Y,Xo,Yo),pearson(X,Y,P),pearson(Xo,Yo,Po),write(P:Po),nl. 0.42823 : 0.963952 222 18. IA: Agrega¸c˜ ao Kmeans No final do programa ia-similar.pl existe uma pequena tabela de dados de clientes. Cada cliente possui um vetor de atributos. Podemos compar´a-los todos com todos, como mostrado abaixo. ?- dds(M), do(M,luis). [luis, edu, mari, mara, lau] d1Mink, luis: 0.00|14.00|26.00|23.00|30.00| ... distEu, luis: 0.00|6.48|10.68|8.54|12.08| coseno, luis: 1.00|0.86|0.31|0.67|0.21| pearson, luis: 1.00|0.78|-0.33|0.41|-0.50| ... 18.2 Criando uma popula¸c˜ ao Antes de apresentarmos o m´etodo de agrupamento (clustering) kmeans vamos mostrar como criar uma popula¸c˜ao, isto ´e, um conjunto de fatos relativos a pessoas, fazendo uso de predicados j´a apresentados aqui e no cap´ıtulo sobre programa¸c˜ao aritm´etica. Pensamos em minerar um grupo de indiv´ıduos do sexo masculino ou feminino. Inicialmente teremos apenas trˆes dados para cada indiv´ıduo: sexo, peso e altura. Segue abaixo uma tabela com dados estat´ısticos sobre peso e altura de homens e mulheres. Para testar um algoritmo de cluster vamos criar uma popula¸c˜ao fict´ıcia baseada nesta tabela de peso e altura. Temos trˆes colunas: altura em cent´ımetros, peso (min-max) para homem e peso (min-max) para mulher. A menor altura ´e 147 e a maior ´e 190. Dentro desta faixa, a tabela tem valor zero na coluna altura para homens com altura menor que 155 e tamb´em para mulheres com altura maior que 180. Estes campos tem valor zero pois estatisticamente as ocorrˆencias s˜ao poucas. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 %% ia-pop.pl %% gerar uma popula¸ c~ ao :- [stat]. %% cap prog aritm´ etica peso(147, 0, 45-59). peso(150, 0, 45-60). peso(152, 0, 46-62). peso(155, 55-66, 47-63). peso(157, 56-67, 49-65). peso(160, 57-68, 50-67). peso(162, 58-70, 51-69). peso(165, 59-72, 53-70). peso(167, 60-74, 54-72). peso(170, 61-75, 55-74). peso(172, 62-77, 57-75). peso(175, 63-79, 58-77). peso(177, 64-81, 60-78). peso(180, 65-83, 61-80). peso(182, 66-85, 0). peso(185, 68-87, 0). peso(187, 69-89, 0). peso(190, 71-91, 0). hHomem(Xs,N):-findall(X,(between(1,N,_),X is normal(172,11)),Xs). 18.2. Criando uma popula¸c˜ ao 22 23 24 25 26 27 28 29 30 31 32 33 34 35 223 hMulher(Xs,N):-findall(X,(between(1,N,_),X is normal(163,10)),Xs). popn(POP,N):- pop(P), length(POP,N),append(POP,_,P). pop(P):-hHomem(H,1000),hMulher(M,1000), criaPar(h,H,HP),criaPar(m,M,MP),append(HP,MP,P). criaPar(SX,[X|Xs],[Y|Ys]):- Y=(X-P)-SX,criaPeso(SX,X,P),criaPar(SX,Xs,Ys). criaPar(_,[],[]). ajusta(h,X,155):-X190. ajusta(m,X,147):-X190. criaPeso(SX,X,P):-ajusta(SX,X,Xo),criaPeso0(SX,Xo,P),!;criaPeso0(SX,X,P). criaPeso0(h,X,P):-peso(X,N-M,_),P is 1+N+random(M-N),!. criaPeso0(m,X,P):-peso(X,_,N-M),P is 1+N+random(M-N),!. criaPeso0(SX,X,P):- X1 is X-1, criaPeso0(SX,X1,P). O problema inicial ´e: a partir das informa¸c˜oes desta tabela gerar uma popula¸c˜ao de 1000 individuos (ou mais), com dados mais ou menos reais de peso e altura. Assumimos que a altura das pessoas segue uma distribui¸c˜ao normal e usando a fun¸c˜ao normal, apresentada no cap´ıtulo sobre programa¸c˜ao aritm´etica, geramos uma popula¸c˜ao de 1000 indiv´ıduos. Inicialmente calculamos a m´edia e o desvio padr˜ao da altura, como mostrado abaixo. Com estes valores de m´edias e de desvios podemos gerar randomicamente quantos indiv´ıduos quisermos, para cada sexo, como exemplificado abaixo. ?- bagof(A,(H^M^peso(A,H,M),H\=0),L),medv(L,Med),std(L,Std). Med = 172.267 Std = 10.8041 ?- bagof(A,(H^M^peso(A,H,M),M\=0),L),medv(L,Med),std(L,Std). Med = 163.5 Std = 10.1119 ?- findall(X,(between(1,20,_),X is normal(163,10)),L0). L0 = [172, 159, 156, 168, 175, 155, 167, 171, 150|...] ?- criaPeso(h,176,P). P = 70 ?- criaPeso(m,176,P). P = 66 ?- popn(P,5). P = [169-62-h, 166-67-h, 191-72-h, 169-68-h, 172-65-h] Ainda, usando a tabela de pesos e alturas, dada uma altura e o sexo podemos inferir um peso. Como a tabela tem um valor m´ınimo e m´aximo de peso, usamos a fun¸c˜ao random para chutar um valor entre o m´ınimo e o m´aximo. O predicado criaPeso codifica esta funcionalidade. Ele trata tamb´em os valores para os homens e as mulheres que est˜ao fora da faixa; se a altura for menor que o m´ınimo da tabela ´e atribu´ıdo o valor m´ınimo de peso; se for maior que o m´aximo da tabela, ´e atribu´ıdo o valor m´aximo do peso; por fim, para uma altura dentro da faixa, mas n˜ao cadastrada, e.g., 161, ´e atribu´ıdo o valor do peso do individuo menor mais pr´oximo, 160. O predicado criaPar gera uma lista de triplas altura-peso-sexo, a partir de uma lista de alturas associada a um dado sexo (h/m). O predicado pop gera uma popula¸c˜ao inicial de 1000 indiv´ıduos. E o predicado popn permite selecionar um grupo com qualquer n´umero de indiv´ıduos, pois quando estamos testando o programa KNN pelas primeiras vezes ´e bom trabalhar com um n´umero m´ınimo de indiv´ıduos (tipo 5), facilitando o trace do programa. A medida que o programa se torna est´avel vamos aumentando o grupo de testes at´e testarmos com a popula¸c˜ao toda. Exerc´ıcio 18.1 Como vemos o predicado popn/2, para valores menores que 500, retorna s´o homens pois foram criadas duas listas, uma com 500 homens e outra com 500 mulheres, que 224 18. IA: Agrega¸c˜ ao Kmeans foram concatenadas com append. Modifique o programa com um predicado que intercala um a um, os homens e as mulheres. Exerc´ıcio 18.2 Utilizando o predicado de regress˜ao linear simples e os dados da tabela, crie as fun¸c˜oes pesoMin, pesoMax para homens e para mulheres. Permitindo calcular os pesos para qualquer valor positivo de altura. Exerc´ıcio 18.3 Incorpore as fun¸c˜oes pesoMin e pesoMax no c´odigo ia-pop.pl. 18.3 Kmeans: Agrupamento O m´etodo kmeans ´e um m´etodo de agrupamento (clustering) bastante difundido. Espera-se que o c´odigo abaixo sirva de base para o desenvolvimento de projetos de programa¸c˜ao interessantes, sobre as in´umeras varia¸c˜oes do kmeans. Esta vers˜ao trabalha apenas com dois atributos (peso e altura) para cada indiv´ıduo, por´em o m´etodo funciona para um n´umero qualquer de atributos. Seja uma popula¸c˜ao de tamanho N e seja um valor K. O kmeans cria K agrupamentos para a popula¸c˜ao. Ele ´e baseado em uma m´etrica de similaridade (ou de distˆancia). Cada agrupamento ´e feito em torno de um indiv´ıduo (ou dos atributos dele) chamado centro (ou centr´oide), com os indiv´ıduos mais similares. Esta vers˜ao do algoritmo kmeans segue as etapas: • (1) inicializa¸c˜ ao: gera-se K valores randˆomicos (entre 1 e N) para selecionar K indiv´ıduos iniciais, que s˜ao os centros dos K grupos; • (2) se houver um centro repetido volta-se `a etapa 1; sen˜ao inicia-se o passo que gera os agrupamentos, tendo como entrada a popula¸c˜ao e os K centros; • (3) agrupamentos: para cada um dos N indiv´ıduos calcula-se `a distˆancia contra os K centros; escolhe-se como grupo o de menor distˆancia; no final desta etapa temos K grupos de indiv´ıduos; • (4) calcula-se a m´edia dos valores dos indiv´ıduos de cada um dos K grupos; para cada atributo calcula-se uma m´edia; seleciona-se K novos centros a partir dos valores das m´edias; • (5) testa-se o fim: compara-se os novos centros com os anteriores, se s˜ao diferentes retorna-se a etapa 3; sen˜ao termina-se o processo, mostrando a m´edia e o desvio padr˜ao da distˆancia entre o centro e os elementos de cada grupo. Segue abaixo a execu¸c˜ao do kmeans para agrupar 50 indiv´ıduos em 3 grupos. Foram necess´arias 4 itera¸c˜oes. No final temos, para cada grupo, a m´edia e o desvio padr˜ao das distˆancias dos elementos ao seu centro. Se rodarmos o programa novamente outros resultado ser˜ao produzidos pois os valores iniciais dos grupos s˜ao diferentes. As m´edias e desvios mostram a qualidade de cada grupo. Normalmente o kmeans converge r´apido, mas para grandes popula¸c˜oes o n´umero de itera¸c˜oes ´e bem maior. Al´em disso, na pr´atica os m´etodos de minera¸c˜ao exploram outros aspectos do processo, por exemplo, para descobrir qual ´e o melhor valor para K; ou eliminar dados identificados como desvios ou excepcionais, melhorando assim a coes˜ao do grupo. 18.3. Kmeans: Agrupamento 225 ?- popn(P,50),kmeans(P,3). Centros iniciais:[146-58, 168-61, 178-81]:[27, 39, 8] ---Passo:1: --cluster:[28*1, 29*1, 31*1] cluster:[3*2, 4*2, 5*2, 6*2, 7*2, 10*2, 12*2, ... 7*2, 49*2, 50*2] cluster:[1*3, 2*3, 8*3, 9*3, 11*3, 13*3, 15*3, ... 43*3, 44*3, 48*3] Novos Centros:[146-59, 167-64, 182-78] ---Passo:2: --cluster:[28*1, 29*1, 31*1] cluster:[3*2, 4*2, 5*2, 6*2, 7*2, ... 45*2, 46*2, 47*2, 49*2, 50*2] cluster:[1*3, 2*3, 8*3, 9*3, 11*3, ... 43*3, 44*3, 48*3] Novos Centros:[146-59, 169-65, 182-78] ---Passo:3: --cluster:[28*1, 29*1, 31*1, 46*1] cluster:[3*2, 4*2, 5*2, 6*2, 7*2, ... 42*2, 45*2, 47*2, 49*2, 50*2] cluster:[1*3, 2*3, 9*3, 11*3, 13*3, ... 41*3, 43*3, 44*3, 48*3] Novos Centros:[156-59, 169-65, 182-78] ---Passo:4: --cluster:[19*1, 21*1, 28*1, 29*1, 31*1, 46*1] cluster:[3*2, 4*2, 5*2, 6*2, 7*2, 8*2, ... 47*2, 49*2, 50*2] cluster:[1*3, 2*3, 9*3, 11*3, 13*3, 15*3, ... 41*3, 43*3, 44*3, 48*3] Novos Centros:[156-59, 169-65, 182-78] Fim no Passo:4 [156-59, 169-65, 182-78] Qualidade:[cluster:1:3.28153:1.76254, cluster:2:4.11917:1.65603, cluster:3:5.2229:2.33628] O c´odigo ´e fortemente baseado no predicado findall(_,between(1,LN,I),..). A popula¸c˜ao ´e uma lista POP de comprimento LN; este comando de controle permite percorrer a lista e fazer algum tipo de processamento para cada indiv´ıduo. Uma estrutura paralela `a lista de indiv´ıduos ´e a lista dos agrupamentos chamada de CLU; nesta, 10*3 denota que o individuo 10 est´a no agrupamento 3. Assim, o mesmo comando de controle serve para percorrer tamb´em os agrupamentos. Associado ao findall temos o predicado nth1(I,POP,IND); neste caso, estamos acessando o I´esimo INDiv´ıduo da POPula¸c˜ao. De forma similar, com findall(_,(between(1,K,I),..) estamos percorrendo a lista dos CENtros; com nth1(I,CEN,C) estamos acessando o centro C de ´ındice I. O predicado kmeansSTEP tem duas vers˜oes de centros: CEN s˜ao os centros de entrada e CENo s˜ao os novos centros, criados na corrente etapa. Se eles s˜ao iguais ent˜ao o processo termina. 1 2 3 4 5 6 7 8 9 10 11 %% ia-kmeans.pl %% Cluster Kmeans wCluster(C/LN/K):- findall(K, (I^between(1,K,I), wCluster(C/LN,I)),_). wCluster(C/LN,K):- findall(I*K,(I^between(1,LN,I), nth1(I,C,I*K)),CLU), writeln(cluster:CLU),!. kmeans(Pi,K):length(Pi,LN), zipper(Pi,POP,_), findall(XY,(between(1,K,_),R is random(LN),nth0(R,POP,XY)),CEN), (dupl(CEN)->kmeans(Pi,K); writeln(’Centros iniciais’:CEN:Ci), kmeansSTEP(1,POP/LN,CEN/K)). kmeansSTEP(Pas,POP/LN,CEN/K):- 226 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 18. IA: Agrega¸c˜ ao Kmeans writeln(’---Passo’:Pas:’---’), findall(I*C,(between(1,LN,I), nth1(I,POP,IND),getIdvCLU(IND,CEN/K,C)),CLU), wCluster(CLU/LN/K), findall(Ck,(Ki^between(1,K,Ki),getCENm(POP/LN, Ki,CLU,Med), getCENi(POP/LN, Med,Ck)),CENo), writeln((’Novos Centros’:CENo)), (CEN=CENo->writeln(’Fim no Passo’:Pas),writeln(CEN), getCENms(POP/LN, CEN/K,CLU,LMS),writeln(’Qualidade’:LMS) ;Pas1 is Pas+1,kmeansSTEP(Pas1,POP/LN,CENo/K)). getCENm(POP/LN, K,CLU,Meo):findall(IND,(between(1,LN,I), nth1(I,CLU,I*K),nth1(I,POP,IND)),INDs), zipper(INDs,H,P),medv(H,Malt),medv(P,Mpeso),Meo=Malt-Mpeso,!. getCENi(POP/LN, Med,Ci):findall(D,(between(1,LN,I),nth1(I,POP,IND),dist0(Med,IND,D)),Ds), minL(Ds,Min),nth1(Io,Ds,Min), nth1(Io,POP,Ci),!. getIdvCLU(IND,CEN/K,CLU):findall(D,(between(1,K,I), nth1(I,CEN,CEi),dist0(CEi,IND,D)),Ds), minL(Ds,Min),nth1(CLU,Ds,Min),!. %% Avalia a qualidade getCENms(POP/LN, CEN/K,CLU,LMS):findall((cluster:I:Meo:Std),(between(1,K,I), getCENms0(POP/LN, CEN/I,CLU,Meo,Std)),LMS). getCENms0(POP/LN, CEN/K,CLU,Meo,Std):nth1(K,CEN,CEi), findall(D,(between(1,LN,I), nth1(I,CLU,I*K),nth1(I,POP,IND),dist0(CEi,IND,D)),Ds), medv(Ds,Meo), std(Ds,Std),!. dist0(X-Y,X1-Y1,D):-distEu([X/2,Y],[X1/2,Y1],D). %% normalizar X/2 minL([L|Ls],M):-minL(Ls,L,M). minL([L|Ls],ACC,M):- (ACCminL(Ls,ACC,M);minL(Ls,L,M)). minL([],M,M). dupl([X|Xs]):-member(X,Xs);dupl(Xs). Os predicados do kmeans n˜ao s˜ao facilmente testados de forma isolada, pois ´e trabalhoso criar para eles os dados de entrada. O melhor m´etodo para depurar um c´odigo deste tipo ´e iniciar uma popula¸c˜ao m´ınima, pode ser 3 indiv´ıduos e um cluster; faz-se um trace passo a passo do programa, vendo o que entra e o que sai para identificar os poss´ıveis erros. No predicado kmeans(Pi,K) entra uma popula¸c˜ao e um valor K inteiro. Com o predicado zipper jogamos fora o atributo sexo ficando apenas o peso e a altura. Depois, se geram K valores randˆomicos para selecionar os K indiv´ıduos que s˜ao os K centros iniciais. No predicado kmeansSTEP(Pas,POP/LN,CEN/K) entra o n´umero da itera¸c˜ao (Passo), a popula¸c˜ao POP/LN e os centros CEN/K; LN e K representam respectivamente o tamanho da popula¸c˜ao e o n´umero de grupos. O predicado getCENm(POP/LN, K,CLU,Meo) recupera, em Meo, as duas m´edias dos atributos para o grupo K. Ele precisa percorrer o CLU e pegar os valores reais na popula¸c˜ao. O predicado getCENi(POP/LN, Med,Ci) retorna o indiv´ıduo mais pr´oximo das m´edias de um grupo. O predicado getCENms(POP/LN, CEN/K,CLU,LMS) retorna uma lista com a m´edia e o desvio padr˜ao de cada cluster; ele chama o getCENms0(POP/LN, CEN/K,CLU,Meo,Std) que retorna a m´edia e o desvio de um cluster. 18.3. Kmeans: Agrupamento 227 O predicado dist0(X-Y,X1-Y1,D) chama o predicado que calcula a distˆancia euclidiana; ele passa os valores da altura normalizados, isto ´e, altura dividida por 2. Neste ponto, pode-se substituir a fun¸c˜ao que calcula a distˆancia por uma outra, como as mostradas anteriormente. A partir deste c´odigo podem ser feitos v´arios projetos novos, tais como, os dos exerc´ıcios que seguem. Exerc´ıcio 18.4 Ler um arquivo de entrada com os dados a serem agrupados; gerar num arquivo os agrupamentos. Exerc´ıcio 18.5 Gerar uma popula¸c˜ao e armazen´a-la num fato; depois para um K de 2 at´e 10 rodar o kmeans salvando os cluster e as avalia¸c˜oes; por fim, escolher qual ´e o melhor K. Exerc´ıcio 18.6 Generalizar: a)permitindo definir a m´etrica de similaridade (distˆancia) num parˆametro; b) permitir dados discretos e cont´ınuos; c)trabalhar com N atributos para cada indiv´ıduo. Exerc´ıcio 18.7 Tratar automaticamente da normaliza¸c˜ao dos atributos. CAP´ITULO 19 IA: Classifica¸c˜ ao Naive Bayes O tema Naive Bayes mostra como fazer inferˆencias utilizando probabilidades condicionais entre eventos. Antes de apresentar o algoritmo vamos mostrar como representar os dados como fatos a partir de listas de valores. 19.1 Os conjuntos de dados Abaixo temos o programa que codifica a forma de tratar os dados. Ele inicia com dois conjuntos de dados, descritos por uma linha de cabe¸calho que define o nome de cada coluna e depois por N linhas de dados. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 %% ia-mkdata.pl %% DATA SETS pre_test_data(10,[ [outlook, temp, humidity, wind, playTennis], [sunny, hot, high,weak, no], [sunny, hot, high,strong, no], [overcast,hot, high,weak, yes], [rain, mild, high,weak, yes], [rain, cool, nml,weak, yes], [rain, cool, nml,strong, no], [overcast,cool,nml,strong, yes], [sunny, mild, high,weak, no], [sunny, cool, nml,weak, yes], [rain, mild, nml,weak, yes], [sunny, mild, nml,strong, yes], [overcast,mild,high,strong, yes], [overcast,hot, nml,weak, yes], [rain, mild, high,strong, no]]). %% 229 230 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 19. IA: Classifica¸c˜ ao Naive Bayes pre_test_data(12,[ [age, income ,student ,credit_rating ,buys_computer], [30, high ,no ,fair ,no], [30, high ,no ,excellent ,no], [35, high ,no ,fair ,yes], [40, medium ,no ,fair ,yes], [40, low ,yes ,fair ,yes], [40, low ,yes ,excellent ,no], [35, low ,yes ,excellent ,yes], [30, medium ,no ,fair ,no], [30, low ,yes ,fair ,yes], [40, medium ,yes ,fair ,yes], [30, medium ,yes ,excellent ,yes], [35, medium ,no ,excellent ,yes], [35, high ,yes ,fair ,yes], [40, medium ,no ,excellent ,no]]). %%-------------------------------------------------------------%% MK DATA SETS mkdata(_):- abolish(data/2),dynamic(dom/3),fail. mkdata(_):- dynamic(data/2),dynamic(dom/3),fail. mkdata(X):-pre_test_data(X,[Y|Ys]),!, mkDom(1,Y,DOM), zipper(DOM,D1,D2),assert(dom(X,DOM,D1)),mktuple(1, Ys). mktuple(N,[X|Xs]):-assert(data(N,X)),N1 is N+1, mktuple(N1,Xs). mktuple(_,[]):-listing(dom),listing(data). mkDom(N,[X|Xs],[(N,X)|NXs]):-N1 is N+1, mkDom(N1,Xs,NXs). mkDom(_,[],[]). getD((Attr,V),(An,V)):- dom(_,VA,_),!, nth1(K,VA,(An,Attr)). getDom([X|L],[DX|DL]):- getD(X,DX),getDom(L,DL). getDom([],[]). l:-listing(dom/3),listing(data/2). getAttV((K,IDs)):- setof(V,Row^V^ID^(data(ID,Row),nth1(K,Row,V)),IDs). getAttDom(L):- dom(N,_,Header),bagof((K,Vs),K^Vs^(member(K,Header),getAttV((K,Vs))),L). zipper([(X,Y)|XYs],[X|Xs],[Y|Ys]):-zipper(XYs,Xs,Ys). zipper([],[],[]). Vamos trabalhar com fatos na base do Prolog, como mostrado na pergunta mkdata(12), abaixo. Esta pergunta instancia o conjunto de dados 12 para ser processado. Ela cria dois fatos dinˆamicos: um para as informa¸c˜oes do dom´ınio dom/3 e outro para os dados em si, data/2. O mkdata chama o mkDom e o mkTuple. O mkDom simplesmente enumera a lista de colunas a partir do um, pois ´e mais f´acil trabalhar com a numera¸c˜ao das colunas. Por´em, caso for preciso trabalhar com nome da coluna ´e poss´ıvel: o dom´ınio permite o mapeamento entre n´umero e nome; o getDom/2 faz o mapeamento de atributo para n´umero. O mkTuple enumera as linhas a partir do um; as linhas dos conjuntos de dados n˜ao possuem um campo chave, logo, um conjunto de dados pode ter linhas duplicadas. Com a enumera¸c˜ao das linhas temos um valor id(entificador) de cada linha. ?- mkdata(12). :-dynamic dom/3. dom(12,[(1,age),(2,income),(3,student),(4,credit_rating),(5,buys_computer)], [1,2,3,4,5]). :- dynamic data/2. 19.2. A inferˆ encia Bayesiana ??????- 231 data(1, [30, high, no, fair, no]). data(2, [30, high, no, excellent, no]). data(3, [35, high, no, fair, yes]). data(4, [40, medium, no, fair, yes]). data(5, [40, low, yes, fair, yes]). data(6, [40, low, yes, excellent, no]). data(7, [35, low, yes, excellent, yes]). data(8, [30, medium, no, fair, no]). data(9, [30, low, yes, fair, yes]). data(10, [40, medium, yes, fair, yes]). data(11, [30, medium, yes, excellent, yes]). data(12, [35, medium, no, excellent, yes]). data(13, [35, high, yes, fair, yes]). data(14, [40, medium, no, excellent, no]). mkDom(1, [aaa,bbb,ccc,2],X). X = [ (1, aaa), (2, bbb), (3, ccc), (4, 2)] getDom( [(age,m30),(income, medium),(student,yes)],L). L = [ (1, m30), (2, medium), (3, yes)] getAttV((2,Vs)). Vs = [high, low, medium] getD((buys_computer,yes), T). T = 5, yes getAttV((2,Vs). Vs = [high, low, medium] getAttDom(L). L=[(1,[30,35,40]), (2,[high,low,medium]), (3,[no,yes]), (4,[excellent,fair]), (5,[no,yes])] O predicado getD retorna o valor da coluna. O predicado getAttV retorna uma lista com todos os valores poss´ıveis para uma determinada coluna. E, por fim, o predicado getAttDom que retorna para cada coluna todos os valores poss´ıveis (o dom´ınio de cada coluna). 19.2 A inferˆ encia Bayesiana O m´etodo de classifica¸c˜ao baseado em inferˆencia Bayesiana trabalha com dados cont´ınuos e discretos. Para dados cont´ınuos, ele assume que os valores seguem uma fun¸c˜ao de distribui¸c˜ao normal, assim, as probabilidades s˜ao inferidas a partir da m´edia e do desvio padr˜ao de grupos de indiv´ıduos. Para dados discretos os valores de probabilidades s˜ao coletados pela contagem nos grupos de indiv´ıduos. Seguem abaixo alguns testes para os predicados de probabilidade condicional para valores discretos e cont´ınuos. O predicado probC_CC ´e para valores cont´ınuos. Dado que o valor da primeira coluna ´e 30: a probabilidade da classe (5ta coluna) ser yes ´e 0.00719275 e de ser no ´e 0.0347488. O predicado probC ´e para valores discretos. Para os mesmos dados os valores s˜ao 0.222222 para yes e 0.6 para no; assim, em ambos casos a probabilidade de ser no ´e maior que a probabilidade de ser yes. O que muda ´e a escala de valores. ?- mkdata(12). ... ?- normal_df(110, 54.54, 120,X). 232 19. IA: Classifica¸c˜ ao Naive Bayes X = 0.00719275 ?- probC_CC([1,2,3,4,5,6,7,8,9,10,11,12,13,14],(1,30),(5,yes),P). P = 0.0347488 probC_CC([1,2,3,4,5,6,7,8,9,10,11,12,13,14],(1,30),(5,no),P). P = 0.0583498 ?- probC([1,2,3,4,5,6,7,8,9,10,11,12,13,14],(1,30),(5,yes),P), Po is P. P = 2/9 Po = 0.222222 ?- probC([1,2,3,4,5,6,7,8,9,10,11,12,13,14],(1,30),(5,no),P), Po is P. P = 3/5 Po = 0.6 %% ?-probC([1,2,3,4,5,6,7,8,9,10,11,12,13,14],(1,40),(2,low),P), Po is P. P = 2/4 Po = 0.5 ?- probC([1,2,3,4,5,6,7,8,9,10,11,12,13,14],(2,low),(1,40),P), Po is P. P = 2/5 Po = 0.4 Nas duas ultimas perguntas, acima, vemos que a probabilidade condicional n˜ ao ´ e sim´ etrica. O predicado principal infer ´e o que faz a inferˆencia, que ´e a pr´opria classifica¸c˜ao. Para esse predicado de inferˆencia, a solu¸c˜ao apresentada aqui s´o trabalha com valores discretos. Para integrarmos com os valores cont´ınuos devemos primeiro ter na descri¸c˜ao do dom´ınio uma informa¸c˜ao dizendo se ele ´e discreto ou cont´ınuo; esta integra¸c˜ao ´e deixada como exerc´ıcio. Assumindo que todos os dados s˜ao a base de treinamento, queremos saber a classifica¸c˜ao para [(age,30), (income,medium),(student,yes),(credit rating,fair)]. Isto ´e, o valor do atributo buys_computer ´e yes ou ´e no? O resultado retornado nas perguntas abaixo ´e 0.0282187 para yes e 0.00685714 para no; portanto, a classifica¸c˜ao deste exemplo ´e yes. Propositadamente retornamos tamb´em os valores numa express˜ao simb´olica sem calcular o valor. ?- infer([(age,30),(income, medium),(student,yes),(credit_rating,fair)], (buys_computer,yes),I), Io is I. I = 9/14* (1* (6/9)* (6/9)* (4/9)* (2/9)) Io = 0.0282187 ?- infer([(age,30),(income, medium),(student,yes),(credit_rating,fair)], (buys_computer,no),I), Io is I. I = 5/14* (1* (2/5)* (1/5)* (2/5)* (3/5)) Io = 0.00685714 Segue abaixo o c´odigo dos predicados. Este programa chama o programa estat.pl para reutilizar os predicados medv, std e normal_df. 1 2 3 4 5 6 7 8 9 10 11 %% ia-bayes.pl %% Inferencia Naive Bayes :-[stat]. prob((K,V),P/Q):- bagof(ID,Row^(data(ID,Row),nth1(K,Row,V)),IDs),length(IDs,P), bagof(T,R^data(T,R),Ts),length(Ts,Q). prob(L,(K,V),P/Q):- bagof(ID,Row^(data(ID,Row),nth1(K,Row,V), member(ID,L)),IDs),length(IDs,P),length(L,Q). prob0(L/Lo,(K,V),P/Q):- bagof(ID,Row^(data(ID,Row),nth1(K,Row,V), member(ID,L)),Lo),length(Lo,P),length(L,Q). probC(L,(K,V),(K1,V1),Po/Qo):- prob0(L/Lo,(K1,V1),_), prob(Lo,(K,V),Po/Qo). probCond(L,A,B,P):-getD(A,Ao),getD(B,Bo),probC(L,Ao,Bo,P). 19.2. A inferˆ encia Bayesiana 12 13 14 15 16 17 18 19 20 21 22 233 infer(L,C,I):-getDom(L,LN),getD(C,C1),infer0(LN,C1,I). infer0(L,(A,V),Io):-bagof(T,R^data(T,R),IDs), prob0(IDs/IDo,(A,V),P/Q),inferL(IDo,L,I),Io = (P/Q)*I. inferL(IDs,[L|Ls],Io):-prob(IDs,L,P/Q),inferL(IDs,Ls,I),Io = I*(P/Q). inferL(_,[],1). %% getAttV(L,(K,Vs)):- bagof(V,Row^V^ID^(member(ID,L),data(ID,Row),nth1(K,Row,V)),Vs). %% probabilidade condicional para coluna com valores cont´ ınuos %% usa a densidade da fun¸ c~ ao normal probC_CC(L,(K,V),(K1,V1),P):- prob0(L/Lo,(K1,V1),_),getAttV(Lo,(K,Vs)), medv(Vs,M),std(Vs,Std),normal_df(M,Std,V,P). Abaixo, mostramos a execu¸c˜ao dos predicados auxiliares, usados para codificar o predicado de inferˆencia, infer. O predicado prob/2 retorna a probabilidade `a priori de um par (coluna, valor); ele considera todos os exemplos da base; o prob/3 faz o mesmo mas considerando s´o os exemplos coletados na lista passada como primeiro parˆametro. O predicado prob0/3 ´e similar a este, por´em retorna em Lo todos os identificadores das linhas da tabela que foram usados no denominador do c´alculo da probabilidade; ele ´e usado no c´alculo da probabilidade condicional. Por fim, os predicados probC/4 e probCond/4 retornam a probabilidade condicional de uma coluna em rela¸c˜ao `a outra. No primeiro a coluna ´e passada como um n´umero e no segundo pelo nome do atributo. ?- prob((5,yes),P). P = 9/14 ?- prob((5,no),P). P = 5/14 ?- prob([1,2,3,4,5,6,7],(5,yes),P). P = 4/7 ?- prob0([1,2,3,4,5,6,7]/Lo,(5,yes),P). Lo = [3, 4, 5, 7] P = 4/7 ?- probC([1,2,3,4,5,6,7,8,9,10,11,12,13,14],(1,30),(5,yes),P), Po is P. P = 2/9 Po = 0.222222 ?- probCond([1,2,3,4,5,6,7,8,9,10,11,12,13,14], (age,30),(buys_computer,yes),P), Po is P. P = 2/9 Po = 0.222222 Exerc´ıcio 19.1 Modifique o algoritmo para trabalhar com valores discretos e cont´ınuos. Comece com a informa¸c˜ao do tipo de dados para cada atributo. Use o formato do Weka: ARFF. Para um atributo num´erico deve ser chamada o predicado da probabilidade condicional continua. Exerc´ıcio 19.2 A vers˜ao apresentada n˜ao consegue fazer inferˆencia se um dos atributos tem probabilidade zero; pois, como ´e um produto, basta um fator ser zero para o resultado ser zero. Existem t´ecnicas para contornar o problema, implemente uma delas. Dica: Uma da t´ecnicas ´e a m-estimativa, que modifica a f´ormula do c´alculo de probabilidade de nc /n para (nc + mp)/(n + m); na ausˆencia de outra informa¸c˜ao, pode-se assumir p = 1/k, se o atributo pode assumir k valores distintos; p ´e a estimativa de probabilidade que se deseja determinar; m ´e uma constante denominada tamanho da amostra equivalente: determina um peso dado a p em rela¸c˜ao aos dados observados nc ; se m for zero, ent˜ao a m-estimativa ´e nc /n; m pode ser interpretada como um aumento de m exemplos virtuais distribu´ıdos de acordo com p; logo para pequenas amostras (10 at´e 100 exemplos), fa¸ca m = 2. 234 19. IA: Classifica¸c˜ ao Naive Bayes Exerc´ıcio 19.3 Para bases de dados maiores, acima de 500 instˆancias. Fa¸ca um comparativos dos m´etodos de classifica¸c˜ao: KNN e Bayes. Rode primeiro as bases no Weka, para saber como fazer o comparativo. Utilize um m´etodo de testes sistem´atico como o N-fold cross validation. CAP´ITULO 20 IA: Similaridade via nGramas Ngramas podem ser utilizados como uma medida de similaridade. Uni-gramas de palavras s˜ao utilizados nos engenhos de busca para recuperar documentos. Bi-gramas ou tri-gramas de caracteres servem para medir a similaridade de duas palavras (ou frases). Tri-gramas de palavras servem para medir o pl´agio entre dois textos. Nos testes abaixo utilizamos bi e tri-gramas de letras para comparar duas palavras eloi X eloy. O n´umero de tri-gramas iguais ´e 3 de um total de 6, resultando em um coeficiente de 0.5. Com bi-gramas o coeficiente vai para 0.6; e com uni-gramas vai para 0.75 (trˆes letras iguais de 4). Aparentemente o valor de 0.75 ´e o mais correto, por´em este valor tamb´em ´e obtido se invertermos a ordem das letras de um dos nomes: eloi X yole. Os bi-gramas e tri-gramas permitem medir similaridade considerando a ordem entre os elementos. ?-wr_ngr(char_tri,eloi,eloy). X:,6:[(32,32,e),(32,e,l),(e,l,o),(l,o,i),(o,i,32),(i,32,32)] Y:,6:[(32,32,e),(32,e,l),(e,l,o),(l,o,y),(o,y,32),(y,32,32)] X^Y:,3:[(32,32,e),(32,e,l),(e,l,o)] 2*3/(6+6)=0.5 ?-wr_ngr(char_big,eloi,eloy). X:,5:[(32,e),(e,l),(l,o),(o,i),(i,32)] Y:,5:[(32,e),(e,l),(l,o),(o,y),(y,32)] X^Y:,3:[(32,e),(e,l),(l,o)] 2*3/(5+5)=0.6 ?-wr_ngr(char_uni,eloi,eloy). X:,4:[e,l,o,i] Y:,4:[e,l,o,y] X^Y:,3:[e,l,o] 2*3/(4+4)=0.75 ?-wr_ngr(char_uni,eloi,yole). X:,4:[e,l,o,i] Y:,4:[y,o,l,e] X^Y:,3:[e,l,o] 235 236 20. IA: Similaridade via nGramas 2*3/(4+4)=0.75 Para gerar os tri-gramas, uma palavra ´e acrescida de dois brancos iniciais e dois finais (foi usado o valor Ascii do branco, 32). Para os bi-gramas foi acrescentado um branco inicial e um branco final. O prop´osito disso ´e favorecer a compara¸c˜ao de palavras pequenas (por exemplo, 3 letras), com prefixos ou sufixos iguais. Por exemplo, elo X eli se forem comparados como tri-gramas iguais o resultado ´e zero, por´em com os dois brancos iniciais o resultado ´e 2/5. Para algumas aplica¸c˜oes, quando os prefixos e sufixos n˜ao tem um valor maior, deve-se remover estes brancos inicias para que sejam contabilizados os bi e tri-gramas puros. Esta discuss˜ao vale tamb´em para comparar textos, nestes casos os ngramas s˜ao de palavras. Um m´etodo bom para identificar pl´agio entre dois textos ´e medir a quantidade de tri-gramas de palavras que eles tem em comum. Seja X^Y a intersec¸c˜ao da lista X com a lista Y e seja |X| o comprimento da lista X. Definimos o coeficiente de Dice como (2*|X^Y|) /(|X|+|Y|), e.g., dice(aabbcc,abc) =(2*3)/9 =6,66; e o coeficiente de Sobreposi¸c˜ao como |X^Y| /min(|X|, |Y|), e.g., sobrep(aabbcc,abc) =3/3 =1. Nesta defini¸c˜ao de intersec¸c˜ao a ordem n˜ao ´e considerada, e.g., dice(aabbcc,abc) =dice(abcabc,cba) =6,66. Estas duas medidas s˜ao boas quando X e Y tˆem poucos elementos repetidos. Quando eles tˆem muitos elementos repetidos devemos considerar outras m´etricas, tais como, o coseno das freq¨uˆencias dos elementos. Segue abaixo o programa ngram-07.pl que codifica predicados para gerar ngramas (n=1,2,3) de caracteres e de palavras. Para palavras fizemos duas vers˜oes: uma considerando os tokens retornados pelo predicado tokenize_atom do SWI-Prolog e outra que usa o predicado atom_to_stem_list, tamb´em do SWI-Prolog, que remove os sufixos das palavras. Este stemmer (em-raizador) ´e para a l´ıngua inglesa, mas serve para ilustrar o uso dos ngramas. Na vers˜ao com stemmer s˜ao removidas as palavras de classe fechada tamb´em chamadas de stop words; para isso, elas foram cadastradas num fato. Os predicados get_chars e get_words transformam uma string em letras ou palavras, respectivamente. Eles tamb´em removem os acentos e deixam tudo com letras min´usculas. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 %% ngram07-elf.pl char_uni(X,Y,Val):- ngram(char_uni,Y,X,Val). char_big(X,Y,Val):- ngram(char_big,Y,X,Val). char_tri(X,Y,Val):- ngram(char_tri,Y,X,Val). word_uni(X,Y,Val):- ngram(word_uni,Y,X,Val). word_big(X,Y,Val):- ngram(word_big,Y,X,Val). word_tri(X,Y,Val):- ngram(word_tri,Y,X,Val). word_uni_stem(X,Y,Val):- ngram(word_uni_stem,Y,X,Val). word_big_stem(X,Y,Val):- ngram(word_big_stem,Y,X,Val). ngramTypes( [word_uni, char_big, char_tri, word_uni, word_big, word_tri, word_uni_stem, word_big_stem, word_tri_stem]). get_chars(F,Ns):-downcase_atom(F,Fd),unaccent_atom(Fd,Fu),atom_chars(Fu,Ns). get_words(F,Ns):-downcase_atom(F,Fd),unaccent_atom(Fd,Fu),tokenize_atom(Fu,Ns). char_uni(F,B):- get_chars(F, B). char_big(F,B):- get_chars(F, Ns),!,mk_big(Ns, B). char_tri(F,B):- get_chars(F, Ns),!,mk_tri(Ns, B). word_uni(F,B):- get_words(F, B). word_big(F,B):- get_words(F, Ns),!,mk_big(Ns, B). word_tri(F,B):- get_words(F, Ns),!,mk_tri(Ns, B). 237 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

word_uni_stem(F,B):-atom_to_stem_list(F,Bo), filter_sw(Bo,B), !. %%c\stemmer word_big_stem(F,B):-atom_to_stem_list(F,Nso),filter_sw(Nso,Ns),!,mk_big(Ns,B). word_tri_stem(F,B):-atom_to_stem_list(F,Nso),filter_sw(Nso,Ns),!,mk_tri(Ns,B). %% ngram(CALL,X,Y,Val):-CX=..[CALL,X,XB],CX,! ,CY=..[CALL,Y,YB],CY,!, listDice(XB,YB,Val). wr_ngr(CALL,X,Y):- CX=..[CALL,X,XB],CX, !,CY=..[CALL,Y,YB],CY,!, nl,writeln(CALL), interS(XB,YB,XYB),length(XB,Xm),length(YB,Ym),length(XYB,XYm), Val is 2*XYm/(Xm+Ym), FR=7,front(FR,XB,XBF), front(FR,YB,YBF), front(FR,XYB,XYBF), nl,write((’X:’,Xm:XBF)), nl,write((’Y:’,Ym:YBF)), nl,write((’X^Y:’,XYm:XYBF)), nl,write(2*XYm/(Xm+Ym)=Val),nl. %% bi-tri-gramas mk_big(F,B):- !,big_([32|F], B). mk_tri(F,B):- !,tri_([32,32|F], B). big_([X,Y,Z|XYZs],[XY,YZ|Bs]):-!, XY=(X,Y),YZ =(Y,Z),big_([Z|XYZs],Bs). big_([X,Y], [XY,YB] ):-!, XY=(X,Y),YB =(Y,32). big_([X], [XB] ):-!, XB=(X,32). big_([], [] ). tri_([X,Y,Z,W|XYZs],[XY,YZ|Bs]):-!, XY=(X,Y,Z),YZ =(Y,Z,W),tri_([Z,W|XYZs],Bs). tri_([X,Y,Z], [XY,YB,ZB]):-!, XY=(X,Y,Z),YB =(Y,Z,32), ZB=(Z,32,32). tri_([X,Y], [XB,YB] ):-!, XB=(X,Y,32),YB=(Y,32,32). tri_([X], [XB] ):-!, XB=(X,32,32). tri_([], [] ). %% STOP WORDS stop(1,’a o as os de do da em no um uns uma umas que te ele ela se por \c para pela ser nao com e cada ou desta dessa daquela daquele mesmo outra \c mas mais menos deve pode ja seja ter varios varias nenhum nenhuma outro’). stop(2,’; . , - = + - : ( ) [ ] \’’). :-abolish(stopw/1), dynamic(stopw). mk_stop:-bagof(L,(LX^X^stop(X,LX), atom_to_stem_list(LX,L)),B),flatten(B,BF), mkw(BF). mkw([X|Xs]):-assert(stopw(X)),mkw(Xs). mkw([]). :-mk_stop. %% filter_sw([L|LS], OS):- stopw(L),!,filter_sw(LS,OS). filter_sw([L|LS], [L|OS]):!,filter_sw(LS,OS). filter_sw([],[]). %% similaridade para ngramas: dice, sobrep, coseno listSobrep(X,Y,D):-length(X,Xm),length(Y,Ym), interS(X,Y,XY),length(XY,XYm), D is XYm/min(Xm,Ym). listDice(X,Y,D):-length(X,Xm),length(Y,Ym), interS(X,Y,XY),length(XY,XYm), D is 2*XYm/(Xm+Ym). %% interS(X,Y,XY):-msort(X,Xs),msort(Y,Ys),inter0(Xs,Ys,XY),!. inter0([X|Xs],[X|Ys],[X|Is]):!,inter0(Xs, Ys,Is). inter0([X|Xs],[Y|Ys], Is):- [email protected],!,inter0([X|Xs],Ys,Is).

238 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 20. IA: Similaridade via nGramas

inter0([],_,[]):-!. inter0(_,[],[]). %% prodX([X|Xs], S):- prodX(Xs, Ss), S is (X*X)+Ss. prodX([],0). prodXY([X|Xs],[Y|Ys], S):- prodXY(Xs,Ys, Ss), S is (X*Y)+Ss. prodXY([],[],0). coseno0_fd(A,B,C):- bins(A,Ad), bins(B,Bd),merge0_fd(Ad,Bd,AB), zipper(AB,_,BXY),zipper(BXY,Xo,Yo),coseno(Xo,Yo,C). coseno_fd(A,B,C):- bins(A,Ad), bins(B,Bd),merge_fd(Ad,Bd,AB), zipper(AB,_,BXY),zipper(BXY,Xo,Yo),coseno(Xo,Yo,C). coseno(X,Y,P):- prodXY(X,Y,Sxy),prodX(X,Sx),prodX(Y,Sy), P is Sxy/(sqrt(Sx)*sqrt(Sy)). %% bins+merge para calcular a distribui¸ c~ ao da interse¸ c~ ao sortbins(L,Xo):- zipper(L,L1,L2),zipper(Lo,L2,L1),msort(Lo,Los),reverse(Los,Xo). bins(L,Do):-msort(L,[X|LS]),!,freq(LS,X,1,Do). freq([X|Xs],X,N,Ls):-!,N1 is N+1, freq(Xs,X,N1,Ls). freq([X|Xs],Y,N,[(Y,N)|Ls]):-!,freq(Xs,X,1,Ls). freq([],Y,N,[(Y,N)]). %% merge0_fd(X,Y,XY):-mrg0(X,Y,XY). %% assume ordem asc mrg0([(X,Fx)|Xs],[(X,Fy)|Ys],[(X,Fx-Fy)|Is]):!,mrg0(Xs, Ys,Is). mrg0([(X,Fx)|Xs],[(Y,Fy)|Ys],[(X,Fx-0)|Is]):- [email protected],!,mrg0([(X,Fx)|Xs],Ys,Is). mrg0([(X,Fx)|Xs],[], [(X,Fx-0)|Is]):!,mrg0(Xs, [],Is). mrg0([], [(Y,Fy)|Ys],[(Y,0-Fy)|Is]):!,mrg0([] ,Ys,Is). mrg0([],[],[]). merge_fd(X,Y,XY):-mrg(X,Y,XY). %% assume ordem asc mrg([(X,Fx)|Xs],[(X,Fy)|Ys],[(X,Fx-Fy)|Is]):- !,mrg(Xs, Ys,Is). mrg([(X,Fx)|Xs],[(Y,Fy)|Ys],Is):- [email protected],!,mrg([(X,Fx)|Xs],Ys,Is). mrg([],_,[]):-!. mrg(_,[],[]). %% utils lists zipper([(X-Y)|XYs],[X|Xs],[Y|Ys]):-!,zipper(XYs,Xs,Ys). zipper([(X,Y)|XYs],[X|Xs],[Y|Ys]):-!,zipper(XYs,Xs,Ys). zipper([],[],[]). front(N,L,F):-length(F,N),append(F,_,L),!. front(_,L,L). top(N,L,T):- msort(L,S),reverse(L,LR),front(N,LR,T).

O predicado interS verifica a intersec¸c˜ao de duas listas, retornando uma lista com todos os elementos que pertencem as duas listas. Para tornar o processamento mais eficiente, primeiro ordenam-se as duas listas sem remover os duplicados. Com j´a foi apresentado, existem dois predicados para medir o coeficiente de similaridade baseado na intersec¸c˜ao: Sobreposi¸c˜ao e Dice. A Sobreposi¸c˜ao favorece a compara¸c˜ao de listas de comprimento diferente sem penalizar a menor lista. O Dice ´e mais apropriado para comparar listas de tamanhos similares; se as listas tˆem tamanhos desiguais este coeficiente ´e baixo. ?- interS([e,l,o,i],[l,i,o,y],X). X = [i, l, o] ?- listDice([e,l,o,i,l,u,i,z,f,a,v,e,r,o],[e,l,o,y],Y). 239 Y = 0.333333 ?- listSobrep([e,l,o,i,l,u,i,z,f,a,v,e,r,o],[e,l,o,y],Y). Y = 0.75 Para comparar cadeias com alta freq¨uˆencia de elementos repetidos, sugerimos o uso do coseno. Neste caso, o predicado bins ´e usado para coletar a freq¨uˆencia dos elementos. Similar ao interS, ´ um pr´eo predicado merge_fd coleta os valores das freq¨uˆencias dos elementos das duas listas. E processamento para fazer o c´alculo do coseno. Existem duas vers˜oes: uma ignora todos os pares que tem freq¨uˆencia zero em um dos elementos e a outra n˜ao. O merge0_fd coleta todos os pares, mesmo os que tˆem zeros. ?- get_chars(aaaabbbbcccddd,A),bins(A,AB). A = [a, a, a, a, b, b, b, b, c|...] AB = [ (a, 4), (b, 4), (c, 3), (d, 3)] ?- get_chars(aaaabbbbcccddd,A),bins(A,AB), get_chars(aaabbeeefffccddd,B),bins(B,BB),merge_fd(AB,BB,MM). A = [a, a, a, a, b, b, b, b, c|...] AB = [ (a, 4), (b, 4), (c, 3), (d, 3)] B = [a, a, a, b, b, e, e, e, f|...] BB = [ (a, 3), (b, 2), (c, 2), (d, 3), (e, 3), (f, 3)] MM = [ (a, 4-3), (b, 4-2), (c, 3-2), (d, 3-3)] ?- get_chars(aaaabbbbcccddd,A),bins(A,AB), get_chars(aaabbeeefffccddd,B),bins(B,BB),merge0_fd(AB,BB,MM). A = [a, a, a, a, b, b, b, b, c|...] AB = [ (a, 4), (b, 4), (c, 3), (d, 3)] B = [a, a, a, b, b, e, e, e, f|...] BB = [ (a, 3), (b, 2), (c, 2), (d, 3), (e, 3), (f, 3)] MM = [ (a, 4-3), (b, 4-2), (c, 3-2), (d, 3-3), (e, 0-3), (f, 0-3)] Podemos pensar numa busca de 5 palavras dentro de um texto com centenas de palavras; n˜ao tem sentido coletar centenas de pares com 0 de freq¨uˆencia; neste caso usa-se o merge_fd. A sa´ıda do merge_fd ´e uma lista de triplas, (token, frqX-frqY); por exemplo, [(a, 5-4), (b, 4-2), (c, 3-2), (d, 3-3)]. Usa-se o zipper para desfazer estas triplas em duas listas: os Xs e os Ys; eles s˜ao entrada da fun¸c˜ao coseno. Esta seq¨uˆencia de passos ´e codificada em conseno_fd. De modo similar, para trabalhar tamb´em com zeros temos coseno0_fd. Seguem abaixo alguns testes para o coseno. Nas duas primeiras perguntas, compara-se a vers˜ao com zeros com a vers˜ao sem zeros; nas duas u´ltimas, compara-se o coseno com zeros com a m´etrica de Dice. ?-get_chars(aaaabbbbcccddd,A),get_chars(aaabbeeefffccddd,B),coseno0_fd(A,B,C). A = [a, a, a, a, b, b, b, b, c|...] B = [a, a, a, b, b, e, e, e, f|...] C = 0.746203 ?- get_chars(aaaabbbbcccddd,A),get_chars(aaabbeeefffccddd,B),coseno_fd(A,B,C). A = [a, a, a, a, b, b, b, b, c|...] B = [a, a, a, b, b, e, e, e, f|...] C = 0.970725 ?- char_tri(aaaabbbbcccddd,A),char_tri(aaabbeeefffccddd,B),coseno0_fd(A,B,C). A = [ (32, 32, a), (32, a, a), (a, a, a), (a, a, a), (b, b, b), ...)|...] B = [ (32, 32, a), (32, a, a), (a, a, a), (a, a, b), (a, b, b), ...)|...] C = 0.579751 240 20. IA: Similaridade via nGramas ?- ngram(char_tri, aaaabbbbcccddd, aaabbeeefffccddd,Z). Z = 0.588235 20.1 O programa de testes O programa dos ngramas, em essˆencia, codifica os predicados para gerar os ngramas e mais os trˆes predicados de m´etricas. Diversos predicados utilizados nele j´a s˜ao nossos conhecidos tais como coseno, prodX, prodXY, bins, freq, zipper, front, etc. Estes predicados j´a conhecidos n˜ao ser˜ao relatados aqui. Abaixo mostramos mais predicados usados para testar os predicados dos ngramas; alguns deles trabalham com arquivos. Inicialmente temos 5 frases como fatos. Depois temos o predicado randCh/1 que gera um caractere randomicamente; a partir desse predicado codificou-se randChs/2 que gera uma lista de caracteres randˆomicos de tamanho N. Depois temos os predicados x4, x16, x32 que multiplicam um string Xvezes. Seguem testes ilustrativos para estes predicados. ?- frase(1,F1),frase(2,F2),ngram(char_tri,F1,F2,V12). F1 = ’em orienta¸ c~ ao a objetos o conceito de generaliza¸ c~ ao’ F2 = ’generaliza¸ c~ ao ´ e um dos conceitos de orienta¸ c~ ao a objetos’ V12 = 0.720721 ?- randCh(X). X = w ?- randCh(X). X = h ?- randChs(10,L). L = [k, o, f, q, z, u, q, w, y|...] ?- time((randChs(10000,L),bins(L,B))). % 59,990 inferences, 0.06 CPU in 0.09 seconds (66% CPU, 959840 Lips) L = [a, o, ... B = [ (a, 425), (b, 406), (c, 370), ...] ?- frase(1,F1),frase(2,F2),x16(F1,F1X),x16(F2,F2X), time(ngram(char_tri,F1X,F2X,V12)). % 4,629 inferences, 0.00 CPU in 0.00 seconds (?% CPU, Infinite Lips) F1X = "em ... F2X = ... V12 = 0.745921 Por fim, temos um conjunto de testes baseados em dados de arquivos. Assume-se que existem os arquivos teste-big.txt, teste1.txt e teste2.txt. S˜ao arquivos de texto; os dois u´ltimos servem para medir a quantidade de pl´agio, sugerimos que eles compartilhem uma boa parte do texto. 1 2 3 4 5 6 7 8 9 10 11 12 %% testa predicados frase(1,’em orienta¸ c~ ao a objetos o conceito de generaliza¸ c~ ao’). frase(2,’generaliza¸ c~ ao ´ e um dos conceitos de orienta¸ c~ ao a objetos’). frase(3,’uma teoria de linguagens formais’). frase(4,’as linguagens de programacao’). frase(5,’as linguagens de programa¸ c~ ao’). randCh(CH):-C is 0’a+random(26),char_code(CH,C). randChs(M,L):-findall(C,(between(1,M,_),randCh(C)),L). x4(F,F4):-string_concat(F,F,F2),string_concat(F2,F2,F4). x16(P,MP):- x4(P,P4), x4(P4, MP). x1616(P,MP):-x16(P,P16),x16(P16,MP). %% 20.1. O programa de testes 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 241 t1 :- frase(1,F1),frase(2,F2),frase(3,F3),frase(4,F4),frase(5,F5), ngram(char_tri,F1,F2,V12),writeln(val:V12), ngram(char_tri,F2,F3,V23),writeln(val:V23), ngram(char_tri,F3,F4,V34),writeln(val:V34). t3:- frase(1,F1),frase(2,F2), x16(F1,F1M),x16(F2,F2M), wr_ngr(char_tri,F1M,F2M). t5:- frase(1,F1),frase(2,F2), x1616(F1,F1M),get_chars(F1M,F2W),bins(F2W,V), length(F2W,L), writeln(len:K), writeln(V). %% FILES do1:-F1=’teste1.txt’, F2=’teste2.txt’, fl2str(F1,X),fl2str(F2,Y), ngramTypes(L),forall(member(NGR,L),wr_ngr(NGR,X,Y)). rd2tokens(F,L):-fl2str(F,S),!,downcase_atom(S,Fd), unaccent_atom(Fd,Fu),tokenize_atom(Fu,L). fl2str(F,Str):- see(F),current_input(Stream), read_stream_to_codes(Stream, Codes), seen,atom_codes(Str,Codes). plagio1(F1,F2):-fl2str(F1,X),fl2str(F2,Y),ngram(char_tri,X,Y,V),writeln(val:V). plagio2(F1,F2):-fl2str(F1,X),fl2str(F2,Y),ngram(word_tri,X,Y,V),writeln(val:V). x:-plagio1(’teste1.txt’,’teste2.txt’). y:-plagio1(’teste1.txt’,’teste1.txt’). %% get_f0(T):-rd2tokens(’text-big.txt’,T). get_f1(T):-rd2tokens(’teste1.txt’,T). get_f2(T):-rd2tokens(’teste2.txt’,T). set_f0(T):- tell(’text-big.ddd’),wrtbins(T),told. set_f1(T):- tell(’teste1.ddd’),wrtbins(T),told. set_f2(T):- tell(’teste2.ddd’),wrtbins(T),told. wrtbins([]) :- !. wrtbins([D|Ds]):-!,D=(X-Y),writeq(X),writeq(’|’),writeq(Y),nl,wrtbins(Ds). %% b0 :- get_f0(T), mk_big(T,T1), bins(T1,D), set_f0(D). b1 :- get_f1(T), mk_big(T,T1), bins(T1,D), sortbins(D,Ds), set_f1(Ds). b2 :- get_f2(T), mk_big(T,T1), bins(T1,D), sortbins(D,Ds), set_f2(Ds). t1 :- get_f1(T), mk_tri(T,T1), bins(T1,D), sortbins(D,Ds), set_f1(Ds). t2 :- get_f2(T), mk_tri(T,T1), bins(T1,D), sortbins(D,Ds), set_f2(Ds). Exerc´ıcio 20.1 Dado um dicion´ario, considere uma lista com todas as palavras que iniciam com a letra (a); a partir da lista crie 10 palavras com uma letra duplicada: ab´obora para abbobora; 10 sem uma letra: abbora; e 10 com duas letras consecutivas trocadas: aobbora. I) Agora gere uma tabela, num arquivo, comparando cada um destas palavras via m´etricas de uni, bi e tri-gramas com todas as palavras corretas. Liste na sa´ıda em ordem decrescente de similaridade. II) Fa¸ca o mesmo modificando os bi e tri-gramas, tirando os c´odigos 32 no in´ıcio e fim de cada palavra. III) Examinando os valores procure fazer uma f´ormula para descobrir cada um destes tipos de erros. Imagine que este processo de inferˆencia ´e para implementar um corretor ortogr´afico. Exerc´ıcio 20.2 Utilizando uma ou mais m´etricas de ngramas, proponha um m´etodo para identificar pl´agio entre dois textos. Fa¸ca um experimento, com um conjunto de amostras. Exerc´ıcio 20.3 Utilizando uma ou mais m´etricas de ngramas, proponha um m´etodo para identificar pl´agio entre dois programas Java. Fa¸ca um experimento, com um conjunto de amostras. 242 20. IA: Similaridade via nGramas Exerc´ıcio 20.4 A partir de uma lista de palavras ra´ızes (palavras fechadas, verbos no infinitivo (sem ar er ir) e nomes comuns no masculino singular) fa¸ca um programa stemmer baseado em m´etricas (1-2-3-gramas de caracteres). Reduza cada palavra de um texto para a palavra raiz mais pr´oxima. Fa¸ca um estudo comparativo com o melhor stemmer para o Portuguˆes. Teste situa¸c˜oes como casamento -> cas(ar); casar~ ao -> casa; canto -> cant(ar); canto -> canto. CAP´ITULO 21 IA: Teoria da Informa¸c˜ ao Aqui apresentamos algumas m´etricas relacionadas com a teoria da informa¸c˜ao. Elas s˜ao u´teis para explorar a manipula¸c˜ao da informa¸c˜ao. Por exemplo, para induzir um classificador a partir de uma lista de atributos estas m´etricas podem validar quais os atributos que influenciam mais na classifica¸c˜ao. Assim, se temos 30 atributos podemos selecionar somente os 7 mais significativos para serem utilizados no desenvolvimento do classificador. 21.1 Bits e quantidade de informa¸c˜ ao O bit ´e a unidade m´ınima de informa¸c˜ao. Com um bit podemos codificar dois valores de uma moeda (1-Kara,0-coroa). Para codificar os valores na faixa de 0 at´e 15, totalizando 16 possibilidade, precisamos 4 bits, pois log2 (16) = 4. Assim, com n bits podemos codificar valores na faixa de 0 at´e 2n − 1. Supondo, agora, uma moeda viciada, que gera a seq¨uˆencia e lan¸camentos KCCCKCCCCC, isto ´e, gerou 2 Karas e 8 Coroas. Se queremos transmitir uma mensagem para esta moeda podemos pensar numa codifica¸c˜ao simples de K=1 e C=0, resultando em 1000100000. Neste caso estamos utilizando 10 bits para os 10 lan¸camentos. Por´em a teoria da informa¸c˜ ao diz que podemos transmitir esta mensagem de um modo mais econˆomico, com apenas 0.722 bits para cada lan¸camento, isto ´e, podemos transmitir os 10 lan¸camentos em menos de 7.22 bits; pois, −(2/10)log2 (2/10) − (8/10)log2 (8/10) = 0.721928. Com ´e feita esta economia de bits? Primeiro, assumimos que a mensagem ´e longa, por exemplo, mil lan¸camentos. Segundo, utilizamos uma codifica¸c˜ao mais inteligente: CC=0, KC=10, CK=110, KK=1110. Assim KCCCKCCCCC = 1001000; neste caso utilizamos apenas 7 bits. Se K ´e um valor pouco freq¨uente, a probabilidade dele ocorrer duas vezes seguido KK ´e bem baixa. Logo, o c´odigo maior 1110 do KK tem pouca probabilidade de acontecer; em mil lan¸camentos provavelmente aconte¸ca. Aqui, a entropia diz quantos bits em m´edia s˜ao necess´arios para transmitir um lan¸camento da moeda. A id´eia da economia depende de um c´odigo de tamanho vari´avel onde os valores mais freq¨uentes recebem os c´odigos menores. Intuitivamente, a entropia aumenta com a variedade dos valores e tamb´em com uma distribui¸c˜ao equilibrada. Para uma moeda n˜ao viciada K=5/10, C=5/10 a 243 244 21. IA: Teoria da Informa¸c˜ ao entropia ´e H([5/10, 5/10])=1 bit. Para uma moeda totalmente viciada K=0/10, C=10/10 a entropia ´e H([0, 1])=0 bit. Ainda, H(KKKKKKKKKK) < H(KKKKCKKKKC) < H(KKKKKCCCCC); 0 < 0.72 < 1. E com variedade: H(KKKKKCCCCC) < H(ABCDABCDAB); 1 < 1.97095; s˜ao 2 valores versus 4 valores. Supondo X uma vari´avel aleat´oria com m valores v1 ...vm e seja P (X = v) a probabilidade de X ter o valor v. Para P (X = v1 ) = p1 ...P (X = vm ) = pm ) a entropia de X ´e: H(X) = −p1 log2 (p1 )... − pm log2 (pm ). Supondo um dado n˜ao viciado, cada face tem 1/6 de probabilidade, H([1/6, 1/6, 1/6, 1/6, 1/6, 1/6]) = 2.58496. Significa que para transmitir um lan¸camento do dado precisamos de quase 2.6 bits. Suponha agora um objeto com trˆes faces ABC, n˜ao viciado, a entropia ´e H([1/3, 1/3, 1/3]) = 1.58496. Como codificar os 10 lan¸camentos ABC ACB CBAA em menos de 16 bits. Uma codifica¸c˜ao pr´oxima da solu¸c˜ao ´e A=0 B=10 C=11, que resulta em 01011 01101 111000. Em resumo, a entropia mede a quantidade de bits necess´arios para transmitir um evento. Para o n´umero ser realista o evento deve ser repetido muitas vezes. Neste cap´ıtulo codificamos alguns predicados para manipular m´etricas baseadas na entropia. Nos predicados calculamos −p∗log2 (p) como −p∗(log(p)/log(2)); pois, log2 (n) = (log(n)/log(2)). ?- inf(8,8,X), Xo is X. X = - (8/ (8+8))*log(8/ (8+8))/log(2)-8/ (8+8)*log(8/ (8+8))/log(2) Xo = 1.0 ?- inf(2,8,X), Xo is X. X = - (2/ (8+2))*log(2/ (8+2))/log(2)-8/ (8+2)*log(8/ (8+2))/log(2) Xo = 0.721928 ?- inf(0,8,X), Xo is X. X = 0, Xo = 0 As perguntas acima exploram o c´alculo da quantidade de informa¸c˜ao para eventos bin´arios Ppositivos e N-negativos, como o lan¸camento de uma moeda. P e N s˜ao as freq¨uˆencias de ocorrˆencias. No c´alculo, usam-se as probabilidades P/(P+N) e N/(P+N). O resultado ´e mostrado simbolicamente como uma f´ormula aritm´etica e tamb´em como um valor. Este modo de apresentar o c´alculo em uma f´ormula facilita o entendimento. Quando o leitor j´a o entendeu, o predicado pode ser modificado para devolver apenas o valor final. Abaixo, a id´eia da quantidade de informa¸c˜ao ´e generalizada para uma vari´avel aleat´oria representada numa lista de probabilidades cujo somat´orio ´e 1, e.g., [6/14, 3/14, 5/14] = 1. Aqui, entropia ´e sinˆonimo de quantidade de informa¸c˜ao. Seguem abaixo v´arios testes. ?- inf([1/2,1/2],X), Xo is X. X = - (1/2)* (log(1/2)/log(2))+ (- (1/2)* (log(1/2)/log(2))+0) Xo = 1.0 ?- inf([10/10, 0/10],X). X = 0.0 ?- inf([2/10,8/10],X), Xo is X. Xo = 0.721928 ?- inf([1/3,1/3,1/3],X), Xo is X. Xo = 1.58496 ?- inf([6/14,3/14,5/14],X), Xo is X. Xo = 1.53062 Segue abaixo o programa principal com os predicados sobre teoria da informa¸c˜ao. 1 2 3 4 %% ia-entropia.pl %% Ganho de Informa¸ c~ ao & Entropia inf([X|Xs],I):- X>0,!, inf(Xs,Is), I = -X*(log(X)/log(2))+Is. inf([X|Xs],I):!, inf(Xs,Is), I = Is. 21.1. Bits e quantidade de informa¸c˜ ao 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 245 inf([],0). inf(P,N,I):- FP=(P/(N+P)), FN=(N/(N+P)),FN>0,FP>0,!, I= -FP*log(FP)/log(2)-FN*log(FN)/log(2). inf(P,N,0). freqAttr( K,LF):-bagof(V,ID^Row^(data(ID,Row),nth1(K,Row,V)),Vs),bins(Vs,LF). freqAttr(IDs,K,LF):-bagof(V,ID^Row^(data(ID,Row),nth1(K,Row,V),member(ID,IDs)),Vs), bins(Vs,LF). freqAttr2( K,L,LF):-bagof((V,Vl),ID^Row^(data(ID,Row), nth1(K,Row,V),nth1(L,Row,Vl)),Vs),bins(Vs,LF). freqAttr2(IDs,K,L,LF):-bagof((V,Vl),ID^Row^(data(ID,Row), nth1(K,Row,V),nth1(L,Row,Vl),member(ID,IDs)),Vs),bins(Vs,LF). entrXY0(IDs,K,L,Io):-freqAttr2(IDs, K,L,F),freqUm(F,LF),inf(LF,I), Io is I. entrXY0( K,L,Io):-freqAttr2(K,L,F),freqUm(F,LF),inf(LF,I), Io is I. entrCondV(L,K,(K1,V1),Eo):- bagof(ID,Row^(data(ID,Row),nth1(K1,Row,V1), member(ID,L)),Lo), entrX(Lo,K,Eo). entrX(IDs,K,I):-freqAttr(IDs, K,F),freqUm(F,LF),inf(LF,I). entrX( K,I):-freqAttr(K,F),freqUm(F,LF),inf(LF,I). entrX0(IDs,K,Io):-freqAttr(IDs, K,F),freqUm(F,LF),inf(LF,I), Io is I. entrX0( K,Io):-freqAttr(K,F),freqUm(F,LF),inf(LF,I), Io is I. %% entropia cond, inf mutua & inf mutua relativa iMutuaRel(L,X,Y,Io):-entrX(L,X,Ex), entrCond(L,X,Y,Eo), Io=(Ex-Eo)/Ex. iMutua(L,X,Y,Io):- entrX(L,X,Ex), entrCond(L,X,Y,Eo), Io is Ex-Eo. iMutuaRel(X,Y,Io):- entrX(X,Ex), entrCond(X,Y,Eo), Io=(Ex-Eo)/Ex. iMutua( X,Y,Io):- entrX(X,Ex), entrCond(X,Y,Eo), Io is Ex-Eo. iMutua_(IDs,X,Y,Mo):-entrXY0(IDs,X,Y,XYo), % outra forma para calcular entrX0(IDs,X,Xo), entrX0(IDs,Y,Yo), Mo is Xo-XYo. iMutua_(X,Y,Mo):-entrXY0(X,Y,XYo),entrX0(X,Xo), entrX0(Y,Yo), Mo is Xo-XYo. entrCond(L,X,Y,Eo):- entrXY0(L,X,Y,Exy),entrX0(L,Y,Ey),Eo is Exy - Ey. entrCond( X,Y,Eo):- entrXY0( X,Y,Exy),entrX0( Y,Ey),Eo is Exy - Ey. %% utils getIDs(L):-setof(ID,Row^data(ID,Row),L). divx(X,Y,Y/X). freqUm(Ls,Lf):-zipper(Ls,As,Bs),sumlist(Bs,S),maplist(divx(S),Bs,Lf). lids(K,Ls,IDs/IDso):- zipper(Ls,As,Bs), bagof((V,ID),Row^(data(ID,Row), nth1(K,Row,V),member(ID,IDs),member(V,As)),IDx), msort(IDx,[(A,I)|Dxo]),mergeX(Dxo,(A,[I]),IDso). mergeX([(A,I)|AVs],(A,IDs),IDso):-!, mergeX(AVs,(A,[I|IDs]),IDso). mergeX([(A,I)|AVs],(B,IDs),[(B,IDs)|IDso]):- mergeX(AVs,(A,[I]),IDso). mergeX([],(A,IDs),[(A,IDs)]). bins(L,Do):-msort(L,[X|LS]),!,freq(LS,X,1,Do). freq([X|Xs],X,N,Ls):-!,N1 is N+1, freq(Xs,X,N1,Ls). freq([X|Xs],Y,N,[(Y,N)|Ls]):-!,freq(Xs,X,1,Ls). freq([],Y,N,[(Y,N)]). zipper([(X-Y)|XYs],[X|Xs],[Y|Ys]):-!,zipper(XYs,Xs,Ys). zipper([(X,Y)|XYs],[X|Xs],[Y|Ys]):-!,zipper(XYs,Xs,Ys). zipper([],[],[]). 246 21.2 21. IA: Teoria da Informa¸c˜ ao Entropia e Entropia conjunta Sejam X e Y duas vari´aveis aleat´orias. H(Y) ´e a entropia de X e H(X,Y) ´e a entropia conjunta das vari´aveis X e Y. H(X,Y) coleta a freq¨uˆencia dos pares (x,y) e calcula a quantidade de informa¸c˜ao necess´aria para transmitir cada par evento. A entropia conjunta ´e sim´etrica: H(X,Y)=H(Y,X). Abaixo mostramos a execu¸c˜ao do predicado freqAttr. Este predicado coleta as freq¨uˆencias de atributo, e.g., F=[(comp,3), (hist,2), (math,4)]. Dada esta lista, o predicado freqUm coleta as probabilidades, e.g., FU=[3/9, 2/9, 4/9]. Esta lista de probabilidades ´e a entrada para a fun¸c˜ao inf que calcula a entropia. O predicado freqAttr2 ´e similar, por´em, coleta os pares (x,y). Os predicados entrX e entrXY implementam, respectivamente, H(X) e H(X,Y). Eles trabalham sobre uma representa¸c˜ao de tabela tipo relacional, ver abaixo. Existem duas vers˜oes do predicado entrX: a primeira calcula a entropia da coluna toda e a segunda, com um parˆametro a mais, permite a escolha das linhas que devem ser consideradas no c´alculo. Por exemplo, abaixo, numa das perguntas calculamos H(X) s´o para as linhas pares. Existem tamb´em as vers˜oes do predicados entrX0 e entrXY0 que retornam apenas um valor num´erico no lugar da express˜ao aritm´etica. ?- mkdata(0). data(1, [math, yes]). data(2, [hist, no]). data(3, [comp, yes]). data(4, [math, no]). data(5, [math, no]). data(6, [comp, yes]). data(7, [hist, no]). data(8, [math, yes]). %% ?- freqAttr(2,F). F = [ (no, 4), (yes, 4)] ?- freqAttr(2,F),freqUm(F,FU). F = [ (no, 4), (yes, 4)] FU = [4/8, 4/8] ?- freqAttr(1,F),freqUm(F,FU). F = [ (comp, 2), (hist, 2), (math, 4)] FU = [2/8, 2/8, 4/8] ?- freqAttr([2,4,6,8],1,F),freqUm(F,FU). F = [ (comp, 1), (hist, 1), (math, 2)] FU = [1/4, 1/4, 2/4] ?- freqAttr2([2,4,6,8],1,2,F). F = [ ((comp, yes), 1), ((hist, no), 1), ((math, no), 1), ((math, yes), 1)] ?- ?- entrX(2,X), Xo is X. X = - (4/8)* (log(4/8)/log(2))+ (- (4/8)* (log(4/8)/log(2))+0) Xo = 1.0 ?- entrX([2,4,6,8],1,X), Xo is X. X=-(1/4)*(log(1/4)/log(2))+(-(1/4)*(log(1/4)/log(2))+(-2/4)*(log(2/4)/log(2)))) Xo = 1.5 ?- entrXY0(1,2,X). X = 2.0 ?- entrXY0(2,1,X). X = 2.0 ?- entrX0(1,X). X = 1.5 ?- entrX0(2,X). X = 1.0 21.3. Entropia condicional e Informa¸c˜ ao m´ utua 21.3 247 Entropia condicional e Informa¸c˜ ao m´ utua Sejam X e Y duas vari´aveis aleat´orias. H(X|Y) ´e a Entropia condicional e I(X;Y) ´e a Informa¸c˜ ao mutua. Em H(X|Y), a entropia de X condicionada a Y ´e o n´umero de bits necess´arios para transmitir X se ambos os lados j´a conhecem Y. Ela ´e calculada a partir da entropia conjunta: H(X|Y) = H(X,Y)-H(Y). A informa¸c˜ao m´utua, I(X;Y), ´e sinˆonimo de ganho de informa¸c˜ ao: se j´a conhecemos X para codificar Y economizamos I(X;Y) de informa¸c˜ao. Ela tamb´em ´e sim´etrica, I(X;Y)=I(Y;X). Ela pode ser calculada a partir da entropia condicional, I(X;Y)= H(X)-H(X|Y), ou a partir da entropia conjunta, I(Y;X)= H(X)+H(Y)-H(X,Y). Ainda, relacionada com a informa¸c˜ao m´utua temos a informa¸c˜ ao mutua relativa, IR(X|Y)= (H(X)-H(X|Y))/H(X). Ela diz o percentual de X que ´e necess´ario transmitir se ambos j´a conhecem Y. Um fato bem importante ´e que as medidas de entropia condicional e informa¸c˜ao mutua relativa s˜ao assim´etricas. Em IA temos muitas medidas sim´etricas e poucas assim´etricas. Em muitos problemas precisamos de medidas assim´etricas. A palavra condicional tem rela¸c˜ao com uma implica¸c˜ao, com a no¸c˜ao de causalidade; o conceito de causalidade numa rede Bayesiana ´e direcional, assim´etrico. Por fim, temos tamb´em a entropia condicional restrita a um valor H(X|Y=v) que ´e a entropia da coluna X restrita as linhas em que Y tem o valor v. Seguem abaixo os testes para estes predicados: entrCondV, entrCond, iMutua e iMutuaRel. Alguns testes destacam a assimetria da iMutuaRel e da entrCond. ?- mkdata(0). ?- entrCondV([1,2,3,4,5,6,7,8],2,(1,hist),P),Po is P. P = - (2/2)* (log(2/2)/log(2))+0 Po = 0.0 ?- entrCondV([1,2,3,4,5,6,7,8],2,(1,math),P), Po is P. P = - (2/4)* (log(2/4)/log(2))+ (- (2/4)* (log(2/4)/log(2))+0) Po = 1.0 ?- entrCond([1,2,3,4,5,6,7,8],1,2,E). E = 1.0 ?- entrXY0(1,2,X). X = 2.0 ?- entrXY0(2,1,X). X = 2.0 ?- entrX0(1,X). X = 1.5 ?- entrX0(2,X). X = 1.0 ?- entrCond(2,1,X). X = 0.5 ?- entrCond(1,2,X). X = 1.0 ?- iMutuaRel(2,1,M), Mo is M. Mo = 0.5 21.4 Escolha de atributos Seguem abaixo trˆes tabelas usadas nos testes do predicados codificados neste cap´ıtulo. Temos tamb´em algum testes que geram os valores de entropia condicional e informa¸c˜ao m´utua para todas as combina¸c˜oes de atributos de uma tabela. 1 2 3 4 pre_test_data(0, [math, yes], [hist, no], [comp, yes], [[xx,yy], 248 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 [math, [math, [comp, [hist, [math, 21. IA: Teoria da Informa¸c˜ ao no], no], yes], no], yes] ] ).

%% pre_test_data(10,[ [outlook, temp, humidity, wind, playTennis], [sunny, hot, high, weak, no], [sunny, hot, high, strong,no], [overcast,hot, high, weak, yes], [rain, mild, high, weak, yes], [rain, cool, nml, weak, yes], [rain, cool, nml, strong, no], [overcast,cool,nml, strong, yes], [sunny, mild, high, weak, no], [sunny, cool, nml, weak, yes], [rain, mild, nml, weak, yes], [sunny, mild, nml, strong, yes], [overcast,mild,high, strong, yes], [overcast,hot, nml, weak, yes], [rain, mild, high, strong, no]]). %% pre_test_data(13,[ [cdcli, classe, sal, id, depto], [a1, high ,10 ,a ,no], [a2, high ,10 ,b ,no], [a3, high ,10 ,c ,no], [a4, med ,20 ,d ,yes], [a5, low ,30 ,d ,yes], [a6, low ,30 ,f ,yes], [a7, low ,30 ,g ,yes]]). %% all_e(DOM,(D1,D2,Eo)):-member(D1,DOM),member(D1,DOM), member(D2,DOM), entrCond(D1,D2,E),Eo is E. all_g(DOM,(D1,D2,Eo)):-member(D1,DOM),member(D1,DOM), member(D2,DOM), D1=

Como comparar em prolog o valos de x

Postagens relacionadas

Publicidade

ÚLTIMAS NOTÍCIAS

Toplistas

Publicidade

Populer

Publicidade

Sobre

Jurídica

Ajuda

Social