Definire operatori. Strutture dati

Definire operatori
Strutture dati
Fabio Massimo Zanzotto
(slides di Andrea Turbati)
University of Rome “Tor Vergata”
Strutture dati
• Le strutture dati, anche complesse, sono alla base
dei vari linguaggi di programmazione
• In Prolog è possibile creare ed utilizzarle in modo
palese
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Strutture dati
• Un database può essere rappresentato in Prolog
come un elenco di fatti
• Per comprendere come creare/usare le strutture
dati in Prolog useremo i seguenti esempi:
– Famiglia
– Automa non deterministico
– Problema delle 8 Regine
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Famiglia
• Una famiglia può essere rappresentata da un fatto,
family, con 3 argomenti:
– Padre
– Madre
– Figli (tramite una lista)
• Gli elementi della famiglia sono delle persone
(person), rappresentati a sua volta da dei termini
complessi formati da 4 elementi: nome, cognome,
data di nascita e salario
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Famiglia
• Rappresentazione della famiglia Smith
• family(
person(bob, smith, date(7, may,1968),30000),
person(ann, smith, date(18, july,1970),32000),
[person(dave, smith, date(1, june,1984),0),
person(edna, smith, date(25, may,1990),0)]).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Famiglia
• Possiamo effettuare varie query, basandoci non
solo sui valori ma anche sulla struttura stessa
• family(person(_,fox, _, _), _, _). si riferisce alla
famiglia fox, usando solo il cognome del padre e
nessun altra informazione
• Esiste un altro modo per riferirsi alla famiglia fox?
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Famiglia
• family(_, _, [_,_,_]). Indica una famiglia con 3
figli
• Come si può indicare una famiglia con almeno 3
figli ?
• Creiamo ora delle regole più “generiche” che però
si appoggiano sempre al termine family
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Regole per family
husband(X):family(X, _, _).
wife(X):family(_, X, _).
child(X):family(_, _, Children),
member(X, Children).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Regole per family
exists(X):husband(X)
;
wife(X)
;
child(X).
salary(person(_, _, _, S), S).
dateOfBirth(person(_, _, Date, _),Date).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Possibili query
• ?- exists(person(mario, rossi, _, _)).
• ?- exists(person(Name, Surname, _, _)).
• ?- child(X),
dateOfBirth(X, date(_,_,Y)),
Y < 2000.
• ?- exists(X),
salary(X, Y),
Y >30000.
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Automa non deterministico
b
s1
a
s2
a
null
b
null
s4
© A.Turbati, F.M.Zanzotto
b
s3
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Automa non deterministico
final(s3).
trans(s1, a, s1).
trans(s1, a, s2).
trans(s1, b, s1).
trans(s2, b, s3).
trans(s3, b, s2).
trans(s1, a, s4).
silent(s2, s4).
silent(s3, s1).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Automa non deterministico
accepts(State, []):final(State).
accepts(State, [X|Rest]):trans(State, X, State1),
accepts(State1, Rest).
accepts(State, Rest):silent(State, State1),
accepts(State1, Rest).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Query Automa
• ?- accepts(s1, [a,a,a,b]).
– true
• ?- accepts(S, [a,b]).
– S=s1;
– S=s3;
• ?- accepts(s1, [X1,X2,X3]).
– X1=a X2=a
– …
X3=b
• ?- String=[_,_,_], accepts(s1, String).
– String = [a,a,b];
– …
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Problema delle 8 Regine
• Posizionare 8 regine su di una scacchiera vuota in
modo che nessuna possa mangiare o essere
mangiata da un’altra
• Esistono varie soluzione in Prolog, qui ne viene
presentata una semplice con il minimo numero di
variabili
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
8 Regine
solution( [] ).
solution( [X/Y | Others] ) :- % First queen at X/Y, other queens at Others
solution( Others),
member( Y, [1,2,3,4,5,6,7,8] ),
noattack( X/Y, Others).
% First queen does not attack others
noattack( _, [] ).
% Nothing to attack
noattack( X/Y, [X1/Y1 | Others] ) :Y =\= Y1,
% Different Y-coordinates
Y1-Y =\= X1-X,
% Different diagonals
Y1-Y =\= X-X1,
noattack( X/Y, Others).
% A solution template
template( [1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8] ).
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizi
• Famiglia:
– Scrivere la regola per avere le famiglie senza figli
– Scrivere la regola per avere Il reddito totale di una
famiglia
– Scrivere la regola per avere le famiglie in cui i figli
guadagnano più dei genitori
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizi
• Automa:
– Scrivere una regola che accetti lo stato iniziale e due
numeri che rappresentino il numero minimo e massimo
di transizioni (non nulle) che si possono fare. Tale
regola dovrà accettare anche una variabile che conterrà
la lista dei simboli di input usati per andare dallo stato
iniziare a quello finale
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizi
• 8 Regine:
– Modificare il programma per trattare un numero
variabile di regine
– Scrivere una nuova versione della soluzione al
problema delle 8 regine
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Operatori
• In Prolog è possibile definire nuovi operatori, ma
ne esistono già alcuni definiti (esempio gli
operatori aritmetici)
• 1*2+3*4 ha i due operatori + e *
• la scrittura in Prolog sarebbe:
– +(*(1,2), *(3,4))
+
*
1
© A.Turbati, F.M.Zanzotto
*
2
Logica per la Programmazione e la Dimostrazione Automatica
3
4
University of Rome “Tor Vergata”
Definire un operatore
• Ogni operatore ha una sua priorità
• a + b*c come deve essere letto?
– +(a, *(b,c) ?
– *( +(a,b), c) ?
• Nel senso comune trasmessoci, * lega di più di +,
*
+
a
b
© A.Turbati, F.M.Zanzotto
+
*
c
a
c
b
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Definire un operatore
Codificare la priorità: l’albero delle interpretazioni
ha priorità decrescenti
+ ha priorità 500
* ha priorità 400
(e quindi + ha priorità più alta di *)
a + b*c
*
+
a
b
© A.Turbati, F.M.Zanzotto
+
*
c
a
c
b
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Definire un operatore
• :- op(Priorità, Tipo, Operatore).
• Priorità è un numero tra 0 e 1200
• Tipo:
– infisso : xfx, xfy, yfx
– prefisso: fx, fy
– postfisso: xf, fy
• Operatore: il nome/simbolo dell’operatore
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Definire un operatore
• Il tipo serve ad indicare anche la precedenza degli
operatori:
– x : la sua priorità deve essere minore di quella
dell’operatore
– y: la sua priorità deve essere minore o uguale a quella
dell’operatore
• :- op(700, yfx, somma).
• Qual è l’albero risultante di
– 9 somma 5 somma 7 ?
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Definire un operatore
• :- op(700, yfx, somma).
• 9 somma 5 somma 7
somma
somm
a
a
somm
a
c
b
b
• Quello a sinistra è corretto, perché?
© A.Turbati, F.M.Zanzotto
somma
a
Logica per la Programmazione e la Dimostrazione Automatica
c
University of Rome “Tor Vergata”
Esercizio
Studiamo la sintassi della lingua
Realizziamo gli operatori «ha» e «di», di modo che
con frasi:
• mario ha la macchina di dario
• giovanni ha il cestino di mario
Risponda a interrogazioni come
Chi ha Cosa di X
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizio
• Definire la regola max(A, B, Max) in modo che in
Max ci vada il massimo tra A e B
• Pensare anche al caso:
– max(A, 5, 9)
– A = 9.
© A.Turbati, F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica