Vincoli in un linguaggio di programmazione:
La programmazione logica a vincoli è del secondo tipo
Un programma di questo tipo, come viene interpretato?
A(X,Y):-X<Y, B(X), C(Y).
Se sia X che Y hanno già un valore, allora X<Y si può valutare
Questa condizione può risultare vera oppure falsa
Nel primo caso, si valuta B(X) e poi C(Y)
Nel secondo caso, la clausola viene scartata e si passa ad altre clausole con A nella testa
Se X oppure Y non sono ancora valutate?
Intuitivamente, valutare A(X,Y) su questo programma dovrebbe dare X=0, Y=1
A(X,Y):-X<Y, B(X), C(Y). B(0). C(1).
Mentre su quest'altro dovrebbe fallire:
A(X,Y):-X<Y, B(X), C(Y). B(1). C(0).
Quindi: la condizione X<Y non la posso valutare finchè non si hanno dei valori per X ed Y
La situazione vista è:
Principio: se incontro un vincolo non valutabile, lo devo memorizzare per poter poi controllare se verrà soddisfatto
Viene mantenuto un insieme di vincoli, detto constraint store (magazzino dei vincoli)
Quando si incontra un vincolo:
Ogni volta che una variabile assume un valore, si va a controllare se ci sono vincoli valutabili nel magazzino
Si valuta A(X,Y) su questo programma:
A(X,Y):-X<Y, B(X), C(Y). B(0). C(1). A(10,10).
Il meccanismo formale lo vediamo più avanti
Si inizia con il magazzino vuoto
Per ora, diciamo che al posto di A(X,Y) si prova a mettere X<Y, B(X), C(Y)
Dato che X<Y è un vincolo, viene aggiunto al magazzino
Siamo al goal B(X), C(Y) con X<Y nel magazzino
Dato che abbiamo B(0) e C(1), il goal si dimostra con X=0, Y=1
Questo soddisfa il vincolo, per cui è una soluzione
Simile:
A(X,Y):-X<Y, B(X), C(Y). B(1). C(0). A(10,10).
Ora però quando si arriva a valutare B(X), C(Y) con X<Y nel magazzino, l'unica possibilità è X=1, Y=0
Il vincolo nel magazzino non è soddisfatto
Si fa backtracking
Come?
Quando si arriva ad un fallimento, si torna indietro
I vincoli che si incontrano tornando indietro vengono eliminati dal magazzino
In sostanza, si è verificato che la clausola A(X,Y):-... non va bene
Dato che il vincolo X<Y era stato inserito nel magazzino solo perchè si era usata questa clausola, ora va tolto
Si prova A(10,10)
Questo va bene, perchè ora X<Y non è più nel magazzino
È quello che ci si aspetta: X<Y deve valere solo se si usa la prima clausola
Se si usa la seconda, questo vincolo non viene imposto
Quando si incontra un vincolo non valutabile, lo si mette nel magazzino
Questo equivale ad assumerlo consistente per andare avanti; si vedrà se è effettivamente consistente quando sarà valutabile
Quindi, il magazzino contiene tutti i vincoli che sono stati assunti essere consistenti per andare avanti
Una sostituzione deve soddisfare tutti i vincoli del magazzino
Quindi, se l'insieme dei vincoli del magazzino non è consistente, è inutile andare avanti
Si valuta A(X)
A(X):-X<0, B(X). B(X):-X>0, C(X). ...
Facciamo una valutazione ad occhio (senza usare le fresh variables):
Ora, C(X) si potrebbe anche dimostrare, soltanto che si è assunto che X soddisfi sia X<0 che X>0
Inutile andare avanti: non si potrà mai trovare un valore che soddisfi tutti i vincoli nel magazzino
Se il magazzino diventa inconsistente, è inutile andare avanti: non si potrà mai trovare una valutazione che soddisfi tutti i vincoli
Si fa quindi backtracking; questo elimina vincoli dal magazzino
Conviene cercare di scoprire prima possibile se il magazzino è inconsistente
Questo fa risparmiare elaborazione
D'altra parte, verificare la consistenza ad ogni passo è un problema difficile
Si usano delle condizioni sufficienti, di solito arc consistency e hyperarch consistency
In generale, quando si ha un goal A(t1,t2) e una clausola A(t3,t4):-corpo con lo stesso predicato A nella testa, si procede cosí:
L'unificazione di due termini t1 e t5 si può vedere come un vincolo t1=t5
Si tratta di una uguaglianza fra due strutture ad albero
Su questo tipo di uguaglianza valgono delle regole di inferenza particolari:
Si tratta comunque di vincoli, solo che si usa questo meccanismo per vedere se sono soddisfatti e per fare inferenza
Una sostituzione X=valore si può anche vedere come un vincolo (di uguaglianza)
In questo caso perè si può sostituire il valore alla variabile in tutti gli altri vincoli
Si considerano vincoli:
I vincoli del secondo tipo si possono anche inserire nel corpo delle clausole
Per esempio, è possibile scrivere:
A(f(X),Y):-f(X)=Y, B(X).
Si possono anche avere disuguaglianze fra termini:
A(f(X),f(Y)):-f(X)!=f(Y), B(X).
Da questa si deriva X!=Y
Considerare le uguaglianze di termini come vincoli permette di dare una semantica semplificata
L'interprete mantiene una lista di goal e il magazzino dei vincoli
Il passo generico è:
Nel passo 3.2, si fa inferenza sul magazzino.
In particolare:
Questo può provare l'inconsistenza
Quando si ottiene inconsistenza, si procede a ritroso
È un algoritmo ricorsivo
Una situazione che si potrebbe verificare è che il goal viene dimostrato senza valutare tutte le variabili:
A(X1,...,Xn):-vincolo1,B(X1,...,Xn).
B(X1,...,Xn):-vincolo2,C(X1,...,Xn).
...
W(X1,...,Xn):-vincolo23,Z(X1,...,Xn).
Z(X1,...,Xn).
Si accumulano tutti questi vincoli nel magazzino
Alla fine Z(X1,...,Xn) dimostra il goal
Però in tutto questo nessuna variabile è stata valutata
Quindi (in generale) non si può dire se i vincoli sono soddisfatti oppure no
È un letterale particolare
Significato:
labeling([variabili]) = fai backtracking sulle variabili
Serve a lanciare un algoritmo di ricerca di una soluzione
Si cerca una valutazione delle variabili che soddisfa tutti i vincoli
Se la variabili non sono tutte, viene cercata una soluzione che soddisfa tutti i vincoli che non hanno altre variabili che non siano in [variabili]
Si scrivono le clausole scrivendo i vincoli dove si vede che servono
Quando si vuole generare effettivamente una valutazione, si mette labeling
Cosa usare prima?
A(variabili):-labeling([variabili]), vincoli.
Oppure:
A(variabili):-vincoli,labeling([variabili]).
In generale, a parità di tutto il resto:
Quindi, conviene cercare di mettere prima i vincoli e poi il labeling
Unico caso in cui non conviene: se i vincoli riguardano variabili non collegate da molti vincoli a quelle precedenti
A(X):-X>0, Y>0, labeling([X,Y]).
Se trovare una soluzione per X e per Y è indipendente, tanto vale fare due labeling separati:
A(X):-X>0, labeling([X]), Y>0, labeling([Y]).
Dimostrare un letterale comporta backtracking:
A(X):-B(X), X>0.
Dimostrare B(X) potrebbe richiedere tempo
Poi magari si scopre che X>0 era già inconsistente
Conviene quindi mettere prima il vincolo e poi il letterale:
A(X):-X>0, B(X).
Labeling lancia una ricerca, usando backtracking o un algoritmo simile
Se si mette troppo presto, si rischia di avere tante soluzioni possibili
A(X):-labeling([X]),B(X).
Molte potrebbero poi non essere consistenti con quello che segue
Nell'esempio, potrebbero risultare non consistenti con B(X)
D'altra parte, se non non verranno aggiunti altri vincoli sulle stesse variabili, conviene verificare subito la consistenza
A(X,Y):-labeling([X]), B(Y).
In generale: si mette quando si sono accumulati più o meno tutti i vincoli su un certo numero di variabili
Nella programmazione logica senza vincoli, la valutazione di un goal può non portare ad un valore per tutte le variabili:
Esempio: goal A(X,Y,Z) con questo programma:
A(10,f(_),_).
Ritorna X=10,Y=f(_),Z=_
Può succedere anche quando ci sono vincoli
Se non si usa il labeling, lo stesso può succedere con i vincoli. Esempio: goal A(X,Y) e programma:
A(X,Y):-X<Y, B(Y). B(1).
Viene valutato Y=1, ma non viene dato valore a X
Contrariamente a prima, non ha senso dire che X può assumere un valore qualsiasi
Infatti, X è vincolato da X<Y
Senza vincoli: sostituzione (es, X/10, Y/f(_), ...)
Con vincoli: constraint store (che include vincoli del tipo Y=1 ecc.)
Quello che viene ritornato è il contenuto del magazzino
Nel caso del programma di prima, viene ritornato:
Y=1, X<Y
Questo sarebbe il magazzino se i vincoli venissero semplicemente aggiunti
In pratica, il magazzino viene semplificato ogni volta che si aggiunge un vincolo, per cui in effetti viene ritornato:
Y=1, X<1
Il dominio di una variabile si specifica in questo modo:
X::[valori]
Si possono quindi specificare valori interi e valori definiti da costanti:
X::[1,2,3,4,5] X::[1..5] X::[tizio,caio,sempronio]
La prima e la seconda dichiarazione sono indipendenti
La terza dichiarazione specifica che il dominio di X contiene tre valori: tizio, caio e sempronio
Si possono anche specificare i domini di più variabili insieme, se sono uguali:
[X,Y]::[3,4,5]
Si possono specificare vincoli su variabili reali
Sono equaglianze e diseguaglianze fra espressioni reali
Le espressioni reali sono espressioni lineari costruite a partire da variabili usando costanti e operatori reali
Una volta inseriti nel magazzino, questi vincoli si semplificando usando:
Si possono avere termini del tipo f(X+1) ecc.
Per esempio, si potrebbe avere il goal A(f(X+1,Y)) e il programma:
A(f(Z,g(K)):-...
Questo porta ad inserire f(X+1,Y)=f(Z,g(K)) nel magazzino
Questo si semplifica a: {X+1=Z, Y=g(K)}
Notare che un vincolo del tipo X+1=f(Y) è violato, perchè X+1 si valuta a un valore (reale o intero) mentre f(Y) è sempre un termine
Detto in altro modo: f(qualcosa) può solo essere uguale a un termine con f nella radice
In altre parole, f(qualcosa) può essere uguale solo a f(qualcosa_altro), e a niente altro
Nella programmazione a vincoli, può succedere che servano tutte le soluzioni, invece che una sola
Si può pensare di ottenere questo cercando tutti i modi di dimostrare il goal
Ossia, si può pensare di andare avanti dopo aver trovato il primo modo di dimostrare il goal
Questo però non sempre funziona
Si cercano tutti i modi di dimostrare A(X) su questo programma:
A(q). A(X):-B(X). B(X):-A(X).
Per valutare A(X) ci sono due possibilità: usare A(q) oppure usare A(X):-B(X)
La clausola che viene provata per prima è A(q), che produce X=q come prima soluzione
Per andare avanti, si usa l'altra possibilità: A(X):-B(X)
Questo richiede di dimostrare B(X), che si può fare solo usando la terza clausola
Viene quindi richiesto di dimostrare di nuovo A(X), e qui ci sono due possibilità: usare A(q) oppure A(X):-B(X)
Viene di nuovo ritornato X=q, e c'è ancora un'altra possibilità aperta, che è quella di usare A(X):-B(X)
Il goal A(X) con il programma:
A(q). A(X):-B(X). B(X):-A(X).
Genera un ciclo, in cui vengono usate nell'ordine queste clausole:
A(q). A(X):-B(X), B(X):-A(X), A(q). A(X):-B(X), B(X):-A(X), A(X):-B(X), B(X):-A(X), A(q). ...
Si va avanti all'infinito senza mai trovare nuove soluzioni
Andare in ciclo può portare a perdere delle soluzioni:
A(q). A(X):-B(X). B(X):-A(X). A(r).
La valutazione di questo programma produce un ciclo in cui si usano solo le prime tre clausole
L'ultima non viene mai usata, per cui la soluzione X=r non viene mai ottenuta
Serve quando si vogliono trovare tutte le soluzioni di un problema
Idea: invece di partire dal goal e trovare tutti i modi di dimostrarlo, si parte dai letterali e si vede cosa dimostrano
Ogni clausola che non contiene letterali nel corpo si considera un possibile punto di partenza
A(X,Y):-X<Y, B(X,Y). B(X,Y):-X>Y, Y>0.
La prima clausola non è un punto di partenza, perchè contiene B(X,Y) nel corpo
La seconda clausola va bene
Tecnicamente, significa: "B(X,Y) è vero se X>Y e se Y>0"
Ora si può usare A(X,Y):-X<Y, B(X,Y) perchè B(X,Y) è attualmente dimostrato (condizionalmente)
Questo dimostra che "A(X,Y) è vero se X<Y, X> e Y>0"
Dato che la precondizione è inconsistente, questo equivale a dire che A(X,Y) non è dimostrato
Quello che si ottiene è un insieme di clausole del tipo:
letterale ← vincoli
Si parte trasformando in questo formato ogni clausola che contiene solo vincoli nel corpo
Nel passo generico, si considerano tutte le clausole testa :- corpo in cui tutti i letterali del corpo sono nell'insieme di sopra
Si considerano insieme: i vincoli del corpo, i vincoli dei letterali, i vincoli di uguaglianza che derivano
Si aggiunge testa ← vincoli all'insieme, dove i vincoli sono quelli dei tre tipi di sopra
La valutazione bottom-up può sempre portare a delle ripetizioni:
A(0). A(X):-X>0. A(X):-X=Y+1,A(Y).
Qui si ottiene subito A(0) e A(X) ← X>0
Se si seguono le regole di sopra, si vede che da A(0) e da A(X):-X=Y+1,A(Y). si deriva A(1)
Usando la stessa clausola, si deriva A(2), poi A(3), ecc.
Però queste sono tutte conseguenze di A(X) ← X>0 (che implica che A(X) vale per ogni valore di X maggiore di zero
Per evitare la ripetizione:
La seconda cosa si può fare (parzialmente) creando il vincolo "opposto" (quello che è soddisfatto da tutti i valori che violano l'altro) e verificando se è consistente con il resto