• Una clausola ` e un termine: :- `e un funtore (in particolare, un operatore infisso) A :- B `e la stessa cosa di ’:-’(A,B)

Metaprogrammazione Programmi e dati sono rappresentati in modo uniforme

• Un atomo ` e un termine: la struttura di un atomo `e uguale a quella di un termine (una struttura)

• Una congiunzione di atomi ` e un termine: la virgola `e un funtore (in particolare, un operatore infisso)

A,B `e la stessa cosa di ’,’(A,B)

• Una clausola ` e un termine: :- `e un funtore (in particolare, un operatore infisso) A :- B `e la stessa cosa di ’:-’(A,B)

Un fatto A `e una clausola della forma A :- true.

I programmi possono essere trattati come dati

Meta-programma: programma che tratta altri programmi come dati

Il predicato clause

?- listing(concat).

concat([], A, A).

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

Yes

?- clause(concat(X,Y,Z), Body).

X = []

Y = _G169 Z = _G169

Body = true ;

X = [_G284|_G285]

Y = _G169

Z = [_G284|_G288]

Body = concat(_G285, _G169, _G288) ;

Un semplice meta-interprete per il Prolog puro Meta-interprete: interprete per un linguaggio scritto nel linguaggio stesso solve(true) :- !.

solve((G1,G2)) :-

!, solve(G1), solve(G2).

solve(Goal) :-

clause(Goal,Body),

solve(Body).

Costruzione dell’albero di dimostrazione durante la verifica di un goal

?- op(300,xfx,’=>’).

solve(true,true) :- !.

solve((G1,G2),(Prova1,Prova2)) :-

!, solve(G1,Prova1), solve(G2,Prova2).

solve(Goal,(Prova => Goal)) :- clause(Goal,Body),

solve(Body,Prova).

genitore(pam,bob).

genitore(bob,pat).

nonno(X,Y) :- genitore(X,Z), genitore(Z,Y).

?- solve(nonno(pam,pat),P).

P = (true=>genitore(pam, bob), true=>genitore(bob, pat))=>nonno(pam, pat) Yes

Realizzazione di sistemi esperti in Prolog: facile fornire al sistema la capacit`a di spiegare il

proprio ragionamento

Manipolazione della base di dati Esempio: i numeri di Fibonacci

fib(1,1).

fib(2,1).

fib(N,F) :- N>2,

N1 is N-1, fib(N1,F1), N2 is N-2, fib(N2,F2), F is F1+F2.

Poco efficiente: per calcolare fib(N2,F2), si deve ricalcolare fib(N1,F1),...

?- dynamic(fib/2). /* direttiva: per SWI-Prolog */

fib(1,1).

fib(2,1).

fib(N,F) :- N>2,

N1 is N-1, fib(N1,F1), N2 is N-2, fib(N2,F2), F is F1+F2,

asserta(fib(N,F)). /* aggiunge la clausola al programma */

?- fib(5,F).

F = 5 Yes

?- listing(fib).

fib(5, 5).

fib(4, 3).

fib(3, 2).

fib(1, 1).

fib(2, 1).

fib(A, B) :- A>2,

C is A-1, fib(C, D), E is A-2, fib(E, F), B is D+F,

asserta(fib(A, B)).

Yes

Cancellazione di clausole

cancella :-

clause(fib(N,F),true), N > 2,

retract(fib(N,F)), fail.

cancella.

?- cancella.

Yes

?- listing(fib).

fib(1, 1).

fib(2, 1).

fib(A, B) :- A>2,

C is A-1, fib(C, D), E is A-2, fib(E, F), B is D+F,

asserta(fib(A, B)).

Yes

Costruzione dell’insieme di tutte le soluzioni Esempio: insieme potenza

powset(Set,_) :-

generate_subset(S,Set), assertz(found(S)),

fail.

powset(_,P) :-

raccogli(P).

raccogli([S|Rest]) :-

retract(found(S)), raccogli(Rest).

raccogli([]).

Attenzione alla definizione di generate subset

subset va bene per controllare se un insieme `e sottoinsieme di un altro, ma non per generare sottoinsiemi: genera infinite soluzioni, con ripetizioni (del primo elemento).

subset([],_).

subset([X|Rest],Set) :- member(X,Set), subset(Rest,Set).

generate_subset([],[]).

generate_subset([X|Rest],[X|Set]) :- generate_subset(Rest,Set).

generate_subset(Rest,[_|Set]) :-

generate_subset(Rest,Set).

bagof, setof, findall

?- bagof(S,generate_subset(S,[1,2,3]),P).

S = _G381

P = [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

Yes

powset2(Set,P) :-

bagof(S,generate_subset(S,Set),P).

bagof, setof, findall

foo(b,a). foo(a,c).

foo(c,a). foo(d,b).

foo(a,b). foo(e,b).

?- bagof(X,foo(X,Y),Bag).

X = _G285 Y = a

Bag = [b, c] ; X = _G285

Y = c

Bag = [a] ; X = _G285 Y = b

Bag = [a, d, e] ; No

?- findall(X,foo(X,Y),Bag).

X = _G297 Y = _G298

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

setof `e come bagof ma restituisce liste ordinate e senza ripetizioni

Differenza tra findall e bagof

?- findall(Y,(member(X,[2,4]),Y is X*2),Result).

Y = _G162 X = _G156

Result = [4, 8] ; No

?- bagof(Y,(member(X,[2,4]),Y is X*2),Result).

Y = _G162 X = 2

Result = [4] ; Y = _G162

X = 4

Result = [8]

Esempi d’uso di findall

pari(X) :- 0 is X mod 2.

?- findall(X,(member(X,[1,2,3,4,5,6]),pari(X)),L).

X = _G165

L = [2, 4, 6]

Yes

filter(P,L,Result) :-

findall(X,(member(X,L),Cond=..[P,X],Cond),Result).

?- filter(pari,[1,2,3,4,5,6],L).

L = [2, 4, 6]

Yes

sublist(+Pred, +List1, ?List2)

Unify List2 with a list of all elements of List1 to which Pred applies.

intersect(S1,S2,S) :-

findall(X, (member(X,S1),member(X,S2)), S).