Linguaggi di Programmazione (AA 2002/2003) Corso di Laurea in Informatica Introduzione al linguaggio...

Linguaggi di ProgrammazioneLinguaggi di Programmazione(AA 2002/2003)(AA 2002/2003)

Corso di Laurea in InformaticaCorso di Laurea in Informatica

Introduzione al linguaggio Prolog - parte 2Introduzione al linguaggio Prolog - parte 2

• Lavora su strutture ad ALBERO– anche i programmi sono strutture dati manipolabili– utilizzo della ricorsione e non assegnamento

• Metodologia di programmazione:– concentrarsi sulla specifica del problema rispetto alla strategia di soluzione

Un PROGRAMMA PROLOG e’ un insieme di clausole di Horn che rappresentano:

– FATTIFATTI riguardanti gli oggetti in esame e le relazioni che intercorrono– REGOLEREGOLE sugli oggetti e sulle relazioni

(SE…..ALLORA)– GOALGOAL (clausole senza testa), sulla base della

conoscenza definita

PrologProlog

Programmazione logica e Programmazione logica e PrologProlog

Clausole Clausole

m21n21

m21n21

m21n21

BBBAAA

BBBAA(A

:Morgan De di teoremail Usando

BBBAAA

:clausola unaPer

BA : B) se(A B da implicatoA oppure

AB a ecorrispondA B :neImplicazio

......

)...()...

......

.

.,...,,

.

.,...,,:

...

...

...

...

false ionecontraddiz

BB-B: goal

A fatto

BBBA regola

PROLOG Notazione

ionecontraddiz

BBB goal

A fatto

BBBA regola

:eparticolarIn

BBBA

BBBA

:positivo letterale soloun haHorn di clausola Una

m21

m21

m21

m21

m21

m21


clausole negative:

domanda X1Xn.B1 B2 Bm)

negazione per applicare la refutazione

~X1Xn.B1 B2 Bm)

X1Xn.B1 ~B2 ~Bm)B1 B2 Bm.

clausole definite:- regole AB1 B2 Bm.- fatti A.

clausole negative: (goalgoal)

B1 B2 Bm.


Un programma logicoprogramma logico:

sum(0,X,X).

sum(s(X),Y,s(Z)) :- sum(X,Y,Z).

Possiamo interpretare s(N) come il successore del numero N

allora 0, s(0), s(s(0)), s(s(s(0)))… rappresentano 0,1,2,3…

Questo programma definisce la somma fra due numeri naturali.


1 2 W W).s(0),),sum(s(s(0) -:

01 W . W),sum(s(0),0 -:

:sono negazioni Le

1 2 W W)s(0),),sum(s(s(0)W

01 W W),sum(s(0),0W

:Domande


Programmazione logica e Programmazione logica e PrologPrologESECUZIONE DI UN PROGRAMMA

• Una computazione corrisponde al tentativo di dimostrare, tramite la risoluzione, che una formula segue logicamente da un programma (e’un teorema).

• Inoltre, si deve determinare una sostituzione per le variabili del goal (detto anche “query”) per cui la query segue logicamente dal programma.

• Dato un programma P e la query: :- p(t1,t2,…,tm).se X1,X2,…,Xn sono le variabili che compaiono in t1,t2,…,tm il significato della query e’: X1, X2,…, Xn p(t1,t2,…,tm)e l’obiettivo e’ quello di trovare una sostituzione = {X1/s1,X2/s2,…,Xn/sn}dove si sono termini tale per cui P |= p(t1,t2,…,tm)]

Dato un insieme di clausole di Horn è possibile derivare la clausola vuota solo se c`è una sola clausola senza testa e tutte le altre clausole hanno la testa.

Quindi in un programma logico P tutte le clausole debbono avere la testa mentre la clausola goal Gla clausola goal G00. non avrà testa. non avrà testa.

Si deve dimostrare che da è possibile derivare la Si deve dimostrare che da è possibile derivare la clausola vuota.clausola vuota.

Come?

Se si tentassero ad ogni passo tutte le risoluzioni possibili e si aggiungessero le clausole inferite all’ insieme di partenza si avrebbe una esplosione combinatoria.

Si deve adottare una strategia di soluzione opportuna.

}{GP 0


Risoluzione ad input lineareRisoluzione ad input lineare

La risoluzione avviene sempre fra l’ultimo goal derivato in ciascun passo e una clausola di programma, mai fra due clausole di programma o fra una clausola di programma ed un goal derivato in precedenza.

Sia dato un programma logico P e un goal G0. Si deve dimostrare che da

è possibile derivare la clausola vuota.

}{GP 0


.,...,,,...,,:

][

.,...,,:

.,...,,

m2m211i

1

m21

m21i

AABBB G

goal nuovoun ottiene si

A[A] che tale eunificatorun esiste se

BBBA regola dalla e

AA-A: G goal dal

La risoluzione avviene sempre fra l’ultimo goal e una clausola di programma.

Si puo’ avere: successo successo (viene generata la clausola vuota)

insuccesso finitoinsuccesso finito

insuccesso infinitoinsuccesso infinito

La sostituzione di risposta è la sequenza di unificatori usati. Applicati alle variabili del goal iniziale danno la risposta.

Programmazione logica e Programmazione logica e PrologPrologRisoluzione ad input lineare (SLD)Risoluzione ad input lineare (SLD)

• Risoluzione Lineare per Clausole Definite con funzione di Selezione (RISOLUZIONE SLD)

• Dato un programma logico P e una clausola goal G0, ad ogni passo di risoluzione si ricava un nuovo risolvente Gi+1, se esiste, dalla clausola goal ottenuta al passo precedente Gi e da una variante di una clausola appartenente a P

• Una variante per una clausola C e’ la clausola C’ ottenuta da C rinominando le sue variabili ( renaming)

– Esempio:p(X):- q(X,g(Z)).p(X1):- q(X1,g(Z1)).



• L’unificazione è un meccanismo che permette di calcolare una sostituzione al fine di rendere uguali due espressioni. Per espressione intendiamo un termine, un letterale o una congiunzione o disgiunzione di letterali.

• SOSTITUZIONE: = [X1/T1, X2/T2,…, Xn/Tn] insieme di legami di termini Ti a variabili Xi che rendono uguali due espressioni.L’applicazione di una sostituzione a un’espressione E, [E] produce una nuova espressione in cui vengono sostituite tutte le variabili di E con i corrispondenti termini.

• Esempio: Espressione 1: c(X,Y) Espressione 2: c(a,K)sostituzione unificatrice: = [X/a, Y/K]

Strategia di risoluzione in profondità con backtracking

Possono esserci più clausole di programma utilizzabili per applicare la risoluzione con il goal corrente.

Si possono adottare diverse strategie di ricerca:


Il prolog adotta una strategia di risoluzione in profondità con Il prolog adotta una strategia di risoluzione in profondità con backtracking.backtracking.•Permette di risparmiare memoria.•Non è completa per le clausole di Horn.

in ampiezzain ampiezza: si considerano in parallelo tutte le possibili alternative.

in profonditàin profondità : si sceglie una clausola e si mantiene fissa questa scelta, finchè non si arriva alla clausola vuota o alla impossibilità di fare nuove risoluzioni. In questo ultimo caso si riconsiderano le scelte fatte precedentemente.


• Una derivazione SLD per un goal G0 dall’insieme di clausole definite P e’ una sequenza di clausole goal G0,…Gn, una sequenza di varianti di clausole del programma C1, …Cn, e una sequenza di sostituzioni 1 ,…, n tali che Gi+1 è derivato da Gi e da Ci+1 attraverso la sostituzione n . La sequenza può essere anche infinita.

• Esistono tre tipi di derivazioni;– successo, se per n finito Gn è uguale alla clausola vuota Gn = :-– fallimento finito: se per n finito non è più possibile derivare un nuovo risolvente da Gn e Gn non è uguale a :-– fallimento infinito: se è sempre possibile derivare nuovi risolventi tutti diversi dalla clausola vuota.

Programmazione logica e Programmazione logica e PrologPrologALBERI DI DERIVAZIONE

• Dato un programma logico P, un goal G0 e una regola di calcolo R, un albero SLD per P {G0} via R è definito come segue:– ciascun nodo dell'albero è un goal (eventualmente vuoto);– la radice dell'albero è il goal G0;– dato il nodo :-A1,...,Am-1,Am,Am+1,...,Ak se Am è l’atomo selezionato dalla regola di calcolo R, allora questo nodo ( genitore) ha un nodo figlio per ciascuna clausola Ci = A:-B1,...,Bq di P tale che A e Am sono unificabili attraverso una sostituzione unificatrice più generale . Il nodofiglio è etichettato con la clausola goal::-[A1,...,Am-1,B1,...,Bq,Am+1,...,Ak] e il ramo dal nodo padre al figlio è etichettato dalla sostituzione e dalla clausola selezionata Ci;– il nodo vuoto (indicato con “:-”) non ha figli.

(cl1) p :- q,r. (cl5) s:- w.(cl2) p :- s,t. (cl6) t.(cl3) q :- u. (cl7) w.(cl4) q :- v.

:- p. (1)(cl1) (cl2)

:- q,r. (2)

:- u,r. (3) :- v,r. (4):- w,t. (6)

:- t. (7)

:- s,t. (5)(cl3)

(cl5)

(cl7)

(cl6):- clausola vuota - successo

goal :- p.

Albero di Albero di risoluzionerisoluzione

fallimento fallimento

(cl4)Strategia

di risoluzione

in profondità

con backtracking


• Ad ogni ramo di un albero SLD corrisponde una derivazione SLD.– Ogni ramo che termina con il nodo vuoto (“:-”) rappresenta una derivazione SLD di successo.

• La regola di calcolo influisce sulla struttura dell’albero per quanto riguarda sia l’ampiezza sia la profondità. Tuttavia non influisce su correttezza e completezza. Quindi, qualunque sia R, il numero di cammini di successo (se in numero finito) è lo stesso in tutti gli alberi SLD costruibili per P {G0} .

• R influenza solo il numero di cammini di fallimento (finiti ed infiniti).

REGOLA DI CALCOLOREGOLA DI CALCOLO


sum(0,X,X). (CL1)sum(s(X),Y,s(Z)):- sum(X,Y,Z). (CL2)G0= :- sum(W,0,0),sum(W,0,K).

Albero SLD con regola di calcolo “left-most”


sum(0,X,X). (CL1)sum(s(X),Y,s(Z)):- sum(X,Y,Z). (CL2)G0= :- sum(W,0,0),sum(W,0,K).

Albero SLD con regola di calcolo “right-most”


(cl1) p:- q,r.(cl2) p.(cl3) q:- q,t.

:- p. (1)(cl1) (cl2)

:- q,r. (2)

:- q,t,r. (3)

:- q,t,t,r. (4)

:-

(cl3)La clausola vuota può essere generata ma il Prolog non è in grado di trovare questa soluzione

Albero di risoluzione

per il goal :- p.

fallimento

Ramo di fallimentoRamo di fallimentoinfinitoinfinito

(cl3)

Strategia

di risoluzione

in profondità

con backtracking

(cl3)

(cl3)

:- q,t,t,t,r. (5)


Dal programma logicoprogramma logico:

sum(0,X,X). (c1)

sum(s(X),Y,s(Z)) :- sum(X,Y,Z). (c2)


La risposta si ottiene dalla sequenza di sostituzioni

W=s(Z1) Z1=s(Z2) Z2=s(0) quindi W=s(s(s(0))) cioè 2+1=3

E dal goalgoal sum(s(s(0)),s(0),W) (g0)

risolvendo il goal g0 con c2 con {X/s(0),Y/s(0),W/s(Z1)}

:- sum(s(0),s(0),Z1) (g1)

risolvendo il goal g1con c1 con {X/0,Y/s(0),Z2/s(0)}

:- clausola vuota

risolvendo il goal g1con c2 con {X/0,Y/s(0),Z1/s(Z2)}

:- sum(0,s(0),Z2) (g2)

1. p(x,z) p(y,z), q(x,y)2. p(x,x)

3. q(a,b) La query 4. p(x,b)

Albero di ricerca

<-- p(y,b), q(b,y)

•

•

•

•

•

•

<-- p(x,b)

x = b2

<-- p(y,b), q(x,y)

1

<-- p(b,b)

3 x = a y = b

2

1

fallimento finito


Luca)ario,Fratello(M

:inferisce si

Luca)iovanni,Genitore(GMario)iovanni,Genitore(G

:da

y)),Genitore(px)(p,p)Genitore(yxy)o(x,y)(Fratell(x,

c)),Genitore(pp)(g,p)Genitore(c),c)(Nonno(g(g,

p)Figlio(c,c)(p,c)Genitore(p,

c),Genitore(mFemmina(m)c)c)Madre(m,(m,

PARENTELE


luca).ario,Fratello(m -:

luca).rio,diverso(ma mario).rco,diverso(ma luca).iovanni,genitore(g

mario).iovanni,genitore(g

marco).ario,genitore(m

luca).uisa,genitore(l

c)),genitore(gp),,genitore(gc),diverso(p,:c),fratello(p

c).,genitore(pp),,genitore(g:c)nonno(g,

p).figlio(c,:c),genitore(p

c).,genitore(m,femmina(m):c)madre(m,

PARENTELE


, marco).

luca).ario,fratello(m -:

luca}/cmario,/{p

. luca),genitore(gmario),,genitore(g luca),rio,diverso(ma -:

luisa}/{g

-:

. luca)uisa,genitore(l -: . luca)iovanni,genitore(g -:

. luca),genitore(gmario),,genitore(g -:{}

fallimento

giovanni}/{g


:- collega(a,c).

(cl1) collega(a,b).

(cl2) collega(c,b).

(cl3) collega(X,Z):- collega(X,Y),collega(Y,Z).

(cl4) collega(X,Y):-collega(Y,X).

:- collega(a,Y1), collega(Y1,c).

collega(b,c)

:- collega(b,Y2), collega(Y2,c).

:- collega(b,Y3),collega(Y3,Z3), collega(Z3,c).

:- collega(c,a).

:- collega(a,c).

cl3 cl4

cl3 cl4

ramoinfinito

ramo infinito

collega(c,b)cl4

cl1

cl3

cl3

cl3

cl4

cl3 cl4


P :- Q,R.

Interpretazione dichiarativa:

P è vero se sono veri Q e R.

Interpretazione procedurale:

Il problema P può essere scomposto nei sottoproblemi P e Q.

Modello di esecuzione:

execute

Programma

Indicatore successo/fallimentoIstanza delle variabili

Lista di goal

Un goal può essere visto come una chiamata ad una procedura.

Una regola può essere vista come la definizione di una procedura in cui la testa è l’intestazione mentre la parte destra è il corpo.


Per rendere il Prolog un linguaggio effettivamente utilizzabile

vengono aggiunti:

•Notazione per le liste.

•Possibilità di manipolare strutture dati.

•Operazioni aritmetiche.

•Meccanismi di controllo del backtracking.Meccanismi di controllo del backtracking.

•Trattamento della negazione.

•Predicati di input/output.

•Meccanismi per modificare/accedere alla base di conoscenza.

•Meccanismi per il caricamento del codice prolog.


CUT e controllo del backtracking

Programmazione logica e Programmazione logica e PrologPrologPredicati di controllo di un programma

Predicati predefiniti che consentono di influenzare econtrollare il processo di esecuzione (dimostrazione) di ungoal.

PREDICATO CUTPREDICATO CUT ( ! )– E’ denotato dal simbolo !– E’ uno dei più importanti e complessi predicati di controlloforniti da Prolog

Per capire come funziona il predicato cut e’ necessariovedere il modello run time di Prolog

Si consideri la clausola:p :- q1, q2,…, qi, !, qi+1, qi+2,…, qn.l’effetto della valutazione del goal ! (cut) durante ladimostrazione del goal "p" è il seguente:– la valutazione di ! ha successo (come quasi tutti i predicati predefiniti) e ! viene ignorato in fase di backtracking;– tutte le scelte fatte nella valutazione dei goal q1, q2,..., qi e in quella del goal p vengono rese definitive; in altri termini, tutti i punti di scelta per tali goal (per le istanze di tali goal utilizzate) vengono rimossi dallo stack di backtracking.– Le alternative riguardanti i goal seguenti al cut non vengono modificate

EFFETTO DEL CUTEFFETTO DEL CUT


Linguaggi imperativi (C , Pascal etc.)

Si specifica come risolvere un problema

Linguaggi dichiarativi

Funzionali (Lisp puro)

Usa il concetto di funzione e di composizione di funzioni

Logici (Prolog)

Si descrivono le relazioni che intercorrono fra i dati.Non ci sono assegnamenti. Non determinismo.


Linguaggi di Programmazione (AA 2002/2003) Corso di Laurea in Informatica Introduzione al linguaggio...

Documents

Transcript of Linguaggi di Programmazione (AA 2002/2003) Corso di Laurea in Informatica Introduzione al linguaggio...