Sostituzioni e Unificazione

(1)

Capitolo 3

Sostituzioni e Unificazione

3.1 Formalmente, le sostituzioni

In questo paragrafo verrà introdotto in modo del tutto formale il concetto di sostituzione[35], e in particolar modo quello di sostituzione idempotente che sta alla base del nostro algoritmo di unificazione. Procediamo fornendo le principali definizioni.

Sostituzione

Una sostituzione è una funzione da V (insieme delle variabili) a T (insieme dei termini) tale che l’insieme D( ) = { x ∈ V | (x) x } è finito. Tale insieme è chiamato dominio della sostituzione .

Se t è un termine, allora t è definito induttivamente a partire da x = (x) se x è una variabile, e f(t

1

,...,t

n

) = f ( t

1

,..., t

n

). Se M è un insieme di termini, allora M denota l’insieme { t | t ∈ Μ }.

Composizione di sostituzioni e sostituzione vuota

• La composizione τ di due sostituzioni e τ è definito da ( τ) x = ( τ x).

• La funzione identità su V è chiamata sostituzione vuota ed è indicata con ε.

(2)

E’ importante notare che la restrizione di una sostituzione è ancora una sostituzione.

Relazioni tra sostituzioni

Una sostituzione σ si dice più generale di una sostituzione τ e si indica con σ τ, se σ è un divisore destro di τ, cioè se esiste una sostituzione ρ tale che ρσ = τ.

Due sostituzioni σ e τ si dicono equivalenti e si indica con σ ∼ τ , se σ τ e τ σ. Si noti che è una relazione riflessiva e transitiva sull’insieme delle sostituzioni.

Qualche piccolo appunto sulla notazione che in genere viene utilizzata per esprimere aspetti correlati a questi concetti:

(a) Se t è un termine, in genere denotiamo con V(t) l’insieme delle variabili che occorrono in t.

(b) Se M è un insieme di termini, allora V(M) denota l’unione di tutti gli insiemi V(t) con t ∈ M.

Sostituzione idempotente

Una sostituzione σ si dice idempotente se e solo se σσ = σ.

Sono equivalenti alla precedente definizione le seguenti affermazioni:

(a) V(σV) e D(σ) sono insiemi disgiunti;

(b) V è l’unione disgiunta di V(σV) e D(σ);

(c) D(σ) e V(σD(σ)) sono insiemi disgiunti.

(3)

Proprietà delle sostituzioni idempotenti

(a) Se σ è una sostituzione idempotente e τ è una sostituzione arbitraria, allora σ è più generale di τ se e solo se τ σ = τ .

(b) Sia σ una sostituzione.

Sia ρ una funzione da V a V tale che ρ x ∈ σ

⁻¹

({ x}) per x ∈ V( σ V) e ρ x = x per x ∈ V \ V(σV). Allora ρ è una sostituzione e ρσ è una sostituzione idempotente che è equivalente a σ.

Ogni sostituzione idempotente che è equivalente a σ può essere ottenuta come ρσ dove ρ è definita come nel punto precendente.

3.2 Unificazione: concetti preliminari

Prima di definire l’algoritmo di unificazione[7][8][9][10] introduciamo le strutture e i concetti sui quali esso opera.

1. Universo dei termini

Definiamo l’universo (insieme) dei termini (che nel nostro caso saranno tipi) sui quali l’algoritmo lavora:

U

_Σ

= { F(t1.…tk) | F ∈ Σ & ar(F) = k & ti ∈ U

_Σ

∀ i }

dove con

Ÿ F si è indicato il funtore cioè il nome della funzione (termine)

Ÿ ar(F) indica l’arità, ovvero il numero di argomenti del funtore

(4)

Un esempio di universo:

U

{a,f: ar(a)=0,ar(f)=2}

= {a, f(a,a), f(f(a,a),a), …….}

2. Cammini su termini

I termini possono essere anche rappresentati come insiemi di cammini. Sia Ck l’insieme di tutti i cammini per termini con funtori di arità massima k. Ck contiene il cammino nullo “ε”, e ogni sequenza di indici in {1..k}. Ck è chiuso rispetto all’operazione di giustapposizione “.” su cammini, ovvero:

∀ p, q ∈ Ck, p.q ∈ Ck

La giustapposizione è associativa a destra e a sinistra, ovvero:

p1.p2.p3 = (p1.p2).p3 = p1.(p2.p3)

ed ha “ε” come elemento neutro destro e sinistro:

ε.p = p ∀ p ≠ ε p.ε = p ∀ p ≠ ε

Sia un insieme di cammini I

k

⊆ Ck, definiamo I

k

superiormente limitato se p.u.q ∈ I

k

, per 1=u=k, allora p.j ∈ I

k

, ∀ 1=j =u

Lemma. Un termine è un insieme superiormente limitato.

(5)

Generalizziamo adesso la giustapposizione a insiemi di cammini, cioè ∀ p ∈ Ck e

∀ I

k

, J

k

⊆ Ck, vale:

p.I

k

= { p.q | q ∈ I

k

}

I

k

. J

k

= { p.q | p ∈ I

k

, q ∈ J

k

}

Infine definiamo, ∀ t ∈ U

Σ

(dato un Σ ed il relativo alfabeto su Σ)

1. Path(t) = { ε } se t ∈ Σ e arità(t) = 0;

2. Path(F(t1.…tk)) = { ε } ∪ ∪

i∈1..k

i.Path(ti)

Lemma. Path(t) è un insieme superiormente limitato.

3. Termine di t all’occorrenza p

Si indica con t|

p

ed è un sottotermine di t così definito:

1. t|

_ε

= t

2. F(t1.…tk)|

i.p

= ti|

p

per i ∈ 1.…k

L’insieme di tutti i sottotermini di un termine è allora dato da

τ(t) = { t|

p

| p ∈ Path(t) }

Il funtore principale di un sottotermine all’occorrenza p è definito da

(6)

3.3 Unificazione: algoritmo

Ÿ Input: Termini in forma di albero.

Ÿ Output: Un insieme di sostituzioni (anche vuoto o con un solo elemento).

Passo 1

Calcolo del Path (cammino).

Indichiamo con N l’insieme delle coppie di termini <T , T’>. Se in tale insieme non esiste una coppia per cui vale Path(T) ≠ { ε } e Path(T’) ≠ { ε } (questo significa che non ci sono più sottotermini) l‘algoritmo termina.

In caso contrario, sia appunto <T , T’> una di queste coppie, con

T = F(t1.…..tk) T’ = G(t1’….tk’)

(i) se F ≠ G l’unificazione restituisce Top (fallimento)

(ii) altrimenti sia k = k’. Allora consideriamo i cammini (sottocammini) che percorrono T e quelli che percorrono T’ e indichiamoli rispettivamente con Path(T) e Path(T’).

A questo punto aggiungiamo ad N una coppia

<T ↓ p , T’ ↓ p> ∀ p ∈ Q = Path(T) ∩ Path(T‘)

dove Q viene anche detto insieme delle occorrenze.

(7)

Passo 2

Ordinamento lessicografico delle coppie in N ottenute al passo precedente (x > y > z).

Tutte le coppie <e , x>, con Path(e) ≠ { ε }, vengono rimpiazzate dalle coppie <x , e>

corrispondenti. Viene inoltre applicata la proprietà transitiva e la riduzione.

Passo 3

Vengono eliminate da N tutte le coppie della forma <u , u>.

Passo 4 Occur-Check

Sia il primo elemento della coppia una variabile e sia l’arità del secondo elemento (sottotermine) diversa da 0. Questa passo consiste nel controllare che la variabile non occorra nel sottotermine.

Vediamolo più formalmente:

∀ <x , a> ∈ N tale che x ∈ Variabili e arità(a) ≠ 0 , se <x , a> è ottenuto da p ovvero a = t↓p allora controllo che x ∉ Variabili( t|

p

)

Nota:

In realtà le coppie che otteniamo realmente sono leggermente diverse da quelle che

(8)

Allora l’Occur-Check diventa data < (t1 , p1) , (t2 , p2) > ∈ N,

se t1↓p1 ∈ Variabili, allora calcoliamo t2↓p2 e ci chiediamo se t1↓p1 ∈ Var(t2↓p2) .

3.4 Algoritmo unificazione: esempio

Passo 1

Questo primo passo consiste nel calcolo del Path (cammino). Esemplifichiamo la procedura con un esempio chiarificatore.

Consideriamo i due termini:

T

1

= f(x, g(a, h(y,y), x)) T

2

= f(a, g(y, z, y))

Come prima cosa calcoliamo:

Path(T

1

) = Path(f(x, g(a, h(y,y), x)))

= {ε} ∪ 1.Path(x) ∪ 2.Path(g(a, h(y,y), x))

= { ε } ∪ 1.{ ε } ∪ 2. ({ ε } ∪ 1.Path(a) ∪ 2.Path(h(y,y)) ∪ 3.Path(x)) = {ε} ∪ {1} ∪ 2.({ε} ∪ {1} ∪ 2.({ε} ∪ 1.Path(y) ∪ 2.Path(y)) ∪ {3}) = { ε } ∪ {1} ∪ 2.({ ε } ∪ {1} ∪ 2.({ ε } ∪ {1} ∪ {2}) ∪ {3})

= passo finale =

= {ε, 1, 2, 2.1, 2.2, 2.2.1, 2.2.2, 2.3}

Calcoliamo adesso molto velocemente il cammino per T

2

(9)

Consideriamo Q, ottenuto intersecando i due cammini calcolati in precedenza

Q = Path(T

1

) ∩ Path(T

2

) = { ε , 1, 2, 2.1, 2.2, 2.3}

Saranno proprio i sottotermini ai livelli indicati in Q a costituire le coppie che dovranno essere unificate.

Infatti, le coppie ottenute in un unico passo da <T

1

, T

2

> sono

{ <T

1

↓ε , T

2

↓ε >, ………..., <T

1

↓ 2.3 , T

2

↓ 2.3>}

ovvero

{ <f , f>, <x , a>, <g , g>, <a , y>, <h , z>, <x , y> }

Passo 2

Questo passo consiste nell’ordinare lessicograficamente (x > y > z > costanti) le coppie ottenute al passo 1.

{ <f , f>, <x , a>, <g , g>, <y , a>, <z , h>, <x , y> }

Applichiamo la proprietà transitiva che si comporta nel seguente modo:

{<x , y>} ∪ {<y , z>} ∪ N = { <x , z>, <y , z> } ∪ N

(10)