Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

27
Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto

Transcript of Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

Page 1: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

Esecuzione dei programmi PrologListe ed operatori aritmetici

Fabio Massimo Zanzotto

Page 2: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

Algoritmo di Risoluzione

… by examples

edge(a,b).

edge(b,c).

edge(a,e).

edge(c,d).

edge(d,e).

edge(f,e).

path(X,Y):- edge(X,Y).

path(X,Y):- path(X,Z),path(Z,Y).

path(a,d).?-

edge(a,d).

X=a,Y=d

fail

X=a,Y=d

path(a,Z),path(Z,d).

edge(a,Z),path(Z,d).

edge(a,b),path(b,d).

edge(a,b),path(b,Z),path(Z,d).

edge(a,b),edge(b,c),path(c,d).

edge(a,b),edge(b,c),edge(c,d). Success!

Page 3: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• Analizza i fatti/regole dall’alto verso il basso (quindi è importante l’ordine con cui vengono scritti)

• Utilizzo del BACKTRACKING per tornare indietro a prima che una variabile fosse unificata o che una certa regola fosse esplorata

• Utilizzo della ricorsione per chiamare le altre regole

• Per avere altre risposte, e quindi forzare il backtracking anche se il programma ne ha già trovata una che funziona, basta premere ;

Esecuzione programma

Page 4: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

«Letture» dei programmi Prolog

• Il mondo dei se può essere letto in maniera:

– Dichiarativa

I problemi sono risolubili attraverso la scrittura di un insieme di regole – Procedurale

I problemi sono risolubili attraverso la scrittura sequenze di istruzioni

Page 5: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

«Lettura» Dichiarativa del Prolog

È la lettura classica (e più corretta):• Una clausola con variabili come

grandparent(X,Y):-

parent(X,Z),

parent(Z,Y).• viene letta:Per ogni X e Y e Z,

grandparent(X,Y) è vero se

parent(X,Z) è vero e

parent(Z,Y) è vero

Page 6: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

«Lettura» Dichiarativa del Prolog

È la lettura classica (e più corretta):

Una query come:

?- grandparent(X,mario).

viene letta come:

esiste un X che tale che grandparent(X,mario) è vero?

Page 7: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

«Lettura» Procedurale del Prolog

È una lettura necessaria:• Una clausola con variabili come

grandparent(X,Y):-

parent(X,Z),

parent(Z,Y).• Può essere anche letta:Per qualsiasi valore delle variabili X e Y e Z,

per soddisfare il goal grandparent(X,Y) soddisfa prima il goal parent(X,Z) e poi il parent(Z,Y).

ATTENZIONE: le variabili NON variano valore durante il soddisfamento del goal

Page 8: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

«Lettura» Procedurale del Prolog

È una lettura necessaria:

Una query come:

?- grandparent(X,mario).

viene letta come:

Soddisfare il goal grandparent(X,mario) trovando il valore della variabile X?

Page 9: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

Osservazioni

• Importanza dell’ordine delle clausole e nelle clausole.

path(X,Y):- path(X,Z),path(Z,Y).

path(X,Y):- edge(X,Y).

Genera un loop infinito!!!

Page 10: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• In Prolog le liste sono molto utilizzate

• Lista: sequenza di vari elementi (anche ripetuti), che possono essere a loro volta delle liste

• Es: [primo, secondo, [primo2, secondo2]].– Lista composta da tre elementi– Il terzo elemento è a sa volta una lista

• La lista può essere vuota (caso molto importante e utilizzato)

Liste

Page 11: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• Ogni lista è composta da due parti:– Head: è il primo elemento– Tail: è il resto della lista (a sua volta una lista)

• Le liste possono essere rappresentati in due modi:– [a,b,c,d]– .(a, .(b, .(c, .(d, []))))

Liste

Page 12: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• Per estrarre la Testa di una lista si usa la notazione:– [H | T ], dove H è la testa e T è la lista rimanente senza

il primo elemento

• Si possono estrarre più elementi contemporaneamente:– [H1, H2 | T]– H1 e H2 sono il primo e il secondo elemento– T è la lista rimanente (la lista di partenza meno i primi

due elementi)

Liste

Page 13: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• member(?Elem, ?List)– Restituisce true se Elem si trova nella lista, può essere

usato in vari modi:• member(b, [a, b, c, d]). -> true• member(e, [a, b, c, d]). -> false• member(X,[a, b, c, d]). -> X = a ; X=b ; … • member(c, [a, b, X, d]). -> X = c

Operatori su liste

Page 14: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• member(?Elem, ?List)

• possibile implementazione:member2(X, [X|_]).

member2(X,[_|T]):-

member2(X,T).

Operatori su liste

Page 15: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• append(?List1, ?List2, ?List1AndList2) – List1AndList2 è la concatenazione di List1 e List2. Vari

utilizzi• append([a,b],[c,d], X). -> X = [a,b,c,d]• append([a,b],X, [a,b,c,d]). -> X = [c,d]• append([a,b],[X,d], [a,b,c,d]). -> X = c• append(X, Y, [a,b,c,d]).

Operatori su liste

Page 16: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• Scrivere una possibile implementazione della append

• Scrivere la regola per invertire tutti gli elementi di una lista, in modo da avere:

?- inverti([a,b,c,d,e,f], X).

X=[f,e,d,c,b,a]

Esercizio

Page 17: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• 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

*

+

*

Page 18: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• Ogni operatore ha una sua priorità• a + b*c come deve essere letto?

– +(a, *(b,c) ?– *( +(a,b), c) ?

• In matematica * lega di più di +, e quindi + ha priorità più alta di *

Definire un operatore

b c

*

+

a

a b

c

*

+

Page 19: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

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

Definire un operatore

Page 20: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

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

Definire un operatore

Page 21: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

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

• Quello a sinistra è corretto, perché?

Definire un operatore

a b

c

somma

somma

b c

somma

somma

a

Page 22: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• Prolog può essere usato anche per fare dei calcoli, con alcune limitazioni

• Come detto gli operatori aritmetici sono già definiti

• A = B + C assegna ad A non il risultato della somma ma assegna proprio B + C

• per eseguire l’operazione bisogna usare is

Aritmentica

Page 23: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• A is 5 + 6 fa sì che in A venga messo il valore 11

• B is 8 + 2 * 3 mette in B 14 (rispetta la priorità)

• A destra di is non possono esserci variabile non ancora istanziate

Aritmetica

Page 24: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• A = 3 , B is A + 4.– A = 3 e B = 7

• A = 3, B = A + C.– A = 3 e B = 3+C

• A = 3, B is A+C, C=4.– ERROR: is/2: Arguments are not sufficiently

instantiated

Aritmetica

Page 25: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• Gli operatori direttamente utilizzabili sono:– +– -– *– /– ** (elevamento a potenza)– // (divisione intera)– mod (modulo, resto della divisione)– <, >, >=, =<, =, \= (sono confronti booleani utili come

predicati, ma non utilizzabili a sinistra di is)– number(X) (vero se X è un numero, falso negli altri casi)

Operatori per i calcoli

Page 26: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• Vedere il file prolog-2.pl per avere un esempio di regole che usano gli operatori per i calcoli

• calcola(X + Y, Z):-

Z is X+Y.

– calcola(5+8,Y).– Y = 13– calcola(5+8+2,X).– X = 15

Esempio

Page 27: Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

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

University of Rome “Tor Vergata”

• Implementare l’operatore div in modo tale che– A is 12 div 6 div 2– A = 4

• 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