Esercizio 11.1			Esercizio 11.2
		Esercizio 11.3			Esercizio 11.4
		Esercizio 11.5			Esercizio 11.6
		Esercizio 11.7			Esercizio 11.8
		Esercizio 11.9			Esercizio 11.10

		Esercizio 11.1

Combinare i meta-interpreti degli esempi in modo da ottenere sia la traccia dei programmi sia la spiegazione delle dimostrazioni.

SOLUZIONE

:- op( 550, xfy, [(<-)]).

solve(true,true):-!, trace_call(true),
trace_exit(true).
solve((A,B),(PROVA1,PROVA2)):- !,
solve(A,PROVA1), solve(B,PROVA2).
solve(A,(A <- PROVA)) :-
trace_call(A),
clause_trace(A,B),
solve(B,PROVA),
trace_exit(A).

trace_call(A) :- writeln(call(A)).
trace_call(A) :- writeln(fail(A)), fail.

clause_trace(A,B) :-
clause(A,B),
trace_redo(A).

trace_redo(A). trace_redo(A) :- writeln(redo(A)), fail.
trace_exit(A) :- writeln(exit(A)).

		Esercizio 11.2

Scrivere una versione di rimuovi(T) che

• rimuova una clausola unificabile con T
• in backtracking aggiunga tale clausola e rimuova la clausola successiva unificabile con T.

SOLUZIONE

rimuovi(T):-
retract(T),
aux(T).

aux(T).
aux(X):- assert(X), !, fail.

		Esercizio 11.3

Definire un meta-interprete per clausole Prolog estese con la presenza dell'operatore or (;).

SOLUZIONE

solve(true):-!.
solve((A,B)):- !,solve(A), solve(B).
solve((A;B)):- solve(A).
solve((A;B)):- solve(B),!.
solve(G):-
clause(G,Body),
solve(Body).

		Esercizio 11.4

Si scriva un meta-interprete che è in grado di sospendere l'esecuzione dopo un certo numero di passi di risoluzione N, dove N è specificato dall'utente. Il meta-interprete applica, inoltre, una strategia di riconoscimento di alcuni casi di (possibile) loop sospendendo l'esecuzione (riportando fallimento e il numero dei passi di risoluzione eseguiti) quando incontra un sottogoal che sia uguale, una variante o un'istanza di un sottogoal incontrato precedentemente durante la dimostrazione. Più formalmente, un atomo A è una variante o è un'istanza di un altro atomo B se esiste una sostituzione s tale che A = {B}s.

SOLUZIONE

% solve riceve in ingresso il numero N massimo di passi
% dopo i quali si deve sospendere l'esecuzione del Goal.
% Acc restituisce, nel caso si concluda la risoluzione, il
%numero di passi effettuati.

solve(Goal,Acc,N):-
solve(Goal,[],L,0,Acc,N).

% la solve/6 contiene, come parametri la lista dei goal da
% risolvere, la lista L1 dei sotto-goal già incontrati durante
% la risoluzione, la lista L3 dei sotto-goal incontrati
% durante la risoluzione attuale, Acc l'accumulatore di
% ingresso per il calcolo dei livelli già esplorati, Acc2
% l'accumulatore di uscita, e N il parametro definito
% dall'utente sul limite dei livelli di profonditˆ.

solve([],L,L,A,A,_):-!.
solve((A,B),L1,L3,Acc,Acc2,N):- !,
solve(A,L1,L2,Acc,Acc1,N),
solve(B,L2,L3,Acc1,Acc2,N).

% nel caso in cui l'accumulatore di ingresso sia uguale al
% parametro N definito dall'utente, si verifica un fallimento

solve(_,_,_,N,_,N):-
write('No. di tentativi maggiore di '),
write(N), nl,!,fail.

% nel caso in cui il goal in ingresso sia uguale, una variante o un'istanza
% di un sotto-goal incontrato precedentemente si verifica un fallimento

solve(Goal,Lista,_,_,_,_):-
loop(Goal,Lista),!,
write('Possibile loop '), nl, fail.

% risoluzione del goal Goal

solve(Goal,Lista1,Lista3,Acc,Acc2,N):-
clause(Goal,Body), Acc1 is Acc+1,
append([Goal],Lista1,Lista2),
solve(Body,Lista2,Lista3,Acc1,Acc2,N).

% loop è un predicato che consente riconoscere un
% sottogoal che è istanza, uguale o variante di un sottogoal già incontrato

loop(_,[]):-!,fail.
loop(Goal,[Head|_]):-
confronta(Goal,Head),!.
loop(Goal,[_|Tail]):-
loop(Goal,Tail).

% confronta il funtore, l'arità e tutti i parametri di Goal e
% Head per individuare se Goal è una istanza, uguale o
% variante di Head

confronta(Goal,Head):-
functor(Goal,F,A),
functor(Head,F,A),
Goal=..[_|Arg1],
Head=..[_|Arg2],
confronta_arg(Arg1,Arg2).

confronta_arg([],[]).
confronta_arg([Arg1h|Arg1t],[Arg2h|Arg2t]):-
var(Arg1h),var(Arg2h),!,
confronta_arg(Arg1t,Arg2t).
confronta_arg([Arg1h|Arg1t],[Arg2h|Arg2t]):-
nonvar(Arg1h), var(Arg2h),!,
confronta_arg(Arg1t,Arg2t).
confronta_arg([Arg1h|Arg1t],[Arg2h|Arg2t]):-
atomic(Arg1h), atomic(Arg2h),
Arg1h==Arg2h,!,
confronta_arg(Arg1t,Arg2t).
confronta_arg([Arg1h|Arg1t],[Arg2h|Arg2t]):-
compound(Arg1h), compound(Arg2h),
confronta(Arg1t,Arg2t).

		Esercizio 11.5

Si costruisca un meta interprete per Prolog (in Prolog) che adotti la strategia breadth-first. Per risolvere il problema si tenga traccia in una lista (coda) dei nodi sia dei sottogoal da dimostrare sia del top goal con le relative istanziazioni. Si consideri come esempio il programma:

a(1) :- b.
a(2): - c.
b:- b,d.
c.

Se il goal è a(X), l'evoluzione della coda dei sottogoal dovrebbe essere:

[([(a(X)], a(X))]
[([b],a(1)),([c],a(2))]
[([c],a(2)),([b,d],a(1))]
[([b,d],a(1)),([true],a(2))]
[([true],a(2)),([b,d,d],a(1))]
[([b,d,d],a(1)),([],a(2))]
[([],a(2)),([b,d,d,d],a(1))]

SOLUZIONE

% bf costruisce una lista (coda) di sottogoal e del relativo
% top goal in modo da tenere traccia del ramo dell'albero
% che si sta percorrendo.

metabf(Goal):- bf([([Goal],Goal)],Goal).

% Se la bf trova una soluzione, restituisce il top goal (con
% le variabili istanziate) che ha portato al successo

bf([([true],Istanza)|_],Istanza).

% La bf precedente ha trovato una soluzione. La bf
% successiva prosegue la ricerca nei restanti rami dell'albero.

bf([([true],_)|S],Goal):-!, bf(S,Goal).

% La findall espande il primo elemento della coda [A|B].

bf([([A|B],Goal1)|S],Goal):-
findall((BB,Goal1),trova(A,B,BB),L),
append(S,L,Newlist),
bf(Newlist,Goal).

trova(A,B,BB):-
clause(A,Body),
mixed_append(Body,B,BB).

% mixed_append concatena una struttura (X,Y) a una lista Z.

mixed_append((X,Y),Z,T):- !, mixed_append(Y,Z,W),T=[X|W].
mixed_append(X,Y,[X|Y]).

		Esercizio 11.6

Si scriva un meta-interprete per assegnare un limite massimo alla profondità dell'albero che esplora. Tale profondità D può essere specificata dall'utente all'atto dell'invocazione del meta-interprete. Nel caso in cui la profondità dell'albero superi D, il meta-interprete non fallisce, ma produce come uscita il ramo corrente dell'albero che stava esplorando. Più in dettaglio, il meta-interprete è invocato con goal della forma:
:- solve(Goal, D,Overflow).
Dove Goal è il goal iniziale e D una profondità massima. Il predicato solve ha successo:

1. Nel caso in cui il Goal ha successo con una profondità massima che non supera D. In questo caso la variabile Overflow verrà istanziata a no_overflow;
2. Nel caso in cui si sia superata la profondità massima D, la variabile Overflow verrà istanziata a una struttura del tipo overfl([A|B]), dove la lista [A|B] contiene i goal e sottogoal sul corrente ramo di ricerca. Dato il programma:

   p(X):-q(X),r(X).
   q(1).
   r(X):-p(X).

   otterremo per:- solve(p(X),5,Overflow), il risultato:
   solve(p(1),5,overfl([p(1),q(1)r(1),p(1),r(1),p(1)])).

SOLUZIONE

% Goal ha successo a una profondità minore di D

solve(true, D1, no_overflow):- D1>0.

% Profondità massima 0

solve(A,0,overfl([])).

% Caso dell'and di due sottogoal

solve((A,B),D,Overflow):-
D>0,
solve(A,D,OverflowA),
solve_conj(OverflowA,B,D,Overflow).

solve(Goal,D,Overflow):-
D>0,
clause(Goal,B),
D1 is D-1,
solve(B,D1,OverflowB),
return_overflow(OverflowB,Goal,Overflow).

solve_conj(overfl(S),B,D,overfl(S)).
solve_conj(no_overflow,B,D,Overflow):-
solve(B,D,Overflow).

% return_overflow torna no_overflow nel caso in cui il
% Goal ha successo con una profonditˆ che non supera D.
% In caso contrario provvede a costruire la lista di goal
% e sottogoal richiesta

return_overflow(no_overflow,A,no_overflow).
return_overflow(overfl(S),A,overfl([A|S])).

		Esercizio 11.7

Si scriva un meta-interprete che utilizza le clausole del programma oggetto non nell'ordine testuale, ma in base al numero di sottogoal del body dando maggiore priorità a quelle che hanno minore numero di sottogoal (ne segue che i fatti sono sempre i primi a essere presi in considerazione). Inoltre, a parità di sottogoal si scelga per prima la clausola che, prima dell'unificazione, presenti un maggiore numero di parametri istanziati.

Ad esempio: con il goal::- a(X,L,3) e il programma

a(X,Y,K):- b(X,Y,K).
a(3,Y,3):- c(Y).
a(4,5,3).

Il metainterprete deve scegliere, come prima clausola, il fatto a(4,5,3), come seconda clausola a(3,Y,3) poiché presenta un solo sottogoal nel body come la prima clausola ma ha un numero di parametri istanziati maggiore della a(X,Y,K).

Per la risoluzione dell'esercizio si supponga di avere a disposizione una clausola sort_cres(L1,L2,L3) che ordini in modo crescente la lista L1 in base ai valori contenuti nella lista L2 e metta il risultato in L3 e sort_decr(L1,L2,L3) che faccia la stessa cosa in senso decrescente.

Esempio: sort_cres([El1,El2,El3],[4,7,1],L3): L3 risulta istanziato a [El3,El1,El2] mentre in sort_decr([El1,El2,El3],[4,7,1],L3) L3 risulta istanziato a [El2,El1,El3].

SOLUZIONE

solve(true):-!.
solve((A,B)):- !, solve(A), solve(B).
solve(A):-
functor(A,Fun,Arity),
functor(Templ,Fun,Arity),
findall([Templ,Body],unif(Templ,Body),L),
sottogoal(L,L1),
parametri_ground(L,L2),
sort(L,L1,L2,L3),
member([H,Body],L3),
H=A,
solve(Body).

unif(Template, Body):-
clause(Template,Body).

% sottogoal/2 riceve in ingresso una lista di liste del tipo
% [H,Body] e fornisce in uscita una lista corrispondente
% alla prima che contiene il numero di sottogoal di
% ciascun elemento della prima lista

sottogoal([],[]).
sottogoal([[_,Body]|Tail],[L|Tail1]):-
length_and(Body,L),
sottogoal(Tail,Tail1).

% parametri_ground/2 riceve in ingresso una lista di liste
% del tipo [H|Body] e fornisce in uscita una lista
% corrispondente alla prima che contiene il numero di
% parametri ground di ciascun elemento della prima lista

parametri_ground([],[]).
parametri_ground([[H,_],Tail],[Num|Tail1]):-
H=..[_|Parametri],
ground(Parametri,Num),
parametri_ground(Tail,Tail1).

ground(Parametri,Num):-
ground(Parametri, 0,Num).
ground([],Acc,Acc).
ground([H|Tail],Acc,N):-
atomic(H),
nonvar(H),
Acc1 is Acc +1,
ground(Tail,Acc1,N).
ground([_|Tail],Acc,N):-
ground(Tail,Acc,N).

% sort/4 ordina la lista L in ordine crescente secondo i
% valori contenuti nella lista L2 e descrescente secondo i
% valori della lista L1. Naturalmente è necessario ordinare
% prima la lista L secondo i valori della lista L2 e poi
% ordinare il risultato secondo i valori della lista L1.

sort(L,L1,L2,L3):-
sort_decr(L,L2,Ldecr),
sort_decr(L1,L2,L1decr),
sort_cresc(Ldecr,L1decr, L3).

% length_and/2 calcola la lunghezza di una struttura and.

length_and((A,B),L):-
length_and(B,L1),!,
L is L1+1.
length_and(A,1).

		Esercizio 11.8

Si scriva un meta-interprete in grado di riconoscere i predicati is/2 e di valutare se le chiamate devono essere sospese o eseguite. Nel caso in cui gli argomenti a destra del predicato non siano sufficientemente istanziati, il predicato deve essere sospeso ponendolo in un'apposita lista; in caso contrario viene eseguito normalmente. Ad esempio A is 2+3 viene sempre eseguito mentre A is B+C viene sospeso se una delle variabili B o C non è istanziata. Al termine dell'esecuzione di ogni sottogoal, il meta-interprete deve controllare se nella lista dei predicati sospesi ne compaiono alcuni che possono essere eseguiti perché sufficientemente istanziati. Se la valutazione del goal termina con successo, ma la lista dei predicati sospesi contiene ancora predicati non sufficientemente istanziati, il meta-interprete restituisce la lista dei goal sospesi.

SOLUZIONE

IPOTESI: si hanno a disposizione fatti del tipo clausola(Head,Body) dove Body è una lista di sottogoal. interi/3 ha come parametri la lista dei goal da eseguire, la lista dei goal sospesi (solo is/2) in ingresso e la lista dei goal sospesi in uscita

interi([],[],_):-!.

% Nel caso in cui si sia giunti al termine dell'esecuzione di un goal e
% la lista dei predicati sospesi non sia vuota, si deve controllare se tale
% lista contiene predicati che possono essere eseguiti. In questo caso
% lista_tutti_is fallisce facendo fallire anche interi che
% però ha un choice point che permette di eseguire i predicati
% divenuti sufficientemente istanziati. In caso contrario vengono stampati
% i goal sospesi e l'esecuzione termina.

interi([],L,_):-
lista_tutti_is(L),!,
write('Lista di goal sospesi'),nl,
stampa(L).
interi([],L,_):-
interi(L,[],_).
interi([Goal|Altri],L2,L1):- !,
interi(Goal,L2,Ltemp),
interi(Altri,Ltemp,L1).

% Caso in cui il predicato è is/2 ma gli argomenti
% sono sufficientemente istanziati.

interi(Goal,Lgoal,Lnuovi):-
is_solvable(Goal),!,
call(Goal),
Lgoal=Lnuovi.

% Caso in cui il predicato è is/2 ma gli argomenti non sono
% sufficientemente istanziati.

interi(Goal,Lgoal,Lnuovi):-
is_not_solvable(Goal),!,
append(Lgoal,[Goal],Lnuovi).

% Caso normale

interi(Goal,Lgoal,Lgoal1):-
clausola(Goal,Body),
interi(Body,Lgoal,Lgoal1).

is_solvable(Goal):-
Goal=..[is,_,B],
B=..[_,L,K],
nonvar(L),nonvar(K),!.

is_not_solvable(Goal):-
Goal=..[is,_,B],
B=..[_,L,K],
(var(L); var(K)).

lista_tutti_is([]).
lista_tutti_is([Lh|Lt]):-
is_not_solvable(Lh),!,
lista_tutti_is(Lt).
lista_tutti_is([Lh|_]):-
is_solvable(Lh),fail.

stampa([]).
stampa([H|T]):-
write(H),nl,
stampa(T).

		Esercizio 11.9

Supponendo di avere un database Prolog composto da fatti del tipo:
regola(nome-modulo,Testa <- Corpo).
dove in Corpo possono apparire goal del tipo:
[<lista nome-moduli>]<<Goal
(che richiede la dimostrazione del Goal utilizzando solo le regole nei moduli della lista di moduli specificata). Si scriva un meta-interprete in grado di interpretare tali programmi e che riporti in uscita, in caso di dimostrazione con successo, anche la lista di moduli le cui regole sono state effettivamente utilizzate per la dimostrazione.
Esempio di programma:

regola(m1, a(X)<-[m2]<<c(X))
regola(m1, c(3)<-true)
regola(m2, c(1)<-[m3,m4]<<d(2))
regola(m3, d(3)<-true)
regola(m4, d(2)<-true)

La soluzione (unica) generata dal meta-interprete per il goal [m1]<-a(X) sarà yes con X legato a 1 e con lista di moduli effettivamente usati: [m1,m2,m4].

SOLUZIONE

solve(true, M, M).

solve((A,B), ModOld, ModNew):-
solve(A, ModOld, ModTemp),
solve(B, ModTemp, ModNew).

solve(LL<<G, ModIn, ModOut):- !,
member(Mod, LL),
regola(Mod, G<-Body),
append([Mod], ModIn, ModTemp),
solve(Body, ModTemp, ModOut).

solve(G, ModIn, ModOut):-
regola(X,G<-Body),
append([X], ModIn, ModTemp),
solve(Body, ModTemp, ModOut).

		Esercizio 11.10

Si costruisca un meta-interprete per Prolog che chieda all'utente i goal che non è in grado di dimostrare, solo se per essi non compaiono fatti ground nel database con lo stesso funtore a arità.

SOLUZIONE

meta1(true):-!.
meta1((X,Y)):- !,meta1(X),meta1(Y).
meta1(X):- clause(X,Body),meta1(Body).

% Non ho dimostrato X: cerco fatti ground nel data-base.
% Se non li trovo chiedo all'utente con ask/1 se X è true o false

meta1(X):-
not(fatti(X)),
ask(X,Risp),call(Risp).

fatti(X):-
functor(X,P,A),
functor(K,P,A),
clause(K,true),
K=..[_|Arg],
gr(Arg).

ask(X,Risp):-
write(X),
write(" true or false ? "),
read(Risp).

% gr controlla che gli argomenti siano ground.

gr([]).
gr([Argh|Argt]):-controllo(Argh),gr(Argt).

% Caso di una costante come argomento

controllo(B):-atomic(B),!.

% Caso di una lista come argomento.

controllo([H|T]):-
!,controllo(H),
controllo(T).

% Caso di un termine composto come argomento.

controllo(B):-
compound(B),
B=..[_|L],
controllo(L).

In alcuni Prolog esistono predicati (non standard) predefiniti ground/1 o nonground/1

LIA WebMaster	LIA PostMaster
LIA Home Page
DEIS Home Page	Alma Mater Home Page