Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)

Definire operatoriStrutture dati

Fabio Massimo Zanzotto

(slides di Andrea Turbati)

© A.Turbati, F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica

University of Rome “Tor Vergata”

• Le strutture dati, anche complesse, sono alla base dei vari linguaggi di programmazione

• In Prolog è possibile creare ed utilizzarle in modo palese

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

Strutture dati



• 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

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)]).

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?

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

Famiglia



husband(X):-

family(X, _, _).

wife(X):-

family(_, X, _).

child(X):-

family(_, _, Children),

member(X, Children).

Regole per family



exists(X):-

husband(X)

;

wife(X)

;

child(X).

salary(person(_, _, _, S), S).

dateOfBirth(person(_, _, Date, _),Date).

Regole per family



• ?- exists(person(mario, rossi, _, _)).

• ?- exists(person(Name, Surname, _, _)).

• ?- child(X),

dateOfBirth(X, date(_,_,Y)),

Y < 2000.

• ?- exists(X),

salary(X, Y),

Y >30000.

Possibili query



Automa non deterministico

s4

s1

s3

s2

b

b

null

a null

a

b



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).




accepts(State, []):-

final(State).

accepts(State, [X|Rest]):-

trans(State, X, State1),

accepts(State1, Rest).

accepts(State, Rest):-

silent(State, State1),

accepts(State1, Rest).




• ?- 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];– …

Query Automa



• 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

Problema delle 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] ).

8 Regine



• 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

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

Esercizi



• 8 Regine:

– Modificare il programma per trattare un numero variabile di regine

– Scrivere una nuova versione della soluzione al problema delle 8 regine

Esercizi



• 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))

Operatori

1 2 3 4

*

+

*



• 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 +,

Definire un operatore

b c

*

+

a

a b

c

*

+




Codificare la priorità: l’albero delle interpretazioni ha priorità decrescenti

+ ha priorità 500

* ha priorità 400

(e quindi + ha priorità più alta di *)

b c

*

+

a

a b

c

*

+

a + b*c



• :- 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




• 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 ?




• :- op(700, yfx, somma).• 9 somma 5 somma 7

• Quello a sinistra è corretto, perché?


a b

c

somma

somma

b c

somma

somma

a



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



• 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.

Esercizio

Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)

Documents

Transcript of Definire operatori Strutture dati Fabio Massimo Zanzotto (slides di Andrea Turbati)