Esecuzione dei programmi PrologListe 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!

© 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

© 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

© 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

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

© 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

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

© 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!!!

© 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

© 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

© 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

© 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

© 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

© 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

© 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

© 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

*

+

*

© 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

*

+

© 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

© 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

© 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

© 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

© 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

© 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

© 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

© 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

© 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