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