I – Programas Em Lógica 1 –

8/14/2019 I Programas Em Lgica 1

1/42

I Programas em Lgica1 Construes BsicasAs construes bsicas da programao em lgica, termos e frases (statements), soinerentes lgica. Existem 3 tipos de frases bsicas: factos, regras e consultas.H s uma estrutura de dados: o termo lgico.

1.1. FACTOSO tipo de frase mais simples o facto. Os factos so meios de dizer que existe umarelao entre objectos.ex: father(abraham,isaac)Um outro nome para uma relao predicado. Nomes de indivduos so conhecidoscomo tomos.A relao plus (mais) pode ser definida custa de factos, atravs duma tabela longa,como por exemplo plus(0,0,0). plus (0,1,1). etc.

Os predicados e tomos nos factos comeam por letra minscula.Um conjunto finito de factos constitui um programa lgico. tambm a descrio deuma situao. Este ponto de vista a base da programao de bases de dados.

ex: de base de dados de uma relao familiar:father(terach,abraham). male(terach).father(terach,nachor). male(abraham).father(terach,haran). male(nachor).father(abraham,isaac). male(haran).father(haran,lot). male(isaac).father(haran,milcah). male(lot).father(haran),yiscah).

female(sarah).mother(sarah,isaac). female(milcah).

female(yiscah).(Program 1.1.)

1.2. CONSULTAS (Queries)A segunda forma de frase a consulta. Consultas so meiOS de encontrarinformao a partir de um programa lgico. Uma consulta pergunta se uma dadarelao existe entre objectos. ex: father(abraham,isaac)?. a resposta yes.Sintacticamente as consultas e os factos parecem similares. NO entanto elesdistinguem-se pelo contexto. Mas mesmo que haja dvidas, o facto termina por pontofinal e a consulta por ?.Chamamos entidade sem o . ou o ? de goal (meta). P. diz que P true P? perguntaonde P true.Uma consulta simples consiste num nico goal.Responder a uma consulta com respeito a um programa determinar quando a query

uma consequncia lgica do programa.As consequncias lgicas so obtidas por aplicao das regras de deduo.

A mais simples regra de deduo a identidade: de P deduz-se P. Umaconsulta uma consequncia lgica de um facto idntico.

Se o programa for s de factos, como o 1.1. s percorr-los para responder yes ouno a uma query. Isso no quer dizer que a query no seja verdadeira.

1.3. A VARIVEL LGICA, SUBSTITUIES E INSTNCIAS Uma varivel lgica diz respeito a um indivduo no especificado.

ex: father(abraham, X)? X a varivel lgica, e ajuda a expressar melhor aconsulta, que tambm podamos fazer por father(abraham,lot)?father(abraham,milcah)? etc...Desta maneira, sumarizam vrias queries.


2/42

Uma consulta contendo uma varivel pergunta onde esto os valores que tornam aquery uma consequncia lgica do programa.So diferentes das variveis nas linguagens convencionais pois representam uma noespecificada mas nica entidade e no uma localizao de memria.Termo a nica estrutura de dados em programas lgicos. A definio indutiva.Constantes e variveis so termos. Tambm termos compostos e estruturas sotermos.Um termo composto formado por um functor (chamado o rpincipal functor do termo)e uma sequncia de um ou mais argumentos, que so termos. Um functor caracterizado pelo seu nome, que um tomo, e a sua aridade ou nmero deargumentos. Sintacticamente f(t1,t2,...,tn).Queries, goals, ou mais genericamente, termos onde no ocorrem variveis, sochamados ground. Se ocorrerem variveis so unground.

Substituio um conjunto finito (eventualmente vazio) de pares da forma Xi=t1 ,onde Xi uma varivel e ti um termo, e XiXj para todo o ij, e Xi no ocorre em tjpara nenhum i e j.

um exemplo consistindo num nico par {X=isaac}. As substituies podem seraplicadas aos termos. O resultado de aplicar uma substituio a um termo A,denotado por A, que o termo obtido por substituio de em qualquer ocorrncia deX por t em A, para todo o par X=t em .O resultado de aplicar {X=isaac} ao termo father(abraham,X) o termofather(abraham,isaac).

A uma instncia de B se h uma substituio tal que A=B

1.4. QUERIES EXISTENCIAISLogicamente falando, as variveis nas queries so existencialmente quantificadas,embora, por convenincia, a quantificao existencial seja geralmente omitida.

2 regra de deduo generalizao: Uma query existencial P uma consequncialgica de uma instncia dela, P, para qualquer substituio .Operacionalmente, para responder a uma query no ground usando um programa defactos, procura-se um facto que uma instncia da query. Se encontrado, a resposta,ou soluo, a instncia.A soluo representada, neste captulo, pela substituio que, se aplicada query,resulta na soluo.

1.5. FACTOS UNIVERSAISAs variveis tambm so teis em factos.ex: fact likes(X,pomegranates) diz que todos gostam em vez de especificar um a um.Desta maneira, as variveis so meios de sumarizar vrios factos. ex: times(0,X,0).

As variveis em factos esto implicitamente quantificadas universalmente.Logicamente, de um facto universalmente quantificado podemos deduzir qualquerinstncia dele.esta a 3 regra de deduo, chamada instanciao: De uma frase universalmentequantificada P, deduz-se uma isntncia dela, P, para qualquer substituio .ex: plus(0,X,X). likes(X,X).Responder a uma query ground com um facto universalmente quantificado directo.ex: plus(0,2,2) yes, baseado no facto plus(0,X,X).Responder a uma query no ground usando um facto no ground envolve uma novedefinio:C uma instncia comum de A e B se for uma instncia de A e uma instncia de B,isto , se houver substituies 1 e 2 tais que C=A1 sintacticamente idntica aB2..ex: plus(0,3,Y) e plus(0,X,X) tm uma isntncia comum plus(0,3,3).


3/42

Em geral, para se responder a uma query usando um facto, procura-se por umainstncia comum ao facto e query. A resposta a instncia comum se existir, se no no.Responder usando a instncia comum envolve instanciao e generalizao.

1.6. QUERIES CONJUNTIVAS E VARIVEIS PARTOLHADASConsultas conjuntivas so uma conjuno de goals postas numa query nica. ex:father(terach,X), Father(X,Y)? a vrgula significa and.As consultas conjuntivas so interessantes quando h uma ou mais variveispartilhadas, variveis que ocorrem em duas diferentes metas da query. ex:father(haran,X), male(X)?O scope/alcance de uma varivel numa query conjuntiva toda a conjuno.As variveis partilhadas so usadas como meio de constrangimento de uma simplesquery restringindo o alcance de uma varivel.Um uso diferente de uma varivel partilhada pode ser visto em father(terach,X),father(X,Y)?Uma query conjuntiva uma consequncia lgica de um programa P se todas as

metas na conjuno so consequncias de P, onde as variveis partilhadas soinstanciadas para os mesmos valores em diferentes metas.Uma condio suficiente que h uma instncia ground da query que consequnciade P. Esta instncia deduz ento os conjunctos na query via generalizao. A restrioa ground no necessria, como se vr no cap.4

1.7. REGRAS Queries conjuntivas interessantes definem, elas prprias, relaes.

ex: father(terach,X), father(X,Y)? questiona sobre os netos de terach.Isto leva-nos terceira, e mais importante, frase na programao em lgica regra que nos permite definir novas relaes em termos de relaes existentes:So da forma A


4/42

Cap. 2 PROGRAMAO DE BASES DE DADOSH 2 estilos bsicos de usar programas lgicos: definindo uma base de dados lgica emanipular estruturas de dados.Uma base de dados lgica contm um conjunto de factos e regras.Veremos como um conjunto de factos pode definir relaes, como nas bases de dadosrelacionais, e como as regras podem definir complexas consultas relacionais, como nalgebra relacional.

2.1. BASES DE DADOS SIMPLESUsaremos a base de dados bblica do exemplo 1.1. e vamos aument-la com regrasexpressando as relaes familiares.A base de dados tem, ela prpria, 4 predicados: father/2, mother/2 male/1 e female/1.vamos adoptar a conveno da teoria das bases de dados, que d a cada relao umesquema de relao que especifica o papel que cada posio na relao (ouargumento na meta) representa. Esquemas de relao so por exemplo:father(Father,Child), male(Person).As variveis tm nomes mnemnicos nas regras, mas habitualmente X ou Y quando

em consultas.Variveis de vrias palavras: NieceOrNephewPredicados de vrias palavras: schedule_conflictDo ponto de vista lgico no importante que relaes so definidas por factos ou porregras.Regras interessantes podem ser obtidas criando relaes explicitamente, a partir dasque esto implcitas na base de dados.Quantas mais relaes h mais fcil se torna definir relaes complexas.

uncle(Uncle,Person)


5/42

transistor(input1,X,Output), transistor(Input2, ground, X),resistor(power,Output).

and_gate(Input1,Input2,Output)


6/42

A consulta and_gate(G,In1,In2,Out)? tem a soluo {G=and(nand(t2,t3,r2),inv(t1,r1)),In1=n3, In2=n5, Out=n1}a estruturao de dados importante em programao em geral e em programaoem lgica em particular. usada para organizar dados duma forma significativa. Asregras podem ser escritas duma forma mais abstracta, ignorando pormenoresirrelevantes. Programas mais modulares podem ser conseguidos.

ex:a) course(complexity, monday, 9,11,david,harel,feinberg,a).b) course(complexity,time(Monday,9,11),lecturer(david,harel),location(feinberg,a)).As regras que no usem valores particulares de um argumento estruturado noprecisam saber como o argumento est estruturado. Ver ex: abaixo no prog.2.4. nocaso de time.No h regras definitivas: No usar dados estruturados conduz a uma maioruniformidade de representao quando os dados so simples. As vantagens daestruturao dos dados so a compactao da representao, que maisapuradamente reflecte a nossa perspectiva da situao e modularidade.

lecturer(Lecturer,Course)


7/42

3.2. LISTASA estrutura bsica para a aritmtica o functor sucessor unrio, o que limitado parafunes recursivas mais complicadas.Por isso definimos agora a estrutura binria lista.O primeiro argumento de uma lista guarda um elemento e o segundo argumento recursivamente o resto da lista.As listas so suficientes para a amior parte das comptuaesPara as listas, tal como para os nmeros, um smbolo constante necessrio paraterminar a recurso. Esta lista vazia, refrerida como nil, ser denotada pelo snmbolo [].:(X,Y) denotado por [X|Y] X chamada a cabea da lista e Y a cauda

Definindo uma lista:list(Xs)


8/42

suffix(Xs,[Y|Ys])


9/42

adjacent(X,Y,Zs)


10/42

Comeamos com a parte recursiva. A forma habitual para argumentos recursivos delistas [X|Xs]. H duas possibilidades a considerar: quando X o elemento a deletar equando no .No primeiro caso, o resultado de recursivamente deletarmos X de Xs o resultadodesejado para a query. A regra apropriada :delete([X|Xs],X,Ys)


11/42

Prog.3.20.verso naive/permutaes paradigma gerar-e-testarsort(Xs,Ys)


12/42

II A Linguagem PrologPara implementar uma linguagem de programao prtica e baseada no modelocomputacional da programao lgica, trs aspectos precisam de ateno_Resolver as escolhas que permanecem na interpretao abstracta para os programaslgicos (ver cap.4)Enriquecer as expressividades da computao pura do modelo, acrescentandofacilidades meta-lgicas e extra-lgicas.Aceder a algumas capacidades do computador, como aritmtica rpida e proverinput/output.

6 Prolog Puro um programa lgico no qual uma ordem definida, quer para as clusulas (clauses)quer para as metas (goals) no corpo da clusula.O interpretador est preparado para tirar vantagens da ordenao da informao.O Prolog puro uma realizao aproximada da programao lgica do modelocomputacional, numa mquina sequencial.

6.1. O Modelo de Execuo do PrologMaiores decises para converter o interpretador abstracto para uma forma de sucessopara uma linguagem de programao concreta:A secolha arbitrria de qual meta no resolvente, reduzir, nomeadamente a poltica deagendamento, tem de ser especificada.A escolha no de terminista da clusula do programa para efectuar a reduo, tem deser implementado.O Prolog est baseado na execuo sequencial.O Prolog escolhe a meta mais esquerda e escolhe a clusula por procura sequencialpara uma clusula unificvel e backtracking.Por outras palavras, adopta uma poltica de agendamento tipo stack. Mantm o

resolvente como uma pilha: tira a meta de topo para reduo e pe as metasderivadas no stack do resolvente.Tambm e em adio, Prolog simula a escolha no determinista da clusula dereduo por procura sequencial e backtacking. Quando tenta reduzir uma meta, aprimeira clusula cuja cabea unifica com a meta escolhida. Se no encontraclusula unificvel para a meta tirada do stack, volta ltima escolha efectuada e aprxima clusula unificvel escolhida.Uma computao duma meta G com respeito a um programa Prolog P a gerao detodas as solues de G com respeito a P. .... = particular rvore de procura de Gobtida escolhendo sempre a meta mais esquerda.Edimburgh = standard:- igual


13/42

daughter(X,Y)


14/42

partition([ ], Y, [ ] , 8 ]).quicksort ([2,1,3], Qs)

partition([1,3],2,Ls,Bs) Ls=[1|Ls1]1 2partition([3],2,Ls1,Bs) Ls1=[3|Ls2]

3 2 falsepartition([3],2,Ls1,Bs) Bs=[3|Bs1]

3 > 2partition([ ],2,Ls1,Bs1) Ls1=[ ]=Bs1

quicksort([1],Qs1)partition([ ],1,Ls2,Bs2) Ls2=[ ] =Bs2quicksort([ ],Qs2) Qs2=[ ]quicksort([ ],Qs3) Qs3= [ ]append([ ], [1], Qs1) Qs1=[1]

quicksort([3],Qs4)partition([ ],3,Ls3,Bs3) Ls3=[ ] =Bs3quicksort([ ],Qs5) Qs5=[ ]

quicksort([ ],Qs6) Qs6= [ ]append([ ], [3], Qs4) Qs4=[3]append([19,[2,3],Qs) Qs=[1,Ys]

append([ ],[2,3],Ys) Ys=[2,3]true

Output: (Qs=[1,2,3])

fig. 6.3. Tracing uma computao de quicksorting (ver livro pg.123)

Introduzimos agora uma distino entre shallow e deep backtacking.Shallow backtracking ocorre quando a unificao entre uma meta e uma clusula falhae uma clusula alternativa tentada.

Deep backtracking ocorre quando a unificao da ltima clusula dum procedimentocom uma meta, falaha e o controlo retorna a outra meta na rvore de computao.

6.2. Comparao com Linguagens de Programao ConvencionaisUma linguagem de programao caracterizada pelos seus mecanismos de controloe de manipulao de dados.O controlo em Prolog como nas linguagens procedimentais.Invocaes de metas/goals correspondem a invocao de procedimentos e a ordemdas metas no corpo da clusula correspondem a uma sequncia de instrues.ex:A


15/42

As estruturas de dados manipuladas pelos programas lgicos, termos, correspondema estruturas de registo gerais. O manuseamento de estruturas de dados muitoflexvel em Prolog. Como no Lisp, Prolog uma linguagem de declaraes livres,linguagem sem tipos.

A maior diferena no uso das estruturas de dados vem da natureza das variveislgicas. Elas referem-se a indivduos em vez de localizaes de memria. No suportapois assignment destrutivo.

A manipulao de dados nos programas lgicos atingida inteiramente via algoritmode unificao. Unificao subsume:assignement nico; Passagem de parmetros; Alocao de registos;leitura/escrita-uma vez acesso aos campos nos registos.

No exemplo da figura 6.3. a unificao da meta inicial quicksort([2,1,3], Qs) com acabea da definio de procedimento quicksort([X|Xs], Ys) ilustra uma data de coisas.A unificao de [2,1,39 com o termo [X|Xs] consegue acesso ao registo lista e

tambm seleco dos dosi campos, a cabea e a cauda.A unificao de [1,3] com Xs uma passagem de parmetros para o procedimentopartition, por causa da partilha de variveis.A criao dum registo pode ser vista com a unificao da meta partition([1,3],2,Ls,Bs)com a cabea do procedimento partition([X|Xs],Z,[X|Ls1],Bs1). Como resultado Ls instanciado a [1|Ls1]. Especificamente, Ls feita numa lista e a sua cabea assignada ao valor 1, nomeadamente, criao de registo e assignamento de campovia unificao.

A ideia bsica da compilao do Prolog traduzir casos especiais de unificao paramanipulao de memria convencional na mquina de von Neumann.

O algoritmo recursivo incorporado em quicksort pode ser visto como manipulao deponteiros em listas.

O Prolog no tem manipulao de erros e excepes. D sempre falha.

O que vimos at aqui no responde questo mais interessante: Como se podecomparar programar em Prolog com programar nas convencionais linguagens deprogramao. o que iremos ver at ao final do livro.

CAP. 7Programao em Prolog PuroO maior objectivo da programao em lgica permitir ao programador programar a

um alto nvel. Idealmente deveramos escrever axiomas que definem as relaesdesejadas, mantendo ignorncia do caminho que sero usadas pelo mecanismo deexecuo.As linguagens correntes, como o Prolog, ainda esto longe desse objectivo ideal daprogramao declarativa.Programas lgicos efectivos requerem conhecimento de como os mecanismos deexecuo fazem as escolhas.Este captulo discute as consequncias do modelo de execuo do Prolog para oprogramador.

7.1. Ordem das RegrasDuas coisas irrelevantes para os programas em lgica, so importantes emcomposio de programss em Prolog: A ordem das regras, ou a ordem das clusulas.Tambm a ordem das metas nos corpos de cada clsula deve ser determinado.


16/42

As decises destas escolhas pode ser imensa no que respeita a eficincia, que podeat ir no terminao em casos mais extremos.A ordem das regras determina a ordem em que as solues so encontradas.Mudar a ordem das regras num procedimento permuta as derivaes em qualquerrvore de procura para uma meta usando aquele procedimento.Este facto claramente visto quando usamos factos para responder a uma consultaexistencial. Mudando a ordem dos factos na nossa rvore bblica altera a ordem dassolues encontradas. Mas, a ordem dos factos no importante.

A ordem de solues de consultas resolvidas por recursividade tambm determinadapela ordem das clusulas.Ex:parent(terach,abraham). parent(abraham,isaac).parent(isaac,jacob). parent(jacob,benjamin).

ancestor(X,Y)


17/42

married(abraham, sarah).married(abraham,sarah)

married(sarah,abraham)married(abraham,sarah)

married(sarah,abraham)....

Regras recursivas que tm uma meta recursiva como primeira meta so conhecidascomo regras recursivas esquerda, que so inerentemente causadoras de problemasem Prolog, pois causam computaes no terminais se chamadas com argumentosimprprios. O melhor evit-las.As relaes comutativas (como o caso anterior) so melhor manejveis definindo umnovo predicado que tem uma clusula para cada permutao dos argumentos. Nonosso caso poderamos resolver com:

are_married(X,Y)


18/42

A ordem de metas ptima varia com os diferentes usos.EX: Para a definio de grandparent h duas possveis regras.grandparent(X,Z)


19/42

a consulta minimum(2,2,M)? tem duas solues, sendo uma redundante.Uma soluo seria, aps exame minucioso, alterar a segunda regra paraminimum(X,Y,Y)


20/42

O programa s no termina se ambos os 2 e 3 argumentos forem lista incompletas.Uma variante para este programa se acrescentarmos o teste XY clususlarecursiva. Como antes, assumimos que est apenas definido para argumentoground. Somos conduzidos ao programa select_first, que tem um signifaicadodiferente de select, ao passo que member_check tinha um significado igual a member.ex3:permutation(Xs,[X|Ys])


21/42

CAP.8 ARITMTICAOs programas lgicos para trabalhar a aritmtica, dados na seco 3.1. so muitoelegantes mas no so prticos.Isto porque no se pode ignorar os recursos que qualquer computador tem para asoperaes aritmticas. Ento temos de estender o Prolog puro para ter tambmsystem predicates (evaluable predicates, builtin predicates, bips)

8.1. PREDICADOS DE SISTEMA PARA ARITMTICAO preo a pagar que algumas operaes aritmticas orientadas pela mquina noso to gerais como as lgicas, mas ganha-se eficincia.ex: Standard Prolog tem um sp is(Value,Expression). is infixo.Os operadores so usados para tornarem os programas mais legveis.Os programadores tambm podem construir os seus prprios operadores, usando obuilt-in op/3.Queries usando o avaliador aritmtico disponibilizado pelo Prolog tm a seguinteforma: Value is Expression?. A expresso aritmtica a valiada e o resultado dado/unificado em Value.

ex: (X is 3+5)? tem a soluo X=8 (3+5 is 3+5) falaha pois o primeiro argumento nounifica com 8, que o resultado da avaliao da expresso.

O que acontece se o termo a ser avaliado no uma vlida expresso aritmtica?Pode ser invlida por duas razes:

- Um termo como 3+x para uma constante x no pode ser avaliado. Emcontraste, um termo 3+Y para a varivel Y pode ser ou no avaliado,dependendo do valor de Y.

A semntica de um programa e, lgica completaente definida e assim no podehaver runtime errors. Por exemplo, a meta X is 3+Y tem as solues {X=3, Y=0}.Todavia quando interfaceamos com um computador temos de contar com as suaslimitaes. Um runtime error acontece quando a computao no pode ser acabada

por falta de informaes, isto , variveis no instanciadas. Isto distinto das metasque simplesmente falham.Extenses do Prolog manejam com estes erros, suspendendo at que os valores dasvariveis em causa sejam conhecidos.O modelo de Prolog introduzido no permite suspenses.A query (X is 3+x) falha porque o argumento do lado direito no pode ser avaliadocomo uma expresso aritmtica.Um erro comum dos iniciados pensarem que is o mesmo que assignar. H atentao de escrever a meta, por exemplo, (N is N+1).

Outros predicados de sistema so =). O Prolog chamadirectamente as operaes aritmticas.

(A


22/42

Similarmente, o maior divisor comum pode ser calculado usando o algoritmo deEuclides:

Prog. 8.1.greatest_common_divisor(X,Y,Z)


23/42

O Prolog no tem variveis de aramzenamento para colocar os resultadosintermdios. Ento usamos argumentos adicionais (acumuladores)

Prog. 8.4.factorial(N,F)


24/42

Prog. 8.9.maxlist([X|Xs], M)


25/42

CAP. 9 Inspeco de Estruturas

O Prolog standard tem vrios predicados ligados a estruturas de termos. Estespredicados so usados para reconhecer os diferentes tipos de termos, para decomporos termos nos seus functores e argumentos e para criar novos termos.

9.1. PREDICADOS DE TIPOS

So relaes unrias que distinguem entre tipos diferentes de termos. O prpriosistema j traz alguns e que dizem se um termo uma estrutura ou uma constante, emais, se a constante um tomo, um inteiro ou real (vrgula flutuante).Os 4 predicados bsicos do Prolog standard so:integer(X)


26/42

flatten([X|Xs],S,[X|Ys])


27/42

subterm(N,Sub,Term)


28/42

falta a figura 9.2. , o prog 9.4. e o prog. 9.5.a

CAP. 10 PREDICADOS META-LGICOSUma extenso poderosa do poder expressivo dos programas lgicos dado pelospredicados meta-lgicos. Estes predicados esto fora do alcance da lgica de 1ordem, porque eles consultam o estado da prova, tratam variveis (em vez dos termosque elas denotam) como objectos da linguagem, e permitem conver~soa de estruturasde dados em metas.Permite-nos ultrapasssar duas dificuldades que sentimos nos cap. anteriores atrabalhar com variveis:1 O comportamento das variveis nos predicados de sistema. Por exemplo, avaliaruma expresso com uma varivel d erro. Assim como chamar predicados de tipo comargumentos como variveis.2 Instanciao acidental de variveis durante a inspeco de estruturas. No cap. 9restringimos a inspeco a termos ground.Este cap. tem 4 seces: 1- discute predicados tipo que determinam quando um termo uma varivel. 2- Comparao de termos. 3- predicados que permitem as variveis

ser manipuladas como objectos. 4 converter dados em metas executveis.10.1. PREDICADOS META-LGICOS DE TIPOO bsico var(Term), que testa se um dado termo , no presente momento, umavarivel no instanciada. O seu comportamento similar aos predicados de tipodiscutidos no captulo anterior.A query var(Term)? tem sucesso se Term uma varivel e falha caso contrrio. ex:var(X)? tem sucesso e var(a)? e var([X|Xs])? falham.O predicado var uma extenso ao Prolog puro. Uma tabela no pode agora serusada para dar todos os nomes de variveis.Um facto var(X) quer dizer que todas as instncias de X so variveis, e no que aletra X denota uma varivel. Ser capaz de referir a um nome de varivel est fora do

alcance da lgica do 1 grau.O predicado nonvar(Term) tem o comportamento contrrio.

Este tipo de predicados pode ser usado para dar alguma flexibilidade aos programasque usam predicados de sistema e tambm para controlar a ordem das metas. oque veremos usando programas j estudados atrs.

Por ex: o programa plus que vamos ver abaixo pode ser usado para soma esubtraco. A ideia checar quais os argumentos que esto instanciados antes,chamando o avaliador aritmtico. Por exe. a 2 regra diz que se o 1 e 3 argumentos,X e Z, no so variveis, o 2 argumento, Y, pode ser determinado como a suadiferena. De notar que se os argumentos no forem inteiros isto falha.

No d erros mas ainda no pode ser usado para gerar partio de um nmero. Issorequer gerao de nmeros.

Prog. 10.1.plus(X,Y,Z)


29/42

Prog. 10.2.lenght(Xs,N)


30/42

formal definio de unificao: Requer que uma varivel no seja unificada com umtermo contendo essa varivel. Para implementar isso tem de se verificar se duasvariveis so idnticas (no apenas unificveis, como quaisquer duas variveis so). este o teste meta-lgico.O Prolog standard d-nos um predicado de sistema, == , para este propsito. A queryX == Y? tem sucesso se X e Y so constantes, variveis idnticas ou estrururas cujosprincipais functores tm a mesmo nome e aridade, e recursivamente Xi == Yi? tmsucesso para todos os correspondentes argumentos Xi e Yi de X e Y.Por exemplo X == 5? falha, em contraste com X=5?Tambm h um predicado de sistema que tem o comportamento contrrio a ==. Aquery X\==Y? tem sucesso a no ser que X e Y sejam termos idnticos.

Prog.10.5.unify(Term1,Term2)


31/42

Na prtica, outro comportamento habitualmente preferido. Os dosi termos X e adevem ser considerados diferentes, e Y deve ser instanciado por X. O outro caso basedo programa 9.3.substitute(Old,New,Term,Term)


32/42

numeradas de N1 a N2-1. O efeito substituir cada varivel do termo por um termo daforma $VAR(N). ver prog.10.8.

10.4. A FACILIDADE META-VARIVELUma caracterstica do Prolog a equivalncia dos programas e dados ambos podemser representados em termos lgicos. Para explorar isto, os programas precisam deser tratados como dados e os dados ttransformados em programas.Vamos ver uma facilidade que permite transformar um termo numa meta:call(X) , chama a meta X para o Prolog resolver.Na prtica, a maioria das implementaes Prolog relaxam a imposio que as metasno corpo de uma clusula tm de ser termos no variveis. A meta-varivel facilidadepermite uma varivel aparecer como meta numa meta conjuntiva ou no corpo de umaclusula. Durante


33/42

Cap. 11Cuts and Negation (Cortes e Negao)O Prolog fornece um sistema de predicados simples, chamados cut, para afectar ocomportamento procedimental dos programas. A sua funo principal reduzir oespao de procura das computaes Prolog, pruning dinamicamente a rvore deprocura.O cut pode ser usado para prevenir o Prolog de seguir caminhos sem frutos, que oprogramador sabe que no podem dar resultados.Podem tambm ser usados, inadvertidamente ou propositadamente, para aprumar oscaminhos de computao que contm solues. Fazendo isto, uma forma fraca denegao pode ser ser efectuada.O uso do cut controverso pois a maior parte dos seus usos s pode ser interpretadoprocedimentalmente, em contraste com o que aconselhamos, que um estilodeclarativo de programao que encorajamos. Usado com parcimnia pode, noentanto, aumentar a eficincia dos programas sem comprometer a sua clareza.

11.1. Green Cuts: Expressing Determinism (Cortes Verdes: Expressando

Determinismo)Consideremos o programa merge (Xs, Ys,Zs). uma operao determinista. Se XY, X=:=Y, s uma pode ser true.

merge(Xs, Ys, Zs)


34/42

conjuno falhe, a procura prossegue desde a ltima alternativa antes da escolha daclusula contendo o corte.

ex: merge com cortesmerge(Xs,Ys,Zs)


35/42

polynomial(Term, X)


36/42

A questo que alcance deve o cut ter. Isso vai para o cap.17. (no interessa).

11.2. Tail Recursion Optimization (Optimizao por recurso da cauda)Como se viu em 8.3. a diferena de perfomance entre a recursividade e a iterao que, enquanto a iterao requer um espao constante, qualquer que seja o nmero deiteraes usadas, a recursividade exige um espao linearmente dependente donmero de chamadas recursivas a executar.Os programas recursivos sero mais elegantes, mas a perda de espao no compensadora. Felizmente h uma espcie de programas recursivos que podem serexecutados em espao constante.A tcnica a Tail Recursion Optimization ou Last Call Optimization. Intuitivamente tentar executar um programa recursivo como se fosse iterativo.......11.3. Negation (Negao)O corte pode ser usado para implementar uma verso da negao como falha. Oprograma 11.6. define um predicado not(Goal), que tem sucesso se o Goal falha.

Tambm usando o corte, o programa usa a facilidade meta varivel descrita nocap.10, e o predicado de sistema fail que falha sempre.not X


37/42

A query unmarried_student(X)? falha com respeito aos dados, ignorando que X=bill uma soluo logicamente implicada pela regra e pelos dois factos. A falha ocorre npgoal not married(X), pois h uma soluo X=joe. O problema pode ser evitado aqui portroca da ordem dos goals no corpo da regra.Um exemplo similar a query not(X=1), X=2?, que falah apesar de haver uma soluoX=2.A implementao da negao como falha no trabalha garantidamente de formacorrecta para goals no ground. ento da responsabilidade do programador garantir que as metas negadas soground antes de estarem resolvidas.Isto pode ser feito ou por anlise esttica do programa ou por um runtime check,usando o predicado ground definido no programa 10.4.O predicado not muito til. Permite-nos definir conceitos interessantes. Por ex.consideremos o predicado disjoint(Xs,Ys), verdadeiro se duas listas Xs e Ys no tmelementos em comum. Pode ser definido como:disjoint(Xs,Ys)


38/42

No programa 11.6 o cut no green mas red. O programa no ter o mesmosignificado se o cut for removido.A combinao cut-fail usada para implementar outros predicados de sistemaenvolvendo a negao. Por exemplo o predicado (escrito como \= no Prologstandard) pode ser facilmente implementado via unificao e cut-fail, em vez de umatabela infinita, com o programa 11.8. Este programa tambm s funcionagarantidamente para goals ground.Com ingenuidade, e um bom entendimento da unificao e do mecanismo deexecuo do Prolog, definies interessantes podem ser encontradas para muitospredicados meta-lgicos.

Prog.11.8. Implementando o XY


39/42

Vamos ver as normas para o uso de cuts:As implementaes do Prolog so mais eficientes se souberem que o predicado determinista. O primeiro objectivo do corte dizer que o predicado determinista eno para controlar o backtracking. As duas regras bsicas para usar o cut so:- Fazer o cut to local quanto possvel- Colocar o cut to cedo assim que for sabido que a clusula correcta foi escolhida.Ex: do quicksort de 3.22.quicksort([X|Xs],Ys)


40/42

CAP. 12 Predicados Extra-Lgicoscaem fora do modelo de programao lgica.H trs tipos: concernentes a I/O, para acessar e manipular o programa e parainterfacear com o sistema operativo. S vamos dar os dois primeiros.12.1. Input/OutpuO predicado bsico de input read(X). Este goal l um um termo do stream de entradacorrente, usualmente o terminal. O termo lido unifica com X e o read tem sucesso oufalha resultante da unificao.Para output write(X).Nem o read nem o write do solues alternativas em backtracking.

Prog. 12.1.writeln([X|Xs])


41/42

A leitura das palavras termina com um carcter end-of-words, um ponto final porexemplo. Neste programa as palavras podem ser separadas por um nmero arbitrriode caracteres de preenchimento.Ser preciso ainda acrescentar as definies de word_char/1, fill_char/1 eend_of_words_char/1. importante que o programa leia um carcter frente e o teste para decidir o quefazer (tem 3 hipteses conforme o carcter seja duma palavra, de preenchimento oude final de lista de palavras).ex:process([ ])


42/42

asserta adiciona no princpio em vez do fim.Para remover usa-se o predicado retract(C), remove a primeira clusula que unifiquecom C.Se for do tipo a

Documents

I – Programas Em Lógica 1 –