<div class="notebook"> <div class="nb-cell html" name="htm1"> <h1> Tutorial em Programação Lógica </h1> <par> Neste notebook vamos exercitar de modo prático a programação lógica, no caso usando a linguagem Prolog. Este tópico é somente um complemento da disciplina e visa preparar todos para a implementação dos exercícios e mini-projetos. Vamos começar!</par> </div> <div class="nb-cell html" name="htm2"> <par> Prolog é uma linguagem simbólica e relacional, e seu elemento básico é um <em>fato</em>. Um fato é formado pelo nome da relação (cláusula) e pelos argumentos (objetos0. Por exemplo, vamos começar com um conjunto de fatos simples mostrando relações familiares.</par> </div> <div class="nb-cell program" data-background="true" name="p1"> pai(joao,marta). pai(joao,clovis). pai(marcos,rogerio). mae(cintia,marta). mae(cintia,telma). mae(maria,felipe). </div> <div class="nb-cell html" name="htm3"> A relação pai(mae) tem só dois argumentos (aridade 2) e se denota (pai/2)(mae/2). Um detalhe de sintaxe é que quando se trata de fatos os argumentos devem ser nomes começando com letras minúsculas mostrando que se trata de constantes (com valores fixos). Variáeis começam com letras maiúsculas, como veremos adiante. Convencionalmente pai(joao,marta) significa que <em>joao</em> é o pai de <em>marta</em>. Tendo um conjunto de fatos (sempre assumidos como verdadeiros) podemos consultá-los usando queries, por exemplo, para saber quem é o pai do "rogerio", digite no prompt (?-) abaixo ?- pai(X,rogerio). e clique na seta azul à dirita que equivale ao comando "run". Note o X maíusculo, denotando uma variável que o sistema deve instanciar os fatos acima), </div> <div class="nb-cell query" name="q1"> </div> <div class="nb-cell html" name="htm4"> A resposta aparece logo em seguida instanciando X=marcos. Se não apareceu é porque você digitou algo errado. Vamos agora dar um passo adiante e inserir uma regra ou procedimento. Uma regra pode relaciar de forma lógica diferentes queries associados à instanciação de fatos. Por exemplo, queremos definir o que significa irmao(X,Y), isto é, preparar o nosso programa para checar quem é irmão de quem, sem ter estes fatos diretamente. Vamos portanto admitir que um dado individuo é irmão de alguém se é do sexo masculino e se tem o mesmo pai ou a mesma mãe. Veja que com a base que temos não é possível saber o sexo de um dado elemento (o sistema só "sabe" o que estiver explicitamente definido na base). Portanto vamos ampliar o nosso probrama para inserir esta informação. </div> <div class="nb-cell program" data-background="true" name="p2"> masculino(joao). masculino(clovis). masculino(marcos). masculino(rogerio). masculino(felipe). feminino(marta). feminino(cintia). feminino(telma). feminino(maria). </div> <div class="nb-cell html" name="htm5"> Agora podemos definir a regra "irmao", </div> <div class="nb-cell program" name="p3"> irmao(X,Y):-masculino(X),pai(Z,X),pai(Z,Y). irmao(X,Y):-masculino(Y),mae(Z,X),mae(Z,Y). </div> <div class="nb-cell html" name="htm6"> Uma regra é definida pelo seu functor e variáveis (irmao(X,Y)) seguido pela descrição (separado :-) que aqui diz que X deve ser do sexo masculino (masculino(X)) e ter um pai Z (pai(Z,X) que é o mesmo pai de Y (pai(Z,Y)). Similarmente a segunda regra diz o mesmo para o caso de X e Y terem a mesma mãe. Podemos agora fazer um querie geral perguntando quem é irmão de quem, e usando apenas variáveis: digite na janela de querie abaixo ?-irmao(X,Y). e e clique na set azul à direita apareceu X-clovie e Y=marta? razoável e intuitivo! Agora note que existe também a opção de clicar em "Next" dizendo ao programa para buscar novas alternativas. Faça isso... </div> <div class="nb-cell query" name="q2"> </div> <div class="nb-cell html" name="htm7"> Esquisito? parece que <em>clovis</em> é irmão dele mesmo, assim como <em>rogerio</em> e <em>felipe </em>. A máquina de inferência simplesmente varre a base de fatos e regras buscando instanciar todas as variáveis. Siga o processamento você mesmo, como se fosse a máquina e veja que execução do procedientoa está correta. A nossa interpretação no entanto rejeita esse resultado. Então, as regras precisam ser modificadas para eliminar esta possibilidade se queremos que o processamento siga a forma como normalmente usamos as relações familiares. Vamos aproveitar para falar sobre os operadores internos (buit-in) do Prolog. Um deles é <em>dif</em>, que retorna "true" e segue a inferência se o termo X for diferente do intuitivamente. Vamos usá-lo para eliminar esse efeito estranho redefinindo a regra <em>irmao</em> dizendo que X tem que ser diferente de Y. </div> <div class="nb-cell program" name="p4"> irmao(X,Y):-dif(X,Y),masculino(X),pai(Z,X),pai(Z,Y). irmao(X,Y):-dif(X,Y),masculino(Y),mae(Z,X),mae(Z,Y). </div> <div class="nb-cell query" name="q3"> irmao(X,Y). </div> <div class="nb-cell html" name="htm8"> Executanto agora o mesmo querie irmão(X,Y) (clique na seta azul à direita)temos como primeira resposta X=clovis e Y=marta. Tente agora clicar no "Next" (quando aparecer a janela de resposta)e a resposta da inferência será "false", indicando que não existem outras alternativas além dessa. Introduziremos mais operadores buil-in na mesdida que forem sendo usados. Exercício: Faça agora o seu programa com o SWISH Prolog. Veja ao lado deste notebook logo abaixo do menu e logo do SWISH Prolog e clique no +; escolha abrir um "program" e experiente colocar seus fatos e regras sobre relações de familia (lembrando sempre que este programa deve ser fechado e completo, isto é, deve permitir que as inferências demandadas pelos queries possam ser feitas de forma correta (existe uma resposta) e completa (não existem respostas espúrias como alguém ser irmão de si mesmo). Depois de definir pai, mae, irmao, experinente outras regras como tio, tia, primo, etc. </div> <div class="nb-cell html" name="htm9"> <h2> <b> Resumo </b> </h2> </div> <div class="nb-cell html" name="htm10"> Prolog é uma linguagem declarativa (diferente das linguagens ditas procedurais como C, Ada, etc.), interpretada, e portanto cada linha de processamento tem escopo próprio (as variáveis só valem na regra que está sendo processada). A repetição da regra (functor e argumentos) significa que temos alternativas para o processamento. Depois do functor e argumentos uma decriç!ao ou cláusula conjuntiva, isto é, outros functores ou operadores separados por vírgula (que significa "and" do ponto de vista lógico. Um terminador, o "." indica que a regra terminou. Em sistemas onde se programa na linha de comando é possível também terminar com um ";" que significa "ou" loógico. No caso do SWISH existe a tecla "Next" que você já usou que é mais interativa. Mas o importante é que para fazer um programa em Prolog, como o exercício sugerido nesta seção, você precisa pensar no programa como um todo já que fica bem mais difícil pensar em procedientos separados e juntá-los depois. Claro, existem predicados built-in, e sempre é possível reutilizar programas, regras, etc. que já estão prontos, mas cada novo programa exigirá um tratamento sistêmico top-down. Porque? como já vimos neste exemplo (muito) simples das relações familiares, é preciso ter um programa correto e completo, isto é, o programa deve corresponder a uma interpretação ou resultados esperados e a sua completeza (a necessidade de eliminar a possibili- dade de um individuo ser irmão de si mesmo) é implementada em função disso e pode altrar o próprio programa. Não se assuste, sabemos que isso pode ser feito com uma certa facilidade em programas pequenos mas será infernal em programas maiores (talvez por isso seja temerário usar Prolog para sistemas de grande porte). Para desafios maiores existem técnicas especiais, podendo até mesclar linguagens como se faz hoje com o Python e Prolog, chamado PyLog (no passado isso era feito com C e até com Pascal). Discutiresmos essa possibilidade no final da disciplina. Mas não vamos fazer nenhum "exercício" de porte médio ou grande. Fique tranquilo! </div> <div class="nb-cell html" name="htm11"> <h2> Lidando com listas </h2> </div> <div class="nb-cell html" name="htm12"> Lista é uma estrutura de dados básica muito usada em computação e também em programas de Inteligênia Artificial. A primeira linguagem ligada à IA foi o LISP que lida basicamente com listas. Uma lista é uma estrutura de dados composta de dois elementos: a cabeça da lista, (head) e o corpo ou o restante da lista (tail). </div> <div class="nb-cell html" name="htm13"> <center> head - . - tail</center> </div> <div class="nb-cell html" name="htm14"> Portanto, se quisermos declarar uma lista de pessoas teríamos algo como... </div> <div class="nb-cell html" name="htm15"> <center> [maria, claudio, jose, giovana, carlos], </center> se prcisarmos instanciar variáveis em [X,Y] terímaos <br> <center> X= Maria <br> Y=[claudio, jose, giovana, carlos] </center> <br> Portanto a cabeça da lista é um elemento constituinte enquanto o corpo é uma lista. <br> Está definda a lista vazia ou []. </div> <div class="nb-cell html" name="htm16"> Como exercício, vamos contar o número de elementos de uma lista declarando o predicado list_count/2 que dada uma lista retorna o número de elementos. Assim, list_count([a,b,c,d,e],X) deve retornar X=5. Como seria este predicado? </div> <div class="nb-cell program" name="p5"> list_count([],0). list_count([_|X],Y):- list_count(X,Z), Y is Z+1. </div> <div class="nb-cell query" name="q4"> list_count([x,y,w,z,m,f],X). </div> <div class="nb-cell html" name="htm17"> Você pode usar no querry o comando "trace" para ver passo a passo o que está acontecendo, e como é feita a instanciação das variáveis e chamada dos procedimentos. Primeiro, será testado o primeiro predicado que checa se estamos contando os elementos de uma lista vazia (o ponto de parada). Se for esse o caso não há necessidade de ir adiante, e simplesmente a variável de retorno (seja lá como seja designada) recebe o valor 0 (zero). Se o primeiro argumento não for uma lista vazia, então chama-se recursivamente o mesmo predicado, agora com o corpo da lista (vamos contar quantos elementos tem o resto da lista). Quando retornar, basta incrementar de um o resultado para obter o número correto de elementos. Este é portanto um procedimento recursivo. A estrutura de listas é particularmente adquada para procedimentos recursivos e este recurso em programação é usado em quase todas as linguagens de programação, sejam procedurais ou declarativas (mas é bastante usado nas linguagens declarativas). Mais um detalhe, note que no segundo predicado estamos definindo alternativamente o predicado list_count como: <br> list_count([_|X], Y), <br> ou, no caso do primeiro argumento não for uma lista vazia então aplica-se o mesmo predicado para uma lista que, tem uma "cabeça" que não importa qual o valor "_" e tem um corpo que deve ser instanciado como X. Como já sabemos que a lista não é vazia tem que ter pelo menos um elemento, e seja qual for, Y será incrementado de uma unidade. </div> <div class="nb-cell html" name="htm18"> Note que se é tão fácil checar, retirar, instanciar o primeiro elemento de uma lista, a cabeça (head) o mesmo não se aplica ao último elemento. Portanto se for preciso saber quem é o último elemento teremos que varrer a lista toda. Vamos fazer este procedimento como exercício. O predicado pode se chamar last_elem/2. </div> <div class="nb-cell program" data-singleline="true" name="p6"> last_elem([X],X). last_elem([_|Y],Z):- last_elem(Y,Z). </div> <div class="nb-cell html" name="htm19"> A condição de parada agora checa se a lista só tem um elemento, "X" (lembre que a cabeça da lista é sempre um elemento). Se for o caso, então este já é o último elemento. Senão, qualquer que seja este elemento o que importa é saber o último elemento do corpo da lista. Mas, o que acontece se um usuário muito chato entrar com um query que pergunta qual é o último elemento de uma lista vazia? rode você o query... </div> <div class="nb-cell query" name="q5"> last_elem([],X). </div> <div class="nb-cell html" name="htm20"> A resposta "false" não parece muito lógica! Mas indica corretamente que o fluxo da inferência não consegue chegar a uma resposta. Nesse caso é bom ter em mente que se quisermos "fechar" de forma lógica todas as possibilidades devemos fazer um programa de fato fechado, isto é, que cobre todas as possibilidades. Nesse caso implica em incluir mais uma cláusula dizendo que listas vazias não têm "último elemento". Pra deixar clara a diferença vamos definir um novo predicado last_element, pareceido com o anterior, mas agora prevendo também a possibilidade do primeiro argumento ser uma lista vazia. </div> <div class="nb-cell program" name="p7"> last_element([],X):- writeln('esta lista é vazia'), fail. last_element([X],X). last_element([_|Y],Z):- last_element(Y,Z). </div> <div class="nb-cell query" name="q6"> last_element([],X). </div> <div class="nb-cell html" name="htm21"> Agora esta possibilidade de ter um argumento vazio está coberta também. E é claro, se não é possível calcular o último elemento o procedimento deve falhar. A dificuldade de fazer um programa lógico talvez esteja justamente em cuidar de todas estas possibilidades. Por outro lado este requisito é fundamental para ter programas que realizam processamentos que podem ser considerados inteligentes. Como exercício vamos dar mais um passo adiante. Agora o objetivo é criar uma estrutura de dados conhecida já usada em liguagens procedurais, como Python, C, etc: uma lista. Agora temos uma disciplina em que o elemento que "sai" da lista é sempre o primeiro (fácil, certo?!) mas novos elementos devem ser inseridos no final da lista. Vamos por partes! como se insere um elemento na cabeça de uma lista? Por exemplo, se temos uma lista [a,b,c,d] e queremos inserir um elemento "f" no inicio como seria? Existe um predicado builtin chamado append/3 que recebe duas listas e retorna uma terceira lista concatenando os dois argumentos. Por exemplo, no caso do nosso exemplo, vamos criar uma nova lista tendo o elemento "f" como primeiro elemento e tendo como corpo da lista [a,b,c,d,e]: </div> <div class="nb-cell query" name="q7"> append([f],[a,b,c,d,e],Z). </div> <div class="nb-cell html" name="htm22"> Agora vamos voltar ao problema inicial: sabem como se agrega um novo elemento no inicio da lista, poderemos ter como objetivo, dada uma lista, onde se quer inserir um último elemento "f", fazer o seguinte: concatenar o último elemento da lista à lista [f], depois o anterior e assim sucdssivamente até colocar toda a lista [a,b,c,d,e], nesta ordem antes do elemento "f". Como ficaria? Note que, coerentemente, append([],Y,Z) retornaria a lista Y, ou seja, a lista vazia é um elemento neutro para a operação "append". Vamos então criar um procediment "line_up" que coloca um novo elemento na fila (no final da fila): </div> <div class="nb-cell program" name="p8"> line_up(X,[],[X]). line_up(X,[W],Z):- append([W],[X], Z). line_up(X,[Y|K],Z):- line_up(X,K,W), append([Y],W,Z). </div> <div class="nb-cell query" name="q8"> line_up(f,[a,b,c,d],Z). </div> <div class="nb-cell html" name="htm23"> Outro problema clássico seria operar uma fila, onde sempre se coloca um novo elemento no início (FIFO) e sempre se retira o último elemento último elemento. Para colocar um novo elemento na fila (que na verdade é uma lista) é simples, o procedimento é comumente chamado "enqueue". Podemos fazer isso sem usar o append... </div> <div class="nb-cell program" name="p9"> enqueue(Element, [], [Element]). enqueue(Element, [X], [X | [Element]]). enqueue(Element, [X | Queue], [X | W]) :- enqueue(Element, Queue, W). </div> <div class="nb-cell html" name="htm24"> Para retirar um elemento da fila teremos que achar o último elemento e ficar com o restante dos elementos preedentes. O procediento, chamado (convencionalmente) dequeue pode ser feito do seguinte modo (usando uma chamada recursiva): </div> <div class="nb-cell program" data-background="true" name="p10"> dequeue([], X,[]). dequeue([Element|Y], Element, Y). </div> <div class="nb-cell html" name="htm25"> Para operar com uma pilha (stack) temos que seguir a regra LIFO (Last in First Out) e os procedimentos seriam os seguintes: </div> <div class="nb-cell program" name="p11"> push(Element, Stack, [Element | Stack]). pop([Element | New_Stack], Element, New_Stack). </div> </div>