Esempi di Programmazione in Prolog

Esempio 1: Albero genealogico

 Il seguente programma e' composto da un database che definisce le relazioni di padre e madre (notare che la linea di dicendenza e' maschile), e da clausole che definiscono le relazioni di genitore, antenato, fratello_sorella (cioe': fratello o sorella), fratellastro_sorellastra(X,Y), e zio_zia(X,Y).

Programma:

padre(pippo,gino).
padre(luca,pippo).
padre(francesco,luca).
padre(pippo,manuela).
padre(luca,genoveffa).
padre(luca,giuseppina).

madre(giulia,gino).
madre(lina,pippo).
madre(gelda,luca).
madre(giulia,manuela).
madre(lina,genoveffa).
madre(franca,giuseppina).

genitore(X,Y) :- padre(X,Y).
genitore(X,Y) :- madre(X,Y).

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

fratello_sorella(X,Y) :-
padre(Z,X), padre(Z,Y), madre(W,X), madre(W,Y), X \= Y.
fratellastro_sorellastra(X,Y) :-
genitore(W,X), genitore(W,Y), X \= Y.
zio_zia(X,Y) :- genitore(Z,Y), fratello_sorella(X,Z).

Esempio di sessione:

Il Programma e' stato salvato in un file "Prog1.pl". Il seguente e' un esempio di sessione con l'interprete SWI-Prolog in cui si carica questo programma e si fanno delle query sulle relazioni madre, genitore, antenato, e fratello_sorella.

[cygnus:catuscia:~/Prolog:6] pl
Welcome to SWI-Prolog (Version 2.7.15)
Copyright (c) 1993-1996 University of Amsterdam. All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

1 ?- consult('Prog1').
Prog1 compiled, 0.01 sec, 2,772 bytes.

Yes
2 ?- madre(X,gino).
X = giulia ;

X = giulia ;

No
3 ?- madre(giulia,Y).

Y = gino ;

Y = manuela ;

No
4 ?- genitore(X,gino).

X = pippo ;

X = giulia ;

No
5 ?- antenato(X,gino).

X = pippo ;

X = giulia ;

X = luca ;

X = francesco ;

X = lina ;

X = gelda ;

No
6 ?- fratello_sorella(X,Y).

X = gino
Y = manuela ;

X = pippo
Y = genoveffa ;

X = manuela
Y = gino ;

X = genoveffa
Y = pippo ;

No
7 ?- halt.
[cygnus:catuscia:~/Prolog:7]

Esempio 2: Analogy

 /*
Programma ANALOGY

Date tre figure A, B e C,
analogy(A,B,C,X) restituisce la figura X
che sta a C come B sta ad A.
*/

/* Definizione del tipo di dato "figura" */

figura(cerchio).
figura(quadrato).
figura(triangolo).
figura(sopra(A,B)) :- figura(A), figura(B).
figura(dentro(A,B)) :- figura(A), figura(B).
figura(accanto(A,B)) :- figura(A), figura(B).

/*
Definizione del predicato principale "analogy".
L'idea e': trova la trasformazione T che permette
di trasformare A in B, ed applicala a C per ottenere X
*/
analogy(A,B,C,X) :-
trasforma(A,B,T), trasforma(C,X,T),
figura(A), figura(B), figura(C), figura(X).
/*
Tutta "l'intelligenza" del programma sta nella definizione
di questo predicato "trasforma".
L'idea e' quella di rappresentare la trasformazione come
un albero (ovvero un termine) in cui ad ogni nodo
sono associate le trasformazioni elementari che abbiamo
applicato nei vari punti della figura.
La definizione di "trasforma" dipende da che tipo di
trasformazioni elementari vogliamo.
Quella che diamo sotto considera come trasformazioni elementari:
l'identita' (ident : identity),
la inversione sopra-sotto, (invert_ab : invert above-below),
la inversione destra-sinista, (invert_lr : invert left-right),
la inversione dentro-fuori, (invert_io : invert inside-outside).
Queste trasformazioni saranno applicate ricorsivamente
anche ai vari pezzi delle figure.
Inoltre dovemo avere delle operazioni che in quel punto
non fanno niente, ma che permettono comunque di accedere
ai vari pezzi della figura e di trasformarli:
entra sopra e sotto, (go_ab : go above and below),
entra a destra e a sinista, (go_lr : go left and right),
entra dentro e fuori, (go_io : go inside and outside).
*/
trasforma(A,A,ident).

trasforma(sopra(A,B), sopra(C,D), invert_ab(T1,T2)) :-
trasforma(A,D,T1), trasforma(B,C,T2).


trasforma(sopra(A,B), sopra(C,D), go_ab(T1,T2)) :-
trasforma(A,C,T1), trasforma(B,D,T2).


trasforma(dentro(A,B), dentro(C,D), invert_io(T1,T2)) :-
trasforma(A,D,T1), trasforma(B,C,T2).


trasforma(dentro(A,B), dentro(C,D), go_io(T1,T2)) :-
trasforma(A,C,T1), trasforma(B,D,T2).


trasforma(accanto(A,B), accanto(C,D), invert_lr(T1,T2)) :-
trasforma(A,D,T1), trasforma(B,C,T2).


trasforma(accanto(A,B), accanto(C,D), go_lr(T1,T2)) :-
trasforma(A,C,T1), trasforma(B,D,T2).

Esempio di sessione:

Il Programma e' stato salvato in un file "Prog2.pl"

[cygnus:catuscia:~/Prolog:13] pl
Welcome to SWI-Prolog (Version 2.7.15)
Copyright (c) 1993-1996 University of Amsterdam. All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

1 ?- consult('Prog2').
Prog2 compiled, 0.01 sec, 3,200 bytes.

Yes
2 ?- analogy(sopra(cerchio,dentro(triangolo,quadrato)),
| sopra(dentro(quadrato,triangolo),cerchio),
| sopra(triangolo,dentro(cerchio,quadrato)),
| X).

X = sopra(dentro(quadrato, cerchio), triangolo) ;

No
3 ?- analogy(sopra(cerchio,dentro(triangolo,quadrato)),
| sopra(dentro(quadrato,triangolo),cerchio),
| X, Y).

X = sopra(cerchio, dentro(cerchio, cerchio))
Y = sopra(dentro(cerchio, cerchio), cerchio) ;

X = sopra(cerchio, dentro(cerchio, quadrato))
Y = sopra(dentro(quadrato, cerchio), cerchio) ;

X = sopra(cerchio, dentro(cerchio, triangolo))
Y = sopra(dentro(triangolo, cerchio), cerchio) ;

X = sopra(cerchio, dentro(cerchio, sopra(cerchio, cerchio)))
Y = sopra(dentro(sopra(cerchio, cerchio), cerchio), cerchio) ;

X = sopra(cerchio, dentro(cerchio, sopra(cerchio, quadrato)))
Y = sopra(dentro(sopra(cerchio, quadrato), cerchio), cerchio) ;

X = sopra(cerchio, dentro(cerchio, sopra(cerchio, triangolo)))
Y = sopra(dentro(sopra(cerchio, triangolo), cerchio), cerchio) ;

X = sopra(cerchio, dentro(cerchio, sopra(cerchio, sopra(cerchio, cerchio))))
Y = sopra(dentro(sopra(cerchio, sopra(cerchio, cerchio)), cerchio), cerchio)

Yes
4 ?- halt.
[cygnus:catuscia:~/Prolog:14]

Esempio 3: N Queens

 /*
Programma N Queens

Dato un numero naturale N, queens(N,Q) restituisce una
possibile disposizione di N regine su una scacchiera
N*N, in modo che nessuna sia sotto lo scacco di un'altra.
La disposizione sara' rappresentata come una lista
Q = [q1,...,qN] di numeri dell'intervallo fra 1 e N
dove qi rappresenta il numero di riga della
regina della colonna i-esima.

Il predicato queens e' definito secondo il pincipio
del "generate and test": prima si genera una possibile
soluzione, poi si controlla se rispetta i vincoli.
In questo caso, prima si genera una permutazione
dei numeri dell'intervallo da 1 a N, poi si controlla che
corrisponda ad una disposizione "safe", cioe' senza scacchi
reciproci.
*/
queens(N,Q) :-
list_int(1,N,L), perm(L,Q), safe(Q).

/* list_int(M,N,L) genera la lista L di tutti i numeri fra 1 e N */
list_int(M,N,L) :-
M > N, L = [].
list_int(M,N,L) :-
M =< N, L = [M|L1], M1 is M+1, list_int(M1,N,L1).

/* perm(L1,L2) genera una permutazione L2 della lista L1 */
perm([],[]).
perm(L,[X|Q]) :-
append(L1,[X|L2],L), append(L1,L2,L3), perm(L3,Q).

/* safe(Q) controlla che la lista Q rappresenti una disposizione "safe" */
safe([]).
safe([X|Q]) :-
check_free(X,Q), safe(Q).

/* check_free(X,Q) controlla che la regina in posizione di riga X
non sia sotto lo scacco di nessuna regina della lista Q */
check_free(X,Q) :-
check_free_aus(1,X,Q).
check_free_aus(_,_,[]).
check_free_aus(N,X,[Y|Q]) :-
X =\= Y+N, X =\= Y-N, N1 is N+1, check_free_aus(N1,X,Q).

Esempio di sessione:

Il Programma e' stato salvato in un file "Prog3.pl"

[cygnus:catuscia:~/Prolog:11] pl
Welcome to SWI-Prolog (Version 2.7.15)
Copyright (c) 1993-1996 University of Amsterdam. All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

1 ?- consult('Prog3').
Prog3 compiled, 0.02 sec, 2,872 bytes.

Yes
2 ?- queens(3,Q).

No
3 ?- queens(4,Q).

Q = [2, 4, 1, 3] ;

Q = [3, 1, 4, 2] ;

No
4 ?- queens(5,Q).

Q = [1, 3, 5, 2, 4] ;

Q = [1, 4, 2, 5, 3] ;

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

Yes
5 ?- queens(6,Q).

Q = [2, 4, 6, 1, 3, 5]

Yes
6 ?- queens(7,Q).

Q = [1, 3, 5, 7, 2, 4, 6]

Yes
7 ?- queens(8,Q).

Q = [1, 5, 8, 6, 3, 7, 2, 4]

Yes
8 ?- halt.
[cygnus:catuscia:~/Prolog:12]

Esempio 4: Metainterprete per gerarchie isa

/* MetaInterprete per Teorie organizzate secondo una gerarchia isa
solve(G,T) risolve il goal G rispetto alla teoria T */

solve(true,_).
solve((G1,G2),T) :- solve(G1,T), solve(G2,T).
solve(solve(A,T),_) :- solve(A,T).
solve(A,T) :- isa_closure(T,T1), clause_in_th(A,B,T1), solve(B,T).


/* isa_closure e' la chiusura simmetrica e transitiva di isa */

isa_closure(T,T).
isa_closure(T1,T2) :- isa(T1,T), isa_closure(T,T2).


/* clause_in_th(A,B,T) verifica che la clausola A:-B appartenga alla teoria T.
Tale appartenenza si suppone che sara' rappresentata inserendo l'atomo
theory(T) come atomo piu' a sinistra nella clausola, cioe' scrivendo
la clausola come A :- (theory(T), B). */

clause_in_th(A,B,T) :- clause(A, (theory(T),B)).


/* Esempio di teorie organizzate secondo una gererchia isa */

isa(mammal,animal).
isa(bird,animal).
isa(human,mammal).
isa(dog,mammal).
isa(john,human).
isa(sally,human).
isa(fido,dog).

male :- (theory(fido), true).
male :- (theory(john), true).

female :- (theory(sally), true).

lactate :- (theory(mammal), female).

lay_eggs :- (theory(bird), female).

owner(sally) :- (theory(fido), true).

work_in(new_york) :- (theory(john), true).
work_in(philadelphia) :- (theory(sally), true).

live_in(X) :- (theory(human), work_in(X)).
live_in(X) :- (theory(dog), (owner(Y), solve(live_in(X), Y))).


Esempio di sessione:

Il Programma e' stato salvato in un file "Prog4.pl"

[cygnus:catuscia:~/Prolog:50] pl
Welcome to SWI-Prolog (Version 2.7.15)
Copyright (c) 1993-1996 University of Amsterdam. All rights reserved.

For help, use ?- help(Topic). or ?- apropos(Word).

1 ?- consult('Prog4').
Prog4 compiled, 0.02 sec, 3,872 bytes.

Yes
2 ?- solve(live_in(X),john).

X = new_york ;

No
3 ?- solve(live_in(X),fido).

X = philadelphia ;

No
4 ?- solve(lactate,T).

T = sally ;

No
5 ?- solve(male,T).

T = fido ;

T = john ;

No
6 ?- halt.
[cygnus:catuscia:~/Prolog:51]