Docsity
Docsity

Prepare-se para as provas
Prepare-se para as provas

Estude fácil! Tem muito documento disponível na Docsity


Ganhe pontos para baixar
Ganhe pontos para baixar

Ganhe pontos ajudando outros esrudantes ou compre um plano Premium


Guias e Dicas
Guias e Dicas

Introdução à programação, Notas de estudo de Cultura

INTRODUÇÃO À PROGRAMAÇÃO PROLOG

Tipologia: Notas de estudo

Antes de 2010

Compartilhado em 24/04/2009

emanuel-messias-ramos-7
emanuel-messias-ramos-7 🇧🇷

2 documentos

Pré-visualização parcial do texto

Baixe Introdução à programação e outras Notas de estudo em PDF para Cultura, somente na Docsity! INTRODUÇÃO À PROGRAMAÇÃO PROLOG Luiz A. M. Palazzo Editora da Universidade Católica de Pelotas / UCPEL Rua Félix da Cunha, 412 - Fone (0532)22-1555 - Fax (0532)25-3105 Pelotas - RS - Brasil EDUCAT Editora da Universidade Católica de Pelotas Pelotas, 1997 © 1997 LUIZ A. M. PALAZZO SUMÁRIO 1. LÓGICA E PROGRAMAÇÃO DE COMPUTADORES 1 1.1 AS RAÍZES 1 1.2 PROGRAMAÇÃO EM LÓGICA 2 1.3 APLICAÇÕES 4 1.4 A QUINTA GERAÇÃO 6 1.5 PORQUE ESTUDAR PROLOG 8 RESUMO 9 2. A LINGUAGEM PROLOG 11 2.1 FATOS 11 2.2 REGRAS 14 2.3 CONSTRUÇÕES RECURSIVAS 17 2.4 CONSULTAS 19 2.5 O SIGNIFICADO DOS PROGRAMAS PROLOG 21 RESUMO 22 EXERCÍCIOS 22 3. SINTAXE E SEMÂNTICA 24 3.1 OBJETOS 24 3.2 UNIFICAÇÃO 27 3.3 SEMÂNTICA DECLARATIVA E SEMÂNTICA PROCEDIMENTAL 28 3.4 SEMÂNTICA OPERACIONAL 30 RESUMO 30 EXERCÍCIOS 31 4. OPERADORES E ARITMÉTICA 33 4.1 OPERADORES 33 4.2 ARITMÉTICA 36 RESUMO 38 EXERCÍCIOS 39 5. PROCESSAMENTO DE LISTAS 41 5.1 REPRESENTAÇÃO DE LISTAS 41 5.2 OPERAÇÕES SOBRE LISTAS 42 5.3 OUTROS EXEMPLOS 48 RESUMO 49 EXERCÍCIOS 50 6. CONTROLE 51 6.1 BACKTRACKING 51 6.2 O OPERADOR "CUT" 52 6.3 APLICAÇÕES DO CUT 56 6.4 NEGAÇÃO POR FALHA 57 6.5 CUIDADOS COM O CUT E A NEGAÇÃO 58 RESUMO 60 EXERCÍCIOS 60 7. ESTRUTURAS DE DADOS 62 7.1 RECUPERAÇÃO DE INFORMAÇÕES 62 7.2 ABSTRAÇÃO DE DADOS 64 7.3 UM AUTÔMATO FINITO NÃO-DETERMINÍSTICO 65 7.4 PLANEJAMENTO DE ROTEIROS AÉREOS 67 RESUMO 69 EXERCÍCIOS 69 8. ENTRADA E SAÍDA 71 8.1 ARQUIVOS DE DADOS 71 8.2 PROCESSAMENTO DE ARQUIVOS DE TERMOS 73 8.3 PROCESSAMENTO DE CARACTERES 77 8.4 CONVERSÃO DE TERMOS 78 8.5 LEITURA DE PROGRAMAS 79 RESUMO 80 EXERCÍCIOS 80 9. PREDICADOS EXTRALÓGICOS 82 9.1 TIPOS DE TERMOS 82 9.2 CONSTRUÇÃO E DECOMPOSIÇÃO DE TERMOS 84 9.3 EQUIVALÊNCIAS E DESIGUALDADES 85 9.4 PROGRAMAS OU BASES DE DADOS? 86 9.5 RECURSOS PARA O CONTROLE DE PROGRAMAS 89 1 1. LÓGICA E PROGRAMAÇÃO DE COMPUTADORES A lógica é a ciência do pensamento correto1. Esta declaração não implica contudo em afirmar que ela seja a ciência da verdade. Mesmo que tudo o que se permita afirmar dentro da lógica seja suposta- mente verdadeiro em determinado contexto, as mesmas afirmações podem resultar falsas se aplicadas ao mundo real. Os filósofos da lógica afirmam que, "para entender o que realmente acontece no mun- do, precisamos entender o que não acontece", isto é, as propriedades invariantes das entidades ou objetos que o compõem. Com essa idéia em mente, podemos considerar lógicos os conjuntos de de- clarações que possuem a propriedade de ser verdadeiros ou falsos independentemente do tempo ou lugar que ocupam no universo considerado. Este insigth inicial costuma ser de grande valia para en- tender como a lógica pode ser empregada na programação de computadores com grande vantagem sobre as linguagens convencionais. O cálculo proposicional, que é o subconjunto da lógica matemáti- ca mais diretamente envolvido nesse processo, formaliza a estrutura lógica mais elementar do discurso definindo precisamente o significado dos conetivos e, ou, não, se...então e outros. No presente capí- tulo esboça-se a forma como evoluiu a idéia de empregar a lógica como linguagem de programação de computadores, comenta-se os principais usos e aplicações das linguagens baseadas na lógica, relata-se os resultados mais significativos obtidos ao longo dos dez anos do controvertido projeto japonês para o desenvolvimento dos denominados "Computadores de Quinta Geração" e, por fim, se tenta antecipar as perspectivas mais promissoras da pesquisa neste ramo do conhecimento científico. 1.1 AS RAÍZES O uso da lógica na representação dos processos de raciocínio remonta aos estudos de Boole (1815- 1864) e de De Morgan (1806-1871), sobre o que veio a ser mais tarde chamado "Álgebra de Boole". Como o próprio nome indica, esses trabalhos estavam mais próximos de outras teorias matemáticas do que propriamente da lógica. Deve-se ao matemático alemão Göttlob Frege no seu "Begriffsschrift" (1879) a primeira versão do que hoje denominamos cálculo de predicados, proposto por ele como uma ferramenta para formalizar princípios lógicos. Esse sistema oferecia uma notação rica e consistente que Frege pretendia adequada para a representação de todos os conceitos matemáticos e para a for- malização exata do raciocínio dedutivo sobre tais conceitos, o que, afinal, acabou acontecendo. No final do século passado a matemática havia atingido um estágio de desenvolvimento mais do que propício à exploração do novo instrumento proposto por Frege. Os matemáticos estavam abertos a novas áreas de pesquisa que demandavam profundo entendimento lógico assim como procedimentos sistemáticos de prova de teoremas mais poderosos e eficientes do que os até então empregados. Al- guns dos trabalhos mais significativos deste período foram a reconstrução axiomática da geometria abstrata por David Hilbert, a aritimética proposta por Giuseppe Peano e a exploração intuitiva da teo- ria geral dos conjuntos, por Georg Cantor, que também produziu a iluminada teoria dos números transfinitos. O relacionamento entre lógica e matemática foi profundamente investigado por Alfred North Whitehead e Bertrand Russel, que em "Principia Mathematica" (1910) demonstraram ser a ló- gica um instrumento adequado para a representação formal de grande parte da matemática. Um passo muito importante foi dado em 1930, em estudos simultâneos, porém independentes, reali- zados pelo alemão Kurt Gödel e o francês Jacques Herbrand. Ambos, em suas dissertações de douto- rado, demonstraram que o mecanismo de prova do cálculo de predicados poderia oferecer uma prova formal de toda proposição logicamente verdadeira. O resultado de maior impacto foi entretanto pro- duzido por Gödel, em 1931, com a descoberta do "teorema da incompleteza dos sistemas de formali- zação da aritmética". A prova deste teorema se baseava nos denominados paradoxos de auto- referência (declarações do tipo: "Esta sentença é falsa", que não podem ser provadas nem verdadeiras 1 Na realidade, de uma certa classe de pensamento correto. 2 nem falsas). Em 1934, Alfred Tarski produziu a primeira teoria semântica rigorosamente formal do cálculo de predicados, introduzindo conceitos precisos para "satisfatibilidade", "verdade" (em uma dada interpretação), "conseqüência lógica" e outras noções relacionadas. Ainda na década de 30, di- versos outros estudos - entre os quais os de Alan Turing, Alonzo Church e outros - aproximaram muito o cálculo de predicados da forma com que é hoje conhecido e estudado. No início da Segunda Guerra Mundial, em 1939, toda a fundamentação teórica básica da lógica com- putacional estava pronta. Faltava apenas um meio prático para realizar o imenso volume de computa- ções necessárias aos procedimentos de prova. Apenas exemplos muito simples podiam ser resolvidos manualmente. O estado de guerra deslocou a maior parte dos recursos destinados à pesquisa teórica, nos EUA, Europa e Japão para as técnicas de assassinato em massa. Foi somente a partir da metade dos anos 50 que o desenvolvimento da então novíssima tecnologia dos computadores conseguiu ofe- recer aos pesquisadores o potencial computacional necessário para a realização de experiências mais significativas com o cálculo de predicados. Em 1958, uma forma simplificada do cálculo de predicados denominada forma clausal começou a despertar o interesse dos estudiosos do assunto. Tal forma empregava um tipo particular muito sim- ples de sentença lógica denominada cláusula. Uma cláusula é uma (possivelmente vazia) disjunção de literais. Também por essa época, Dag Prawitz (1960) propôs um novo tipo de operação sobre os ob- jetos do cálculo de predicados, que mais tarde veio a ser conhecida por unificação. A unificação se revelou fundamental para o desenvolvimento de sistemas simbólicos e de programação em lógica. A programação em lógica em sistemas computacionais, entretanto, somente se tornou realmente pos- sível a partir da pesquisa sobre prova automática de teoremas, particularmente no desenvolvimento do Princípio da Resolução por J. A. Robinson (1965). Um dos primeiros trabalhos relacionando o Prin- cípio da Resolução com a programação de computadores deve-se a Cordell C. Green (1969) que mos- trou como o mecanismo para a extração de respostas em sistemas de resolução poderia ser empregado para sintetizar programas convencionais. A expressão "programação em lógica" (logic programming, originalmente em inglês) é devido a Ro- bert Kowalski (1974) e designa o uso da lógica como linguagem de programação de computadores. Kowalski identificou, em um particular procedimento de prova de teoremas, um procedimento com- putacional, permitindo uma interpretação procedimental da lógica e estabelecendo as condições que nos permitem entendê-la como uma linguagem de programação de uso geral. Este foi um avanço es- sencial, necessário para adaptar os conceitos relacionados com a prova de teoremas às técnicas com- putacionais já dominadas pelos programadores. Aperfeiçoamentos realizados nas técnicas de imple- mentação também foram de grande importância para o emprego da lógica como linguagem de pro- gramação. O primeiro interpretador experimental foi desenvolvido por um grupo de pesquisadores liderados por Alain Colmerauer na Universidade de Aix-Marseille (1972) com o nome de Prolog, um acrônimo para "Programmation en Logique". Seguindo-se a este primeiro passo, implementações mais "praticas" foram desenvolvidas por Battani e Meloni (1973), Bruynooghe (1976) e, principalmente, David H. D. Warren, Luís Moniz Pereira e outros pesquisadores da Universidade de Edimburgo (U.K.) que, em 1977, formalmente definiram o sistema hoje denominado "Prolog de Edimburgo", usado como referência para a maioria das atuais implementações da linguagem Prolog. Deve-se tam- bém a Warren a especificação da WAM (Warren Abstract Machine), um modelo formal empregado até hoje na pesquisa de arquiteturas computacionais orientadas à programação em lógica. 1.2 PROGRAMAÇÃO EM LÓGICA Uma das principais idéias da programação em lógica é de que um algoritmo é constituído por dois elementos disjuntos: a lógica e o controle. O componente lógico corresponde à definição do que deve ser solucionado, enquanto que o componente de controle estabelece como a solução pode ser obtida. O programador precisa somente descrever o componente lógico de um algoritmo, deixando o controle 3 da execução para ser exercido pelo sistema de programação em lógica utilizado. Em outras palavras, a tarefa do programador passa a ser simplesmente a especificação do problema que deve ser soluciona- do, razão pela qual as linguagens lógicas podem ser vistas simultaneamente como linguagens para especificação formal e linguagens para a programação de computadores. Um programa em lógica é então a representação de determinado problema ou situação expressa atra- vés de um conjunto finito de um tipo especial de sentenças lógicas denominadas cláusulas. Ao contrá- rio de programas em Pascal ou C, um programa em lógica não é a descrição de um procedimento para se obter a solução de um problema. Na realidade o sistema utilizado no processamento de programas em lógica é inteiramente responsável pelo procedimento a ser adotado na sua execução. Um programa em lógica pode também ser visto alternativamente como uma base de dados, exceto que as bases de dados convencionais descrevem apenas fatos tais como "Oscar é um avestruz", enquanto que as sen- tenças de um programa em lógica possuem um alcance mais genérico, permitindo a representação de regras como em "Todo avestruz é um pássaro", o que não possui correspondência em bases de dados convencionais. Na figura abaixo se procura explicitar as principais diferenças entre programação con- vencional e programação em lógica. PROGRAMAS CONVENCIONAIS PROGRAMAS EM LÓGICA Processamento Numérico Processamento Simbólico Soluções Algorítmicas Soluções Heurísticas Estruturas de Controle e Conhecimento Integradas Estruturas de Controle e Conhecimento Separadas Difícil Modificação Fácil Modificação Somente Respostas Totalmente Corretas Incluem Respostas Parcialmente Corretas Somente a Melhor Solução Possível Incluem Todas as Soluções Possíveis Figura 1.1 Programas Convencionais x Programas em Lógica O paradigma fundamental da programação em lógica é o da programação declarativa, em oposição à programação procedimental típica das linguagens convencionais. A programação declarativa engloba também a programação funcional, cujo exemplo mais conhecido é a linguagem Lisp. Lembrando en- tretanto que Lisp data de 1960, a programação funcional é um estilo conhecido há bastante tempo, ao contrário da programação em lógica, que só ganhou ímpeto a partir dos anos 80, quando foi escolhida como a linguagem básica do projeto japonês para o desenvolvimento dos denominados computadores de quinta geração. O ponto focal da programação em lógica consiste em identificar a noção de com- putação com a noção de dedução. Mais precisamente, os sistemas de programação em lógica reduzem a execução de programas à pesquisa da refutação das sentenças do programa em conjunto com a ne- gação da sentença que expressa a consulta, seguindo a regra: "uma refutação é a dedução de uma contradição". Pode-se então expressar conhecimento (programas e/ou dados) em Prolog por meio de cláusulas de dois tipos: fatos e regras2. Um fato denota uma verdade incondicional, enquanto que as regras defi- nem as condições que devem ser satisfeitas para que uma certa declaração seja considerada verdadei- ra. Como fatos e regras podem ser utilizados conjuntamente, nenhum componente dedutivo adicional precisa ser utilizado. Além disso, como regras recursivas e não-determinismo são permitidos, os pro- gramadores podem obter descrições muito claras, concisas e não-redundantes da informação que de- sejam representar. Como não há distinção entre argumentos de entrada e de saída, qualquer combina- ção de argumentos pode ser empregada. Os termos "programação em lógica" e "programação Prolog" tendem a ser empregados indistinta- mente. Deve-se, entretanto, destacar que a linguagem Prolog é apenas uma particular abordagem da programação em lógica. As características mais marcantes dos sistemas de programação em lógica em geral - e da linguagem Prolog em particular - são as seguintes: 2 Ver o Apêndice A para uma abordagem mais formal. 6 tões sobre a estrutura de sentenças em linguagem natural fossem formuladas como objetivos ao sistema, e (3) que diferentes procedimentos de prova aplicados a representações lógicas da lin- guagem natural correspondiam a diferentes estratégias de análise. • Educação: A programação em lógica poderá vir a oferecer no futuro uma contribuição bastante significativa ao uso educacional de computadores. Esta proposta foi testada em 1978 quando Kowalski introduziu a programação em lógica na Park House Middle School em Wimbledon, na Inglaterra, usando acesso on-line aos computadores do Imperial College. O sucesso do em- preendimento conduziu a um projeto mais abrangente denominado "Lógica como Linguagem de Programação para Crianças", inaugurado em 1980 na Inglaterra com recursos do Conselho de Pesquisa Científica daquele país. Os resultados obtidos desde então tem mostrado que a pro- gramação em lógica não somente é assimilada mais facilmente do que as linguagens convenci- onais, como também pode ser introduzida até mesmo a crianças na faixa dos 10 a 12 anos, as quais ainda se beneficiam do desenvolvimento do pensamento lógico-formal que o uso de lin- guagens como o Prolog induz. • Arquiteturas Não-Convencionais: Esta área vem se tornando cada vez mais um campo extre- mamente fértil para o uso da programação em lógica especialmente na especificação e imple- mentação de máquinas abstratas de processamento paralelo. O paralelismo pode ser modelado pela programação em lógica em variados graus de atividade se implementado em conjunto com o mecanismo de unificação. Duas implementações iniciais nesse sentido foram o Parlog, des- envolvido em 1984 por Clark e Gregory, e o Concurrent Prolog (CP), por Shapiro em 1983. O projeto da Quinta Geração, introduzido na próxima seção, foi fortemente orientado ao uso da programação em lógica em sistemas de processamento paralelo. Muitas outras aplicações poderiam ainda ser citadas, principalmente na área da inteligência artificial, que tem no Prolog e no Lisp as suas duas linguagens mais importantes. Novas tecnologias de hardwa- re e software tais como sistemas massivamente paralelos, redes de computadores, assistentes inteli- gentes, bases de dados semânticas, etc., tornam o uso do Prolog (e de outras linguagens baseadas em lógica) cada vez mais atraentes 1.4 A QUINTA GERAÇÃO Em 1979 o governo japonês iniciou estudos para um novo, ambicioso e único projeto na área da com- putação normalmente denominado Sistemas Computacionais de Quinta Geração cujo objetivo princi- pal era o desenvolvimento, no espaço de uma década, de hardware e software de alto desempenho, caracterizando uma nova geração de computadores. O projeto iniciou em 1982 e foi oficialmente en- cerrado em maio de 1992. Muito foi dito e escrito sobre o projeto, que produziu inúmeros resultados e diversos subprodutos ao longo desses dez anos. Um de seus principais méritos, entretanto, parece ter sido chamar a atenção da comunidade científica mundial para as potencialidades da lógica como lin- guagem de programação de computadores. Sistemas de processamento lógico paralelo derivados do Prolog foram desenvolvidos para servir como linguagens-núcleo (kernel languages) dos novos equi- pamentos que seriam produzidos a partir dos resultados do projeto. Considerado um sucesso por seus dirigentes, o projeto foi entretanto criticado por não haver conseguido colocar as tecnologias desen- volvidas à disposição do grande público. Em outras palavras: ainda não dispomos hoje (1994) de mi- crocomputadores pessoais de quinta geração - denominados máquinas PSI (Personal Sequential Infe- rence machines) - comercialmente viáveis para o grande público. Os resultados teóricos obtidos e os protótipos construídos foram entretanto de grande valia para que num futuro próximo isso venha a ser possível. Nestas novas máquinas o papel da linguagem assembly será desempenhado por um dialeto do Prolog orientado ao processamento paralelo. Um relatório sobre o projeto, organizado por Ehud Shapiro e David Warren em 1993, reuniu as opini- ões de diversos pesquisadores dele participantes, entre os quais Kazuhiro Fuchi, seu líder, Robert Kowalski, Koichi Furukawa, Kazunori Ueda e outros. Todos os depoimentos foram unânimes em 7 declarar que os objetivos do projeto foram plenamente atingidos. Na Figura 1.2 é mostrada uma adaptação em português do diagrama "de intenções" apresentado por Fuchi, no Fifth Generation Computer Systems Congress de 1981 (FGCS'81), o congresso que deu a conhecer ao mundo um dos mais ambiciosos projetos da história da computação. ANO 1 ANO 5 ANO 10  Network --- Ótica ---  Personal Inference Machine (Redução a chips) Máquina Prolog +  (Novo Software) LISP APL Smalltalk PS, etc. Programação: em lógica e funcional (comparáveis às máquinas de grande porte de 1981)  Ambientes de Programação Inteligentes  Ambientes de Projeto Orientados à Prototipagem  Máquinas Altamente Configuráveis (Chips e Módulos)  Supermáquinas (Realmente Inteligentes) Nova Linguagem 5G Core Language (INFERENCE MACHINE) Data Flow Machine Database Machine Paralelismo Associatividade  SOFTWARE -----------> Engenharia de Conhecimento (Acumulação) ---------------------------------------------------------> Engenharia de Software (Teorias Básicas) Pesquisa em Inteligência Artificial Solução de Problemas: Bases de Conhecimento: Simbolismo em Alto Nível: Planejamento Programação Prova de Teoremas Jogos Entendimento da Linguagem Natural Consultas Figura 1.2 Diagrama Conceitual do Projeto do Computador de Quinta Geração Segundo o relatório de Shapiro e Warren, um dos primeiros passos do projeto consistiu em definir uma linguagem de programação em lógica que ao mesmo tempo fosse adequada ao paralelismo do hardware e aos requisitos sofisticados especificados para o software. Baseada no Parlog e no Cuncur- rent Prolog, uma equipe de pesquisadores liderada por Kazunori Ueda desenvolveu a linguagem GHC (Guarded Horn Clauses), que deu origem à KL0 (Kernel Language Zero). Um refinamento dessa ver- são beta4, realizado pela equipe de Takashi Chikayama produziu, em 1987, a linguagem KL1. Todos os sub-projetos do FGCS foram revistos para trabalhar com essa linguagem. Em 1988 os primeiros protótipos do computador de quinta geração foram construídos, recebendo o nome genérico de Pa- rallel Inference Machines (PIMs). Tais computadores possuiam arquitetura massivamente paralela e tinham velocidade de processamento calculada em MLIPS (milhões de inferências lógicas por segun- do). Uma dessas máquinas, denominada Multi-PSI foi apresentada com grande sucesso no FGCS'88. 4 Uma versão distribuida a grupos selecionados de usuários para teste e depuração. 8 A linguagem KL1 foi empregada para escrever o sistema operacional PIMOS (Parallel Inference Ma- chine Operating System), em 1988. É importante ressaltar aqui que a linguagem KL1 é uma lingua- gem de muito alto nível5 e, ao mesmo tempo, uma linguagem de máquina, isto é, adequada à progra- mação a nível de registradores, posições de memória e portas lógicas. As versões mais recentes do PIMOS provam definitivamente que KL1 (agora já KL2) é uma linguagem muito mais adequada do que as linguagens convencionais para a construção de software básico em máquinas paralelas. Outras linguagens de programação foram - e ainda vem sendo - pesquisadas. Por exemplo, uma linguagem de programação em lógica com restrições denominada GDCC foi projetada em um nível ainda mais alto que a KL1. Uma outra linguagem, denominada "Quixote" foi produzida para lidar com bases de dados dedutivas e orientadas a objetos. Para o gerenciamento de sistemas paralelos distribuídos foi especifi- cada a linguagem Kappa-P. Todas essas linguagens, com as quais - ou com seus dialetos - todos cer- tamente estaremos em contato num futuro próximo, estão baseadas nos conceitos e resultados da pes- quisa em programação em lógica. Tecnicamente considera-se que o projeto atingiu a primeira parte de seus objetivos: diversos compu- tadores paralelos foram construídos. Tais computadores são denominados coletivamente de máquinas de inferência paralela (PIMs), incorporam a linguagem KL1 e o sistema operacional PIMOS. Além disso as máquinas PIM mais recentemente construídas lograram atingir um pico de desempenho da ordem de 1 gigalips (1 bilhão de inferências lógicas por segundo), o que era um dos objetívos con- cretos do projeto considerados mais difíceis de atingir. A segunda parte do projeto, entretanto, a construção de máquinas orientadas à bases de dados (data- base machines) foi menos claramente abordada. Tal objetivo foi reformulado a partir do sucesso obti- do com a construção de linguagens de programação em lógica concorrente para a construção de im- plementações baseadas em KL1 na mesma plataforma de hardware das máquinas PIM. De um modo geral, entretanto, considera-se que o projeto demonstrou ser a tecnologia PIM bem suce- dida em novas aplicações envolvendo paralelismo em diversas áreas, especialmente computação não- numérica e inteligência artificial. Em suma, segundo o relatório Shapiro-Warren: "(...) uma ponte foi construída entre a computação paralela e as aplicações envolvendo inte- ligência artificial. Entretanto, as duas extremidades finais da ponte ainda se encontram por concluir e a ponte em si é mais frágil do que poderia ter sido. É sem dúvida ainda muito cedo para se esperar que a ponte seja inaugurada recebendo uma grande aclamação." 1.5 PORQUE ESTUDAR PROLOG Normalmente há um gap de 10 a 20 anos entre o estágio básico de uma pesquisa tecnológica e o mo- mento em que esta é colocada à disposição da sociedade consumidora. Na área de informática esse intervalo costuma ser menor, entretanto, estamos assistindo a uma completa transformação: do para- digma da quarta geração, ora em fase de esgotamento6 para arquiteturas inovadoras, contemplando sistemas de processamento paralelo, a concorrência de processos e layers baseados em lógica. A grande explosão da informática atualmente persegue conceitos tais como interoperabilidade, conecti- vidade, orientação a objetos, sistemas multimídia, agentes inteligentes cooperativos, hiperdocumen- tos, realidade virtual, inteligência de máquina e outros, cuja evolução irá determinar nos próximos anos uma mudança tão radical quanto foi a das carruagens para os veículos automotores - mais ainda, segundo alguns autores, - terminando por transformar completamente a própria estrutura social. A programação Prolog é uma excelente porta de entrada para a informática do futuro, tendo em vista 5 Quanto mais alto o nível de uma linguagem, mais próxima da linguagem natural ela se encontra. 6 As atuais tecnologias de integração de circuitos (VLSI/ULSI) tendem a atingir os limites físicos além dos quais se tornam economicamente inviáveis. 11 2. A LINGUAGEM PROLOG A principal utilização da linguagem Prolog reside no domínio da programação simbólica, não- numérica, sendo especialmente adequada à solução de problemas, envolvendo objetos e relações entre objetos. O advento da linguagem Prolog reforçou a tese de que a lógica é um formalismo conveniente para representar e processar conhecimento. Seu uso evita que o programador descreva os procedi- mentos necessários para a solução de um problema, permitindo que ele expresse declarativamente apenas a sua estrutura lógica, através de fatos, regras e consultas. Algumas das principais característi- cas da linguagem Prolog são: • É uma linguagem orientada ao processamento simbólico; • Representa uma implementação da lógica como linguagem de programação; • Apresenta uma semântica declarativa inerente à lógica; • Permite a definição de programas reversíveis, isto é, programas que não distinguem entre os argumentos de entrada e os de saída; • Permite a obtenção de respostas alternativas; • Suporta código recursivo e iterativo para a descrição de processos e problemas, dispensando os mecanismos tradicionais de controle, tais como while, repeat, etc; • Permite associar o processo de especificação ao processo de codificação de programas; • Representa programas e dados através do mesmo formalismo; • Incorpora facilidades computacionais extralógicas e metalógicas. No presente capítulo introduz-se informalmente os conceitos essenciais da linguagem Prolog, visando conduzir rapidamente o leitor ao domínio da sintaxe e a um entendimento intuitivo da semântica asso- ciada aos programas. 2.1 FATOS Considere a árvore genealógica mostrada na Figura 2.1. É possível definir, entre os objetos (indivídu- os) mostrados, uma relação denominada progenitor que associa um indivíduo a um dos seus progeni- tores. Por exemplo, o fato de que João é um dos progenitores de José pode ser denotado por: progenitor(joão, josé). onde progenitor é o nome da relação e joão e josé são os seus argumentos. Por razões que se tornarão claras mais tarde, escreve-se aqui nomes de pessoas (como João) iniciando com letra minúscula. A relação progenitor completa, como representada na figura acima pode ser definida pelo seguinte pro- grama Prolog: progenitor(maria, josé). progenitor(joão, josé). progenitor(joão, ana). progenitor(josé, júlia). progenitor(josé, íris). progenitor(íris, jorge). O programa acima compõe-se de seis cláusulas, cada uma das quais denota um fato acerca da relação progenitor. Se o programa for submetido a um sistema Prolog, este será capaz de responder algumas questões sobre a relação ali representada. Por exemplo: "José é o progenitor de Íris?". Uma consulta como essa deve ser formulada ao sistema precedida por um "?-". Esta combinação de sinais denota que se está formulando uma pergunta. Como há um fato no programa declarando explicitamente que 12 José é o progenitor de Íris, o sistema responde "sim". ?-progenitor(josé, íris). sim Maria João José Ana Júlia Íris Jorge Figura 2.1 Uma árvore genealógica Uma outra questão poderia ser: "Ana é um dos progenitores de Jorge?". Nesse caso o sistema respon- de "não", porque não há nenhuma cláusula no programa que permita deduzir tal fato. ?-progenitor(ana, jorge). não A questão "Luís é progenitor de Maria?" também obteria a resposta "não", porque o programa nem sequer conhece alguém com o nome Luís. ?-progenitor(luís, maria). não Perguntas mais interessantes podem também ser formuladas, por exemplo: "Quem é progenitor de Íris?". Para fazer isso introduz-se uma variável, por exemplo "X" na posição do argumento corres- pondente ao progenitor de Íris. Desta feita o sistema não se limitará a responder "sim" ou "não", mas irá procurar (e informar caso for encontrado) um valor de X que torne a assertiva "X é progenitor de Íris" verdadeira. ?-progenitor(X, íris). X=josé Da mesma forma a questão "Quem são os filhos de José?" pode ser formulada com a introdução de uma variável na posição do argumento correspondente ao filhos de José. Note que, neste caso, mais de uma resposta verdadeira pode ser encontrada. O sistema irá fornecer a primeira que encontrar e aguardar manifestação por parte do usuário. Se este desejar outras soluções deve digitar um ponto-e- vírgula (;), do contrário digita um ponto (.), o que informa ao sistema que a solução fornecida é sufi- ciente. ?-progenitor(josé, X). X=júlia; X=íris; não Aqui a última resposta obtida foi "não" significando que todas as soluções válidas já foram forneci- das. Uma questão mais geral para o programa seria: "Quem é progenitor de quem?" ou, com outra formulação: "Encontre X e Y tal que X é progenitor de Y". O sistema, em resposta, irá fornecer (en- quanto se desejar, digitando ";") todos os pares progenitor-filho até que estes se esgotem (quando então responde "não") ou até que se resolva encerrar a apresentação de novas soluções (digitando "."). No exemplo a seguir iremos nos satisfazer com as três primeiras soluções encontradas. ?-progenitor(X, Y). 13 X=maria Y=josé; X=joão Y=josé; X=joão Y=ana. Pode-se formular questões ainda mais complicadas ao programa, como "Quem são os avós de Jor- ge?". Como nosso programa não possui diretamente a relação avô, esta consulta precisa ser dividida em duas etapas, como pode ser visto na Figura 2.2. A saber: (1) Quem é progenitor de Jorge? (Por exemplo, Y) e (2) Quem é progenitor de Y? (Por exemplo, X) Esta consulta em Prolog é escrita como uma seqüência de duas consultas simples, cuja leitura pode ser: "Encontre X e Y tais que X é progenitor de Y e Y é progenitor de Jorge". ?-progenitor(X, Y), progenitor(Y, jorge). X=josé Y=íris X Y Jorge progenitor progenitor avô Figura 2.2 A relação avô em função de progenitor Observe que se mudarmos a ordem das consultas na composição, o significado lógico permanece o mesmo, apesar do resultado ser informado na ordem inversa: ?-progenitor(Y, jorge), progenitor(X, Y). Y=íris X=josé De modo similar podemos perguntar: "Quem é neto de João?": ?-progenitor(joão, X), progenitor(X, Y). X=josé Y=júlia; X=josé Y=íris. Ainda uma outra pergunta poderia ser: "José e Ana possuem algum progenitor em comum?". Nova- mente é necessário decompor a questão em duas etapas, formulando-a alternativamente como: "En- contre um X tal que X seja simultaneamente progenitor de José e Ana". ?-progenitor(X, josé), progenitor(X, ana). X=joão Por meio dos exemplos apresentados até aqui acredita-se ter sido possível ilustrar os seguintes pontos: • Uma relação como progenitor pode ser facilmente definida em Prolog estabelecendo-se as tu- plas de objetos que satisfazem a relação; • O usuário pode facilmente consultar o sistema Prolog sobre as relações definidas em seu pro- grama; • Um programa Prolog é constituído de cláusulas, cada uma das quais é encerrada por um ponto (.); • Os argumentos das relações podem ser objetos concretos (como júlia e íris) ou objetos genéri- cos (como X e Y). Objetos concretos em um programa são denominados átomos, enquanto que os objetos genéricos são denominados variáveis; 16 Adicionaremos ainda uma última relação ao nosso programa para exemplificar mais uma particulari- dade da linguagem Prolog. Uma cláusula para a relação irmã se embasaria na seguinte declaração lógica: Para todo X e Y X é irmã de Y se X e Y possuem um progenitor comum e X é do sexo feminino. Ou, sob a forma de regra Prolog: irmã(X, Y) :- progenitor(Z, X), progenitor(Z, Y), feminino(X). Deve-se atentar para a forma sob a qual o requisito "X e Y possuem um progenitor comum" foi expres- sa. A seguinte formulação lógica foi adotada: "Algum Z deve ser progenitor de X e esse mesmo Z deve também ser progenitor de Y". Uma forma alternativa, porém menos elegante, de representar a mesma condição seria: "Z1 é progenitor de X e Z2 é progenitor de Y e Z1 é igual a Z2". Se consultarmos o sistema com "Júlia é irmã de Íris?" , obteremos, como é esperado, um "sim" como resposta. Podería- mos então concluir que a relação irmã, conforme anteriormente definida, funciona corretamente, en- tretanto, há uma falha muito sutil que se revela quando perguntamos: "Quem é irmã de Íris?". O sis- tema irá nos fornecer duas respostas: ?-irmã(X, íris). X=júlia; X=íris dando a entender que Íris é irmã de si própria. Isso não é certamente o que se tinha em mente na defi- nição de irmã, entretanto, de acordo com a regra formulada, a resposta obtida pelo sistema é perfeita- mente lógica. Nossa regra sobre irmãs não menciona que X e Y não devem ser os mesmos para que X seja irmã de Y. Como isso não foi requerido, o sistema, com toda razão, assume que X e Y podem denotar a mesma pessoa e irá achar que toda pessoa do sexo feminino que possui um progenitor é irmã de si própria. Para corrigir esta distorção é necessário acrescentar a condição de que X e Y devem ser diferentes. Isso pode ser feito de diversas maneiras, conforme se verá mais adiante. Por enquanto vamos assumir que uma relação diferente(X, Y) seja reconhecida pelo sistema como verdadeira se e somente se X e Y não forem iguais. A regra para a relação irmã fica então definida por: irmã(X, Y) :- progenitor(Z, X), progenitor(Z,Y), feminino(X), diferente(X, Y). Os pontos mais importantes vistos na presente seção foram: • Programas Prolog podem ser ampliados pela simples adição de novas cláusulas; • As cláusulas Prolog podem ser de três tipos distintos: fatos, regras e consultas; • Os fatos declaram coisas que são incondicionalmente verdadeiras; • As regras declaram coisas que podem ser ou não verdadeiras, dependendo da satisfação das condições dadas; • Por meio de consultas podemos interrogar o programa acerca de que coisas são verdadeiras; • As cláusulas Prolog são constituídas por uma cabeça e um corpo. O corpo é uma lista de objeti- vos separados por vírgulas que devem ser interpretadas como conjunções; • Fatos são cláusulas que só possuem cabeça, enquanto que as consultas só possuem corpo e as regras possuem cabeça e corpo; 17 • Ao longo de uma computação, uma variável pode ser substituída por outro objeto. Dizemos então que a variável está instanciada; • As variáveis são assumidas como universalmente quantificadas nas regras e nos fatos e existen- cialmente quantificadas nas consultas 2.3 CONSTRUÇÕES RECURSIVAS Iremos adicionar agora ao programa a relação antepassado, que será definida a partir da relação pro- genitor. A definição necessita ser expressa por meio de duas regras, a primeira das quais definirá os antepassados diretos (imediatos) e a segunda os antepassados indiretos. Dizemos que um certo X é antepassado indireto de algum Z se há uma cadeia de progenitura entre X e Z como é ilustrado na Figura 2.3. Na árvore genealógica da Figura 2.1, João é antepassado direto de Ana e antepassado indi- reto de Júlia. A primeira regra, que define os antepassados diretos, é bastante simples e pode ser formulada da se- guinte maneira: Para todo X e Z X é antepassado de Z se X é progenitor de Z. Maria João Júlia Íris Jorge progenitor progenitor progenitor(a) (b) antepassado direto antepassado indireto Figura 2.3 Exemplos da relação antepassado ou, traduzindo para Prolog: antepassado(X, Z) :- progenitor(X, Z). Por outro lado, a segunda regra é mais complicada, porque a cadeia de progenitores poderia se esten- der indefinidamente. Uma primeira tentativa seria escrever uma cláusula para cada posição possível na cadeia. Isso conduziria a um conjunto de cláusulas do tipo: antepassado(X, Z) :- progenitor(X, Y), progenitor(Y, Z). antepassado(X, Z) :- progenitor(X, Y1), progenitor(Y1, Y2), progenitor(Y2, Z). antepassado(X, Z) :- progenitor(X, Y1), progenitor(Y1, Y2), progenitor(Y2, Y3), progenitor(Y3, Z). ... etc. Isso conduziria a um programa muito grande e que, de qualquer modo, somente funcionaria até um determinado limite, isto é, somente forneceria antepassados até uma certa profundidade na árvore 18 genealógica de uma família, porque a cadeia de pessoas entre o antepassado e seu descendente seria limitada pelo tamanho da maior cláusula definindo essa relação. Há entretanto uma formulação ele- gante e correta para a relação antepassado que não apresenta qualquer limitação. A idéia básica é definir a relação em termos de si própria, empregando um estilo de programação em lógica denomina- do recursivo: Para todo X e Z X é antepassado de Z se existe um Y tal que X é progenitor de Y e Y é antepassado de Z. A cláusula Prolog correspondente é: antepassado(X, Z) :- progenitor(X, Y), antepassado(Y, Z). Assim é possível construir um programa completo para a relação antepassado composto de duas re- gras: uma para os antepassados diretos e outra para os indiretos. Reescrevendo as duas juntas tem-se: antepassado(X, Z) :- progenitor(X, Z). antepassado(X, Z) :- progenitor(X, Y), antepassado(Y, Z). Tal definição pode causar certa surpresa, tendo em vista a seguinte pergunta: Como é possível ao de- finir alguma coisa empregar essa mesma coisa se ela ainda não está completamente definida? Tais definições são denominadas recursivas e do ponto de vista da lógica são perfeitamente corretas e inte- ligíveis, o que deve ficar claro, pela observação da Figura 2.4. Por outro lado o sistema Prolog deve muito do seu potencial de expressividade à capacidade intrínseca que possui de utilizar facilmente definições recursivas. O uso de recursão é, em realidade, uma das principais características herdadas da lógica pela linguagem Prolog. Z X Y antepassado antepassado progenitor Figura 2.4 Formulação recursiva da relação antepassado Há ainda uma questão importante a ser respondida: Como realmente o sistema Prolog utiliza o pro- grama para encontrar as informações procuradas? Uma explicação informal será fornecida na próxima seção, antes porém vamos reunir todas as partes do programa que foi sendo gradualmente ampliado pela adição de novos fatos e regras. A forma final do programa é mostrada na Figura 2.5. O programa ali apresentado define diversas relações: progenitor, masculino, feminino, antepassado, etc. A relação antepassado, por exemplo, é definida por meio de duas cláusulas. Dizemos que cada uma delas é so- bre a relação antepassado. Algumas vezes pode ser conveniente considerar o conjunto completo de cláusulas sobre a mesma relação. Tal conjunto de cláusulas é denominado um predicado. 21 antepassado(Y, Z). Como anteriormente, as variáveis X e Z são instanciadas para joão e íris, respectivamente. A variável Y, entretanto, não está instanciada ainda. O objetivo original, antepassado(joão, íris) é então substi- tuído por dois novos objetivos derivados por meio da regra [pr2]: progenitor(joão, Y), antepassado(Y, íris). Encontrando-se agora face a dois objetivos, o sistema tenta satisfazê-los na ordem em que estão for- mulados. O primeiro deles é fácil: progenitor(joão, Y) pode ser unificado com dois fatos do programa: progenitor(joão, josé) e progenitor(joão, ana). Mais uma vez, o caminho a ser tentado deve correspon- der à ordem em que os fatos estão escritos no programa. A variável Y é então instanciada com josé nos dois objetivos acima, ficando o primeiro deles imediatamente satisfeito. O objetivo remanescente é então: antepassado(josé, íris). Para satisfazer tal objetivo, a regra [pr1] é mais uma vez empregada. Essa segunda aplicação de [pr1], entretanto, nada tem a ver com a sua utilização anterior, isto é, o sistema Prolog usa um novo conjunto de variáveis na regra cada vez que esta é aplicada. Para indicar isso iremos renomear as variáveis em [pr1] nessa nova aplicação, da seguinte maneira: antepassado(X', Z') :- progenitor(X', Z'). A cabeça da regra deve então ser unificada como o nosso objetivo corrente, que é antepassado(josé, íris). A instanciação de X'e Y' fica: X'=josé e Y'=íris e o objetivo corrente é substituído por: progenitor(josé, íris) Esse objetivo é imediatamente satisfeito, porque aparece no programa como um fato. O sistema en- controu então um caminho que lhe permite provar, no contexto oferecido pelo programa dado, o obje- tivo originalmente formulado, e portanto responde "sim". 2.5 O SIGNIFICADO DOS PROGRAMAS PROLOG Assume-se que um programa Prolog possua três interpretações semânticas básicas. A saber: interpre- tação declarativa, interpretação procedimental, e interpretação operacional. Na interpretação declarativa entende-se que as cláusulas que definem o programa descrevem uma teoria de primeira ordem. Na interpretação procedimentas, as cláusulas são vistas como entrada para um método de prova. Finalmente, na interpretação operacional as cláusulas são vistas como comandos para um procedimento particular de prova por refutação. Tais alternativas semânticas são valiosas em termos de entendimento e codificação de programas Prolog. A interpretação declarativa permite que o programador modele um dado problema através de assertivas acerca dos objetos do universo de discurso, simplificando a tarefa de programação Prolog em relação a outras linguagens tipicamente procedimentais como Pascal ou C. A interpretação proce- dimental permite que o programador identifique e descreva o problema pela redução do mesmo a sub- problemas, através da definição de uma série de chamadas a procedimentos. Por fim, a interpretação operacional reintroduz a idéia de controle da execução (que é irrelevante do ponto de vista da semân- tica declarativa), através da ordenação das cláusulas e dos objetivos dentro das cláusulas em um pro- grama Prolog. Essa útima interpretação é semelhante à semântica operacional de muitas linguagens convencionais de programação, e deve ser considerada, principalmente em grandes programas, por questões de eficiência. É interessante notar que o programador pode comutar de uma interpretação para outra, produzindo um efeito sinérgico que facilita consideravelmente a codificação dos progra- mas Prolog. 22 Essa habilidade específica do Prolog, de trabalhar em detalhes procedimentais de ação sobre o seu próprio domínio de definição, isto é, a capacidade de ser meta-programado, é uma das principais vantagens da linguagem. Ela encoraja o programador a considerar a semântica declarativa de seus programas de modo relativamente independente dos seus significados procedimental e operacional. Uma vez que os resultados do programa são considerados, em princípio, pelo seu significado declara- tivo, isto deveria ser, por decorrência, suficiente para a codificação de programas Prolog. Isso possui grande importância pratica, pois os aspectos declarativos do programa são em geral mais fáceis de entender do que os detalhes operacionais. Para tirar vantagem dessa característica o programador deve se concentrar principalmente no significado declarativo e , sempre que possível, evitar os detalhes de execução. A abordagem declarativa, na realidade, torna a programação em Prolog mais fácil do que nas linguagens convencionais. Infelizmente, entretanto, essa interpretação nem sempre é suficiente. Como deverá ficar claro mais adiante, em problemas de maior complexidade os aspectos operacionais não podem ser ignorados. Apesar de tudo, a atribuição de significado declarativo aos programas Pro- log deve ser estimulada, na extensão limitada por suas restrições de ordem prática. RESUMO • A programação em Prolog consiste em estabelecer relações entre objetos e em formular con- sultas sobre tais relações. • Um programa Prolog é formado por cláusulas. Há três tipos de cláusulas: fatos ou assertivas, regras ou procedimentos e consultas; • Uma relação pode ser especificada por meio de fatos, que estabelecem as tuplas de objetos que satisfazem a relação, por meio de regras, que estabelecem condições para a satisfação das rela- ções, ou por meio de combinações de fatos e regras descrevendo a relação; • Denomina-se predicado ao conjunto de fatos e regras empregados para descrever uma determi- nada relação; • Interrogar um programa acerca de suas relações por meio de uma consulta corresponde a con- sultar uma base de conhecimento. A resposta do sistema Prolog consiste em um conjunto de objetos que satisfazem as condições originalmente estabelecidas pela consulta; • Em Prolog, estabelecer se um objeto satisfaz a uma consulta é freqüentemente um problema de certa complexidade, que envolve inferência lógica e a exploração de caminhos alternativos em uma árvore de busca ou de pesquisa, com a possível utilização de mecanismos especiais de re- torno (backtracking). Tudo isso é feito automaticamente pelo sistema, de forma transparente ao usuário; • Três tipos de semântica são atribuídas aos programas Prolog: declarativa, procedimental e ope- racional. O programador deve empregá-las conforme o problema a ser resolvido, tirando pro- veito da situação apresentada. EXERCÍCIOS 2.1 Amplie o programa apresentado na Figura 2.5 para representar as relações tio, prima, cunhado e sogra. 2.2 Programe a relação descendente(X, Y), onde X é descendente de Y. 2.3 Escreva um programa Prolog para representar o seguinte: João nasceu em Pelotas e Jean nasceu em Paris. Pelotas fica no Rio Grande do Sul. Paris fica na França. Só é gaúcho quem nasceu no Rio Grande do Sul. 23 2.4 Escreva um programa Prolog para representar o seguinte: Os corpos celeste dignos de nota são as estrelas, os planetas e os cometas. Vênus é um corpo celeste, mas não é uma estrela. Os cometas possuem cauda quando estão perto do sol. Vênus está perto do sol, mas não possui cauda. 2.5 Assuma que os arcos em um grafo expressem custos, como no exemplo abaixo: A B C D E F 3 5 4 2 4 5 2 2 e sejam descritos através de assertivas da forma arco(R, S, T) significando que há um arco de custo T entre os nodos R e S. Por exemplo, arco(A, B, 3) descre- ve um arco de custo 3 entre os nodos A e B. Assuma também que o relacionamento mais(X, Y, Z) vale quando X+Y=Z. Defina o relacionamento custo(U, V, L) de forma a expressar que existe um caminho de custo L entre os nodos U e V. 26 Essa situação é diferente para as constantes: o mesmo átomo sempre significa o mesmo objeto ao longo de todo o programa. 3.1.3 ESTRUTURAS Objetos estruturados, ou simplesmente estruturas, são objetos que possuem vários componentes. Os próprios componentes podem, por sua vez, ser também estruturas. Por exemplo, uma data pode ser vista como uma estrutura com três componentes: dia, mes e ano. Mesmo que sejam formadas por di- versos componentes as estruturas são tratadas no programa como objetos simples. Para combinar os componentes em uma estrutura é necessário empregar um functor. Um functor é um símbolo funcio- nal (um nome de função) que permite agrupar diversos objetos em um único objeto estruturado. Um functor adequada ao exemplo dado é data, então a data correspondente a 13 de outubro de 1993, cuja estrutura está presente na Figura 3.2, pode ser escrita como: data(13, outubro, 1993) data 13 out. 1993 data functor argumentos (13, outubro, 1993) (a) (b) Figura 3.2 Uma data como exemplo de objeto estruturado Na figura acima, em (a) temos a representação de data sob a forma de árvore e em (b) a forma como é escrita em Prolog. Todos os componentes no exemplo são constantes (dois inteiros e um átomo), en- tretanto, podem também ser variáveis ou outras estruturas. Um dia qualquer de março de 1996, por exemplo, pode ser representado por: data(Dia, março, 1996) Note que "Dia" é uma variável e pode ser instanciada para qualquer objeto em algum ponto da execu- ção. Sintaticamente todos os objetos em Prolog são denominados termos. O conjunto de termos Prolog, ou simplesmente termos, é o menor conjunto que satisfaz às seguintes condições: • Toda constante é um termo; • Toda variável é um termo; • Se t1, t2, ..., tn são termos e f é um átomo, então f(t1, t2, ..., tn) também é um termo, onde o átomo f desempenha o papel de um símbolo funcional n-ário. Diz-se ainda que a expressão f(t1, t2, ..., tn) é um termo funcional Prolog. Todos os objetos estruturados podem ser representados como árvores. A raiz da árvore é o functor e os ramos que dela partem são os argumentos ou componentes. Se algum dos componentes for também uma árvore, então ele passa a constituir uma sub-árvore do objeto estruturado completo. Por exemplo, na Figura 3.3 é mostrada a estrutura em árvore correspondente à expressão: (a + b) * (c - 5) De acordo com a sintaxe dos termos Prolog, anteriormente apresentada, e tomando os símbolos "*", "+" e "-" como functores, a expressão dada pode ser escrita: *(+(a, b), -(c, 5)) 27 * + - a b c 5 Figura 3.3 Uma expressão aritmética estruturada em árvore Este é, naturalmente, um termo legal em Prolog, entretanto, não é a forma trivial com a qual estamos acostumados. Normalmente se irá preferir a notação usual, infixa, como é utilizada na matemática. Na verdade a linguagem Prolog admite as duas formas, prefixa e infixa, para a escrita de expressões arit- méticas. Detalhes sobre operadores e definição de operadores especiais serão abordados mais adiante. 3.2 UNIFICAÇÃO Na seção anterior foi visto como os objetos podem ser utilizados na representação de objetos de dados complexos. A operação mais importante entre dois termos Prolog é denominada unificação. A unifi- cação pode, por si só, produzir alguns resultados interessantes. Dados dois termos, diz-se que eles unificam se: (1)Eles são idênticos, ou (2)As variáveis de ambos os termos podem ser instanciadas com objetos de maneira que, após a substituição das variáveis por esses objetos, os termos se tornam idênticos. Por exemplo, os termos data(D, M, 1994) e data(X, março, A) unificam. Uma instanciação que torna os dois termos idênticos é: D é instanciada com X; M é instanciada com março; A é instanciada com 1994. Por outro lado, os termos data(D, M, 1994) e data(X, Y, 94) não unificam, assim como não unificam data(X, Y, Z) e ponto(X, Y, Z). A unificação é um processo que toma dois termos como entrada e verifica se eles podem ser unificados. Se os termos não unificam, dizemos que o processo falha. Se eles unificam, então o processo é bem-sucedido e as variáveis dos termos que participam do processo são instanciadas com os valores encontrados para os objetos, de modo que os dois termos participan- tes se tornam idênticos. Vamos considerar novamente a unificação entre duas datas. O requisito para que essa operação se efetue é informada ao sistema Prolog pela seguinte consulta, usando o operador "=": ?-data(D, M, 1994) = data(X, março, A) Já foi mencionada a instanciação D=X, M=março e A=1994, que obtém a unificação. Há, entretanto, outras instanciações que também tornam os termos idênticos. Duas delas são: D=1, X=1, M=março, A=1994 D=terceiro, X=terceiro, M=março, A=1994 Essas duas instanciações são consideradas menos gerais do que a primeira, uma vez que restringem o valor das variáveis D e X mais fortemente do que seria necessário.. Para tornar os dois termos do exemplo idênticos, basta que D e X tenham o mesmo valor, seja qual for esse valor. A unificação em Prolog sempre resulta na instanciação mais geral, isto é, a que limita o mínimo possível o escopo de valores das variáveis, deixando a maior liberdade possível às instanciações posteriores. As regras 28 gerais que determinam se dois termos S e T unificam são as seguintes: • Se S e T são constantes, então S e T unificam somente se ambos representam o mesmo objeto; • Se S é uma variável e T é qualquer coisa, então S e T unificam com S instanciada com T. In- versamente, se T é uma variável, então T é instanciada com S; • Se S e T são estruturas, unificam somente se: (1) S e T tem o mesmo functor principal, e (2) to- dos os seus componentes correspondentes também unificam. A instanciação resultante é deter- minada pela unificação dos componentes. Essa última regra pode ser exemplificada pelo processo de unificação dos termos triângulo(ponto(1, 1), A, ponto(2, 3)) com triângulo(X, ponto(4, Y), ponto(2, Z)) cuja representação em árvore é apresentada na Figura 3.4. triângulo ponto A ponto 1 1 2 3 triângulo ponto 2 Z ponto 4 Y X Figura 3.4 Termos representados em árvore O processo de unificação começa pela raiz (o functor principal). Como ambos os functores unificam, o processo parte para a unificação dos argumentos, onde a unificação dos pares de argumentos corres- pondentes ocorre. Assim o processo completo pode ser visto como a seguinte seqüência de operações de unificação simples: triângulo = triângulo ponto(1, 1) = X A = ponto(4, Y) ponto(2, 3) = ponto(2, Z) O processo completo de unificação é bem sucedido porque todas as unificações na seqüência acima também o são. A instanciação resultante é: X = ponto(1, 1) A = ponto(4, Y) Z = 3 3.3 SEMÂNTICA DECLARATIVA E SEMÂNTICA PROCEDIMENTAL Conforme se estudou no capítulo anterior, os programas Prolog podem ser interpretados de três ma- neiras distintas: declarativamente, procedimentalmente e operacionalmente. Iremos agora aprofundar 31 • O escopo léxico das variáveis em um programa é uma cláusula. O mesmo nome de variável em duas cláusulas distintas representa duas variáveis diferentes; • As estruturas Prolog podem ser sempre representadas por meio de árvores. Prolog pode ser vista como uma linguagem orientada ao processamento de árvores; • A operação de unificação toma dois termos e tenta torná-los idênticos por meio da instanciação das variáveis em ambos; • Quando a unificação é bem sucedida, resulta na instanciação mais geral das variáveis envolvi- das; • A semântica declarativa do Prolog define se um objetivo é verdadeiro com relação a um dado programa e, se for, para que particulares instanciações de variáveis isto ocorre; • Uma vírgula entre os objetivos significa a sua conjunção, enquanto que um ponto-e-vírgula si- gnifica a sua disjunção; • A semântica operacional representa um procedimento para satisfazer a lista de objetivos no contexto de um dado programa. A saída desse procedimento é o valor-verdade da lista de obje- tivos com a respectiva instanciação de sua variáveis. O procedimento permite o retorno auto- mático (backtracking) para o exame de novas alternativas; • A interpretação declarativa de programas escritos em Prolog puro não depende da ordem das cláusulas nem da ordem dos objetivos dentro das cláusulas; • A interpretação procedimental depende da ordem dos objetivos e cláusulas. Assim a ordem pode afetar a eficiência de um programa. Uma ordenação inadequada pode mesmo conduzir a chamadas recursivas infinitas; EXERCÍCIOS 3.1 Quais dos seguintes objetos estão sintaticamente corretos e a que tipo de objeto pertencem? a. Daniela b. daniela c. 'Daniela' d. _daniela e. 'Daniela vai a Paris' f. vai(daniela, paris) g. 8118 h. 2(X, Y) i. +(sul, oeste) j. três(Cavalos(Baios)) 3.2 Sugira uma representação para retângulos, quadrados, círculos e elipses, usando uma abordagem similar à apresentada na Figura 3.4. Procure obter a representação mais geral possível, por exem- plo, um quadrado é um caso especial de retângulo e um círculo pode ser considerado um caso es- pecial de elipse. 3.3 Quais das próximas operações de unificação serão bem sucedidas e quais irão falhar? Para as que forem bem sucedidas, quais são as instanciações de variáveis resultantes? a. ponto(A, B) = ponto(1, 2) b. ponto(A, B) = ponto(X, Y, Z) c. mais(2, 2) = 4 d. +(2, D) = +(E, 2) e. t(p(-1,0), P2, P3) = t(P1, p(1, 0), p(0, Y)) 3.4 Defina uma representação Prolog para segmentos de reta no plano expressos em função dos 32 pontos limites. Que termo irá representar qualquer segmento de reta vertical em X=5? 3.5 Supondo que um retângulo seja representado pelo termo: retângulo(SupEsq, InfDir) onde SupEsq representa o ponto superior esquerdo e InfDir o ponto inferior direito de um retân- gulo em uma tela de vídeo (1280 x 1024), defina a relação quadrado(R, ...) que é verdadeira se R é um quadrado. 3.6 Considere o seguinte programa: f(1, um). f(s(1), dois). f(s(s(1))), três). f(s(s(s(X))), N) :- f(X, N). Como iria o sistema Prolog responder as seguintes questões? Quando várias respostas são possí- veis, dê pelo menos duas: a. ?-f(s(1), A). b. ?-f(s(s(1)), dois). c. ?-f(s(s(s(s(s(s(1)))))), C). d. ?-f(D, três). 33 4. OPERADORES E ARITMÉTICA 4.1 OPERADORES Na matemática costuma-se escrever expressões como 2*a + b*c onde + e * são operadores e 2, a, b e c são argumentos. Em particular, + e * são denominados opera- dores infixos porque se localizam entre os dois argumentos que operam. Tais expressões são repre- sentadas por árvores como na Figura 4.1 e podem ser escritas, se for desejado, sob a forma de termos Prolog, com os símbolos + e * como functores: +(*(2, a), *(b, c)) + * * 2 a b c Figura 4.1 Representação em árvore da expressão +(*(2, a), *(b, c)) Normalmente, entretanto, é preferível escrever as expressões matemáticas na forma usual, com os operadores infixos, como em: 2*a + b*c Tal notação é também aceita pelo Prolog, entretanto, trata-se apenas da representação externa deste objeto, que será automaticamente convertida para a forma convencional dos termos Prolog. Na saída, entretanto, o termo será novamente convertido para a forma externa, com os operadores infixos. Assim, as expressões matemáticas são manipuladas pelo Prolog como meras extensões notacionais e nenhum novo princípio para a estruturação de objetos está sendo proposto. Se for escrito a+b, o sis- tema irá reconhecer e manipular tal expressão exatamente como se houvesse sido escrito +(a, b). Para que o sistema entenda apropriadamente expressões tais como a+b*c, é necessário existir uma priori- dade de execução entre os operadores. Assim o operador + é executado prioritariamente ao operador *. É essa prioridade de execução que decide qual a interpretação correta da expressão. Por exemplo, a expressão a+b*c poderia em princípio ser entendida como: +(a, *(b, c)) ou *(+(a, b), c) A regra geral é que o operador de maior prioridade seja o functor principal do termo. Se expressões contendo + e * devem ser entendidas segundo as convenções usuais, então + deve ter maior precedên- cia que *. Assim a expressão a+b*c deve ser entendida como a+(b*c). Se outra interpretação é preten- dida, deve ser indicada explicitamente com o uso de parênteses, como em (a+b)*c. O programador Prolog pode também definir os seus próprios operadores, isto é, definir átomos tais como tem e suporta como se fossem operadores infixos e então escrever no programa fatos como: pedro tem informações assoalho suporta mesa que são exatamente equivalentes a 36 <===> ¬ ∨ ∧ ¬ ¬ A B A B Figura 4.4 Interpretação do termo ¬(A ∧ B) <===> ¬A ∨ ¬B 4.2 ARITMÉTICA A linguagem Prolog é principalmente utilizada - como já se viu - para a computação simbólica, onde as necessidades de cálculo são comparativamente modestas. Assim, o instrumental da linguagem Prolog destinado a computações numéricas é algo simples em comparação com outras linguagens destinadas especificamente para esse fim, como por exemplo o Pascal-SC. Alguns dos operadores pré- definidos, anteriormente vistos podem ser usados para computação numérica. Tais operadores são mostrados na Tabela 4.2. Tais operadores, excepcionalmente, executam uma certa operação. Mesmo em tais casos, entretanto, é necessário introduzir uma indicação adicional para executar a ação necessária. O sistema sabe como conduzir a operação denotada pelos operadores, entretanto isso não é suficiente para conduzir a se- qüência da ação. Tabela 4.2 Operadores pré-definidos para computação numérica OPERADOR PRIORIDADE TIPO SIGNIFICADO + 500 yfx adição - 500 yfx subtração * 400 yfx multiplicação / 400 yfx divisão div 400 yfx divisão inteira mod 300 xfx resto da divisão inteira ^ 200 xfy potenciação A consulta mostrada a seguir, assim como a resposta obtida, representam uma tentativa ingênua de obter computação numérica: ?-X = 1 + 2. X = 1 + 2 e não X = 3 como se poderia esperar. A razão é simples: a expressão "1 + 2" denota simplesmente um termo Prolog, onde + é o functor e 1 e 2 são os argumentos. Não há nada no termo acima que efetiva- mente obrigue o Prolog a ativar a operação de adição. Um operador pré-definido especial "is" é forne- cido para ordenar a execução da operação representada, forçando as computações numéricas envolvi- das. A maneira correta de se obter o resultado da adição proposta acima é: ?-X is 1 + 2. X = 3 A adição é aqui executada por um procedimento especial associado ao operador "is". Tais procedi- mentos são denominados procedimentos embutidos. Não há concordância geral sobre notação aritmé- tica em Prolog, de forma que diferentes implementações da linguagem podem utilizar notações algo diferentes. Por exemplo, o operador "/" pode denotar divisão inteira ou divisão em ponto flutuante, 37 dependendo da implementação. Aqui, "/" denotará a divisão em ponto flutuante, enquanto que o ope- rador "div" denotará a divisão inteira. Exemplificando, na consulta abaixo: ?-X is 3/2, Y is 3 div 2. X=1.5 Y=1 O argumento à esquerda do operador "is" deve ser um objeto simples. O argumento à direita deve ser uma expressão aritmética, composta de operadores aritméticos, variáveis e números. Uma vez que o operador "is" irá forçar a execução da operação indicada, todas as variáveis contidas na expressão devem estar instanciadas com números no momento da execução de tal objetivo. A prioridade dos operadores aritméticos pré-definidos (ver Figura 4.4) é tal que a associatividade dos argumentos com os operadores é a mesma normalmente usada em matemática. Os parênteses podem ser usados para indicar associações diferentes. Note que +, -, *, / e div são definidos como yfx, o que significa que a execução se dará da esquerda para a direita. Por exemplo, X is 5-2-1 é interpretado como X is (5-2)-1. A aritmética também é envolvida na comparação de valores numéricos. Por exemplo, a verificação se o produto de 277 por 37 é maior que 10000 pode ser especificada pelo objetivo: ?-277 * 37 > 10000. sim Note que de forma semelhante ao operador "is", o operador ">" também força a avaliação de expres- sões. Suponha-se, por exemplo, uma relação denominada "nasceu", que relaciona nomes de pessoas com seus respectivos anos de nascimento. Então é possível recuperar os nomes das pessoas nascidas entre 1970 e 1980 inclusive, com a seguinte questão: ?-nasceu(Nome, Ano), Ano >= 1970, Ano =< 1980. Na tabela abaixo apresenta-se um conjunto padrão de operadores de comparação utilizados em Pro- log: Tabela 4.3 Operadores de Comparação OPERADOR PRIORIDADE TIPO SIGNIFICADO > 700 xfx maior que < 700 xfx menor que >= 700 xfx maior ou igual a =< 700 xfx menor ou igual a =:= 700 xfx valores iguais =\= 700 xfx valores diferentes Note que a diferença existente entre o operador de unificação e o operador =:=, por exemplo, nos objetivos X = Y e X =:= Y. O primeiro objetivo irá ocasionar a unificação dos objetos X e Y, instan- ciando, se for o caso, alguma variável em X e Y. Por outro lado, X =:= Y ocasiona a avaliação arit- mética sem causar a instanciação de nenhuma variável. As diferenças se tornam claras nos exemplos a seguir: ?-1+2 =:= 2+1. sim ?-1+2 = 2+1. não ?-1+A = B+2. A=2 B=1 Mesmo não sendo direcionadas para a computação aritmética, as diferentes implementações do Prolog normalmente possuem um conjunto de funções pré-definidas para a execução de cálculos científicos. Tais funções podem ser empregadas em expressões matemáticas de modo similar às linguagens con- vencionais. Um conjunto padrão de tais funções é apresentado na tabela abaixo: Tabela 4.4 Funções Pré-Definidas em Prolog 38 FUNÇÃO SIGNIFICADO abs(X) Valor absoluto de X acos(X) Arco-cosseno de X asin(X) Arco-seno de X atan(X) Arco-tangente de X cos(X) Cosseno de X exp(X) Valor de "e" elevado a X ln(X) Logaritmo natural de X log(X) Logaritmo decimal de X sin(X) Seno de X sqrt(X) Raiz quadrada de X tan(X) Tangente de X round(X,N) Arredonda X para N casas decimais Pi Valor de p com 15 casas decimais Random Um número aleatório entre 0 e 1 Por exemplo, são válidas as seguintes expressões Prolog: X is 3 * (cos(random))^2. Y is sin(pi/6)*sqrt(tan(pi/12)). Como um exemplo mais complexo, suponha o problema de computar o máximo divisor comum de dois números. Dados dois inteiros positivos, X e Y, seu máximo divisor comum D pode ser encontra- do segundo três casos distintos: (1)Se X e Y são iguais, então D é igual a X; (2)Se X<Y, então D é igual ao mdc entre X e a diferença X-Y; (3)Se X>Y, então cai-se no mesmo caso (2), com X substituído por Y e vice-versa. As três cláusulas Prolog que que expressam os três casos acima são: mdc(X, X, X). mdc(X, Y, D) :- X < Y, Y1 is Y-X, mdc(X, Y1, D). mdc(X, Y, D) :- X > Y, mdc(Y, X, D). Naturalmente, o último objetivo na terceira cláusula poderia ser de modo equivalente substituído por: X1 is X-Y, mdc(X1, Y, D). Um último exemplo será dado para recursivamente calcular o fatorial de um número inteiro dado. O programa é: fatorial(0, 1). fatorial(X, Y) :- X1 is X-1, fatorial(X1, Y1), Y is X*Y1. É interessante notar aqui que o processo recursivo mantém latentes todas as operações aritméticas até que o fato "fatorial(0, 1)" seja alcançado, quando então, todas as operações pendentes são executadas para fornecer em Y o fatorial desejado. RESUMO • A notação para definição de operadores permite ao programador adequar a sintaxe de seus pro- gramas para suas necessidades particulares, melhorando consideravelmente sua legibilidade; 41 5. PROCESSAMENTO DE LISTAS Uma importante classe de estruturas de dados em Prolog é composta de expressões simbólicas, tam- bém denominadas "S-Expressões", que permitem a representação de listas de tamanho indefinido como tipos de árvores onde os ramos, também denominados sub-árvores, são reunidos entre parênte- ses e outros delimitadores para formar sequências de objetos. A analogia entre listas aninhadas e árvo- res é fundamental para o perfeito entendimento de algumas operações realizadas em listas. A sintaxe das listas em Prolog é uma variante da sintaxe empregada em LISP, que é uma linguagem tradicio- nalmente empregada em inteligência artificial e computação simbólica. No presente capítulo aborda- se a representação em listas, a codificação em Prolog de diversas operações e a construção de algumas aplicações empregando estruturas em listas. 5.1 REPRESENTAÇÃO DE LISTAS Listas são estruturas simples de dados, largamente empregadas em computação não-numérica. Uma lista é uma seqüência de qualquer número de itens, como: brasil, uruguai, argentina, paraguai. Uma lista deste tipo pode ser escrita em Prolog como: [brasil, uruguai, argentina, paraguai] Essa, entretanto, é apenas a aparência externa das listas. Como já foi visto, todos os objetos estrutura- dos em Prolog são na realidade árvores e as listas seguem a regra. Como representar listas como ob- jetos Prolog? Dois casos devem ser considerados: a lista vazia e a lista não-vazia. No primeiro caso, a lista é representada simplesmente como um átomo, []. No segundo, a lista deve ser pensada como constituída de dois componentes: uma "cabeça" e um "corpo". Por exemplo, na lista dada, a cabeça é "brasil" e o corpo é a lista [uruguai, argentina, paraguai]. Em geral, a cabeça pode ser qualquer objeto Prolog - como uma árvore ou uma variável. O corpo, entretanto, deve ser obrigatoriamente uma lista. A cabeça e o corpo são combinados em uma estrutura por meio de um functor especial. A escolha desse functor depende da implementação considerada da linguagem Prolog. Aqui será assumido o ponto "•" que é o símbolo funcional adotado com maior freqüência na representação de listas nas diversas implementações Prolog: •(Cabeça, Corpo) Uma vez que a variável Corpo representa, por sua vez, uma lista, esta pode ser vazia ou possuir a sua própria cabeça e corpo, portanto, para a representação de listas de qualquer tamanho, nenhum princí- pio adicional é necessário. O exemplo de lista dado é então representado pelo termo Prolog: •(brasil, •(uruguai, •(argentina, •(paraguai, [])))). • • • • brasil uruguai argentina paraguai [] Figura 5.1 Uma lista representada como árvore. Na Figura 5.1 apresenta-se a correspondente estrutura em árvore. Note que a lista vazia aparece no termo acima. Isso ocorre porque o último "corpo" é uma lista de um único item [paraguai], que possui uma lista vazia como seu corpo: 42 [paraguai] = •(paraguai, []) Esse exemplo mostra como o princípio geral para a estruturação de objetos Prolog também se aplica a listas de qualquer tamanho. Como o exemplo também mostra, a notação direta com o uso do functor " •" pode produzir expressões bastante confusas. Por essa razão o sistema Prolog oferece uma notação simplificada para as listas, permitindo que as mesmas sejam escritas como seqüências de itens separa- dos por vírgulas e incluídos entre colchetes. O programador pode empregar qualquer notação, entre- tanto, a que utiliza colchetes é normalmente preferida. Segundo tal notação, um termo da forma [H|T] é tratado como uma lista de cabeça H e corpo T. Listas do tipo [H|T] são estruturas muito comuns em programação não-numérica. Deve-se recordar que o corpo de uma lista é sempre outra lista, mesmo que seja vazia. Os seguintes exemplos devem servir para demonstrar tais idéias: [X | Y] ou [X | [Y | Z]] unificam com [a, b, c, d] [X, Y, Z] não unifica com [a, b, c, d] [a, b, c] == [a | [b | [c]]] == [a | [b, c]] == [a, b | [c]] == [a, b, c | []] As consultas abaixo também são elucidativas: ?-[X | Y] = [a, b, c]. X=a Y=[b, c] ?-[X, Y, Z] = [a, b, c, d]. não ?-[X | [Y | Z]] = [a, b, c, d]. X=a Y=b Z=[c, d] 5.2 OPERAÇÕES SOBRE LISTAS Estruturas em lista podem ser definidas e transformadas em Prolog de diversas maneiras diferentes. Na presente seção procura-se, através de uma variedade de exemplos, mostrar a flexibilidade das lis- tas na representação de situações complexas. Emprega-se, para maior clareza, de agora em diante a notação: simbolo_predicativo/aridade para a identificação de predicados. Por exemplo gráfico/3 denota uma relação denominada gráfico com três argumentos. Esse detalhamento é às vezes importante. Nome e aridade são os elementos necessários e suficientes para a perfeita identificação de um predicado. 5.2.1 CONSTRUÇÃO DE LISTAS A primeira necessidade para a manipulação de listas é ser capaz de construí-las a partir de seus ele- mentos básicos: uma cabeça e um corpo. Tal relação pode ser escrita em um único fato: cons(X, Y, [X | Y]). Por exemplo: ?-cons(a, b, Z). Z=[a | b] Durante a unificação a variável X é instanciada com a, Y com b e Z com [X|Y], que por sua vez é instanciada com [a|b], devido aos valores de X e Y. Se X for um elemento e Y uma lista, então [X|Y] é uma nova lista com X como primeiro elemento. Por exemplo: ?-cons(a, [b, c], Z). Z=[a, b, c] ?-cons(a, [], Z). Z=[a] A generalidade da unificação permite a definição de um resultado implícito: 43 ?-cons(a, X, [a, b, c]). X=[b, c] Neste último exemplo as propriedades de simetria dos argumentos, lembram um solucionador de equações: um X é encontrado tal que [a|X] = [a, b, c]. Entretanto, se o primeiro argumento for uma lista com, digamos, três elementos e o segundo uma lista com dois, o resultado não será uma lista com cinco elementos: ?-cons([a, b, c], [d, e], Z). Z=[[a, b, c], d, e] de modo que o predicado cons/3 não resolve o problema de concatenar duas listas em uma terceira. Mais adiante será estudado o predicado conc/3 que realiza tal função. 5.2.2 OCORRÊNCIA DE ELEMENTOS EM UMA LISTA Vamos implementar um tipo de relação de ocorrência que estabelece se determinado objeto é membro de uma lista, como em: membro(X, L) onde X é um objeto e L uma lista. O objetivo membro(X, L) é verdadeiro se X ocorre em L. Por exemplo, são verdadeiros: membro(b, [a, b, c]) membro([b,c], [a, [b, c], d]) mas a declaração membro(b, [a, [b, c]]) é falsa. O programa que define a relação membro/2 baseia-se na seguinte afirmação: X é membro de L se (1) X é a cabeça de L, ou (2) X é membro do corpo de L. que pode ser representada em Prolog por meio de duas cláusulas. A primeira, um fato, estabelece a primeira condição: X é membro de L, se X é a cabeça de L. A segunda, uma regra que será empregada quando X não é cabeça de L, é uma chamada recursiva que diz que X ainda pode ser membro de L, desde que seja membro do corpo de L. Em Prolog: membro(X, [X | C]). membro(X, [Y | C]) :- membro(X, C). Note-se que o corpo da lista na primeira cláusula é sempre um resultado sem qualquer interesse, o mesmo ocorrendo com a cabeça da lista na segunda. É possível então empregar variáveis anônimas e escrever o predicado de forma mais elegante: membro(X, [X | _]). membro(X, [_ | C]) :- membro(X, C). 5.2.3 CONCATENAÇÃO DE LISTAS Para a concatenação de duas listas quaisquer, resultando em uma terceira, se definirá a relação: conc(L1, L3, L3) onde L1 e L2 são duas listas e L3 é a concatenação resultante. Por exemplo: conc([a, b], [c, d], [a, b, c, d]) Novamente, dois casos devem ser considerados para a definição de conc/3, dependendo do primeiro argumento L1: (1)Se o primeiro argumento é uma lista vazia, então o segundo e o terceiro argumentos devem ser 46 A relação que inverte uma lista, isto é , que organiza seus elementos na ordem inversa é útil para os mais diversos propósitos. Abaixo temos alguns exemplos de inversão: inverter([a, b, c], [c, b, a]). inverter([], []). inverter([a, [b, c], d], [d, [b, c], a]) Dentre os diversos mecanismos lógicos capazes de inverter uma lista, o denominado "inversão ingê- nua" baseia-se numa abordagem muito direta, embora seu tempo de execução seja proporcional ao quadrado do tamanho da lista: (1)Tomar o primeiro elemento da lista; (2) Inverter o restante; (3)Concatenar a lista formada pelo primeiro elemento ao inverso do restante. Em Prolog, escreve-se: inverter([], []). inverter([X | Y], Z) :- inverter(Y, Y1), conc(Y1, [X], Z). Esse programa, juntamente com o predicado conc/3, costuma ser empregado como um teste ben- chmark para sistemas Prolog. Quando o número de inferências lógicas, ou chamadas de objetivos Prolog é dividido pelo número de segundos gastos, o número obtido mede a velocidade do sistema Prolog em LIPS (logic inferences per second). A inversão de listas pode, entretanto ser obtida de modo mais eficiente por meio de um predicado auxiliar, iterativo, aux/3, tornando o tempo de execu- ção apenas linearmente proporcional ao tamanho da lista a inverter: inverter(X, Y) :- aux([], X, Y). aux(L, [], L). aux(L, [X | Y], Z) :- aux([X | L], Y, Z). 5.2.6 SUBLISTAS Iremos considerar agora a relação sublista/2 que possui como argumentos uma lista S e uma lista L tais que S ocorre em L como sublista. Assim, é verdadeira a afirmação: sublista([c, d, e], [a, b, c, d, e, f]) mas é falso declarar que: sublista([c, e], [a,b,c,d,e,f]) O programa Prolog para a relação sublista/2 pode se basear na mesma idéia explorada na definição do predicado membro1/2, com a diferença que, desta vez, a relação é mais genérica, podendo ser formu- lada por: S é sublista de L se: (1) L pode ser decomposta em duas listas, L1 e L2, e (2) L2 pode ser decomposta em S e L3. Como foi visto anteriormente, a relação conc/3 pode ser usada para a decomposição de listas. Assim a formulação acima pode ser expressa em Prolog por: sublista(S, L) :- conc(L1, L2, L), conc(S, L3, L2). O programa sublista/2 pode ser usado de modo bastante flexível em diversas aplicações. Apesar de ter sido projetado para verificar se alguma lista ocorre como sublista de outra, ele pode, por exemplo, ser 47 usado para obter todas as sublistas de uma lista: ?-sublista(S, [a, b, c]). S=[]; S=[a]; S=[a, b]; S=[a, b, c]; S=[b]; S=[b,c]; S=[c]; não 5.2.7 PERMUTAÇÃO DE LISTAS Algumas vezes pode ser interessante gerar permutações de uma dada lista. Com essa finalidade defi- ne-se a relação permutar/2 cujos argumentos são duas listas tais que cada uma é permutação da outra. A intenção é permitir a geração de todas as permutações possíveis de uma dada lista empregando o mecanismo de backtracking que pode ser disparado a partir da relação permutar/2, como por exemplo em: ?-permutar([a, b, c], P). P=[a, b, c]; P=[a, c, b]; P=[b, a, c]; P=[b, c, a]; P=[c, a, b]; P=[c, b, a]; não O programa permutar/2 deve novamente basear-se na consideração de dois casos, dependendo da lista a ser permutada: (1)Se a primeira lista é vazia, então a segunda também é; (2) Se a primeira lista é não-vazia, então possui a forma [X|L] e uma permutação de tal lista pode ser construída primeiro permutando L para obter L1e depois inserindo X em qualquer posição de L1, conforme a Figura 5.3. LX L1 permutar L inserir X obtendo uma permutação de [X | L]. Figura 5.3 Permutação de Listas A relação Prolog correspondente é: permutar([], []). permutar([X | L], P) :- permutar(L, L1), inserir(X, L1, P). O uso normal da relação permutar/2 seria como no exemplo dado anteriormente, permutar([a, b, c], P). Uma tentativa diferente seria propor ao sistema: ?-permutar(L, [a, b, c]). Aqui o programa dado irá, de início, obter em L as seis permutações existentes para [a, b, c], mas depois, se o usuário pedir mais soluções, o programa nunca irá responder "não", entrando em um laço infinito na tentativa de encontrar outra permutação onde já não há mais nenhuma. Assim, algum cui- dado é necessário no uso desta relação. 48 5.3 OUTROS EXEMPLOS Dada a importância do uso de listas em Prolog, apresenta-se informalmente na presente seção algumas aplicações adicionais definidas sobre listas que podem vir a ser de grande utilidade em programas futuros, deixando-se ao leitor a tarefa de verificar o seu funcionamento segundo as diferentes inter- pretações estudadas. 5.3.1 TAMANHO DE UMA LISTA A relação tamanho/2, representada por tamanho(L, T) será verdadeira quando T for o número de ele- mentos existentes em L: tamanho([], 0). tamanho([_ | R], N) :- tamanho(R, N1), N is N1+1. Por exemplo: ?-tamanho([a, b, c, d, e], X). X=5 5.3.2 SELEÇÃO DE ELEMENTOS PARTICULARES Muitas vezes é necessário identificar em uma lista um determinado elemento que possua uma certa propriedade. Isso pode ser realizado através da relação prop/2, abaixo, onde p/1 representa a proprie- dade procurada, devendo estar definida no programa. Note a semelhança dessa relação com o predica- do membro/2, anteriormente discutido. prop(X, [X | _]) :- p(X). prop(X, [_ | Y]) :- prop(X, Y). Outras vezes é necessário selecionar exatamente o enésimo elemento de uma lista. O predicado ené- simo/3, a seguir, realiza esta função: enésimo(1, X, [X | _]). enésimo(N, X, [_ | Y]) :- enésimo(M, X, Y), N is M+1. Exemplos de utilização desse predicado são: ?-enésimo(3, X, [a, b, c, d]). X=c ?-enésimo(N, b, [a, b, c, d]). N=2 Outra necessidade freqüente é reunir em um lista separada determinados elementos de uma lista, identificados pela sua posição. Isso é obtido pelo predicado seleciona/3, abaixo, que por sua vez em- prega a relação enésimo/3: seleciona([], _, []). seleciona([M | N], L, [X | Y]) :- enésimo(M, X, L), seleciona(N, L, Y). Por exemplo: ?-seleciona([2, 4], [a, b, c, d, e], L). L=[b, d] 5.3.3 SOMA E PRODUTO 51 6. CONTROLE Como já foi visto, o programador pode controlar a execução de seu programa através da reordenação das cláusulas ou de objetivos no interior destas. Neste capítulo se estudará um outro instrumento para o controle de programas - denominado "cut" - que se destina a prevenir a execução do backtracking quando este não for desejado. Também se introduzirá a "negação por falha", uma forma operacional da negação lógica. Exemplos serão apresentados com a finalidade de ilustrar os conceitos desenvolvi- dos. 6.1 BACKTRACKING Na execução dos programas Prolog, a evolução da busca por soluções assume a forma de uma árvore - denominada "árvore de pesquisa" ou "search tree" - que é percorrida sistematicamente de cima para baixo (top-down) e da esquerda para direita, segundo o método denominado "depth-first search" ou "pesquisa primeiro em profundidade". A Figura 6.1 ilustra esta idéia. Ali é representada a árvore cor- respondente à execução do seguinte programa abstrato, onde a, b, c, etc. possuem a sintaxe de termos Prolog: a :- b. a :- c. a :- d. b :- e. b :- f. f :- g. f :- h. f :- i. d. a b c d e f g h i 1 2 3 4 5 6 7 8 9 Figura 6.1 Ordem de visita aos nodos da árvore de pesquisa O programa representado na figura acima será bem sucedido somente quando o nodo d for atingido, uma vez que este é o único fato declarado no programa. De acordo com a ordenação das cláusulas, d será também o último nodo a ser visitado no processo de execução. O caminho percorrido é dado abaixo a, b, e, (b), f, g, (f), h, (f), i, (f), (b), (a), c, (a), d onde o caminho em backtracking é representado entre parênteses. 52 Como foi visto, os objetivos em um programa Prolog podem ser bem-sucedidos ou falhar. Para um objetivo ser bem-sucedido ele deve ser unificado com a cabeça de uma cláusula do programa e todos os objetivos no corpo desta cláusula devem também ser bem-sucedidos. Se tais condições não ocorre- rem, então o objetivo falha. Quando um objetivo falha, em um nodo terminal da árvore de pesquisa, o sistema Prolog aciona o mecanismo de backtracking, retornando pelo mesmo caminho percorrido, na tentativa de encontrar soluções alternativas. Ao voltar pelo caminho já percorrido, todo o trabalho executado é desfeito. O seguinte exemplo, sobre o predicado gosta/2 pode ajudar a esclarecer tais idéias. gosta(joão, jazz). gosta(joão, renata). gosta(joão, lasanha). gosta(renata, joão). gosta(renata, lasanha). O significado intuitivo do predicado gosta(X, Y) é "X gosta de Y". Supondo o conhecimento acima, queremos saber do que ambos, joão e renata, gostam. Isto pode ser formulado pelos objetivos: gosta(joão, X), gosta(renata, X). O sistema Prolog tenta satisfazer o primeiro objetivo, desencadeando a seguinte execução top-down: 1. Encontra que joão gosta de jazz 2. Instancia X com "jazz" 3. Tenta satisfazer o segundo objetivo, determinando se "renata gosta de jazz" 4. Falha, porque não consegue determinar se renata gosta de jazz 5. Realiza um backtracking na repetição da tentativa de satisfazer gosta(joão, X), esquecendo o valor "jazz" 6. Encontra que joão gosta de renata 7. Instancia X com "renata" 8. Tenta satisfazer o segundo objetivo determinando se "renata gosta de renata" 9. Falha porque não consegue demonstrar que renata gosta de renata 10.Realiza um backtracking, mais uma vez tentando satisfazer gosta(joão, X), esquecendo o valor "renata" 11.Encontra que joão gosta de lasanha 12.Instancia X com "lasanha" 13.Encontra que "renata gosta de lasanha" 14.É bem-sucedido, com X instanciado com "lasanha" O backtracking automático é uma ferramenta muito poderosa e a sua exploração é de grande utilidade para o programador. Às vezes, entretanto, ele pode se transformar em fonte de ineficiência. A seguir se introduzirá um mecanismo para "podar" a árvore de pesquisa, evitando o backtracking quando este for indesejável. 6.2 O OPERADOR "CUT" O papel desempenhado pelo operador "cut", é de extrema importância para semântica operacional dos programas Prolog, permitindo declarar ramificações da árvore de pesquisa que não devem ser retoma- das no backtracking. Seu uso deve ser considerado pelas seguintes razões: (i) O programa irá executar mais rapidamente, porque não irá desperdiçar tempo tentando satisfa- 53 zer objetivos que não irão contribuir para a solução desejada. (ii)Também a memória será economizada, uma vez que determinados pontos de backtracking não necessitam ser armazenados para exame posterior. Algumas das principais aplicações do cut são as seguintes: • Unificação de padrões, de forma que quando um padrão é encontrado os outros padrões possí- veis são descartados • Na implementação da negação como regra de falha • Para eliminar da árvore de pesquisa soluções alternativas quando uma só é suficiente • Para encerrar a pesquisa quando a continuação iria conduzir a uma pesquisa infinita, etc. Sintaticamente o uso do cut em uma cláusula tem a aparência de um objetivo sem nenhum argumento, representado por um ponto de exclamação "!". Vamos estudar agora o comportamento de um pequeno programa que realiza algum backtracking des- necessário. Identificaremos onde isso ocorre e mostraremos como a eficiência do programa pode ser melhorada. Considere a função cujo gráfico é apresentado na Figura 6.2. 0 1 2 3 4 5 6 7 8 9 10 X 0 1 2 3 4 Y=F(X) Figura 6.2 Uma função em degraus A relação entre X e Y para a função apresentada na figura acima pode ser especificada, para o domí- nio dos inteiros não negativos, por meio de três regras: (1)Se X < 3, então Y = 0 (2)Se 3 ≤ X e X < 6, então Y = 2 (3)Se 6 ≤ X, então Y = 4 que podem ser escritas em Prolog como uma relação binária f(X, Y), como se segue: f(X, 0) :- X < 3. f(X, 2) :- 3 =< X, X < 6. f(X, 4) :- 6 =< X. Este programa assume que antes de f(X, Y) ser avaliada, X deve obrigatoriamente estar instanciada para algum número, como é requerido pelos operadores de comparação. Faremos duas experiências com esse programa. Em cada uma delas será identificada uma fonte de ineficiência no programa, que será removida com o uso do cut. 6.2.1 EXCLUSÃO MÚTUA Vamos analisar o que ocorre quando a seguinte questão é formulada: ?-f(1, Y), 2 < Y 56 execução de C, sendo completamente invisível do ponto de vista de A. Assim o backtracking automá- tico continua ativo independentemente do cut na cláusula usada para satisfazer o objetivo C. 6.3 APLICAÇÕES DO CUT Apresenta-se nesta seção alguns exemplos de pequenas aplicações empregando o operador cut, visan- do ilustrar o seu uso em programas reais. 6.3.1 MÁXIMO DE DOIS NÚMEROS O procedimento para encontrar o maior de dois números pode ser programado como uma relação max(X, Y, Max), onde Max=X se X for maior ou igual a Y e Max=Y se este for maior que X. Isto pode ser escrito em Prolog por meio das seguintes cláusulas: max(X, Y, X) :- X >= Y. max(X, Y, Y) :- X < Y. Essas duas regras são mutuamente exclusivas. Se a primeira for bem sucedida, então a segunda certa- mente irá falhar e vice-versa. Portanto uma forma mais econômica de representar o mesmo programa com o uso do cut seria: max(X, Y, X) :- X >= Y, !. max(X, Y, Y). 6.3.2 SOLUÇÃO ÚNICA PARA A OCORRÊNCIA No capítulo anterior definiu-se a relação membro(X, L) para estabelecer se X está presente na lista L. O programa era: membro(X, [X|_]). membro(X, [_|Y]) :- membro(X, Y). Essa solução é não-determinística. Se X ocorre várias vezes, então qualquer ocorrência pode ser en- contrada. Vamos agora mudar o predicado membro/2, tornando-o um programa determinístico que irá sempre encontrar a primeira ocorrência de X. A modificação a fazer é simples: apenas evitamos o backtracking tão logo X tenha sido encontrado, o que acontece quando a primeira cláusula é bem- sucedida. O programa modificado fica: membro(X, [X|_]) :- !. membro(X, [_|Y]) :- membro(X, Y). e agora somente a primeira solução será encontrada. Por exemplo: ?-membro(X, [a, b, c, d]). X=a; não 6.3.3 ADIÇÃO DE ELEMENTOS SEM DUPLICAÇÃO Freqüentemente deseja-se adicionar um item X a uma lista L de modo que X seja adicionado a L so- mente se X ainda não estiver em L. Se X já estiver em L, então a lista permanecerá a mesma, porque não desejamos a duplicação dos elementos em L. Uma adição adicionar(X, L, L1), com essas caracte- rísticas, pode ser formulada da seguinte maneira: Se X é membro da lista L, então L1 = L senão, L1 é igual a L com a inserção de X na cabeça. 57 É mais fácil inserir X como primeiro elemento, de modo que X se torna a cabeça de L1 quando se verifica a sua ausência na lista. Em Prolog escreve-se: adicionar(X, L, L) :- membro(X, L), !. adicionar(X, L, L1). O comportamento desse programa pode ser ilustrado pelos exemplos abaixo: ?-adicionar(a, [b,c], L). L=[a, b, c] ?-adicionar(X, [b,c], L). X=b L=[b, c] ?-adicionar(a, [b, c, X], L). X=a L=[b, c, a] Esse exemplo é instrutivo, porque não é possível programar facilmente a "adição sem duplicatas" sem o uso do cut ou de alguma outra construção dele derivada. Portanto o cut é necessário aqui para espe- cificar a relação correta e não somente para incrementar a eficiência do programa. 6.3.4 IF-THEN-ELSE A programação procedimental estruturada pode ser simulada em Prolog. Neste exemplo a estrutura if- then-else é descrita através da relação: ifThenElse(X, Y, Z) que deve ser interpretada da seguinte maneira: "Se X for verdadeiro, então execute Y, senão execute Z". O programa Prolog é: ifThenElse(X, Y, _) ¬ X, !, Y. ifThenElse(_, _, Z) ¬ Z. Deve-se notar que este programa emprega meta-variáveis (variáveis que podem ser instanciadas com chamadas a predicados), o que não é diretamente representado em todas as implementações Prolog. Em sendo possível, o exemplo abaixo ilustra a utilização de tal programa: ?-ifThenElse(X, Y is Z+1, Y is 0). Aqui, se o predicado representado por X for verdadeiro, a variável Y será instanciada com "Z+1", caso contrário, se X for falso, Y será instanciada com o valor zero. O emprego de meta-variáveis requer alguma experiência em programação em lógica. Tal recurso não deve ser aplicado indiscriminadamente sob pena de comprometer a legibilidade e o perfeito entendi- mento do programa. Por outro lado, se bem utilizado, é um recurso muito poderoso nas mãos de um bom programador. 6.4 NEGAÇÃO POR FALHA "Maria gosta de todos os animais, menos de cobras". Como podemos dizer isto em Prolog? É fácil expressar uma parte dessa declaração: Maria gosta de X se X é um animal, isto é: gosta(maria, X) ¬ animal(X). mas é necessário ainda excluir as cobras. Isto pode ser conseguido empregando-se uma formulação diferente: Se X é uma cobra, então não é verdade que maria gosta de X senão se X é um animal, então maria gosta de X. Podemos dizer que alguma coisa não é verdadeira em Prolog por meio de um predicado pré-definido 58 especial, "fail", que sempre falha, forçando o objetivo pai a falhar. A formulação acima pode ser dada em Prolog com o uso do fail da seguinte maneira: gosta(maria, X) :- cobra(X), !, fail. gosta(maria, X) :- animal(X). Aqui a primeira regra se encarrega das cobras. Se X é uma cobra, então o cut evita o backtracking (assim excluindo a segunda regra) e o fail irá ocasionar a falha da cláusula. As duas regras podem ser escritas de modo mais compacto como uma única cláusula, por meio do uso do conetivo ";": gosta(maria, X) :- cobra(X), !, fail; animal(X). Pode-se usar essa mesma idéia para definir a relação diferente(X, Y) que, se for verdadeira, significa que X e Y não unificam. Isto pode ser formulado por: Se X e Y unificam então diferente(X, Y) falha senão diferente(X, Y) é bem-sucedido. Em Prolog: diferente(X, X) :- !, fail. diferente(X, Y). que também pode ser escrito sob a forma de uma só cláusula: diferente(X, Y) :- X=Y, !, fail; true. onde "true" é um objetivo pré-definido que sempre é bem-sucedido. Esses exemplos indicam que seria útil dispor de um objetivo unário "not" tal que not(Objetivo) seja verdadeiro se Objetivo não for ver- dadeiro. A relação not/1 pode ser definida da seguinte maneira: Se Objetivo é bem-sucedido então not(Objetivo) falha senão not(Objetivo) é bem-sucedido. que pode ser escrita em Prolog como: not(P) :- P, !, fail; true. A relação not/1 é pré definida na maioria das implementações Prolog e se comporta como o procedi- mento apresentado acima. Vamos assumir ainda, como ocorre na maioria das vezes, que o not seja definido como um operador prefixo, de modo que podemos escrever not(cobra(X)) como not co- bra(X). Deve ser notado que a relação not/1, definida como negação por falha, como foi feito, não correspon- de exatamente à negação da lógica matemática. Essa diferença pode ocasionar um comportamento inesperado do programa, se o not for usado sem cuidado. Apesar disso, o not é um instrumento muito útil e pode ser utilizado com vantagem no lugar do cut. Os dois exemplos dados anteriormente poderi- am ser escritos com o uso do not da seguinte maneira: gosta(maria, X) :- animal(X), not cobra(X). diferente(X, Y) :- not (X = Y). que certamente são formulações melhores que as anteriores. São mais naturais e mais fáceis de ler. 6.5 CUIDADOS COM O CUT E A NEGAÇÃO As vantagens e desvantagens do uso do cut foram ilustradas por meio de exemplos nas seções anterio- res. Vamos resumir primeiro as vantagens: 61 Defina este procedimento de uma forma mais eficiente usando cuts. 6.3 Escreva um programa denominado reparte(Números, Positivos, Negativos). que reparte uma lista de números em duas listas: uma de números positivos (incluindo o zero) e outra de números negativos. Por exemplo: reparte([3,-1,0,5,-2], [3,0,5], [-1,-2]). Proponha duas versões: uma com um único cut e outra sem nenhum. 6.4 Defina o predicado: unificável(Lista1, Termo, Lista2) onde Lista2 é a lista de todos os elementos de Lista1 que unificam com Termo, deixando-os não instanciados na resposta. Por exemplo: ?-unificável([X, b, t(Y)], t(a), Lista). Lista=[X, t(Y)] Note que X e Y devem permanecer não-instanciados, apesar de a unificação com t(a) causar sua instanciação. Dica: use not (Termo1=Termo2). Se Termo1=Termo2 for bem-sucedido, então not (Termo1=Termo2) falha e a instanciação realizada é desfeita. 62 7. ESTRUTURAS DE DADOS A possibilidade de empregar em Prolog estruturas de dados com unificação, backtracking e aritmética tornam essa linguagem de programação extremamente poderosa. No presente capítulo estudaremos estruturas de dados complexas por meio de exemplos de programas: recuperação de informação es- truturada em uma base de dados, a simulação de um autômato não-determinístico e um planejamento de roteiros de viagens. Também se introduzirá o conceito de abstração de dados em Prolog. 7.1 RECUPERAÇÃO DE INFORMAÇÕES O exercício apresentado a seguir desenvolve a habilidade de representar e estruturar objetos de dados e também ilustra a visão do Prolog como uma linguagem natural de consulta a bases de dados. Consi- dere a figura 7.1. família Plá pessoa pessoapessoa datadata Ari Plá trab 17 05 65 ibn 1500 data Ana Plá trab 06 11 68 rbz 1100 Ada Plá nt 18 02 91 Figura 7.1 Informação estruturada sobre uma família Uma base de dados pode ser naturalmente representada em Prolog como um conjunto de fatos. Por exemplo, uma base de dados sobre famílias pode ser representada de modo que cada família seja des- crita como um termo. A Figura 7.1 mostra como a informação sobre cada família pode ser estruturada em um termo família/3, com a seguinte forma: família(Pai, Mãe, Filhos) onde Pai e Mãe são pessoas e Filhos é uma lista de pessoas. Cada pessoa é, por sua vez, representada por uma estrutura com quatro componentes: nome, sobrenome, data de nascimento e trabalho. A data de nascimento é fornecida como um termo estruturado data(Dia, Mes, Ano). O trabalho, ou é forneci- do por um termo trab(Empresa, Salário), ou pela constante nt, indicando que a pessoa em questão não trabalha. A família exemplificada pode então ser armazenada na base de dados como uma cláusula do tipo: família(pessoa(ari, plá, data(17,05,65), trab(ibn,1500)), pessoa(ana, plá, data(06,11,68), trab(rbs,1100)), [pessoa(ada, plá, data(18,02,91), nt)] ) A base de dados poderia ser vista então como uma seqüência de fatos, descrevendo todas as famílias que interessam ao programa. A linguagem Prolog é, na verdade, muito adequada para a recuperação da informação desejada a partir de uma base de dados. Um detalhe muito interessante é que os objetos desejados não precisam ser completamente especificados. Pode-se simplesmente indicar a estrutura 63 dos objetos que interessam e deixar os componentes particulares apenas indicados. Por exemplo, se queremos recuperar todas as famílias "Oliveira", basta especificar: ?-família(pessoa(_, oliveira, _, _), _, _). ou as famílias cujas mães não trabalham: ?-família(_, pessoa(_, _, _, nt), _). as famílias que não possuem filhos: ?-família(_, _, []). ou ainda famílias que possuem três ou mais filhos: ?-família(_, _, [_, _, _| _]). As possibilidades de consulta são as mais diversas. Com esses exemplos queremos demonstrar que é possível especificar os objetos de interesse, não pelo seu conteúdo, mas sim pela sua estrutura, sobre a qual restringimos os componentes conforme nossas necessidades e/ou disponibilidades, deixando os demais indefinidos. Na Figura 7.2 é apresentado um programa demonstrando algumas das relações que podem ser estabelecidas em função de uma base de dados estruturada na forma definida por fa- mília/3: pai(X) :- família(X, _, _). mãe(X) :- família(_, X, _). filho(X) :- família(_, _, Filhos), membro(X, Filhos). membro(X, [X|_]). membro(X, [_|Y]) :- membro(X, Y). existe(Pessoa) :- pai(Pessoa); mãe(Pessoa); filho(Pessoa). nasceu(pessoa(_, _, Data, _), Data). salário(pessoa(_, _, _, trab(_,S)), S). salário(pessoa(_, _, _, nt), 0). Figura 7.2 Um programa baseado na relação família/3 Algumas aplicações para os procedimentos mostrados na figura acima podem ser encontrados nas seguintes consultas à base de dados: • Achar o nome e sobrenome de todas as pessoas existentes na base de dados: ?-existe(pessoa(Nome, Sobrenome, _, _)). • Achar todas as crianças nascidas em 1993: ?-filho(X), nasceu(X, data(_,_,93)). • Achar todas as pessoas desempregadas que nasceram antes de 1976: ?-existe(pessoa(_, _, data(_,_,A), nt), A < 76. • Achar as pessoas nascidas após 1965 cujo salário é maior do que 5000: ?- existe(Pessoa), nasceu(Pessoa, data(_,_,A)), A > 65, salário(Pessoa, Salário), Salário > 5000. Para calcular o total da renda familiar, pode ser útil definir a soma dos salários de uma lista de pesso- as como uma relação de dois argumentos: 66 os strings "abb" e "abba". É fácil demonstrar que o autômato aceita qualquer string que termina em "ab" e rejeita todos os demais. Autômatos como esse podem ser descritos por meio de três relações: (1)Uma relação unária, final/1, que define os estados finais do autômato; (2)Uma relação de três argumentos, trans/3, que define as transições de estado de forma que trans(S1, X, S2) significa que uma transição do estado S1 para o estado S2 é possível quando o símbolo de en- trada X for lido; (3)Uma relação binária, silêncio(S1, S2), significando que um "movimento silencioso" é possível de S1 para S2. Para o autômato apresentado na Figura 7.3 essas três relações podem ser formuladas em Prolog da seguinte maneira: final(s3). trans(s1, a, s1). trans(s1, a, s2). trans(s1, b, s1). trans(s2, b, s3). trans(s3, b, s4). silêncio(s2, s4). silêncio(s3, s1). Representaremos os strings de entrada como listas, de modo que o string "aab" será representado por [a, a, b]. Dada a descrição do autômato, o simulador processará um determinado string de entrada e decidirá se este deve ser aceito ou rejeitado. Por definição, os autômatos não-determinísticos aceitam um dado string se, partindo de um estado inicial, após ter lido o string completo o autômato pode estar em seu estado final. O simulador é programado por meio de uma relação binária, aceita/2, que define a aceitação de um determinado string a partir de um estado inicial. Assim a relação aceita(Estado, String). é verdadeira se o autômato, a partir do de um estado inicial "Estado", aceita o string "String". A rela- ção aceita/2 pode ser definida por meio de três cláusulas, que correspondem aos três casos seguintes: (1)O string vazio, [], é aceito a partir de um determinado estado S se S é um estado final; (2)Um string não-vazio é aceito a partir de um estado S, se a leitura do primeiro símbolo no string pode conduzir o autômato a algum estado S1 e o resto do string é aceito a partir de S1; (3)Um string é aceito a partir de um estado S, se o autômato pode realizar um movimento silencio- so de S para S1, e então aceitar o string completo a partir de S1. Esses três casos originam as seguintes cláusulas: aceita(S, []) :- final(S). aceita(S, [X | R]) :- trans(S, X, S1), aceita(S1, R). aceita(S, L) :- silêncio(S, S1), aceita(S1, L). Por meio dessa relação é possível perguntar se um determinado string é aceito pelo autômato. Por exemplo: ?-aceita(s1, [a, a, a, b]). sim Como foi visto anteriormente, os programas Prolog são frequentemente capazes de solucionar pro- blemas mais gerais do que aqueles para os quais foram originalmente concebidos. No presente caso, podemos por exemplo perguntar ao simulador a partir de quais estados ele aceitaria um determinado string: 67 ?-aceita(S, [a, b]). S=s1; S=s3; não Outra possibilidade seria perguntar quais são os strings de três símbolos que são aceitos pelo autô- mato a partir de um determinado estado: ?-aceita(s1, [X, Y, Z]). X=a Y=a Z=b; X=b Y=a Z=b; não É possível ainda realizar diversos outros experimentos envolvendo questões ainda mais gerais, como por exemplo: "a partir de que estados o autômato aceitará strings de tamanho sete?", etc. Experimen- tos ainda mais complexos podem inclusive requerer modificações na estrutura do autômato, mudando as relações final/1, trans/3 e silêncio/2. 7.4 PLANEJAMENTO DE ROTEIROS AÉREOS Na presente seção iremos construir um programa para auxiliar o planejamento de roteiros aéreos. Apesar de bastante simples, o programa será capaz de responder questões tais como: • Em que dias da semana há vôos entre o Rio e Munique? • Como se pode chegar a Tóquio partindo de Porto Alegre numa terça-feira? • Tenho que visitar Montevidéu, Buenos Aires e Assunção, partindo de Brasília numa terça-feira à noite e chegando ao Rio na sexta-feira para o fim-de-semana. Em que seqüência deve ser rea- lizada a viagem de forma que eu não tenha de fazer mais de um vôo por dia? O programa será desenvolvido em função de uma base de dados possuindo informações sobre os vôos, representada por meio de uma relação com três argumentos: horário(Cidade1, Cidade2, ListaDeVôos). onde ListaDeVôos é uma lista de termos estruturados na forma: Partida/Chegada/CódVôo/DiasDaSemana Partida e Chegada representam termos contendo os horários de partida, em Cidade1, e chegada em Cidade2. CódVôo é uma constante utilizada na identificação do vôo. DiasDaSemana é uma lista con- tendo os dias da semana em que o vôo é realizado, ou a constante "todos", significando que o vôo é realizado todos os dias. Uma cláusula da relação horário/3 poderia ser, por exemplo: horário('porto alegre', miami, [12:30/21:00/vrg127/todos, 15:30/24:00/vrg911/[seg,qua,sex]]). Os horários são representados como objetos estruturados com dois componentes, horas e minutos, separados por ":". O problema principal será encontrar uma rota exata entre duas cidades, partindo em um determinado dia da semana. Isso será programado como uma relação de quatro argumentos: rota(Cidade1, Cidade2, Dia, Rota) onde Rota é uma seqüência de vôos que satisfaz aos seguintes critérios: (1)O ponto de partida da Rota é Cidade1; (2)O ponto de chegada da Rota é Cidade2; (3)Todos os vôos são no mesmo dia Dia; (4)Todos os vôos em Rota estão na relação horário/3; (5)Há tempo suficiente para as transferências de vôo. A rota é representada por uma lista de termos estruturados na forma: De-Para : CódVôo : Partida 68 e serão empregados os seguintes predicados auxiliares: (1)vôo(Cidade1, Cidade2, Dia, CódVôo, Partida, Chegada): dizendo que há um vôo (CódVôo) en- tre Cidade1 e Cidade2, no dia da semana Dia, que parte no horário de Partida e chega no horá- rio de Chegada; (2)partida(Rota, Hora): A partida da rota Rota ocorre na hora Hora; (3) transferência(Hora1, Hora2): Há pelo menos 40 minutos entre Hora1 e Hora2, que devem ser suficientes para a transferência entre dois vôos. O problema de encontrar uma rota, dadas as condições apresentadas, é em muitos pontos semelhante à simulação de um autômato finito não-determinístico apresentada na seção anterior. Os pontos comuns aos dois problemas são: • Os estados do autômato correspondem às cidades; • Uma transição entre dois estados corresponde a um vôo entre duas cidades; • A relação trans/3 do autômato corresponde à relação horário/3 do planejador de vôo; • O simulador do autômato encontra um caminho no grafo de transição entre um estado inicial e um estado final. O planejador de vôo encontra uma rota entre a cidade de partida e a cidade destino da viagem. Não é portanto surpresa que a relação rota/4 possa ser definida de maneira semelhante à relação acei- ta/2. Uma vez que agora não há "movimentos silenciosos", devemos nos concentrar em dois casos: (1)Vôo Direto: Se há um vôo direto entre as cidades C1 e C2, então a rota consiste em um único vôo: rota(C1, C2, Dia, [C1-C2:CodVôo:Partida]) :- vôo(C1,C2,Dia,CodVôo,Partida,Chegada). (2)Vôo com Conexões: A rota entre C1 e C2 consiste em: primeiro um vôo de C1 para alguma ci- dade intermediária, C3, seguida por uma rota entre C3 e C2. Além disso, deve haver tempo su- ficiente entre a chegada de um vôo e a partida do seguinte para a transferência de avião: rota(C1,C2,Dia,[C1-C3:CodVôo1:Partida1 | Rota]) :- rota(C2, C3, Dia, Rota), vôo(C1, C3, Dia, CodVôo1, Partida1, Chegada1), partida(Rota, Partida2), transferência(Chegada1, Partida2). As relações auxiliares vôo/6, partida/2 e transferência/2 são facilmente programadas e estão definidas juntamente com o programa completo de planejamento de roteiros aéreos, apresentado na Figura 7.4, onde também se encontra incluído um pequeno exemplo da base de dados construída com a relação horário/3. O planejador de roteiros aéreos ali apresentado, apesar de extremamente simples pode resolver com eficiência o planejamento de rotas aéreas desde que a base de dados não seja demasiadamente grande. Para esses casos seria necessário um planejador mais eficiente que permitisse lidar com um número muito grande de rotas alternativas. 71 8. ENTRADA E SAÍDA Neste capítulo estudaremos alguns recursos embutidos, presentes na maioria das implementações Prolog, destinados à leitura e gravação de dados em arquivos. Tais recursos podem também ser em- pregados pelo usuário para a formatação de objetos no programa, de modo a atingir alguma represen- tação externa desejada para tais objetos. Também introduziremos os recursos para a leitura de pro- gramas e para a construção e decomposição de átomos e termos. 8.1 ARQUIVOS DE DADOS O método de comunicação entre o usuário e o programa que estivemos usando até agora consiste em consultas realizadas pelo usuário que são respondidas pelo programa por meio de instanciações de variáveis. Esse método é simples e prático e, apesar de sua simplicidade, é suficiente para obter a entrada e saída de informações. Muitas vezes, entretanto, tal método não é suficientemente adequado tendo em vista a sua rigidez. Extensões a esse método básico tornam-se necessárias nos seguintes casos: • Entrada de dados sob forma diferente das consultas, por exemplo, sob a forma de sentenças em linguagem natural, • Saída de informações em qualquer formato desejado, e • Entrada e saída para qualquer arquivo periférico do computador e não somente para o terminal do usuário. Predicados pré-definidos, construídos com o objetivo de apoiar tais intenções são dependentes de cada particular implementação da linguagem Prolog. Aqui se introduz um repertório simples, que se encontra presente na maioria dessas implementações, apesar disso, o manual específico do Prolog utilizado deve ser consultado para detalhes. Inicialmente se estudará o problema de direcionar a entrada e saída de dados para arquivos e, depois, como os dados podem entrar e sair em diferentes formatos. A Figura 8.1 mostra uma situação geral onde um programa Prolog se comunica com diversos arquivos: Terminal do Usuário Programa Prolog Arquivo 1 Arquivo 2 Arquivo 3 Arquivo 4 Fontes de Entrada Fontes de Saída Figura 8.1: Comunicação entre um programa Prolog e diversos arquivos Como pode ser visto na figura acima, o programa pode se comunicar com diversos arquivos, receben- do informações das denominadas "fontes de entrada" e transmitindo informações às denominadas "fontes de saída". Os dados que vem do terminal do usuário são tratados como uma outra fonte de entrada qualquer. Da mesma forma, os dados transmitidos ao terminal do usuário são tratados como uma fonte de saída. Esses dois pseudo-arquivos são nomeados pela constante "user". Os nomes dos outros arquivos podem ser escolhidos pelo programador de acordo com as regras adotadas em cada particular implementação. 72 A qualquer momento da execução de um programa Prolog, somente dois arquivos estão ativos: um para entrada e outro para saída. Esses dois arquivos se denominam respectivamente "fonte de entrada corrente" e "fonte de saída corrente.. No início da execução essas duas fontes correspondem ao termi- nal do usuário. A fonte de entrada corrente pode ser mudada a qualquer momento para um outro ar- quivo qualquer, digamos "novoArqEnt", por meio do objetivo: see(novoArqEnt). Esse objetivo é sempre bem sucedido (a menos que haja alguma coisa errada com NovoArqEnt. Um exemplo típico de utilização do predicado see/1 é a seguinte seqüência de objetivos, que lê alguma coisa de um certo arquivo, "arq1", e então retorna ao terminal do usuário: ... see(arq1). lê_do_arquivo(Informação). see(user). ... A fonte de saída corrente pode também ser mudada por um objetivo da forma: tell(novoArqSai). Uma seqüência de objetivos para enviar alguma informação para "arq3" e depois redirecionar a saída para o terminal do usuário poderia ser: ... tell(arq3). grava_no_arquivo(Informação). tell(user). ... Dois outros predicados pré-definidos que devem ser mencionados aqui são seen/0 e told/0, cujo efeito é fechar os arquivos correntes de entrada e saída respectivamente. Os arquivos podem ser processados somente na forma sequencial. nesse sentido, todos os arquivos se comportam da mesma maneira que o terminal do usuário. Cada requisição para a leitura de alguma coisa a partir de alguma fonte de entrada irá ocasionar a leitura a partir da posição corrente dessa fonte de entrada. Após a leitura, a posição corrente dessa fonte de entrada será, naturalmente, o pró- ximo item que ainda não foi lido, de forma que uma nova requisição de leitura irá iniciar a ser execu- tada iniciando nessa nova posição corrente. Se uma requisição de leitura é feita para o fim do arquivo, então a informação devolvida será a constante "end_of_file", indicandio que o fim do arquivo foi atingido. Uma vez que alguma informação foi lida, não é possível lê-la novamente a menos que se retome a leitura do arquivo a partir do início. A saída de informações ocorre de maneira similar. Cada requisição de saída irá adicionar a informa- ção requisitada no final da fonte de saída corrente. Da mesma forma que na leitura, não é possível retornar e reescrever sobre a porção do arquivo que já foi escrita. Todos os arquivos são do tipo "texto", isto é, arquivos de caracteres. Os caracteres podem ser letras, dígitos, ou de algum tipo especial. Alguns desses últimos são ditos ser "não-imprimíveis" porque quando são direcionados para o terminal do usuário eles não aparecem no vídeo. Podem, no entanto, possuir algum outro efeito como o espaçamento entre colunas e linhas, reposicionamento do cursor, etc. Há duas maneiras diferentes de se utilizar os arquivos em Prolog, dependendo da forma que se deseja empregar para os dados. A primeira delas considera o caracter como o elemento básico do arquivo. Assim uma requisição de entrada ou saída ocasionará a leitura ou escrita de um único caracter. Os predicados pré-definidos para tratar essa modalidade de arquivo são get/1, get0/1 e put/1. A outra forma de utilizar arquivos em Prolog é considerar unidades maiores de informação como ele- mentos básicos de entrada e saída. Tais unidades são os termos Prolog. Assim, cada requisição de 73 entrada ou saída desse tipo irá ocasionar a transferência de um termo inteiro. Os predicados que exe- cutam a transferência de termos são read/1 e write/1. Naturalmente, nesse caso, a informação deverá se encontrar numa forma que seja consistente com a sintaxe dos termos Prolog. O tipo de organização a ser escolhido para um determinado arquivo depende naturalmente do proble- ma que se está tentando resolver, entretanto, sempre que a especificação do problema permitir, iremos preferir trabalhar com arquivos de termos, que permitem a transferência de uma unidade significativa completa através de uma única requisição. Por outro lado, há problemas cuja natureza determina o emprego de alguma outra organização. Um exemplo é o processamento de sentenças em linguagem natural para, digamos, estabelecer um diálogo com o usuário. Em tais casos os arquivos deverão ser vistos como seqüências de caracteres, uma vez que a linguagem natural não pode, normalmente, ser reduzida para a forma de termos. 8.2 PROCESSAMENTO DE ARQUIVOS DE TERMOS 8.2.1 READ & WRITE O predicado pré-definido read/1 é usado para a leitura de termos a partir da fonte de entrada corrente. O objetivo read(X) irá ocasionar a leitura do próximo termo T que será unificado com X. Se X é uma variável, então, como resultado da leitura, X será instanciada com T. Se a unificação não for possível, então o objeti- vo read(X) irá falhar. O predicado read/1 é determinístico, significando que, em caso de falha, não haverá backtracking para a leitura de outro termo. cada termo, no arquivo de entrada, deve ser seguido por um ponto e um espaço ou "carriage-return". Se read(X) é executado sobre o final do arquivo de entrada, então a variável X será instanciada com o termo "end_of_file". O predicado pré-definido write/1 fornece a saída de um termo. Assim o objetivo write(X) irá ocasio- nar a escrita do termo X sobre a fonte de entrada corrente. X será escrito com a mesma forma sintática padrão utilizada pelo Prolog na apresentação de termos. Um recurso muito útil do Prolog é que o pre- dicado write/1 "sabe" apresentar qualquer termo, independente de sua complexidade. Há ainda dois predicados adicionais para a formatação da saída. Eles são usados para inserir espaços e linhas na fonte de saída. O objetivo tab(N) irá ocasionar a saída de "N" espaços. O predicado nl/0 (sem argumentos) irá ocasionar o início de uma nova linha. os seguintes exemplos ilustram o uso dos procedimentos estudados. Vamos assumir que temos um procedimento que computa o cubo de um número dado: cubo(N, C) :- C is N*N*N. Suponha que desejamos empregá-lo para calcular os cubos de uma seqüência de números. Isso pode ser obtido por meio de uma seqüência de questões: ?-cubo(2, X). X=8 ?-cubo(5, Y). Y=125 ?-cubo(12, Z). Z=1728 Aqui, para cada número é necessário formular um objetivo completo. Vamos agora modificar o pro- grama de forma a "interiorizar" a ação, tornando mais suave o interface com o usuário. O programa agora irá manter-se lendo um número e apresentando o seu cubo até que a constante "fim" seja lida da fonte de entrada. cubo :- read(X), processa(X). 76 8.2.3 FORMATAÇÃO DE TERMOS Vamos considerar novamente a representação sob a forma de termos usada para definir famílias, dis- cutida na seção 7.1. Se uma variável F for instanciada com o termo cuja estrutura é mostrada na figura 7.1, o objetivo write(F) irá ocasionar a saída do termo correspondente no formato padrão do Prolog. Alguma coisa como: família(pessoa(ari, plá, data(17,05,65), trab(ibn,1500)), pessoa(ana, plá, data(06,11,58), trab(rbz,1100)), [pessoa(ada, plá, data(18,02,91), nt)]) O termo acima contém, sem dúvida, toda a informação, entretanto sob uma forma bastante confusa, tornando difícil seguir as partes da informação que formam as unidades semânticas. Iríamos, certa- mente, preferir que a informação fosse apresentada de outra maneira, por exemplo, na forma abaixo: Pais: ari plá, nasc: 16/05/65, trab: ibn, sal: 1500 ana plá, nasc: 06/11/68, trab: rbz, sal: 1100 Filhos: ada plá, nasc: 18/02/91, não trabalha. Tal formato pode ser obtido por meio do procedimento escreveFam/1 mostrado na Figura 8.2. 8.2.4 PROCESSAMENTO DE ARQUIVOS DE TERMOS Uma típica seqüência de objetivos para processar completamente um arquivo "A" se pareceria com o seguinte: ... see(A), processaArq, see(user), ... Aqui processaArq/0 é um procedimento para ler e processar cada termo em A, um após o outro, até que o fim do arquivo seja encontrado. Um esquema típico para processaArq é o seguinte: processaArq :- read(Termo), processa(Termo). processa(end_of_file) :- !. processa(Termo) :- trata(Termo), processaArq. Aqui o procedimento trata/1 representa qualquer coisa que se deseje fazer com cada um dos termos presentes no arquivo. Um exemplo poderia ser um procedimento para apresentar no terminal cada um dos termos do arquivo, juntamente com o seu respectivo número de ordem. Vamos chamar tal proce- dimento mostraArq(N), onde N é um argumento adicional para contar os termos lidos. mostraArq(N) :- read(Termo), mostra(1, Termo). mostra(_, end_of_file) :- !. mostra(N, Termo) :- write(N), tab(2), write(Termo), N1 is N+1, mostraArq(N1). outro exemplo de utilização do esquema dado para o processamento de arquivos de termos é o se- guinte: Temos um arquivo denominado "arq1" que contém termos na forma: item(Nro, Descrição, Preço, Fornecedor) Cada termo descreve uma entrada num catálogo de itens. Desejamos produzir um outro arquivo que contenha somente os itens fornecidos por um determinado fornecedor. Como o fornecedor nesse novo arquivo será sempre o mesmo, o seu nome somente precisa ser escrito no início do arquivo, sendo omitido nos demais termos. Denominaremos tal procedimento de fazArq(Fornecedor) Por exemplo, se o catálogo original é armazenado em arq1 e desejamos produzir um arquivo arq2 com todos os artigos fornecidos por 'Palmeira & Cia", então usaremos o procedimento fazArq/1 da se- 77 guinte maneira: ..., see(arq1),tell(arq2),fazArq('Palmeira & Cia'),see(user),tell(user), ... O procedimento fazArq/1 é apresentado na Figura 8.3 fazArq(F) :- write(F), write('.'), nl, fazResto(F). fazResto(F) :- read(Item), processa(Item, F). processa(end_of_file, _) :- !. processa(item(N, D, P, F), F) :- !, write(item(N, D, P)), write('.'), nl, fazResto(F). processa(_, F) :- fazResto(F). Figura 8.3 Processando um arquivo de itens Note que no programa acima, o predicado processa/2 grava um ponto após cada termo escrito em arq2, de modo a possibilitar leituras posteriores desse arquivo por meio do comando read/1. 8.3 PROCESSAMENTO DE CARACTERES Um caracter é escrito na fonte de saída corrente por meio do objetivo: put(C) onde C é o código ASCII (um número entre 0 e 255) do caracter a ser escrito. Por exemplo, a consul- ta: ?-put(65), put(66), put(67). produz a saída: ABC uma vez que 65 é o código ASCII de 'A', 66 de 'B' e 67 de 'C'. Por sua vez um caracter pode ser lido a partir da fonte de entradacorrente por meio do objetivo: get0(C) que ocasiona a leitura do caracter corrente e torna a variável C instanciada para com o código ASCII deste caracter. Uma variação do predicado get0/1 é o get/1, que é utilizado para a leitura apenas de caracteres imprimíveis, saltando sobre todos os caracteres não-imprimíveis, particularmente espaços em branco. Como um exemplo do uso de predicados que transferem caracteres, vamos definir um procedimento comprime/0 para ler uma sentença da fonte de entrada corrente e apresentar essa sen- tença reformatada, de forma que múltiplos espaços em branco entre as palavras sejam substituídos por um único espaço em branco (código ASCII = 32). Para simplificar, vamos assumir que toda sentença de entrada processada pelo procedimento comprime/0 termina com um ponto final (código ASCII = 46) e que as palavras estejam separadas por um ou mais espaços em branco e nenhum outro caracter. Uma entrada aceitável seria: Genialidade é 1% de inspiração e 99% de transpiração. para a qual o procedimento comprime/0 devolveria: Genialidade é 1% de inspiração e 99% de transpiração. O procedimento comprime/0 terá uma estrutura similar aos procedimentos para processamento de arquivos estudados nas seções anteriores. Inicialmente ele vai ler o primeiro caracter e enviá-lo à saí- da e então completar o processo, dependendo do caracter que for lido. A exclusão mútua entre as três alternativas é obtida por meio de cuts: comprime :- get0(C), put(C), continua(C). 78 continua(46) :- !. continua(32) :- !, get(C), put(C), continua(C). continua(_) :- comprime. 8.4 CONVERSÃO DE TERMOS Frequentemente deseja-se trabalhar com informações que foram lidas sob a forma de caracteres, con- vertidas em termos como representação interna para processamento de entrada e saída. Há um predi- cado pré-definido, name/2, que pode ser usado com essa finalidade, relacionando os átomos com o seu código ASCII. Assim, name(X, L) é verdadeiro, se L é a lista dos códigos dos caracteres em A. Por exemplo, a assertiva abaixo é verdadeira: name(zx232, [122, 120, 50, 51, 50]) Há dois usos típicos para o predicado name/2: • Decompor um termo dado em seus caracteres, e • Dada uma lista de caracteres, converte-la em um termo. Um exemplo do primeiro tipo de aplicação seria a decomposição de átomos em átomos menores, com tamanho pré-definido. Suponhamos que recebemos, de alguma fonte de entrada, átomos de tamanho fixo de 13 caracteres, dos quais os oito primeiros correspondem ao CEP, os dois seguintes à unidade da federação (UF) e os três últimos à sigla internacional de cidade. Por exemplo: 90120040rspoa e 70605220dfbsb e desejamos, para fins de processamento, separá-los nos sub-átomos: 90120040 rs poa e 70605220 df bsb O predicado separa/4, abaixo, obtém o resultado desejado: separa(A, S1, S2, S3) :- name(A, L), conc([S1, S2, S3], [], L), tam(S1, 8), !, tam(S2, 2), !, tam(S3, 3). conc([], L, L). conc([X | L1], L2, [X | L3]) :- conc(L1, L2, L3). tam([], 0). tam([_|R], N) :- tam(R, N1), N1 is N+1. O próximo exemplo ilustra o uso da combinação de caracteres em átomos. Definiremos um predicado, fazFrase(Lista) que lê uma sentença em linguagem natural e instancia Lista com cada palavra da sen- tença representada por um átomo. Por exemplo, se a entrada fosse a seguinte frase, atribuída a Albert Einstein dirigindo-se a Sigmund Freud: "No matter what mind is and never mind what matter is." o objetivo fazFrase(Lista) ocasionaria a seguinte instanciação: Lista = ['No',matter,what,mind,is,and,never,mind,what,matter,is] para simplificar, assume-se que cada sentença termina com um ponto final e que não há símbolos de pontuação na sentença. O programa completo é mostrado na Figura 8.4. O procedimento fazFrase/1 lê o caracter corrente, C, e então transmite esse caracter ao procedimento fazResto para completar o serviço. fazFrase(Lista) :- get0(C), fazResto(C, Lista). 81 tença deve ser fornecida em sua forma original, representada como uma seqüência de caracteres ou como um átomo. O programa fazFrase/2 apresentado neste capítulo pode ser adequadamente modificado para atender as necessidades deste exercício. 8.5 Escreva um programa relatório/0 para ler um arquivo de termos na forma cliente(Nome, Endere- ço, Telefone) e produzir um relatório formatado da seguinte maneira: NRO CLIENTE ENDEREÇO TELEFONE 001 XXX... XXX... XXX.... 002 XXX... XXX... XXX... ..... ..... ..... ..... 8.6 Escreva um programa, plural(Palavra, Plural), para a formação do plural de palavras em portu- gues. Crie para isso uma base de regras de formação do plural de palavras. O resultado esperado é, por exemplo: ?-plural(pássaro, X). X=pássaros 82 9. PREDICADOS EXTRALÓGICOS Todas as implementações Prolog oferecem, em maior ou menor quantidade, um certo número de pre- dicados pré-definidos orientados a execução de rotinas que, ou são necessárias com muita freqüência, ou são de difícil programação, ou se destinam a um domínio particular realçado pela implementação, ou por todas essas razões em diferentes proporções. No presente capítulo se introduz alguns desses predicados, que facilitam muito a construção de programas interativos e orientados a aplicações con- cretas. 9.1 TIPOS DE TERMOS Os termos Prolog podem assumir os mais diversos aspectos, desde simples constantes até estruturas complexas altamente elaboradas. Se um termo é uma variável, então esta pode ou não estar instancia- da em algum momento da execução do programa. Além disso, se estiver instanciada, seu valor pode ser uma constante, uma estrutura, etc. Algumas vezes pode ser de utilidade para o programador identi- ficar de que tipo é esse valor. Por exemplo, podemos querer adicionar os valores de duas variáveis, X e Y, por meio de: Z is X + Y Antes desse objetivo ser executado, X e Y devem ser instanciados com valores inteiros. Se não há certeza de que tal instanciação ocorreu, então deve-se fazer tal verificação antes de executar a oprera- ção aritmética envolvida. Com essa finalidade podemos utilizar o predicado pré-definido integer(X), que é verdadeiro se X esti- ver instanciada com um varlor inteiro. O objetivo de adicionar X e Y então pode ser protegido da seguinte maneira, garantindo a validade dos operandos: ..., integer(X), integer(Y), Z is X + Y, ... `Se X e Y não estiverem ambas instanciadas com valores inteiros, então a operação aritmética que se segue ao teste não será realizada. Os predicados pré-definidos para a classificação de dados comuns a maioria das implementações são os seguintes: Predicado Descrição atom(X) É bem sucedido se X é uma constante textual (átomo). integer(X) É bem sucedido se X é um número inteiro. float(X) É bem sucedido se X é um número em ponto flutuante. number(X) É bem sucedido se X é um número. string(X) É bem sucedido se X é um string. atomic(X) É bem sucedido se X é do tipo atômico. var(X) É bem sucedido se X é uma variável não-instanciada. nonvar(X) É bem-sucedido se X não é uma variável ou se X é uma variável instanciada. O programa classifica/1, apresentado na figura abaixo, ilustra o emprego de tais predicados. O programa classifica/1 (Figura 9.1) irá reconhecer o tipo do seu argumento, informando-o ao usuá- rio. Em particular, se o dado é do tipo atômico, o subtipo também é informado, como é ilustrado abai- xo: 83 ?-X=1, classifica(X). Tipo Atômico ---> Numero Inteiro ?-X=[], classifica(X). Tipo Atômico ---> Lista Vazia ?-X=tio(josé), classifica(X). Termo Estruturado classifica(X) :- var(X), !, nl, write('Variável Não-instanciada'). classifica(X) :- atomic(X), !, nl, write('Tipo Atômico:'), tipoAtomico(X). classifica([_|_]) :- !, nl, write('Lista'). classifica(X) :- nl, write('Termo Estruturado'). tipoAtomico([]) :- !, nl, tab(5), write('---> Lista Vazia'). tipoAtomico(X) :- atom(X), !, nl, tab(5), write('---> Átomo'). tipoAtomico(X) :- integer(X), !, nl, tab(5), write('---> Número Inteiro'). tipoAtomico(X) :- float(X), !, nl, tab(5), write('---> Número em Ponto Flutuante'). tipoAtomico(X) :- string(X), !, nl, tab(5), write('---> String'). Figura 9.1 Programa para classificar tipos de dados. Vamos supor agora que se deseje contar quantas vezes um determinado átomo ocorre em uma lista de objetos dada. Com esse propósito se definirá o procedimento conta(A, L, N) onde A é o átomo, L é a lista e N é o número de vezes que A ocorre em L. Uma primeira tentativa de definir conta/3 seria: conta(_, [], 0). conta(A, [A | L], N) :- !, conta(A, L, N1), N is N1+1. conta(A, [_ | L], N) :- conta(A, L, N). Algumas tentativas de utilização de tal programa são: ?-conta(a, [a, b, a, a], N). N=3 ?-conta(a, [a, b, X, Y], Na). X=a Y=a Na=3 ?-conta(b, [a, b, X, Y], Nb). X=b Y=b Nb=3 ?-L=[a, b, X, Y], conta(a, L, Na), conta(b, L, Nb). X=a Y=a Na=3 Nb=1 Neste último exemplo, X e Y foram ambas instanciadas com "a", e portanto obtivemos Nb=1 somente. Não era isso, entretanto que se tinha em mente na construção do procedimento conta/3. Na verdade o que se queria era o número real de ocorrências de um dado átomo e não o número de termos capazes de unificar com esse átomo. De acordo com essa definição mais precisa da relação conta/3, devemos verificar se a cabeça da lista é um átomo. A nova versão da relação conta é a seguinte: conta(_, [], 0). conta(A, [B | L], N) :- atom(B), A=B, !, conta(A, L, N1), N is N1+1. conta(A, [_ | L], N) :- 86 Até o momento, três "tipos de igualdade" foram estudados, iniciando pela baseada na unificação, re- presentada por: X = Y que é verdadeira se X é Y unificam. Um outro tipo de igualdade é X is Expressão que é verdadeira se X unifica com o valor da expressão aritmética Expressão. Tem-se tambem: Expresão1 =:= Expressão2 que é verdadeira se os os valores das expressões aritméticas Expressão1 e Expressão2 são iguais. Se, ao contrário as expressões possuem valor diferente, escreve-se: Expressão1 =\= Expressão2 Algumas vezes poderá ser necessário um tipo mais estrito de igualdade: a igualdade literal entre dois termos. Esse tipo de igualdade é implementado por meio de um predicado pré-definido escrito como o operador infixo "==", de modo que Termo1 == Termo2 é verdadeira se os termos Termo1 e Termo2 são idênticos, isto é, possuem exatamente a mesma es- trutura e todos os componentes correspondentes são os mesmos. Em particular, os nomes das variá- veis devem também ser os mesmos. A relação complementar é a não-identidade, escrita como: Termo1 \== Termo2 Os exemplos abaixo abordam o uso de tais operadores: ?-f(a, b) == f(a, b). sim ?-f(a, b) == f(a, X). não ?-f(a, X) == f(a, Y). não ?-X \== Y. sim ?-t(X, f(a, Y)) \== t(X, f(a, Y)). não 9.4 PROGRAMAS OU BASES DE DADOS? De acordo com o modelo relacional, uma base de dados é a especificação de um conjunto de relações. Sob tal prisma, um programa Prolog pode ser visto como uma base de dados: a especificação das rela- ções é parcialmente implícita (regras) e parcialmente explícita (fatos). Além disso existem predicados pré-definidos que tornam possível a atualização da base de dados durante a execução do programa. Isso é feito em tempo de execução, pela adição ou remoção de cláusulas do programa. Os predicados que servem a tais propósitos são assert/1, asserta/1, assertz/1 e retract/1. Um objetivo como: assert(C) é sempre bem sucedido e, como efeito colateral, ocasiona a adição da cláusula C na base de dados. Por outro lado um objetivo retract(C) faz o oposto, isto é, apaga uma cláusula que unifica com C da base de dados. O diálogo abaixo exem- plifica esses dois predicados: ?-crise. não ?-assert(crise). sim 87 ?-crise. sim ?-retract(crise). sim ?-crise. não As cláusulas inseridas por meio do predicado assert/1, atuam exatamente como se fossem parte do programa original. O seguinte exemplo ilustra o uso de assert/1 e retract/1 como um método para controlar situações que se modificam ao longo do tempo. Vamos assumir o programa abaixo, sobre as condições do tempo: bom :- sol, not chuva. instável :- sol, chuva. deprimente :- chuva, neblina. chuva. neblina. O diálogo a seguir mostra como a base de dados pode ir sendo gradualmente atualizada: ?-bom. não ?-deprimente. sim. ?-retract(neblina). sim ?-deprimente. não ?-assert(sol) sim ?-instável. sim ?-retract(chuva). sim ?-bom sim Qualquer tipo de cláusula pode ser objeto dos predicados assert/1 ou retract/1. No próximo exemplo mostraremos que retract/1 é também não-determinístico: um conjunto completo de cláusulas pode ser removido, por meio do mecanismo de bactracking, através de um único objetivo retract/1. Vamos assumir um programa com os seguintes fatos: veloz(senna). veloz(prost). meiaBoca(alesi). meiaBoca(barrichello). lento(katayama). lento(moreno). Podemos adicionar uma regra ao programa da seguinte maneira: ?-assert( (vence(X, Y) :- veloz(X), not veloz(Y)) ). sim ?-vence(A, B). A=senna B=alesi; A=senna B=barrichello; A=senna B=katayama; A=senna B=moreno; A=prost B=alesi; A=prost B=barrichello; A=prost B=katayama; A=prost B=moreno; 88 não Note que quando uma regra é inserida na base de dados, por meio do predicado assert, as regras sintá- ticas do Prolog exigem que esta seja fornecida entre parênteses. Na introdução de uma cláusula, podemos desejar especificar a posição na qual a cláusula deve ser inserida na base de dados. Os predicados asserta/1 e assertz/1 permitem controlar a posição de inser- ção. O objetivo asserta(C) introduz a cláusula C no início da base de dados, enquanto que o objetivo assertz(C) adiciona a cláusula C no final da base de dados. O seguinte exemplo ilustra esses efeitos: ?-assert(p(a)), assertz(p(b)), asserta(p(c)). sim ?-p(X). X=c; X=a; X=b; não Há uma relação entre consult/1 e assertz/1. "Consultar" um arquivo pode ser definido em termos de assertz/1 da seguinte maneira: para "consultar" um arquivo, ler cada um dos seus termos (cláusulas) e inserí-los no final da base de dados: consult(X) :- see(X), transfere(C), see(user). transfere(end_of_file) :- !. transfere(C) :- read(C), assertz(C), transfere(C1). Já uma aplicação útil do predicado asserta/1 é armazenar respostas já computadas para consultas for- muladas ao programa. Por exemplo, vamos considerar que o predicado resolve(Problema, Solução) esteja definido. Podemos agora formular alguma consulta e requerer que a resposta seja lembrada para consultas futuras: ?-resolve(prob1, Sol), asserta(resolve(prob1, Sol)). Se o primeiro objetivo acima é bem-sucedido, então a resposta(Solução) é armazenada e utilizada, como qualquer outra cláusula, na resposta a questões futuras. A vantagem de memorizar as respostas é que uma consulta posterior que unifique com "prob1" será respondida muito mais rapidamente. O resultado é obtido agora pela recuperação de um fato, não sendo necessárias computações adicionais que possivelmente consumiriam muito mais tempo. Uma extensão dessa idéia é a utilização do assert para gerar todas as soluções possíveis na forma de uma tabela de fatos. Por exemplo, podemos gerar uma tabela com os produtos de todos os pares de inteiros de 0 a 9 da seguinte maneira: geramos um par de inteiros, X e Y, computamos Z is X*Y, inse- rimos os três números como uma linha da tabela de produtos e então forçamos a falha do procedi- mento que, por meio de backtracking, irá gerar a tabela completa. O procedimento tabMult/0, abaixo, implementa essa idéia: tabMult :- L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], membro(X, L), membro(Y, L), Z is X*Y, assert(produto(X, Y, Z)), fail. tabMult. O efeito colateral da execução de tabMult/0 é adicionar a correspondente tabela de multiplicação à base de dados. Depois disso, podemos perguntar, por exemplo, que pares da tabela resultam em 8: 91 coleta(Lista) :- retract(solução(X)), !, (X==fim, !, Lista=[]; Lista=[X | Resto], coleta(Resto)). No programa acima, todas as soluções para o objetivo "Objetivo" são geradas por meio de backtracking. Toda solução gerada é imediatamente incluída na base de dados, de forma que não é perdida quando a próxima solução é encontrada. Depois de encontrar todas as soluções, estas devem ser coletadas em uma lista e retiradas da base de dados. RESUMO • Uma implementação Prolog normalmente fornece um conjunto de predicados pré-definidos para diversas operações de uso frequente que nem sempre são de fácil codificação em Prolog "puro"; • O tipo de um termo Prolog pode ser testado por meio dos seguintes predicados pré-definidos: var(X) X é uma variável não-instanciada, nonvar(X) X não é uma variável não-instanciada, atom(X) X é um átomo, integer(X) X é um valor inteiro, float(X) X é um valor em ponto flutuante, atomic(X) X é um átomo ou um valor inteiro, e string(X) X é um string; • Termos Prolog podem ser construídos os decompostos através dos seguintes predicados pré- definidos: Termo =.. [Functor | Argumentos] functor(Termo, Functor, Aridade) arg(Ord, Termo, Argumento) name(Atomo, Códigos) • Os seguintes operadores pré-definidos são empregados na verificação de equivalências e desi- gualdades: X = Y X e Y unificam, X is E X é o valor da expressão aritmética E, E1 =:= E2 E1 e E2 tem o mesmo valor, E1 =\= E2 E1 e E2 tem valores diferentes, T1 == T2 T1 e T2 são idênticos, T1 \== T2 T1 e T2 não são idênticos; • Um programa Prolog pode ser visto como uma base de dados relacional, que pode ser atualiza- da por meio dos seguintes predicados: assert(Cláusula) asserta(Cláusula) assertz(Cláusula) retract(Cláusula) • Um predicado pré-definido não-determinístico para o controle de programas é o repeat/0, desti- nado à geração de um número ilimitado de alternativas para o backtracking, que é definido como: repeat. repeat :- repeat. • Todos os objetos que satisfazem uma dada condição podem ser coletados em uma lista por meio dos seguintes predicados: bagof(Objeto, Condição, Lista) setof(Objeto, Condição, Lista) findall(Objeto, Condição, Lista) EXERCÍCIOS 92 9.1 Escreva um procedimento denominado simplifica/2 para simplificar simbolicamente expressões de soma envolvendo números e átomos representandovariáveis. O procedimento deve rearranjar a expressão resultante de modo que os átomos precedam os números. Alguns exemplos do seu uso seriam: ?-simplifica(1+1+a, E). E=a+2 ?-simplifica(1+b+4+2+c+a, E). E=a+b+c+7 ?-simplifica(3+x+x, E). E=2*x+3 9.2 Defina o predicado básico(Termo), que é verdadeiro se Termo não possui nenhuma variável não- instanciada. 9.3 Defina o relação subentende(Termo1, Termo2), que é verdadeira se Termo1 é "mais geral" que Termo2. Por exemplo: ?-subentende(X, c). sim ?-subentende(g(X), g(t(Y))). sim ?-subentende(f(X, Y), f(a, a)). sim ?-subentende(f(X, X), f(a, b)). não 9.4 Defina a relação copia(Termo, Cópia), que produz em Cópia uma cópia de Termo com todas as suas variáveis renomeadas. Isso pode ser facilmente programado empregando os predicados as- sert/1 e retract/1. 9.5 Use o predicado bagof/3 para definir a relação potência(Conjunto, Subconjuntos), que computa o conjunto de todos os subconjuntos de um dado conjunto, sendo todos os conjuntos representados como listas. Por exemplo: ?-potência([a, b, c], P). P=[[], [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c]] 93 10. LÓGICA E BASES DE DADOS 10.1 BASES DE DADOS RELACIONAIS Uma "base de dados" pode ser entendida como uma coleção de dados interrelacionados, armazenada de modo independente do programa que a utiliza, permitindo a recuperação, inserção, remoção e mo- dificação de forma controlada. A quantidade de dados é tipicamente grande e o conteúdo muda ao longo do tempo. Em Prolog, uma base de dados é definida como um conjunto de fatos, não havendo, entretanto, nada que impeça a linguagem de trabalhar diretamente com bases de dados convencionais. Além disso a linguagem Prolog possui características que a tornam um excelente interface para lidar com bases de dados relacionais. Um dos marcos mais importantes no desenvolvimento da pesquisa acerca de bases de dados foi a in- trodução do modelo relacional, por Codd em 1970. Em tal modelo, os dados são definidos por meio de relações sobre domínios e os fatos individuais são representados como tuplas de valores sobre tais domínios. Uma relação com um conjunto de tuplas é também denominada uma "tabela". O modelo relacional é conceitualmente muito "limpo" e elegante, apoiado por sólida fundamentação matemáti- ca. Diferentemente de outros modelos de bases de dados, o modelo relacional não possui o conceito de "pointer", de modo que a associação entre diferentes tabelas é feita através da identidade explícita de valores de atributos. Este princípio concentra o esforço de implementação em obter maior velocidade de acesso, ao passo que a vantagem natural é a grande flexibilidade e fácil entendimento do processo de modelagem de dados. O modelo relacional tem produzido um grande esforço de pesquisa. O propósito de sua introdução aqui tem sua origem no fato de que tabelas correspondem a uma forma muito natural de armazenar fatos interrelacionados em Prolog. 10.1.1 EXEMPLO DE UMA BASE DE DADOS RELACIONAL Considere as seguintes relações: • pessoa/4, contendo nome, sexo, pai e mãe; • carro/4, contendo a placa, o fabricante, o proprietário e a cor. Tais relações podem originar tabelas como as apresentadas abaixo: Tabela 10.1(a): Relação pessoa/4 Nome Sexo Pai Mãe Marcelo m Luiz Gilda Luiz m Alfredo Lina Gilda f Miguel Ana Lúcia f Luiz Gilda Paulo m Miguel Ana Lina f Francisco Júlia
Docsity logo



Copyright © 2024 Ladybird Srl - Via Leonardo da Vinci 16, 10126, Torino, Italy - VAT 10816460017 - All rights reserved