Programação Logica

Programação Lógica\n\n\"P: Quantas pernas tem um cachorro, se chamamos sua cauda de perna? R: Quatro. Chamar uma cauda de perna não a transforma em uma perna.\"\nAbraham Lincoln\n\nVISÃO GERAL DO CAPÍTULO\n\n15.1 LÓGICA E CLÁUSULAS DE HORN 414\n15.2 PROGRAMAÇÃO LÓGICA EM PROLOG 417\n15.3 EXEMPLOS PROLOG 430\n15.4 RESUMO 443\nEXERCÍCIOS 443\n\nA programação lógica (declarativa) surgiu como um paradigma distinto nos anos 70. A programação lógica é diferente dos outros paradigmas porque ele requer que o programador declare os objetivos da computação, em vez dos algoritmos detalhados por meio dos quais esses objetivos podem ser alcançados. Os objetivos são expressos como uma coleção de assertivas, ou regras, sobre os resultados e as restrições da computação. Por essa razão, a programação lógica, às vezes, é chamada programação baseada em regras.\n\nAs aplicações de programação declarativa se classificam em dois domínios principais: inteligência artificial e acesso de informações em bancos de dados. No campo da inteligência artificial, Prolog tem sido influente. Alguns subcampos da inteligência artificial usam outras linguagens declarativas, como MYCIN, para modelar sistemas especializados. Na área de bancos de dados, a Structured Query Language (SQL) tem sido bem popular. Para que o assunto seja compreendido com profundidade, este capítulo focaliza apenas a programação lógica com Prolog, e estuda suas aplicações em processamento de linguagem natural e na solução de problemas.\n\nDuas características interessantes e diferenciadas dos programas lógicos são não-determinismo e backtracking. Um programa lógico não-determinístico pode encontrar várias soluções para um problema em vez de apenas uma, como seria normal em outros domínios de programação. Além disso, o mecanismo backtracking que possibilita o não-determinismo está dentro do interpretador Prolog, e, portanto, é implícito em todos os programas Prolog. Ao contrário, o uso de outras linguagens para escrever programas backtracking requer que o programador defina o mecanismo de backtracking explicitamente, como vimos na Seção 13.4.2. Neste capítulo, veremos o poder do backtracking e do não-determinismo. 15.1 LÓGICA E CLÁUSULAS DE HORN\n\nUm programa lógico expressa as especificações para soluções de problemas com o uso de expressões em lógica matemática. Este estilo evoluiu a partir das necessidades dos pesquisadores em processamento de linguagem natural e na prova automática de teoremas. As linguagens de programação convencionais não são particularmente bem adequadas para as necessidades desses pesquisadores. No entanto, escrevemos a especificação de um teorema usando uma gramática (como a gramática BNF, usada para definir a sintaxe Clite) como uma expressão lógica formal para um veículo eficaz para estudar o processo de prova de teoremas e a relação entre linguagem natural e um cenário experimental de laboratório.\n\nAssim, a lógica proposicional e preditiva (veja o Apêndice B) proporcionam os fundamentos formais para a programação lógica. A cláusula de Horn é um tema particular para a programação lógica.\n\nDefinição: Uma cláusula de Horn tem uma parte mais importante h, que é um atributo, e um corpo, que é uma lista de atributos p1, p2, ... pn.\n\nCláusulas de Horn são escritas no seguinte estilo:\nh ⇐ p1, p2, ..., pn\n\nIsso significa que h é verdadeiro (true) somente se p1, p2, ..., pn forem simultaneamente true. Definição: A atribuição de valores a variáveis durante a resolução é chamada instânciação.\nDefinição: Unificação é um processo de correspondência de padrões que determinam que instânciações, em particular, podem ser feitas a variáveis ao mesmo tempo em que se faz uma série de resoluções simultâneas.\nA unificação é repetitiva, assim ela eventualmente encontra todas as instâncias possíveis para as quais podem ser adotadas resoluções. Ilustramos a unificação em detalhe na Seção 15.2. 15.1.1 Resolução e Unificação\nÉ denominado resolução o ato de se fazer uma única inclusão a partir de um par de cláusulas de Horn. O princípio da resolução é similar à ideia da transitividade em álgebra.\nDefinição: Quando aplicada às cláusulas de Horn, a resolução diz que h é a cabeça de uma cláusula de Horn e ela corresponde a um dos termos de uma outra cláusula de Horn, então aquele termo pode ser substituído por h.\nEm outras palavras, se nós temos as cláusulas:\nh ← terms\nt ← t₁, h, t₂\nt então podemos resolver a segunda cláusula para t ← t₁, terms, t₂. Por exemplo, considere as seguintes cláusulas:\nspeaks(Mary, English)\ntalkswith(X, Y) ← speaks(X, L), speaks(Y, X + Y)\nA primeira é uma cláusula de Horn com uma lista vazia de variáveis em seu dicionário nem true. Portanto, a resolução nos permite deduzir a ideia de que:\ntalkswith(Mary, Y) ← speaks(Mary, English), speaks(X, Y)\ncom a hipótese de que as variáveis X e L são atribuídas aos valores \"Mary\" e \"English\" na segunda regra. A resolução, portanto, ajuda a chegar conclusões. 15.2 PROGRAMAÇÃO LÓGICA EM PROLOG\nProlog é a linguagem principal usada em programação lógica. O desenvolvimento do Prolog foi baseado em dois poderosos princípios descobertos por Robinson (Robinson, 1965) chamados resolução e unificação. A Prolog surgiu em 1970, resultado do trabalho de Colmerauer, Rousseau e Kowalski (Kowalski e Kuehne, 1970), e tem sido a principal linguagem de programação lógica até os dias atuais. As aplicações da programação lógica estão espalhadas pelas áreas de processamento de linguagem natural, raciocínio automatizado e prova de teoremas, pesquisa em bases de dados e áreas similares especializadas.\n15.2.1 Elementos de um Programa Prolog\nOs programas Prolog são feitos a partir de termos, que podem ser constantes, variáveis ou estruturas. Uma constante é um átomo (tipo the, zebra, 'Bob', e '.') ou um inteiro não-negativo (como 24). Uma variável é uma série de letras (A-Z, a-z, ...) que deve começar com uma letra maiúscula (como Bob). Uma estrutura é um predicado com zero ou mais argumentos, escritos em notação funcional. Por exemplo, veja algumas estruturas Prolog:\nn(zebra)\nspeaks(Who, russian)\nnp(X, Y)\nO número de argumentos é chamado aridade da estrutura (1, 2 e 2, nestes exemplos).\nFatos e regras Prolog são realizações da ideia formal das cláusulas de Horn, como foram introduzidas na Seção 15.1. Um fato é um termo seguido de um ponto (.) e é similar a uma cláusula de Horn sem o lado direito; uma variável não pode ser um fato. Uma regra é um termo seguido de :- e uma série de termos separados por vírgulas que termina em um ponto (.). Uma regra tem a seguinte forma:\nterm1 :- term2, term3, ..., termn.\nIsso é equivalente a cláusula de Horn:\nterm ← term1, term2, ..., termn. 15.2 Programação Lógica em Prolog 419\npara carregar o arquivo denominado diff que contém a função d, podemos usar o comando:\n?- consult(diff).\nFatos e regras Prolog são geralmente digitados em um arquivo separado, para o qual é usado o comando consult para carregar aquele arquivo no interpretador. O interpretador então afirma cada um dos fatos e das regras que estão definidos no programa.\nApós o carregamento do programa, podem ser feitas queries ao interpretador na forma de assertões com variáveis, e o interpretador tentará responder a elas.\nAqui estão algumas diretrizes gerais para escrever programas Prolog:\n1 Identificadores que começaram com uma letra maiúscula ou um caractere sublinhado são tomados como variáveis; todos os outros identificadores são tratados como constantes.\n2 Não deve haver nenhum espaço entre o nome do predicado e o parêntese esquerdo que abre sua lista de argumentos.\n3 Os fatos, as regras e as queries devem terminar com um ponto.\n4 Um arquivo de programa deve terminar com um fim de linha.\nPor exemplo, suponha que temos o seguinte arquivo de programa Prolog chamado\nspeaks:\nspeaks(allen, russian).\nspeaks(bob, english).\nspeaks(mary, russian).\nspeaks(mary, english).\ntalkswith(Person1, Person2) :-\nspeaks(Person1, L), speaks(Person2, L), Person1 \\= Person2.\nEntão podemos carregar esse programa com:\n?- consult(speaks).\nspeaks compiled, 0.00 sec, 1,312 bytes.\nYes\nA resposta Yes diz que o programa Prolog verificou com sucesso a sintaxe e carregou o arquivo, assim podemos ir em frente e propor queries.\nUnificação, Ordem de Avaliação e Backtracking Considera a seguinte query:\n?- speaks(Who, russian).\nAo procurar uma solução, o programa Prolog examina todos os fatos e as regras que tiveram uma parte importante (head) que corresponda a uma função mencionada na query (neste caso, speaks). Se houver mais de uma (neste caso, há quatro), ele irá considerá-las na ordem em que elas aparecerem no programa. Como russian é uma constante, a única variável a ser resolvida é a variável Who. Usando o primeiro fato no programa, Prolog responde com:\nWho = allen ;\nWho = mary ;\nNo Capítulo 15 Programação Lógica 420\njá que aquela atribuição à variável Who faz o primeiro fato ser sucesso. Nesse ponto, o usuário pode gerar saber se há outras maneiras de satisfazer a mesma query, na qual é digitado um ponto-e-vírgula (;). Prolog continua sua pesquisa por intermédio do programa, relatando o próximo sucesso, se houver um. Quando não há mais instâncias bem-sucedidas para a variável Who, Prolog finalmente responde No e o processo para. Aqui está uma interação completa:\n?- speaks(Who, russian).\nWho = allen ;\nWho = mary ;\nNo\nOutro tipo de query que esse programa pode manipular é aquela que faz perguntas como \"Bob conversa com Allen?\" ou \"Quem conversa com Allen?\" ou \"Que pessoas falam umas com as outras?\". Essas perguntas podem ser escritas na forma das seguintes queries Prolog, com as respostas às duas primeiras abaixo delas:\n?- talkstwith(bob, allen).\nNo\n?- talkstwith(Who, allen).\nNo\n?- mary ;\nNo\n?- talkstwith(P1, P2).\nPara ver como essas queries são satisfeitas, precisamos observar como a regra\ntalkswith é avaliada. Qualquer query da forma talkswith(X, Y) e para aquela\nque pode ser satisfeita somente se houver uma instanciação comum para as variáveis X e Y e se ambas as queries speaks(X, L), speaks(Y, L) = X \\= Y são simultaneamente satisfeitas. Esses três termos às vezes são chamados de subobjetivos do objetivo principal talkswith(X, Y).\nProlog tenta satisfazer aos subobjetivos em uma regra da esquerda para a direita, de forma que é feita primeiro uma pesquisa dos valores de X e L para a qual speaks(X, L) é satisfeita. Uma vez encontrados tais valores, esses mesmos valores serão usados onde suas variáveis aparecerem na pesquisa para satisfazer aos subobjetivos adicionais para aquela regra, como speaks(Y, L) e X \\= Y. O processo de tentar satisfazer a primeira query acima está diagramado na árvore de pesquisa mostrada na Figura 15.1. 15.2 Programação Lógica em Prolog 421\ntalkswith(Who, allen)\n1\n8\nfail\nspeaks(Who, L)\nspeaks(allen, L)\nWho = allen\n2\n3\n4\nspeaks(allen, russian)\nspeaks(allen, russian)\n5\n7\n| Figura 15.2 Primeira Tentativa de Satisfazer a Query talkswith(Who, allen)\nEsse processo falha porque a única instanciação de L que satisfaz speaks(bob, L)\nnão satisfaz simultaneamente speaks(allen, L) para esse programa. Os números atribuídos às setas neste diagrama indicam a ordem na qual são tentados os subobjetivos.\nA resposta não indica que o programa Prolog não pode encontrar mais soluções para uma query. Em geral, o programa Prolog opera sob aquilo que chamamos suposição de um mundo fechado, o que significa que qualquer coisa que não tenha sido informada a ele não é verdadeira. Nesse exemplo, o mundo fechado contém apenas fatos que foram declarados sobre pessoas específicas que falam línguas específicas, e nada mais.\nO processo para satisfazer a segunda query acima é um pouco mais complexo. Ele falha na sequência mostrada na Figura 15.2. Embora os subobjetivos speaks(Who, L) e speaks(allen, L) sejam satisfeitos pela instanciação Who = allen, o terceiro subobjetivo falha, pois allen = allen falha.\nUma vez ocorrida essa falha, o processo retrocede (backtracks) para o passo denominado 2 na figura e procura por outras instanciações de Who e L que satisfazem aos três subobjetivos simultaneamente. Assim, o processo eventualmente continua com as instanciações Who = mary e L = russian, mas nenhuma outra.\nPesquisa em Base de Dados – A Árvore Genealógica Pode ficar evidente que o Prolog é bem adequado para solução de problemas que requerem pesquisas em uma base de dados. Na verdade, o desenvolvimento de sistemas especializados durante os anos 70 e 80 foi facilitado em grande parte por programas Prolog. O programa speaks nesta seção pode ser visto como um programa muito simples para pesquisas em dados, que é um dos primeiros autores de figurações para pesquisa bem-sucedida. Em Figura 15.3 a diagrama confidencial que \"pai\" relaciona pessoas em níveis adjacentes. prefix(X, Z) :- append(X, Y, Z).\nsuffix(Y, Z) :- append(X, Y, Z).\n\nA terceira função útil define repetidamente a noção de participante em uma lista. X é um membro de uma lista se ele for idêntico ao primeiro elemento ou a um membro do fim (tail) da lista.\n\nmember(X, [X | _]).\nmemeber(X, [_ | Y]) :- member(X, Y).\n\nObserve aqui o uso da notação “não importa” (don’t care) em partes da definição que não afetam a definição. Na primeira linha, não nos importamos em saber como o resto da lista X é por idêntico ao primeiro membro. Na segunda linha, também não nos importamos em saber do início (head) da lista S X for um membro do fim (tail).\n\n| Figura 15.3 Uma Árvore Genealógica Parcial\n\nparent(A,B) :- father(A,B).\nparent(A,B) :- mother(A,B).\ngrandparent(C,D) :- parent(C,E), parent(E,D).\nmother(mary, sue).\nmother(mary, bill).\nmother(sue, nancy).\nmother(sue, jeff).\nmother(jane, ron).\n\nfather(john, sue).\nfather(john, bill).\nfather(bob, nancy).\nfather(bob, jeff).\nfather(bill, ron).\n\nPodemos consultar essa base de dados de várias maneiras para fazer diferentes perguntas. Por exemplo, a pergunta “Quem é um avô de Ron” pode ser colocada assim:\n\n?- grandparent(Who, ron).\n\nPodem ser definidas relações adicionais para possibilitar uma variedade mais ampla de perguntas a serem feitas. Por exemplo, a relação sibling pode ser definida entre duas pessoas diferentes que compartilham o mesmo pai:\n\n?- sibling(X, Y) :- parent(W, X), parent(W, Y), X \\= Y.\n 15.2 Programação Lógica em Prolog\n\nDeve-se notar que Prolog sofre do síndrome do mundo fechado. Um programa Prolog somente sabe aquilo que foi dito a ele. Neste exemplo, um father (pai) poderia facilmente ser tanto uma mulher quanto um homem. O sistema não tem senso de gênero; ele não entende que um pai biológico deve ser um homem nem que os pais de uma pessoa devem ser distintos.\n\nListas A estrutura básica de dados em programação Prolog é a lista, que é escrita como uma série de termos separados por vírgulas e envolvidos por colchetes [ e ]. Sentenças geralmente são representadas como listas de átomos (coisas minúsculas), como no exemplo a seguir:\n\n[the, giraffe, dreams]\n\nA lista vazia é representada por [], enquanto uma entrada do tipo não importa (don’t care) em uma lista é representada por uma sublinha (_). Os exemplos a seguir representam listas em um, dois e três elementos, respectivamente.\n\n[X, Y]\n[_, _, Z]\n\nO elemento Head (primeiro) da lista é distinguido dos demais elementos por uma barra vertical. Assim,\n\n[Head | Tail]\n\nrepresenta uma lista cujo primeiro elemento é Head e cujos demais elementos formam a lista [Tail], muitas vezes chamado de final (tail) da lista.\n\nAqui está uma função Prolog simples que define o encadeamento de duas listas para juntá-las e formar uma só. Os dois primeiros argumentos para essa função representam as duas listas que estão sendo encadeadas, e a terceira representa o resultado.\n\nappend([], X, X).\nappend([Head | Tail], Y, [Head | Z]) :- append(Tail, Y, Z).\n\nEssa definição repetitiva um tanto estranha tem duas partes. O “base case” é definido pela primeira linha, que simplesmente afirma que a lista vazia encadeada com qualquer outra lista retorna aquela outra lista como resultado. O caso repetitivo, definido pela segunda linha, diz que se Z é o resultado do encadeamento de listas Tail e Y, então o encadeamento que produz a nova lista [Head | Tail] com Y dá o resultado [Head | Z].\n\nÉ importante entender a dinâmica de execução para essa função, pois essa forma de definição repetitiva ocorre frequentemente em Prolog. Considere a query\n\n?- append([english, russian], [spanish], L).\n\nque produziria a lista L = [english, russian, spanish]. A Figura 15.5 traz uma árvore de pesquisa parcial que rastreia as instâncias de H, T, X, Y e Z à medida que esse resultado é desenvolvido.\n\nAs duas primeiras chamadas da árvore de pesquisa repetitiva, que espera um Head do primeiro elemento e chama de volta append uma lista mais cuja trama primeiro aprimora. append([english, russian], [spanish], L).\n\nH = english, T = [russian], Y = [spanish], L = [english | Z]\n\nappend([russian], [spanish], [Z]).\n\nH = russian, T = [], Y = [spanish], [Z] = [russian | Z'].\n\nappend([], [spanish], [Z']).\n\nX = [spanish], Z' = spanish\n\nappend([english], [spanish], [spanish]).\n\n| Figura 15.5 Árvore de Pesquisa Parcial para append([english, russian], [spanish], L).\n\nA chamada final usa o base case, que força a instanciação da variável X = [spanish] e Z' = spanish.3 Desse modo, o resultado [H | Z'] na segunda chamada é resolvido como [russian, spanish] e identificado como a lista Z na primeira chamada. Finalmente, a lista L é determinada para [english, russian, spanish], usando seu valor que acaba de ser descoberto para Z como sendo sua cauda.\n\nAqui estão mais três funções com listas que são muito úteis em programação Prolog. As duas primeiras, chamadas prefixo e sufixo, significam exatamente o que seus nomes sugerem. X é um prefixo de Z se houver um Y que pudermos acrescentar a X para fazer Z. A definição E como sufixo de Z é similar. 15.2 Programação Lógica em Prolog\n425\nPara ilustrar, suponha que temos as seguintes atribuições de lista em Prolog:\nL = [my, dog, has, many, fleas]\nM = [many, fleas, spoil, the, picnic]\nEntão as seguintes queries Prolog produzem as respectivas respostas mostradas abaixo de cada uma delas:\n? - prefix(Answer, L).\nAnswer = [];\nAnswer = [my];\nAnswer = [my, dog];\n...\nAnswer = [my, dog, has, many, fleas];\nNo\n? - suffix(Answer, L), prefix(Answer, M).\nAnswer = [];\nAnswer = [many, fleas];\nNo\n? - member(spoil, L).\nNo\n? - member(spoil, M).\nYes\n15.2.2 Aspectos Práticos de Prolog\nNa prática, Prolog não é uma linguagem de programação lógica totalmente \"pura\". Em particular, ela tem algumas características projetadas para tornar a programação mais eficiente e prática. Nesta seção, discutimos várias características importantes, entre elas: o como o operador \"cut\", o operador is e a função assert.\nTracing\nMuitas implementações Prolog proporcionam os atributos trace e untrace, que são usados para ligar e desligar o tracing de outros atributos. Como pode haver diferentes atributos com o mesmo nome, e diferentes aridades (número de argumentos), o traço espera que o nome de um atributo seja seguido de uma barra diagonal e sua aridade. Por exemplo, considere o atributo factorial definido da seguinte forma:\nfactorial(0, 1).\nfactorial(N, Result) :- N > 0, M is N - 1,\nfactorial(M, SubRes), Result is N * SubRes.\nEsse atributo define a função fatorial recursivamente, com a primeira linha definindo o base case (0! = 1) e a segunda e terceira linhas definindo o caso repetitivo (n! = n(n - 1)!). Note que precisamos introduzir a variável intermediária M para fazer a avaliação de N - 1. 426\nPara rastrear (trace) essa função, podemos fazer o seguinte:\n? - trace(factorial/2).\nfactorial/2: call redo exit fail\nYes\n? - factorial(4, X).\nCall: ( 7) factorial(4, _G173)\nCall: ( 8) factorial(3, _L131)\nCall: ( 9) factorial(2, _L144)\nCall: ( 10) factorial(1, _L157)\nCall: ( 11) factorial(0, _L170)\nExit: ( 11) factorial(0, 1)\nExit: ( 10) factorial(1, 1)\nExit: ( 9) factorial(2, 2)\nExit: ( 8) factorial(3, 6)\nExit: ( 7) factorial(4, 24)\nX = 24\nO atributo listing, como em listing(factorial/2), mostrará todos os fatos e as regras corretas para o argumento de predicado:\n? - listing(factorial/2).\nfactorial(0, 1).\nfactorial(A, B) :- A > 0,\nC is A-1,\nfactorial(C, D),\nB is A*D.\nYes\nO atributo listing sem argumentos lista todas as funções do programa consultado corretamente.\nCut e Negação\nProlog tem uma função especial chamada cut, que força a avaliação de uma série de subobjetivos no lado direto de uma regra que não será julgada se o lado direito tiver sucesso uma vez. A função cut é escrita inserindo-se um ponto de exclamação (!) como subobjetivo no lugar em que a interrupção deve ocorrer. 427\nPara ilustrar, considere o seguinte programa, que executa o algoritmo de bubble sort em uma lista:\n? - bsort([5,2,3,1], Ans).\nCall: ( 7) bsort([5, 2, 3, 1], _G221)\nCall: ( 8) bsort([2, 3, 1], _G221)\nCall: ( 9) bsort([3, 1], _G221)\nCall: ( 10) bsort([1], _G221)\nCall: ( 11) bsort([], _G221)\nExit: ( 11) bsort([], [])\nExit: ( 10) bsort([1], [1])\nExit: ( 9) bsort([3, 1], [1, 3])\nExit: ( 8) bsort([2, 3, 1], [1, 2, 3])\nExit: ( 7) bsort([5, 2, 3, 1], [1, 2, 3, 5])\nAns = [1, 2, 3, 5];\nNo\n| Figura 15.6 Trace de bsort para a Lista [5, 2, 3, 1]\nbsort(L, S) :- append(U, [A, B | V], L),\nB < A, !,\nappend(U, [B, A | V], M),\nbsort(M, S).\nEsse programa primeiro divide uma lista L encontrando duas sublistas U e [A, B | V], para as quais B < A é verdadeiro. Uma vez encontrada essa partição, é formada a lista M acrescentando as sublistas U e [B, A | V] e depois repetidamente, aplicando o bubble sort para formar a nova lista S.\nEsse processo se repete até que não se possa encontrar mais partições de L; até que não haja nenhuma sublista [A, B | V] de na qual B < A. Essa é uma maneira compacta de dizer que a lista L está ordenada. Nesse ponto, a única regra aplicável que resta é bsort(L, L), que retorna a lista ordenada como resposta. A Figura 15.6 mostra um trace do programa.\nSe a instrução cut não estivesse presente nesse programa, o processo de pesquisa teria continuado com um Redo da regra no nível 11, pois o programa Prolog iria procurar todas as soluções:\nRedo: ( 11) bsort([2, 1, 3, 5], _G221)\ne isso levaria a primeira de uma série de respostas incorretas. A função cut é, portanto, uma forma de evitar que o retrabalho ocorra e força o programa a executar a primeira série de instâncias para as variáveis do lado direito que satisfazem a regra, mas não outras. factorial(0, 1).\nfactorial(N, Result) :- N > 0, M is N - 1,\nfactorial(M, P),\nResult is N * P.\n\n| Figura 15.7 A Função Fatorial em Prolog\n\n?- factorial(4, X).\nCall: ( 7) factorial(4, _G173) 4 3 _G173 4*P\nCall: ( 8) factorial(3, _G131) 3 2 _G131 3*2\nCall: ( 9) factorial(2, _L144) 2 1 _L144 2*P\nCall: (10) factorial(1, _L157) 1 0 _L157 1*P\nExit: (11) factorial(1, 1) 0 _L170 1*\nExit: (10) factorial(1, 1) 1*1= 1\nExit: ( 9) factorial(2, 2) 2*1= 2\nExit: ( 8) factorial(3, 6) 3*2= 6\nExit: ( 7) factorial(4, 24) 4*6= 24\n\n| Figura 15.8 Trace do Fatorial (4)\n\nOs Operadores is, not e Outros O operador interfixo is pode ser usado para forçar a instanciação de uma variável:\n?- X is 3+7.\nX = 10\nyes\n\nProlog tem operadores aritméticos (+, -, *, /,^) e operadores relacionais (<, >, =, =<, >=, =\\=) com suas interpretações usuais. Observe que, para manter os símbolos =< e >= livre para serem usados como sets, a Prolog usa =< para comparações menores ou igual e >= para comparações maior ou igual. A função assert. As aplicações Prolog às vezes encontram situações nas quais o programa deve “atualizar-se” em resposta à query mais recente. Por exemplo, em uma aplicação de base de dados como aquela mostrada na Seção 15.2.1, alguém pode querer acrescentar um novo número a uma árvore genealógica e deixar aquele elemento desempenhe um papel na resposta do programa nas próximas queries. Isso pode ser feito usando a função assert, que essencialmente permite que o programa se altere dinamicamente, acrescentando novos fatos e novas regras aos existentes. Por exemplo, suponha que queremos acrescentar no programa da Figura 15.3 a afirmativa de que Jane é a mãe de Joe. Faríamos isso com a seguinte instrução:\n\n?- assert(mother(jane,joe)).\n\nEsse fato agora será acrescentado a todos os outros no programa, e afetará queries como estas:\n\n?- mother(jane, X).\nX = ron ;\nX = joe ;\nNo\n\nAlém disso, a função assert pode ser acrescentada ao próprio corpo de uma definição de função e dinamicamente acrescentar novos fatos e novas regras a base de dados. 15.3 EXEMPLOS PROLOG\nNas próximas seções, apresentamos exemplos de aplicações Prolog por meio de uma vasta gama de aplicações de inteligência artificial: diferenciação simbólica, solução de palavras cruzadas, processamento de linguagem natural, semânticas e o problema das oito rainhas.\nCada um desses exemplos destaca vários pontos fortes da programação declarativa, especialmente o mecanismo backtracking interno do Prolog e o não-determinismo resultante. Enquanto estudam esses exemplos, os leitores deverão pensar sobre o que será necessário para resolver esses tipos de problemas em um paradigma de programação imperativo; normalmente, o trabalho para escrever o código será muito maior do que em Prolog.\n15.3.1 Diferenciação Simbólica\nO uso de Prolog para manipulação simbólica e prova de teoremas é amplo. Esse exemplo ilustra alguns dos poderes de dedução natural do Prolog na área de raciocínio lógico, executando diferenciação simbólica e simplificação de fórmulas de cálculo simples. A Figura 15.9 mostra as regras familiares para diferenciação.\nPor exemplo, diferenciando-se a função 2 * x + 1 usando essas regras resulta na resposta (não simplificada) 2 + x * 0, que simplificada resulta em 2.\nA solução Prolog imita essas regras uma a uma. Elas são indistinguíveis repetitivas, e assim é fácil corrigir Prolog, como mostra a Figura 15.10.\nEsse Prolog será expressão adicional, enquanto pesquisa analisará a expressão repetidamente antes de chegar ao base caso, no qual restam os termos e os fatores individuais. A Figura 15.11 mostra uma árvore de pesquisa para a query d x, 2*x+1, Ans (não são mostrados os ramos que conduzem a falha).\nNesta ilustração, as variáveis temporárias _G268, _G269, _G275 e _G278 representam variáveis anônimas geradas pela Prolog à medida que ela encontra respostas para os termos intermediários na expressão original.\n\n\\[ \\frac{dc}{dx} = 0 \\quad c \\text{ é uma constante} \\]\n\\[ \\frac{dx}{dx} = 1 \\]\n\\[ \\frac{d}{dx}(u + v) = \\frac{du}{dx} + \\frac{dv}{dx} \\]\n\\[ \\frac{d}{dx}(u - v) = \\frac{du}{dx} - \\frac{dv}{dx} \\]\n\\[ \\frac{d}{dx}(uv) = u \\frac{dv}{dx} + v \\frac{du}{dx} \\]\n\\[ \\frac{d}{dx}\\left(\\frac{u}{v}\\right) = \\frac{v \\frac{du}{dx} - u \\frac{dv}{dx}}{v^2} \\]\n\n| Figura 15.9 Regras de Diferenciação Simbólica Figura 15.10\nDiferenciador Simbólico em Prolog\n\nOs leitores devem observar que a tarefa de simplificar uma expressão algébrica não é coberta pelas regras de diferenciação simbólica. Por exemplo, a seguinte query não dá a resposta intuitiva yes, pois o resultado simbólico 2 * 1 + x * 0 + 0 obviamente não é equivalente a 2. A tarefa de simplificação depende de identidades como 1 * X = X e 0 + X = X assim por diante. Um exercício no fim deste capítulo proporciona uma oportunidade ampliar o programa da diferenciação simbólica dessa maneira.\n\n?- d(x, 2*x, 2).\n\n15.3.2 Resolvendo Palavras Cruzadas\nA lógica, às vezes, nos pede para resolver problemas que são palavras cruzadas, que são uma série de afirmações a partir das quais várias inferências podem ser feitas, e podem ser tiradas conclusões complexas. Veja aqui um exemplo simples:\n\nBaker, Cooper, Fletcher, Miller e Smith moram em um prédio de cinco andares. Baker não mora no quinto andar e Cooper não mora no primeiro. Fletcher não mora no...\n\nFigura 15.11\nÁrvore de Pesquisa para a Query d(x, 2*x+1, Ans) Figura 15.12\nSolução Prolog para o Problema do Prédio\n\n... último andar nem no térreo, e ele não mora em um andar adjacente a Smith ou Cooper. Miller mora em algum andar acima de Cooper. Quem mora em qual andar?\n\nfloors([floor(_,5),floor(_,4),floor(_,3),floor(_,2),floor(_,1)]).\nbulding(Floors) :- floors(Floors),\n member(floor(baker, B), Floors), B = 5,\n member(floor(cooper, C), Floors), C \= 1,\n member(floor(fletcher, F), Floors), F = 1, F = 5,\n member(floor(miller, M), Floors), M > C,\n member(floor(smith, S), Floors), not(adjacent(S, F)),\n not(adjacent(F, C)),\n print_floors(Floors).\n\nA função auxiliar print_floors é uma rotina repetitiva simples para mostrar os elementos de uma lista em linhas separadas. As cinco pessoas moram em algum lugar, assim a função member é usada para garantir isso.\n\nprint_floors([A | B]) :- write(A), nl, print_floors(B).\nprint_floors([]).\n\nmember(X, [X | _]).\nm tber(X, [_ | Y]) :- member(X, Y).\n\nA função adjacent tem sucesso sempre que seus dois argumentos X e Y diferem de 1, assim ela define o que é necessário para que dos andares sejam adjacentes um ao outro. Figura 15.13\nUma gramática BNF simples e árvore de análise para \"A girafa sonha\" (Giraffe Dreams)\n\nO quebra-cabeça é resolvido usando-se a seguinte query, que encontra as instâncias das cinco variáveis que, juntas, satisfazem a todas as restrições e atribuem uma lista de valores ao conjunto X:\n\n? - building(X).\n\n15.3.3 Processamento de Linguagem Natural\nPodemos escrever programas Prolog que são efetivamente gramáticas BNF, que, quando executados, analisarão sentenças em uma linguagem natural. A Figura 15.13 mostra um exemplo de uma gramática dessas, juntamente a uma árvore de análise para a sentença \"a girafa sonha\" (the giraffe dreams).\n\nQuando usamos a representação lista para sentenças, podemos escrever regras Prolog que dividem uma sentença em suas categorias gramaticais, usando a estrutura definida pelas próprias regras gramaticais. Por exemplo, considere a seguinte regra gramatical BNF, na qual np e vp representam as noções \"sentença\", \"frase substantivo\" e \"frase verbo\".\n\ns -> np vp\n\nUma regra Prolog correspondente poderia ser:\n\ns(X, Y) :- np(X, U), vp(U, Y).\n\nAs variáveis nessa regra representam listas. Em particular, X é a representação lista da sentença que está sendo analisada, e Y representa o fim resultante da lista que resta a sequência.\n\na interpretação aqui espelha aquilo a regra gramatical original: \"X é uma sentença, restando Y, e o início de X pode ser identificado como um verbo-frase, restando U, e o início de U pode ser identificado como um verbo-frase, restando Y.\" 434 Capítulo 15 Programação Lógica\n\nO programa Prolog para a gramática da Figura 15.13 é mostrado a seguir:\n\ns(X, Y) :- np(X, U), vp(U, Y).\n\nnp(X, Y) :- det(X, U), n(U, Y).\n\nvp(X, Y) :- iv(X, Y).\nvp(X, Y) :- tv(X, U), np(U, Y).\n\ndet --> [the].\ndet --> [a].\nn --> [giraffe].\nn --> [apple].\niv --> [dreams].\ntv --> [dreams].\ntv --> [eats].\n\nObserve que os fatos que identificam símbolos terminais (girafa, come etc.) efetiva-\nmente retiram aqueles símbolos do início (head) da lista que está sendo passada por meio\nda gramática.\n\nPara ver como isso funciona, considere a seguinte query Prolog, que pergunta se \"a\ngirafa sonha\" é ou não uma sentença.\n\n?- s([the, giraffe, dreams], []).\n\nAqui, X e Y são identificados com as duas listas dadas como argumentos, e a tarefa\ne encontrar uma lista U que satisfaça, na ordem dada, a cada um dos seguintes objetivos\n(usando o lado direito da primeira regra no programa).\n\nUma maneira de ver a dinâmica de todo o processo de análise gramatical é rodar um\ntrace na própria query, que é mostrada na Figura 15.14. Por meio desse trace, podemos\nver que as variáveis U e Y são instanciadas para [dreams] e [I] respectivamente. Após o\ncálculo do trace, uma uma leitura cujas palavras são removidas da lista. Uma leitura cu-\ndados desse trace revela uma correspondência direta entre as chamadas bem-sucedidas\n(aplicações de regras) e nós da árvore gramatical mostradas na Figura 15.13\n(ou seja, a leitura de um trace pode ajudar a desenvolver uma árvore de\nanálise gramatical complexa para uma sentença.\n\nO uso de Prolog para codificar gramáticas complexas dessa maneira às vezes mais árida\npara o aluno. Por essa razão, Prolog fornece uma notação muito compacta de inú-\ndireta e notação das próprias regras gramaticais livres de contexto. Essa notação é cha-\nmada Definite Clause Grammar (DCG) e é simples de assimilar: O operador Prolog -> 15.3 Exemplos Prolog\n\n?- s([the, giraffe, dreams],[]).\nCall: ( 7) s([the, giraffe dreams], []) ?\nCall: ( 8) np([the, giraffe,] _L131) ?\nCall: ( 8) det([the, giraffe,] _L143) ?\nExit: ( 8) det([the, giraffe], [giraffe, dreams]) ?\nExit: ( 8) n[giraffe, dreams] _L131) ?\nExit: ( 9) n[giraffe, dreams], [dreams]) ?\nExit: ( 8) np([the, giraffe, dreams], [dreams]) ?\nCall: ( 8) vp[dreams], [] ?\nCall: ( 8) iv[dreams], [] ?\nExit: ( 8) vp[dreams], [] ?\nCall: ( 7) s([the, giraffe, dreams], [I) ?\nYes\n\n| Figura 15.14 Execução de Tracing de uma Query Prolog\nd\n\né utilizado em lugar do operador :- em cada regra, e as variáveis de lista dentro da regra\nsão, portanto, supridas. Por exemplo, a regra\n\ns(X, Y) :- np(X, U), vp(U, V).\n\npode ser substituída pela seguinte versão simplificada equivalente:\n\ns --> np, vp.\n\nAo fazer essa transformação, é importante enfatizar que não estamos mudando a\n\naridade da função s (ainda 2) ou o significado da própria regra original. Essa notação foi\nintroduzida como uma espécie de \"macro\" que permite que as regras Prolog sejam escri-\ntas de forma quase idênticas às regras gramaticais BNF que elas representam. Veja abaixo\numa reescrita completa do programa Prolog para a gramática na Figura 15.13:\n\ns --> np, vp.\nnp --> det, n.\nvp --> iv.\nvp --> tv, np.\ndet --> [the].\ndet --> [a].\nn --> [giraffe].\nn --> [apple].\niv --> [dreams].\ntv --> [dreams].\ntv --> [eats]. 436 Capítulo 15 Programação Lógica\n\nUm refinamento adicional para as regras de escrita gramatical proporciona capacidade\npara gerar um árvore de análise gramatical diretamente a partir da gramática. Isto é, a gramá-\ntica mostrada aqui pode ser modificada de maneira que uma query não dê apenas uma resposta\nYes ou No, mas uma árvore de análise gramatical completa em forma funcional como respon-\nda. Por exemplo, a forma funcional da árvore de análise gramatical da Figura 15.13 é:\n\ns(np(det(the), n(giraffe)), vp(iv(dreams)))\n\nEssa modificação é feita acrescentando-se um argumento adicional ao lado esquer-\ndo de cada regra e variáveis apropriadas para conter os valores intermediários que são\nderivados nos estágios intermediários da execução. Por exemplo, a primeira regra na\ngramática acima seria ampliada da seguinte forma:\n\ns(s(NP,VP)) --> np(NP), vp(VP).\n\nIsso significa que a query precisa de um argumento extra, juntamente a ser\nanalisada gramaticalmente e à lista vazia. Tal argumento, que aparece primeiro na query,\né uma variável que conterá a árvore de análise gramatical, como mostramos abaixo:\n\n?- s(Tree, [the, giraffe, dreams], []).\n\nDeixamos como exercício um revisão completa da gramática acima, que englobasse\nrefinamento.\n\nÉ importante destacar que Prolog pode ser usado para gerar sentenças bem como\npara análises gramaticais. Por exemplo, considere a aplicação da seguinte query\npara o programa Prolog dessa gramática:\n\n?- s(Sentence, []).\n\nEssa query, quando iniciada, solicita o processo de pesquisa que encontre todas as\ninstâncias da variável Sentence que terão sucesso com essa gramática. Na lista de\nrespostas, encontramos a instância a seguir, bem como todas as outras que podem ser\ngeradas por essa gramática:\n\nSentence = [the, giraffe, dreams] ;\nSentence = [the, giraffe, eats, the, apple] ;\n... Aqui, cada var representa uma variável e cada val representa seu valor atribuído no momento.\n\nO estado é uma espécie de janela de observação em um ambiente de desenvolvimento integrado (integrated development environment – IDE). Ele está sempre ligado a uma instrução particular do programa fonte e mostra para cada variável de programa seu valor corrente. Em nossa implementação Java, o estado foi implementado como uma tabela hash na qual o identificador de variável era a chave e o valor associado era o valor corrente da variável.\n\nUm estado aqui é representado naturalmente como uma lista, com cada elemento da lista sendo um par que representa a ligação de uma variável ao seu valor. Assim, o estado Clite:\n\n{(x, 1), (y, 5)}\n\npode ser representado como uma lista Prolog:\n\n[[X, 1], [Y, 5]]\n\nEm seguida, implementamos as funções de acesso de estado denominadas get e on ion (união de substituição) da implementação Java. Lembre-se de que a função get base case é que o par variável-valor ocorre no início da lista de estado, caso em que o valor associado com a variável é o valor resultante desejado. Caso contrário, a pesquisa continua até o fim da lista.\n\n5. Um leitor astuto que já tenha lido o Capítulo 14 pode querer comparar essa implementação com a implementações Scheme ou Haskell.\n\nget(Var, [[Var, Val] | _], Val).\nget(Var, [_ | Rest], Val) :- get(Var, Rest, Val).\n\nUma aplicação da função get é:\n\n?- get(Y, [[X, 5], [Y, 3], [Z, 11]], V).\nV = 3.\n\nA função onion toma uma variável de entrada, um valor de entrada, um estado de entrada e produz um novo estado com a parte valor do par correspondente a variável-valor substituído pelo novo valor.\n\n/* onion(Var, val, inState, outState) */\n\nLembre-se de que a função onion é capaz de gerar a hipótese simplificada de que a variável que estamos procurando ocorre exatamente uma vez no vetor de estado. O base case é que a variável que está sendo correspondendo ocorre no início da lista; o estado de saída é apenas um novo par variável-valor encadeado com o resto do estado de entrada. Caso contrário, o novo estado é construído a partir do início encadeado com o estado de saída resultante da aplicação repetitiva de on ion no fim do estado de entrada.\nonion(Var, Val, [[Var, _] | Rest], [[Var, Val] | Rest]).\nonion(Var, Val, [Xinvar | Rest], [Xvar | OState]).\nonion(Var, Val, Rest, OState).\n\nUma aplicação de onion é:\n\n?- onion(Var, 4, [[X, 5], [Y, 3], [Z, 11]], S).\nS = [[X, 5], [Y, 4], [Z, 11]].\n\nEm seguida, considera a função de significado para a avaliação de expressão Clite somente para os inteiros. Para facilitar isto, escolhemos uma representação apropriada para uma expressão Clite em sintaxe abstrata. Uma possibilidade é usar listas; em lugar disso, preferimos usar estruturas:\n\nvalue(val), where val is a number\nvariable(ident), where ident is a variable name\noperator(term1, term2), where operator is one of:\nplus minus times div - arithmetic\ngt, lt, =, ge, gt, eq - relational\n\nA implementação dessas funções de significado segue diretamente das regras dadas no Capítulo 8. Assumimos também que tenha sido executada uma verificação estática de semânticos. O significado de uma expressão Clite abstrata é implementado em forma de regras, dependendo do tipo de expressão. Em Prolog, essas regras tomam uma expressão de entrada e um estado de entrada e retornam um valor:\n\n/* mexpression(expr, state, val) */\nO significado de uma expressão value é exatamente o próprio valor.\nmexpression(value(Val), __ , Val).\n\nO significado de uma variable é o valor associado com a variável no estado corrente, obtido com a aplicação da função get.\nmexpression(variable(Var), State, Val) :- get(Var, State, Val).\n\nO significado de uma expressão binária é obtido aplicando-se o operador ao significado dos operandos; mostramos abaixo o significado para plus:\nmexpression(plus(Expr1, Expr2), State, Val) :-\nmexpression(Expr1, State, Val1),\nmexpression(Expr2, State, Val2),\nVal is Val1 + Val2. Essa definição diz que primeiro deve-se avaliar Expr1 em State dando Val1, depois avaliar Expr2 em State dando Val2. Depois, some os dois valores, e teremos o valor resultante. Os demais operadores binários são implementados de forma similar.\n\nFinalmente, precisamos escolher uma representação para a sintaxe abstrata das instruções Clite. Embora pudéssemos usar uma representação lista (como fizemos para Scheme), preferimos usar estruturas:\n\nskip\nassignment(target, source)\nblock([s1, ... sn])\nloop(test, body)\nconditional(test, thenbranch, elsebranch)\n\nO significado de uma Instrução abstrata é uma função de transformação de estado da forma que toma um Estado como entrada e produz um Estado como saída. A implementação dessas funções de significado segue diretamente das regras dadas no Capítulo 8 (e resumidas aqui). Assumimos também que tenha sido executada uma verificação estática de semânticas. A função de significado para uma instrução Clite pode ser escrita como uma sequência de regras Prolog. Lembre-se de que a função de significado para uma instrução toma uma instrução e um estado de entrada e calcula um estado:\n\n/* minstruction(statement, inState, outState) */\n\nUma instrução Skip corresponde a uma instrução vazia. Como tal, ela deixa o estado inalterado; o estado de saída é uma cópia do estado de entrada.\nminstruction(skip, State, State).\n\nUma instrução Atribuição consiste em uma Variável alvo e uma Expressão de origem. O estado de saída é computado a partir do estado de entrada, substituindo o Valor de Variável pelo valor computado da Expressão de origem, que é avaliada usando-se o estado de entrada. Todas as outras variáveis têm o mesmo valor no estado de saída que elas tinham no estado de entrada.\n\nAssim, a implementação do significado de uma atribuição avalia a expressão de origem em estado atual, resultando em um valor, e utiliza esse valor para produzir um estado de saída (usando onion). 440\nCapítulo 15 Programação Lógica\nEsse desenvolvimento de uma pequena parte da semântica formal de Clite deve convencê-lo de que um modelo semântico completo para uma linguagem imperial pode ser definido em Prolog. Portanto, via interpretação, o Prolog é capaz de computar qualquer função que possa ser programada em uma linguagem interpretativa. O inverso também é verdadeiro, já que a maioria dos modernos computadores são fundamentalmente imperativos em sua natureza, e como os intérpretes Prolog existem nessas máquinas, qualquer função programada em Prolog pode ser computada por um programa imperativo. Assim, em teoria, as linguagens imperativas e as linguagens de programação lógica são equivalentes em seu poder de computação.\n15.3.5 O Problema dos Oito Rainhas\nFinalmente, retornamos ao problema backtracking da Seção 13.4.2. Como o backtracking é o mecanismo de controle natural do Prolog, podemos passar ao desenvolvimento de uma solução para o problema das oito rainhas sem nos preocupar em desfazer movimentos de teste.\nEm geral, o problema é colocar N rainhas mutuamente antagônicas em um tabuleiro de xadrez N × N de maneira que nenhuma rainha possa capturar qualquer rainha em um único movimento. Ao desenvolver a solução, usaremos as mesmas codificações das diagonais que nos exponha na Seção 13.4.2.\nDesenvolvemos a solução de baixo para cima. Um grande problema no uso de Prolog é que não há estruturas globais do dado funcional, ou seja, as informações necessárias devem ser passadas como argumentos para os atributos necessários. Como antes, trabalharemos coluna por coluna, procuramos uma fileira na qual possamos colocar segurança a próxima rainha. Se for encontrada uma fileira segura, passaremos para a próxima coluna, caso contrário, o programa reverterá à última coluna em que a rainha foi colocada.\nAs fileiras ocupadas são armazenadas como uma lista, com o número da fileira mais recente armazenado no início da lista. Assim, para um tabuleiro 4 × 4, a lista [2, 0] representa a configuração do tabuleiro:\n0 1 2 3\n0 Q\n1\n2 Q\n3\nComo na solução Java, numeramos as fileiras e as colunas começando em 0. Assim, para formar um tabuleiro de xadrez N × N:\n0 ≤ fileira, coluna < N\nPrimeiro determinamos se um trial row move é seguro. Isso é feito passando como argumentos a lista de fileiras ocupadas, diagonais sudoeste e sudeste. Para tirar vantagem do atributo member, tudo isso é passado como três listas separadas. Um trial row move é válido se o número da fileira não estiver na lista de fileiras ocupadas 441\n15.3 Exemplos Prolog\ne se suas diagonais associadas sudoeste e sudeste não forem membros das listas de diagonais associadas:\n/* valid(TrialRow, TrialSwDiag, TrialSeDiag,\nRowList, SwDiagList, SeDiagList) */\nvalid(_, _ , _ , [ ]).\nvalid(TrialRow, TrialSwDiag, TrialSeDiag,\nRowList, SwDiagList, SeDiagList) :-\n not(member(TrialRow, RowList)),\n not(member(TrialSwDiag, SwDiagList)),\n not(member(TrialSeDiag, SeDiagList)).\nEm seguida, dadas uma fileira e uma coluna, precisamos computar as diagonais sudoeste e sudeste. Da Seção 13.4.2, lembramos que a primeira é a soma dos números de fileira e coluna, enquanto a última é sua diferença:\n/* compute SeDiag, SwDiag */\ngetDiag(Row, Col, SeDiag, SwDiag) :-\n SwDiag is Row + Col, SeDiag is Row - Col.\nEm seguida, para determinada coluna, tentamos encontrar uma fileira segura para colocar a próxima rainha. Isso é feito por meio de uma iteração sobre a sequência de números de fileira 0 ... N - 1:\n/* for current col, find safe row */\nplace(N, Row, Col, RowList, SwDiagList, SeDiagList, Row) :-\n Row < N,\n getDiag(Row, Col, SwDiag, SeDiag),\n valid(Row, SeDiag, RowList, SwDiagList, SeDiagList).\nplace(N, Row, Col, RowList, SwDiagList, SeDiagList, Answer) :-\n NextRow is Row + 1,\n NextRow < N,\n place(N, NextRow, Col, RowList, SwDiagList, SeDiagList, Answer). 442\nCapítulo 15 Programação Lógica\nBasicamente, a mesma lógica é aplicada à iteração sobre as colunas. Nesse caso, se o atributo solve tem sucesso, o último argumento é a lista de posicionamento de fileiras em ordem inversa:\n/* iterate over columns, placing queens */\nsolve(N, Col, RowList, _ , RowList) :-\n Col = N.\nsolve(N, Col, RowList, SwDiagList, SeDiagList, Answer) :-\n Col < N,\n place(N, 0, Col, RowList, SwDiagList, SeDiagList, Row),\n getDiag(Row, Col, SwDiag),\n NextCol is Col + 1,\n solve(N, NextCol, [Row|RowList], [SwDiag | SwDiagList], Answer).\nFinalmente, precisamos do próprio driver principal, que nos permite resolver para um tabuleiro arbitrário N × N, para N ≥ 0:\nqueens(N, Answer) :- solve(N, 0, [ ], [ ], Answer).\nO segundo argumento é o resultado que contém a lista das posições de fileiras em ordem inversa. Abaixo está um exemplo da execução desse programa para N = 0, 1, 2, 3 e 4:\n?- queens(0, R).\nR = [].\nno\n?- queens(1, R).\nR = [0].\nno\n?- queens(2, R).\nR = [].\nno\n?- queens(3, R).\nR = [].\nno\n?- queens(4, R).\nR = [2,0,3,1].\nno\n?- queens(4, R).\nR = [1,3,0,2].\nno\n?- 15.4 RESUMO\n\nLinguagens de programação lógica como Prolog proporcionam uma maneira diferente de pensar sobre a solução de um problema. Após alguns sucessos iniciais, especialistas previram que as linguagens lógicas substituiriam amplamente as linguagens imperativas (Kowalski, 1988). Por exemplo, Prolog foi a base para o projeto Japonês do Computador de Quinta Geração (Fifth Generation Computer) (Shapiro, 1983) que começou no início dos anos 80. Porém, esse projeto foi abandonado após cerca de 10 anos (Fuchi et al., 1993).\n\nApesar do fracasso dessas expectativas, foram usadas muitas outras linguagens declarativas para criar aplicações bem-sucedidas. Por exemplo, o sistema de avaliação na universidade de um dos autores era baseado em regras bem-sucedidas por muitos anos, para certificar os estudantes para a graduação. Outros sistemas bem-sucedidos baseados em regras incluem programas para identificar interações de drogas, diagnóstico de doenças a partir de sintomas e configuração de instalações de computadores.\n\nFora da área de inteligência artificial, as pesquisas continuam no desenvolvimento de linguagens declaratívas. Um exemplo é a linguagem Datalog (Ullman, 1989), que foi desenvolvida para sistemas de bases de dados. Datalog também foi usada recentemente em uma área de otimização de compilador de código (Waley e Lam, 2004). A simplicidade e a clareza das regras para otimização de código em Datalog, comparadas com C ou Java, ajudam a enfatizar a importancia do desenvolvimento de linguagens baseadas em regras.\n\nEXERCÍCIOS\n\n15.1 Identifique por uma variável lógica cada uma das cláusulas nas seguintes instruções, e depois reserve essas instruções na forma de cláusulas de Horn.\n(a) Se o filme Fantasma estiver sendo exibido, e os preços dos ingressos forem razoáveis, então iremos ao cinema.\n(b) Se a economia local estiver boa ou se Webber estiver na cidade, então os preços dos ingressos serão razoáveis.\n(c) Webber está na cidade.\n\n15.2 Escreva as seguintes instruções como uma série de fatos e regras Prolog: mamíferos têm quatro pernas e não têm braços, ou dois braços e duas pernas. Uma vaca não tem braços.\n\n15.3 Considere a árvore genealógica definida na Figura 15.4. Desenhe uma árvore de pesquisa no estilo daquela mostrada na Figura 15.2 para a query grandparent(Who, ron).\n\n15.4 Reconsidere a Figura 15.4, defina uma nova relação \"primo\" que represente a relação entre quaisquer quais sejam os irmãos e irmãs. Escreva uma query que será expandid o que identifique todas as pessoas que sejam primas de Ron. 15.7 Amplie o programa de diferenciação simbólica de maneira que ele diferencie funções com expoentes, bem como somas e produtos. Essa ampliação deve se basear no seguinte conhecimento:\n\nd\\r\ndx = nu^{n-1}*\\frac{du}{dx}\npara inteiros n > 0\n\nAo resolver esse problema, use o símbolo ^ para representar a exponenciação. Isto é, a expressão x^{2} deve ser digitada como x ^ 2.\n\n15.8 Use o seu programa ampliado de diferenciação simbólica para diferenciar as seguintes funções:\n(a) x^{2} + 2x + 1\n(b) (5x - 2y)(x^{2} + 1)\n\n15.9 Considere o problema de simplificar uma expressão algébrica como, por exemplo, o resultado da diferenciação simbólica. Sabemos que identidades do tipo 0 * x = 0 e x^{0} = 1 são usadas na simplificação de expressões.\n(a) Proponha uma série de regras para simplificação, com base nas propriedades de 0 e 1 somados ou multiplicados por outras expressões, e escreva uma função repetitiva Prolog simp que simplifica uma expressão algébrica arbitrária.\n(b) Mostre como simp pode ser usada para simplificar o resultado de expressões a e b na seguinte expressão. 15.10 Considerando as funções append, prefix e suffix definidas neste capítulo, desenhe uma árvore de pesquisa para uma das seguintes queries Prolog:\n(a) suffix([D], L), prefix(L, [a, b, c]).\n(b) suffix([D], L), prefix(L, [a, b, c]).\n\n15.11 Considere um programa Prolog para calcular o fatorial de um número n, dado na Seção 15.2.2. Descreva uma maneira de codificá-lo como um programa Prolog para a calcular o fatorial de n.\n\n15.12 Considere adicionar o seguinte fato e a seguinte regra ao programa da árvore genealógica discutido na Seção 15.2.1:\nancestor(X, X).\nancestor(X, Y) :- ancestor(Z, Y), parent(X, Z).\n(a) Explique a resposta do Prolog à query ancestor(bill, X) usando uma árvore de pesquisa de subobjetivos.\n(b) Descreva as circunstâncias gerais sob as quais um laço infinito pode ocorrer em um programa Prolog.\n(c) Sugira uma pequena revisão do fato e da regra acima que evitará o problema que ficou descoberto na parte (a) dessa questão.