ALBERI SLD
esercizi
Compito 14 Gennaio 2003
• Si consideri il seguente programma Prolog, che calcola il
minimo di una lista:
min(A,B,A) :- A < B, !.
min(A,B,B).
minlist([X],X):- !.
minlist([H|T],M) :minlist(T,M1),
min(H,M1,M).
• Si rappresenti l’albero SLD corrispondente
all’invocazione
?- minlist([1,2,3],2).
• Il risultato è corretto? Se no, come dovrebbe essere
modificato il programma per avere il comportamento
corretto?
Soluzione
minlist([1,2,3],2)
H/1, T/[2,3], M/2
minlist([2,3],M1), min(1,M1,2)
H’/2, T’/[3], M’/M1
minlist([3],M1’), min(2,M1’,M1), min(1,M1,2)
M1’/3
min(2,3,M1), min(1,M1,2)
A/3, B/2, M1/2
2<3, !, min(1,2,2)
A’/1, B’/2 (clausola 2)
true
Esercizio
• Si consideri la seguente definizione del
predicato length, che calcola la lunghezza di una
lista:
length([],0).
length([_|T],N):- length(T,M),
N is M+1.
• Si mostri l’albero SLD relativo al goal
length([1,2,3],X).
• Si scriva poi il predicato in maniera tail-recursive
e si mostri l’albero SLD relativo allo stesso goal.
8 Luglio 2003
• Il seguente programma Prolog:
sumtree(n(TL,TR),N) :sumtree(TL,L),
sumtree(TR,R),
N is L+R.
sumtree(X,X).
dà errore in backtracking.
• Si inserisca un cut che permetta di avere un
comportamento corretto e si rappresenti l’albero SLD
corrispondente alla invocazione
:- sumtree(n(1,n(2,3)),N).
1 sumt ree(n(TL, TR), N): !,
sumtree(TL , L),
sumtree(TR, R),
N is L+R.
2 sumt ree(X, X).
1) sumtree(n(1, n(2, 3)), N)
1 - {TL1/1, TR1/ n(2, 3), N1/N}
#!1
2) !, sumtree(1, L 1), sumt ree(n(2, 3), R1), N is L1+R1
12) Pruned
branch cl(2)
!1
3) sumtree(1, L 1), sumt ree(n(2, 3), R1), N is L1+R1
2 - {X3/1, L 1/1}
4) sumtree(n(2, 3), R1), N is1+R1
#!4
1 - { TL4/2, TR4/3, N4/R1}
5) !, sumtree(2, L4), sumtree(3, R4), R1 is L4+R4, N is1+R1
!4
6) sumtree(2, L4), sumtree(3, R4), R1 is L4+R4, N is1+R1
2 - {X6/2, L 4/2}
7) sumtree(3, R4), R1 i s 2+R4, N is1+R1
2 - {X7/3, R4/3}
8) R1 is2+3, N is1+R1
- {R1/5}
9) N is 1+5
- { N/6}
10. success
{ N/6}
11) Pruned
branch cl(2)
Occur check
• Si consideri il seguente programma Prolog:
add([],[]).
add([N|R],[N,N|T]).
member(J,[J|_]).
member(J,[_|K]) :- member(J,K).
• Si rappresenti l’albero SLD relativo alla query:
:- add([A,B],L), member([A,B],L).
fino alla prima soluzione nell’ipotesi che venga
controllato l’Occur Check. Si mostri poi la
risposta calcolata.
add([],[]).
add([N|R],[N,N|T]).
member(J,[J|_]).
member(J,[_|K]) :member(J,K).
Soluzione
add([A,B],L), member([A,B],L).
N/A, R/[B], L/[A,A|T]
member([A,B],[A,A|T]).
J’/[A,B], K’/[A|T]
A/[A,B]
fail
(Occur check)
member([A,B],[A|T]).
J”/[A,B], K”/T
A/[A,B]
member([A,B],T).
fail
(Occur check)
T/[[A,B]|_]
true
…
22 Giugno 2006
• L’algoritmo di Euclide per il calcolo del MCD è dato da:
A
se


mcd ( A, B)  mcd ( A, B  A) se
mcd ( A  B, B) se

AB
A B
AB
• Si consideri il seguente programma Prolog:
mcd(A,A,A):-!.
mcd(A,B,M):- A<B,!, C is B-A, mcd(A,C,M).
mcd(A,B,M):- I is A-B, mcd(I,B,M).
• L’algoritmo va in loop con il goal
?- mcd(2,2,1).
• Si corregga il programma e si disegni l’albero SLD
relativo all’invocazione
?- member(X,[1,2]), mcd(2,X,1).
Programma corretto
mcd(A,A,A):-!.
mcd(A,B,M):- A<B,!, C is B-A, mcd(A,C,M).
mcd(A,B,M):- A>B, I is A-B, mcd(I,B,M).
Albero SLD
mcd(A,A,A):-!.
mcd(A,B,M):- A<B,!,C is B-A, mcd(A,C,M).
mcd(A,B,M):- A>B, I is A-B, mcd(I,B,M).
20 Dicembre 2004
• Si consideri il seguente programma Prolog che calcola se
un numero è primo (dove mod calcola il modulo, cioè il
resto della divisione intera):
primo(N):- not(divisibile(N)).
divisibile(N):- compreso(2,M,N),0 is N mod M.
compreso(I,X,S):- I>=S, !, fail.
compreso(I,I,S).
compreso(I,X,S):- J is I+1, compreso(J,X,S).
• Si disegni l’albero SLDNF relativo al goal:
?- primo(3).
primo(N):not(divisibile(N)).
divisibile(N):compreso(2,M,N),
0 is N mod M.
compreso(I,X,S):-I>=S,!,fail.
compreso(I,I,S).
compreso(I,X,S):- J is I+1,
compreso(J,X,S)
16 Dicembre 2005
• Si consideri il seguente programma Prolog:
isground(X):- not(X=skolem).
reversible(S=Op):rewrite(S,Op,R=NewOp),
R is NewOp.
rewrite(S,A+B,S=A+B):- isground(A), isground(B), !.
rewrite(S,A+B,A=S-B):- isground(S), isground(B),!.
rewrite(S,A+B,B=S-A):- isground(S), isground(A).
Si rappresenti l’albero di derivazione SLD relativo al goal:
?- reversible(6=X+2).
e si dica qual è la risposta calcolata.
Standard Backtracking in Prolog
(16 Maggio 2002)
•
•
•
•
•
Si abbia il seguente problema di colorazione di una mappa, con 4 regioni da
colorare con 3 colori (individuati dai primi tre numeri naturali, 1, 2 e 3)
Il problema sia modellato in Prolog dai seguenti fatti:
domain([1,2,3]). %colori disponibili
adiac(1,2). %regione 1 e 2 adiacenti
1
2
adiac(1,3). %regione 1 e 3 adiacenti
adiac(2,3). %
...
3
4
adiac(2,4).
adiac(3,4).
e sia data la seguente nozione di incompatibilità tra coppie di variabili e
corrispondenti valori per il problema in esame:
noattack(V1,V2,C1,C2):(adiac(V1,V2); adiac(V2,V1)),!, C1\==C2.
noattack(V1,V2,_,_):- not adiac(V1,V2).
Si realizzi un programma Prolog che generi la soluzione applicando la
tecnica di standard backtracking. In particolare, si realizzi un predicato,
invocato come segue:
?-solution([r(1,C1), r(2,C2), r(3,C3), r(4,C4)])
in grado di istanziare i colori (C1, C2, ...) per le quattro regioni.
Soluzione
solution(L):domain(D),
map(L,[],D).
map([], Placed, _).
map([r(X,Cx)|Xs], Placed, D):member(Cx, D),
noattack_placed(r(X,Cx),Placed),
map(Xs,[ r(X,Cx)|Placed],D).
noattack_placed(r(X,Cx),[]):-!.
noattack_placed(r(X,Cx),[r(Y,Cy)|RestPlaced]):noattack(X,Y,Cx,Cy).