Programac¸˜ao em Prolog ´ UMA ABORDAGEM PRATICA Eloi L. Favero Departamento de Inform´atica CCEN - UFPA (Vers˜ao 2006) [email protected] • Parte I: Fundamentos e Te´cnicas de Programac¸a˜o – 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 • Parte III: Estudos de Casos e Aplicac¸o˜es – 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] Copyright (cid:13)c 2006 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; equeumaboalinguagemdeprograma¸c˜ao´eumapoderosaferramenta 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 pu´blicos, 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 pu´blico-alvo, diferentes cap´ıtulos e se¸c˜oes do livro s˜ao usados. No final deste pref´acio sugerimos algumas sequ¨ˆ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. Aabordagemdolivro´eessencialmentepr´atica, emoposi¸c˜aoaoenfoquete´oricodaPrograma¸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 rela- cionado ao ditado que diz: o talento nasce da pr´atica fiel. A habilidade de desenvolver progra- mas pensando em Prolog nasce de atividades pr´aticas de programa¸c˜ao. Para isso, apresentamos inu´meros exerc´ıcios associados a cada novo assunto apresentado. Por outro lado, em especial na terceirapartedolivro, apresentamosestudosdecasosbaseadosemproblemascoletadosemdiversas 1Usamos 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 Desdeosurgimento,in´ıciodosanos70,oPrologmant´emsuapopularidadedevido`acombina¸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 ClauseGrammar(DCG),que´eessencialparaodesenvolvimentodeaplica¸c˜oes(ouprot´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 automod- ificar. 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,veioafirmarasintaxedoPrologEdimburgocomopadr˜ao,apenasapresentandoumconjunto 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 pos- itivas 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 co´digo: 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 identificarpossibilidadesdereusodepredicados. Porexemplo, opredicadoappend(paraconcatenar 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. OProlog´ebaseadonumsistemaderesolu¸c˜aoassociadoaumprocessodeunifica¸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 van- tagens 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 sequ¨ˆ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 Lingu¨´ı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(60horas). Olivro´eindicadoparaapartedalinguagem 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 Computac¸˜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.