Termini Costanti

(1)

Termini Costanti

Atomi

Numeri (studiare la matematica del Prolog)

?- 10 = 5+5.

No

?- 10 is 5+5.

Yes

?- X is 5+5.

X = 10 Yes

?- 10 is X+5.

ERROR: Arguments are not sufficiently instantiated Variabili (variabile anonima: )

Strutture

(2)

Strutture f(t

¹

,...,t

n

) Funtore applicato a termini

libro(’Le tigri di Mompracem’,autore(emilio,salgari)) 3+X

C’` e qualche differenza sintattica tra strutture e fatti?

(Studiare: Operatori)

Strutture e alberi libro

Le tigri di Mompracem autore

emilio salgari

(3)

Rappresentazione di alberi binari

/* is_tree(T) : T e’ un albero binario */

is_tree(empty).

is_tree(t(Left, _, Right)) :- is_tree(Left),

is_tree(Right).

/* occorrenza di un elemento in un albero binario */

in_tree(El, t(_, El, _)).

in_tree(El, t(Left, _, _)) :- in_tree(El, Left).

in_tree(El, t(_, _, Right)) :- in_tree(El, Right).

Le due regole di in tree si possono compattare in una regola sola, utilizzando il ; (OR):

/* occorrenza di un elemento in un albero binario */

in_tree(El, t(_, El, _)).

in_tree(El, t(Left, _, Right)) :- in_tree(El, Left);

in_tree(El, Right).

(4)

Alberi binari di ricerca

/* inserimento in un ABR */

ins_abr(El, empty, t(empty, El, empty)).

ins_abr(El, t(Left, El, Right), t(Left, El, Right)).

ins_abr(El,t(Left,Middle,Right),t(LeftN, Middle, Right)) :- El < Middle,

ins_abr(El, Left, LeftN).

ins_abr(El,t(Left,Middle,Right),t(Left, Middle, RightN)) :- El > Middle,

ins_abr(El, Right, RightN).

/* ricerca in un ABR */

search_in_abr(El, t(_, El, _)).

search_in_abr(El, t(Left, Middle, _)) :- El < Middle,

search_in_abr(El, Left).

search_in_abr(El, t(_, Middle, Right)) :- El > Middle,

search_in_abr(El, Right).

(5)

Classificazione dei termini Il Prolog `e un linguaggio a tipizzazione dinamica

Predicati predefiniti per riconoscere il tipo di un termine var, nonvar

?- var(X).

X = _G147 Yes

?- var(padre(X)).

No

?- X=Y, Y=23, var(X).

No

integer, float, number atom

atomic

?- atom(pippo).

Yes

?- atom(3).

No

?- atomic(3).

Yes

(6)

Accesso ai componenti e costruzione delle strutture:

functor, arg e Univ

?- functor(f(a,b,c),F,N).

F = f N = 3 Yes

?- functor(X,f,3).

X = f(_G199, _G200, _G201) Yes

?- arg(2,f(a,b,c),X).

X = b Yes

?- f(a,b,c) =.. X.

X = [f, a, b, c] /* [f, a, b, c] e’ una LISTA */

Yes

(7)

Liste

Una lista `e un oggetto strutturato: si pu`o rappresentare utilizzando un funtore, ad esempio cons, e una costante per la lista vuota, ad esempio nil

cons(a,cons(b,cons(c,nil))) is_lst(nil).

is_lst(cons(_,X)) :- is_list(X).

elemento(X,cons(X,_)).

elemento(X,cons(_,Y)) :- elemento(X,Y).

?- elemento(b,cons(a,cons(b,cons(c,nil)))).

Yes

(8)

La struttura dati predefinita per le liste [a, b, c] Lista vuota: []

Il “cons” `e l’operatore . (prefisso) oppure | (infisso)

?- [a,b,c] = .(a,.(b,.(c,[]))).

Yes

?- [a,b,c] = [a | [b | [c | [] ] ] ].

Yes

?- [a,b,c] = [X|Y].

X = a

Y = [b, c]

Yes

Gli elementi delle liste possono essere di tipo qualsiasi, non necessariamente omogeneo

?- X = [1, pippo, padre(pippo), [a,b,c]].

X = [1, pippo, padre(pippo), [a, b, c]]

Yes

?- X = .(pippo,pluto).

X = [pippo|pluto]

Yes

Si possono rappresentare alberi, coppie e tuple mediante liste.

(9)

Rappresentazione di alberi n-ari mediante liste

is_ntree([_|Tlist]) :-

is_ntreelist(Tlist).

is_ntreelist([]).

is_ntreelist([T|Tlist]) :- is_ntree(T),

is_ntreelist(Tlist).

/* selettori */

root([X|_], X).

left([_,L|_], L).

treerest([X,_|Rest], [X|Rest]).

?- is_ntree([1,[2],[3,[4],[5]]]).

Yes

?- T = [1,[2],[3,[4],[5]]], root(T,R), left(T,L), treerest(T,Rest).

T = [1, [2], [3, [4], [5]]]

R = 1 L = [2]

Rest = [1, [3, [4], [5]]]

(10)

Predicati predefiniti sulle liste Le “operazioni” su liste: member, append, length, delete ...

in Prolog sono relazioni

?- member(X,[1,2,3]), X>2.

X = 3

?- append(X,[4,5],[1,2,3,4,5]).

X = [1, 2, 3]

?- length(X,3).

X = [_G224, _G227, _G230]

?- delete([1,2,1,3,1,4], 1, X).

X = [2, 3, 4]

?- delete([1,2,1,3,1,4], X, [2, 3, 4]).

X = 1

Vedere sul manuale di SWI-Prolog: library(lists).

(11)

Esempio: concatenazione di liste (append `e predefinito)

/* concat(X,Y,Z): Z e’ la concatenazione di X e Y */

concat([],X,X).

concat([X|L1],L2,[X|L3]) :- concat(L1,L2,L3).

?- concat([a,b],[c],X).

X = [a, b, c]

Yes

?- concat(X,[b,c],[a,b,c]).

X = [a]

Yes

?- concat(X,Y,[a,b,c]).

X = []

Y = [a, b, c] ; X = [a]

Y = [b, c] ;

X = [a, b]

Y = [c] ;

X = [a, b, c]

Y = [] ;

No

(12)

listing

?- listing(append).

% Foreign: append/1

append([], A, A).

append([A|B], C, [A|D]) :- append(B, C, D).

Yes

(13)

Altri esempi /* -- ultimo elemento di una lista -- */

last(X,List) :- append(_,[X],List).

/* -- elementi vicini in una lista -- */

next_to(X,Y,List) :- append(_,[X,Y|_],List).

/* -- appartenenza a una lista: definizione alternativa -- */

elemento(X,List) :- append(_,[X|_],List).

/* --- costruzione di un ABR da una lista --- */

from_list([], empty).

from_list([Head|Tail], Abr) :- from_list(Tail,Tree), ins_abr(Head,Tree,Abr).

Quali dei predicati definiti fin qui sono “reversibili”?

(14)

Esempio: rappresentazione di automi non deterministici

s1

s2 a

b

a

b s3

a b

initial(s1).

initial(s2).

final(s3).

trans(s1,a,s1).

trans(s1,b,s1).

trans(s1,a,s2).

trans(s2,b,s3).

trans(s3,a,s3).

trans(s3,b,s3).

accepts(String) :- initial(Q),

accepts(Q,String).

accepts(Q,[]) :- final(Q).

accepts(Q,[X|Rest]) :- trans(Q,X,Q1),

accepts(Q1,Rest).

?- accepts([a,a,a,b,b,b]).

Yes

?- accepts([a,a,a]).

No

?- accepts(X).

ERROR: Out of local stack

Spiegare perch´ e

(15)

Oltre la logica

Esempio: ricerca di un cammino in un grafo Un grafo rappresenta una relazione binaria

a b

e c d

arc(a,b).

arc(a,e).

arc(b,a).

arc(b,c).

arc(c,c).

arc(c,d).

arc(d,c).

arc(d,b).

arc(e,c).

(16)

Ricerca di un cammino: prima versione

path(X,X,[X]).

path(X,Y,[X|P]) :- arc(X,Z), path(Z,Y,P).

Va bene solo per grafi aciclici

?- path(d,c,P).

P = [d, c] ; P = [d, c, c] ; P = [d, c, c, c]

Yes

?- path(b,c,P).

ERROR: Out of local stack

(17)

Ricerca di un cammino: seconda versione Per gestire i cicli si deve tener traccia dei nodi gi`a visitati.

path(X,Y,P) :- path(X,Y,P,[]).

path(X,X,[X],_).

path(X,Y,[X|P],Visited) :-

not(member(X,Visited)), arc(X,Z),

path(Z,Y,P,[X|Visited]).

Nota: path/3 e path/4 sono due predicati distinti.

?- path(a,d,P).

P = [a, b, c, d] ; P = [a, e, c, d] ; No

Attenzione: il predicato not del Prolog non ` e la negazione logica

(18)

Not: negazione come fallimento

Mediante la risoluzione SLD non si possono derivare informazioni negative: se P è un programma logico e A un atomo, ¬A non è mai una conseguenza logica di P perché P ∪ {A} è sempre soddisfacibile.

student(joe).

student(bill).

student(jim).

teacher(mary).

¬ student(mary) non `e una conseguenza logica del programma

?- not(student(mary)).

Yes

not(student(mary)) = student(mary) non ` e una conseguenza logica del pro- gramma, e questo si stabilisce in modo finito (la risoluzione SLD termina).

Se Goal fallisce, allora not(Goal) ha successo;

se Goal ha successo, allora not(Goal) fallisce

not non `e la negazione logica: se not(Goal) ha successo, non significa che la negazione di

Goal `e dimostrabile dal programma, ma che Goal non `e dimostrabile

(19)

Assunzione del mondo chiuso (CWA)

Ogni cosa vera può essere derivata dal programma, quindi se qualcosa non è derivabile è falso

CWA: regola molto naturale nei database

E un esempio di regola di inferenza ` non-monotona: l’aggiunta di nuovi assiomi pu`o far diminuire l’insieme dei teoremi

Se al programma logico si aggiunge il fatto student(mary), il goal not(student(mary)) non `e pi`u derivabile.

Attenzione con l’uso del not

r(a).

q(b).

p(X) :- not(r(X)).

?- q(X), p(X).

X = b Yes

?- p(X).

No

Problemi quando alcune variabili non sono istanziate all’interno di una chiamata a not

(20)

Caratteristiche extralogiche:

il controllo del backtracking Esempio: calcolo del massimo tra due numeri X e Y:

se X ≥ Y allora il massimo `e X, altrimenti (se X < Y ) il massimo `e Y . max(X,Y,X) :- X >= Y.

max(X,Y,Y) :- X < Y.

greater_than_both(Z,X,Y) :- max(X,Y,M), Z>M.

Le due clausole di max sono mutuamente esclusive: se X >= Y ha successo, `e inutile cercare un’altra soluzione mediante la seconda clausola

greater than both(5,8,3) max(8,3,M), 5>M

M=8, 8>=3, 5>M

· · ·

M=3, 8<3, 5>M

· · ·

Il ramo di sinistra fallisce, ma `e comunque inutile cercare una soluzione nel ramo di destra:

non esistono altre soluzioni per max(8,3,M).

Il sottoalbero rosso potrebbe essere potato

(21)

Il controllo del backtracking: il cut max(X,Y,X) :- X >= Y, !. /* cut: ha sempre successo */

max(X,Y,Y) :- X < Y.

greater_than_both(Z,X,Y) :- max(X,Y,M), Z>M.

greater than both(5,8,3) max(8,3,M), 5>M

M=8, 8>=3, !, 5>M

· · ·

M=3, 8<3, 5>M

· · ·

Quando il backtracking ritorna al cut (dopo il fallimento di 5>M), il sottoalbero rosso viene potato

max(8,3,M), 5>M: parent goal , che ha attivato la clausola contenente il cut.

Se il backtracking ritorna al cut, il sistema ignora (taglia) tutto il resto del sottoalbero che

ha radice nel parent goal.

(22)

Cut a :- b, c.

a :- d, e.

b :- b

¹

, b

²

, !, b

³

. /* clausola 1 */

b :- b

⁴

...

Significato dichiarativo: il predicato “cut” ha sempre successo

Significato operazionale: il “cut” congela le scelte fatte dall’interprete dal momento in cui `e stato invocato il goal b e unificato con la testa della clausola 1:

• tutte le scelte nella dimostrazione di b

¹

, b

²

sono congelate (eventuali alternative sono eliminate)

• la scelta della clausola per dimostrare b `e congelata alla clausola 1

Goal: a. Viene usata la prima clausola che definisce a e il goal diventa b, c (parent goal) Per cercare di dimostrare b, viene usata la prima clausola che definisce b, e il goal diventa b

¹

, b

²

, !, b

³

, c

Si trova il primo modo possibile di dimostrare b

¹

, b

²

Con la soluzione trovata per b

¹

, b

²

, si cerca di dimostrare b

³

, c. Se questo tentativo fallisce, il backtracking non considera altre possibili soluzioni per b

¹

, b

²

e nemmeno altri modi per soddisfare b (anche la seconda clausola che definisce b viene ignorata).

Il tentativo di dimostrare a torna a considerare la seconda clausola che definisce a.

(23)

Il cut e la logica p :- a, b.

p :- c.

p ≡ (a ∧ b) ∨ c

p :- a, !, b.

p :- c.

p ≡ (a ∧ b) ∨ (not a ∧ c) p :- c.

p :- a, !, b.

p ≡ (a ∧ b) ∨ c

(24)

Definizione del not Il not del Prolog `e in realt`a un costrutto derivato dal “cut”:

not(G) :- G, !, fail.

not(_).

Si noti che i due schemi seguenti sono equivalenti:

A :- B, C.

A :- not(B), D.

A :- B, !, C.

A :- D.

La prima forma è più comprensibile, la seconda più efficiente.

Il “cut” aumenta il potere espressivo del linguaggio Usando il “cut” `e possibile definire regole “if-then-else”:

if(X,Y,_) :- X, !, Y.

if(_,_,Z) :- Z.

(25)

Diversi usi del cut

• L’uso del “cut” consente di specificare situazioni deterministiche e di migliorare l’effi- cienza dei programmi: non si perde tempo a cercare di soddisfare goal dei quali si sa gi`a che non contribuiranno alla soluzione

Inoltre: risparmio di memoria (non si conservano punti di backtracking)

In questi casi, il cut non cambia il significato dichiarativo del programma: cut verde.

max(X,Y,X) :- X >= Y, !.

max(X,Y,Y) :- X < Y.

/* merge di liste ordinate */

merge(X,[],X).

merge([],X,X).

merge([X|R1],[Y|R2],[X,Y|R]) :- X=Y, !,

merge(R1,R2,R).

merge([X|R1],[Y|R2],[X|R]) :- X<Y, !,

merge(R1,[Y|R2],R).

merge([X|R1],[Y|R2],[Y|R]) :- X>Y, !,

merge([X|R1],R2,R).

(26)

• In alcuni casi l’uso del “cut” `e necessario per ottenere il funzionamento corretto dei programmi.

Il cut cambia il significato dichiarativo del programma: cut rosso.

/* max / / inserimento insiemistico */

max(X,Y,X) :- X >= Y, !. setadd(X,L,L) :- member(X,L), !.

max(_,Y,Y). setadd(X,L,[X|L]).

Non `e possibile definire l’inserimento insiemistico senza il cut o un costrutto derivato dal cut (not).

Cut rosso: il cut `e necessario per definire la relazione correttamente (dal punto di vista procedurale), e non solo per migliorare l’efficienza

/* intersezione insiemistica */

intersect(_,[],[]).

intersect([],_,[]).

intersect([X|Rest],Y,[X|R]) :- member(X,Y), !,

intersect(Rest,Y,R).

intersect([_|Rest],Y,R) :-

intersect(Rest,Y,R).

(27)

Cut verdi e cut rossi

cut verdi: migliorano l’efficienza; in caso di fallimento non si tentano altre alternative, che sarebbero comunque destinate a fallire

Un cut verde dice al sistema: “se sei arrivato fin qui, hai trovato e scelto l’unica regola corretta per soddisfare questo goal ed `e inutile cercare alternative”

cut rossi: il significato procedurale non corrisponde a quello dichiarativo.

L’uso di cut rossi aumenta il potere espressivo del linguaggio, consentendo di specificare regole mutuamente esclusive.

Un cut rosso dice al sistema: “se sei arrivato fin qui, hai trovato e scelto la regola corretta per soddisfare questo goal” (conferma la scelta di una regola)

Un terzo uso del cut: la combinazione cut-fail

“se sei arrivato fin qui, non devi pi`u cercare di soddisfare questo goal”

Esempi:

/* definizione del not */

not(G) :- G, !, fail.

not(_).

/* different */

different(X,X) :- !, fail.

different(_,_).

(28)

Problemi con il cut Il “cut” pu`o rovinare la reversibilit`a dei predicati

Esempio: assumiamo di voler definire concat sapendo che verrà sempre utilizzato con due liste date per costruire la loro concatenazione: se la prima lista è vuota, la prima regola è l’unica corretta

concat([],X,X) :- !.

concat([X|L1],L2,[X|L3]) :- concat(L1,L2,L3).

?- concat([a,b],[c,d,e],X).

X = [a, b, c, d, e]

?- concat(X,Y,[a,b,c]), member(a,X).

No

?- append(X,Y,[a,b,c]), member(a,X).

X = [a]

Y = [b, c]

(29)

Utilizzando il cut si deve aver presente come si useranno esattamente le regole

number_of_parents(adam,0) :- !.

number_of_parents(eve,0) :- !.

number_of_parents(_,2).

?- number_of_parents(adam,X).

X = 0 ; No

?- number_of_parents(adam,2).

Yes

(30)

Un altro esempio /* intersezione insiemistica */

intersect(_,[],[]).

intersect([],_,[]).

intersect([X|Rest],Y,[X|R]) :- member(X,Y), !,

intersect(Rest,Y,R).

intersect([_|Rest],Y,R) :- intersect(Rest,Y,R).

?- intersect([2],[2],[]).

Yes

Per avere un comportamento corretto anche quando il terzo argomento non `e variabile, si deve modificare l’ultima clausola: