Dichiarativo: si concentra sulla descrizione del problema.

Paradigmi di programmazione Imperativo: orientato alla soluzione algoritmica del problema

(Assembler, C, Pascal, Ada, ...)

Dichiarativo: si concentra sulla descrizione del problema.

Il programmatore specifica che cosa si deve calcolare, piuttosto che “come” calcolare;

descrive il problema, le relazioni e concetti in esso coinvolti, non il modo dettagliato in cui il problema va risolto.

Funzionale: il programma definisce funzioni Logico: il programma definisce relazioni

PROLOG: PROgramming in LOGic

Linguaggio usato per risolvere problemi che coinvolgono oggetti e relazioni tra oggetti.

Programmare in Prolog consiste nel

• dichiarare fatti su oggetti e relazioni

• definire regole su oggetti e relazioni

• fare domande su oggetti e relazioni

Fatti e regole costituiscono il programma logico.

Programma logico

Un programma logico `e costituito da un insieme di clausole definite: disgiunzioni di letterali con uno ed un unico letterale positivo

P ∨ ¬Q ¹ ∨ ¬Q ² ∨ ... ∨ ¬Q _n (con n ≥ 0, e P, Q ¹ , ..., Q n atomiche).

Se n = 0, allora la clausola `e un fatto.

Altrimenti, la clausola si pu`o riscrivere nella forma equivalente:

(Q ¹ ∧ Q ² ∧ ... ∧ Q _n →P ) (P ← Q ¹ ∧ Q ² ∧ ... ∧ Q _n ) P :- Q1, Q2, ..., Qn.

regola

P: testa della regola Q1, Q2, ..., Qn: corpo della regola Il segno :- `e un “se” (←). La virgola `e un ∧.

Un insieme di clausole definite (un programma logico) ` e sempre soddisfa-

cibile.

Goal

Un goal `e una clausola negativa: tutti i letterali sono negativi:

¬Q ¹ ∨ ¬Q ² ∨ ... ∨ ¬Q _n che equivale a

¬(Q ¹ ∧ Q ² ∧ ... ∧ Q _n )

?- Q1, Q2, ..., Qn.

goal Questa clausola corrisponde alla formula

∀x ¹ ...∀x _k ¬(Q ¹ ∧ Q ² ∧ ... ∧ Q _n ) che equivale a

¬∃x ¹ ...∃x k (Q ¹ ∧ Q ² ∧ ... ∧ Q _n ) Questa formula corrisponde alla negazione della “query”.

Quindi il goal ?- Q1, Q2, ..., Qn. corrisponde alla query

∃x ¹ ...∃x _k (Q ¹ ∧ Q ² ∧ ... ∧ Q _n )

Le variabili nel goal hanno lettura “esistenziale”, la virgola `e un “AND”.

Esecuzione del programma logico P con goal G: la query corrispondente a G `e derivabile

dall’insieme di formule corrispondenti a P ?

Programmazione logica Supponiamo di avere la seguente base di conoscenza (KB):

{padre(aldo, piero), padre(piero, ugo),

∀x∀y(∃z(padre(x, z) ∧ padre(z, y))→nonno(x, y))}

Verificare se da KB `e derivabile ∃x nonno(x, ugo) equivale a verificare se KB∪{¬∃x nonno(x, ugo)}

`e insoddisfacibile.

Il programma logico P corrispondente a KB `e la forma a clausole di KB:

padre(aldo, piero) padre(piero, ugo)

nonno(x, y) ∨ ¬padre(x, z) ∨ ¬padre(z, y)

padre(aldo,piero).

padre(piero,ugo).

nonno(X,Y) :- padre(X,Z), padre(Z,Y).

Verificare se da P `e derivabile ∃x nonno(x, ugo) si riduce a derivare 2 (clausola vuota) da P ∪ {?- nonno(X, ugo)}.

Risoluzione SLD con la regola di calcolo “scelta del primo atomo”:

?- n(X, ugo) n(X ¹ , Y ) :- p(X ¹ , Z), p(Z, Y )

?- p(X, Z), p(Z, ugo) p(aldo, piero)

?- p(piero, ugo) p(piero, ugo) 2

Quindi KB |= ∃x nonno(x, ugo)

Programmazione logica per rispondere a domande ASK Domande ASK hanno spesso la forma “quale x `e tale che ...?”

Un programma serve per calcolare dei valori e non solo per rispondere SI o NO.

Informazioni utili si possono estrarre dalle sostituzioni applicate nella refutazione SLD.

Le sostituzioni applicate nella derivazione data sopra sono:

θ ⁰ = {X/X ¹ , ugo/Y } θ ¹ = {aldo/X, piero/Z}

θ ² = ∅

La loro composizione `e:

θ = θ ⁰ ◦ θ ¹ ◦ θ ² = {aldo/X, ugo/Y, piero/Z}

Non solo P |= ∃x nonno(x, ugo), ma anche

P |= nonno(X, ugo)θ cio`e P |= nonno(aldo, ugo)

Quindi la composizione delle sostituzioni utilizzate nella SLD-refutazione fornisce una ri- sposta alla domanda: “chi `e un nonno di ugo?”

Sostituzione di risposta (answer substitution): restrizione di θ ⁰ ◦ θ ¹ ◦ ... ◦ θ _n alle variabili del goal.

Una esecuzione in programmazione logica consiste nel tentativo di dimostrare che esi-

ste un’istanza della query che segue logicamente dal programma, e, se esiste, calcolare la

sostituzione di risposta data dalla dimostrazione.

PROGRAMMAZIONE = LOGICA + CONTROLLO

• Un programma PROLOG `e una rappresentazione logica del problema

• Il problema viene risolto dal motore di inferenza del PROLOG, basato sulla riso- luzione SLD, con strategia di ricerca in profondit` a.

Importanti meccanismi di base:

– unificazione (che differenza c’`e tra unificazione e pattern matching?) – procedimento di ricerca mediante backtracking

PROLOG utilizzato soprattutto in Intelligenza Artificiale

• sistemi esperti e, in generale, sistemi basati sulla conoscenza

• elaborazione del linguaggio naturale

• pianificazione automatica

Facilit`a di “rapid prototyping”

Semantica dichiarativa e semantica procedurale

La chiave della programmazione logica `e il fatto che una “regola” si pu`o leggere in due modi:

nonno(X,Y) :- padre(X,Z), padre(Z,Y).

• lettura dichiarativa (“che cosa”):

per ogni X e Y,

se esiste Z tale che X `e padre di Z e Z `e padre di Y, allora X `e nonno di Y

∀X∀Y ∀Z(padre(X, Z) ∧ padre(Z, Y )→nonno(X, Y )) Programma = specifica del problema

• lettura procedurale (“come”):

per risolvere il problema nonno(X,Y), si trovi Z che risolve il problema padre(X,Z)

e risolvere poi il problema padre(Z,Y)

L’insieme delle clausole che definiscono un predicato P costituiscono la definizione della procedura P

Il Prolog puro consente sia la lettura dichiarativa che quella procedurale di un programma

Osservazione sulla lettura delle regole nonno(X,Y) :- padre(X,Z), padre(Z,Y).

`e la sintassi Prolog per la clausola

nonno(x, y) ∨ ¬padre(x, z) ∨ ¬padre(z, y) Questa clausola corrisponde alla formula

∀x∀y∀z(padre(x, z) ∧ padre(z, y)→nonno(x, y)) Dato che z non occorre nel conseguente, la formula equivale a

∀x∀y(∃z(padre(x, z) ∧ padre(z, y))→nonno(x, y)) In una regola della forma

testa :- corpo.

• le variabili nella testa hanno un significato “universale” (su tutta la clausola);

• le variabili in corpo che non occorrono in testa hanno un significato “esistenziale”

all’interno del corpo.

PROLOG: rappresenta oggetti e relazioni vicino(c,c1).

vicino(c,c2).

colore(c1,blu).

colore(c2,rosso).

colore(X,Y) :- vicino(X,Z), colore(Z,Y).

colore `e una relazione: un oggetto pu`o avere pi`u colori.

?- colore(c,X).

ha pi`u di una “soluzione”

REVERSIBILIT ` A dei predicati: una stessa “procedura” pu`o essere invocata con diversi parametri di input/output

?- colore(c,X).

?- colore(X,rosso).

?- colore(X,Y).

Fatti, regole, procedure Fatti

genitore(pam,bob).

genitore(tom,bob).

genitore(tom,liz).

genitore(bob,ann).

genitore(bob,pat).

genitore(pat,jim).

Regole

figlio(X,Y) :- genitore(Y,X).

madre(X,Y) :- genitore(X,Y), femmina(X).

nonno(X,Y) :- genitore(X,Z), genitore(Z,Y).

Procedure: insiemi di fatti e regole

antenato(X,Y) :- genitore(X,Y).

antenato(X,Y) :- genitore(X,Z), antenato(Z,Y).

Le clausole (fatti e regole) di una procedura rappresentano modi alternativi di risolvere

problemi della stessa forma (antenato).

Ricerca in profondit` a genitore(pam,bob).

genitore(tom,bob).

genitore(tom,liz).

genitore(bob,ann).

genitore(bob,pat).

genitore(pat,jim).

antenato(X,Y) :- genitore(X,Y).

antenato(X,Y) :- genitore(X,Z), antenato(Z,Y).

?- antenato(bob,jim).

a(bob,jim)

g(bob,jim) NO

g(bob,Z), a(Z,jim)

Z=ann a(Z,jim) g(Z,jim)

NO

g(Z,Z ¹ ), a(Z ¹ ,jim) NO

Z=pat a(Z,jim) g(Z,jim)

YES

g(Z,Z ¹ ), a(Z ¹ ,jim)

Trace 1 ?- [bratko1].

% bratko1 compiled 0.00 sec, 3,336 bytes Yes

2 ?- trace.

Yes

[trace] 2 ?- antenato(bob,jim).

Call: (6) antenato(bob, jim) ? Call: (7) genitore(bob, jim) ? Fail: (7) genitore(bob, jim) ? Redo: (6) antenato(bob, jim) ? Call: (7) genitore(bob, _G466) ? Exit: (7) genitore(bob, ann) ? Call: (7) antenato(ann, jim) ? Call: (8) genitore(ann, jim) ? Fail: (8) genitore(ann, jim) ? Redo: (7) antenato(ann, jim) ? Call: (8) genitore(ann, _G466) ?

Redo: (7) genitore(bob, _G466) ?

Exit: (7) genitore(bob, pat) ?

Call: (7) antenato(pat, jim) ?

Call: (8) genitore(pat, jim) ?

Exit: (8) genitore(pat, jim) ?

Exit: (7) antenato(pat, jim) ?

Exit: (6) antenato(bob, jim) ?

Yes

Il backtracking Ogni sottogoal ha il proprio “puntatore” al programma likes(mary,food). /* 1 */

likes(mary,wine). /* 2 */

likes(john,beer). /* 3 */

likes(john,wine). /* 4 */

likes(john,mary). /* 5 */

?- likes(mary,X), likes(john,X).

• Goal 1: likes(mary,X): X=food.

Puntatore alla prossima clausola: 2 Goal 2: likes(john,X) con X=food.

Fallimento dopo aver scandito tutta la procedura

• Tentativo di risoddisfare Goal 1, a partire dalla clausola 2: X=wine

Goal 2 con X=wine (scansione della procedura dall’inizio): successo

Ricerca in profondit` a

La scelta di una strategia di ricerca pu` o compromettere la completezza del sistema:

Ricerca in profondit` a: si pu`o espandere un cammino infinito e non trovare mai una soluzione

Riordino delle clausole nel programma o degli atomi nel corpo delle regole:

il significato dichiarativo non cambia, ma pu`o cambiare il significato procedurale.

Riordino delle clausole nel programma

vicino(c,c1).

vicino(X,Y) :- vicino(Y,X).

?- vicino(c1,c).

Yes

vicino(X,Y) :- vicino(Y,X).

vicino(c,c1).

?- vicino(c1,c).

ERROR: Out of local stack

Riordino dei goal nel corpo delle regole

pam bob

pat

ann

jim

tom liz

/* Prima variante */

antenato(X,Y) :- genitore(X,Y).

antenato(X,Y) :- genitore(X,Z), antenato(Z,Y).

?- antenato(bob,jim).

Yes

?- antenato(liz,bob).

No

/* riordino dei goal nel corpo della regola */

antenato(X,Y) :- genitore(X,Y).

antenato(X,Y) :- antenato(Z,Y), genitore(X,Z).

?- antenato(bob,jim).

Yes

?- antenato(liz,bob).

ERROR: Out of local stack

Il goal non ` e derivabile dal programma, ma il meccanismo di ricerca non termina antenato(X,Y) :- genitore(X,Y).

antenato(X,Y) :- antenato(Z,Y), genitore(X,Z).

?- antenato(liz,bob).

(liz non `e genitore di nessuno) a(liz,bob)

g(liz,bob) NO

a(Z,bob), g(liz,Z)

g(Z,bob), g(liz,Z) ...

NO

a(Z ¹ ,bob), g(Z,Z ¹ ), g(liz,Z)

g(Z ¹ ,bob), g(Z,Z ¹ ), g(liz,Z)

...

NO

a(Z ² ,bob), g(Z ¹ ,Z ² ), g(Z,Z ¹ ), g(liz,Z)

...

Riordino delle clausole e dei goal

pam bob

pat

ann

jim

tom liz

antenato(X,Y) :- antenato(Z,Y), genitore(X,Z).

antenato(X,Y) :- genitore(X,Y).

?- antenato(bob,jim).

ERROR: Out of local stack Goal derivabile ma la ricerca non termina

?- antenato(liz,bob).

ERROR: Out of local stack

Goal non derivabile e la ricerca non termina

Regole di programmazione

1. In una procedura, prima i fatti poi le regole (prima le cose pi`u semplici, poi quelle pi`u complicate)

2. Nel corpo di una regola, prima i goal pi`u semplici da dimostrare o refutare, poi quelli

pi`u difficili

Il Prolog ` e corretto?

Il predicato predefinito = controlla se due termini sono unificabili:

Term ¹ = Term ² unifica Term ¹ con Term ² . Ha successo se l’unificazione ha successo

?- f(X,pippo) = f(pluto,Y).

X = pluto Y = pippo Yes

Ma attenzione:

?- X = f(X).

X = f(f(f(f(f(f(f(f(f(f(...)))))))))) Yes

?- unify_with_occurs_check(X,f(X)).

No

L’unificazione utilizzata dal motore di inferenza non esegue l’occur check

figlio(X,padre(X)).

?- figlio(pippo,Y).

Y = padre(pippo) Yes

?- figlio(Y,Y).

X = padre(padre(padre(padre(padre(padre(padre(padre(padre(padre(...))))))))))

Yes