Stati

Nella semantica normale usiamo una diversa rappresentazione di un proces- so, detta stato. La definizione di stato si basa sull’idea di rappresentare un processo come un multi-insieme di processi di base, ovvero somme, replica- zioni e match.

Per esempio il processo ben-etichettato P =!¯xn|¯xn|¯xn|x(yβ₎

pu`o essere rappresentato con il multi-insieme {(!¯xn, 1), (¯xn, 2), (x(yβ_{), 1)}.}

`

E da notare che i multi-insiemi sono necessari per mantenere l’informazione sul numero di occorrenze dei processi di base.

Tra i processi base non consideriamo le restrizioni, poich´e queste possono essere eliminate. Infatti, dato che consideriamo solo processi ben-etichettati, il nome ristretto `e certamente un nome fresh.

Per esempio nel processo Q = (νnχ_)(¯na|n(yβ_).¯yb)

il nome ristretto n `e nuovo, quindi nella rappresentazione in stato pu`o essere eliminato ottenendo

{(¯na, 1), (n(yβ_{).¯yb, 1)}.}

Tuttavia la rappresentazione di un processo esclusivamente tramite un multi- insieme di processi di base non `e abbastanza informativa.

Tale rappresentazione infatti non permette di distinguere i nomi ristretti da quelli liberi.

Consideriamo per esempio i processi Q = (νnχ_)(¯na|n(yβ_).¯yb)

Q0 _{= ¯na|n(y}β_).¯yb.

`

E immediato notare che i due processi sono diversi, in quanto nel processo Q il nome n `e ristretto, mentre nel processo Q0 <sub>n `e libero. Di conseguenza, `e</sub>

ovvio che anche gli stati che li rappresentano devono essere diversi. La rap- presentazione tramite multi-insieme invece non ci permette di distinguerli, dato che Q e Q0 _{hanno gli stessi processi di base. Per risolvere questo pro-}

blema introduciamo nello stato una nuova componente, ovvero la funzione R, che mantiene l’associazione tra le etichette delle restrizioni e gli insiemi contenenti i relativi nomi. Pertanto, abbiamo che i processi Q e Q0 _sono

rappresentati rispettivamente dai seguenti stati ({(¯na, 1), (n(yβ_{).¯yb, 1)}, R}

1)

({(¯na, 1), (n(yβ_{).¯yb, 1)}, R}

2)

dove R1(χ) = {n} e R2(χ) = ∅.

Inoltre, per predire staticamente le propriet`a a cui siamo interessati `e ne- cessario catturare in modo semplice quali nomi verranno legati alle variabili durante l’esecuzione di un processo.

Per esempio, consideriamo il seguente processo Q0 _{= ¯na|n(y}β_).¯yb.

che con un passo di computazione pu`o transire in Q00_{= ab.}

Abbiamo bisogno di mantenere l’informazione del legame tra l’etichetta β e la variabile y e tra y e il nome a, di conseguenza introduciamo nello stato le seguenti componenti:

• B, che mantiene l’associazione tra le etichette e le variabili oggetto degli input prefix, che sono stati coinvolti in una comunicazione;

• env, che mantiene l’associazione tra variabili e nomi.

In questo modo possiamo rappresentare il processo Q00 _{con lo stato}

({(¯yb, 1)}, B, env, R)

dove le funzioni B ed env sono tali che B(β) = {y} e env(y) = a.

Di seguito consideriamo la funzione env come l’ambiente dei nomi in cui so- no valutati le variabili e i nomi liberi dei processi base presenti nello stato. Pertanto, env mantiene le associazioni, non solo per le variabili oggetto degli input prefix che sono stati coinvolti in una comunicazione, ma anche per ogni variabile e nome libero dei processi base dello stato.

Presentiamo adesso la definizione di stato e definiamo le operazioni di inclu- sione e unione tra stati.

Indichiamo con PB l’insieme dei processi base ben-etichettati, ovvero quelli della forma P = π.Q, P =P+P, P =!Q e P = [x = y]Q.

Consideriamo inoltre un’estensione dell’insieme dei nomi che indichiamo con e

N⊥,>, ottenuta aggiungendo gli elementi ⊥ e > all’insieme eN .

Definizione 3.5 (Stati) Uno stato S ∈ S `e una quadrupla (P roc, B, env, R) dove

• P roc ∈ PROC `e un multi-insieme di processi base ben-etichettati;

• B : LabI _{→ ℘(V), con B ∈ B, `e una funzione totale tale che ∀β ∈}

LabI _{: B(β) ⊆ V} β;

• env : eN → eN⊥,>, con env ∈ EN V, `e una funzione totale tale che

• R : LabR _{→ ℘(N ), con R ∈ R, `e una funzione totale tale che ∀χ ∈}

LabR _{: R(χ) ⊆ N} χ.

In uno stato le funzioni B ed env forniscono l’informazione sui canali a cui una data variabile `e legata. Analizzando il multi-insieme P roc e la funzione env inoltre `e possibile determinare i canali che vengono inviati su un dato canale. Infine, la funzione R consente di individuare i nomi legati da un operatore di restrizione.

Introduciamo adesso alcune notazioni usate di seguito.

Notazioni

• Sia f : A → B una funzione e siano a ∈ A e b ∈ B. Scriviamo f [a 7→ b] per indicare che f `e aggiornata con la nuova associazione tra a e b, sovrascrivendo l’associazione gi`a presente.

• Sia env ∈ EN V una funzione. Indichiamo con dom(env) l’insieme degli elementi del dominio di env associati ad un elemento diverso da ⊥, ovvero dom(env) = {y|env(y) 6=⊥}.

• Sia S = (P roc, B, env, R) uno stato. Indichiamo con hP roc, envi il multi-insieme dei processi dello stato S valutati nell’ambiente env, ov- vero

hP roc, envi = {(Q, n)|Q = hP, envi ∧ (P, n) ∈ P roc} dove

hP, envi = P [env(n1)/n1, . . . , env(ni)/ni] con {n1, . . . , ni} = f n(P )

Introduciamo di seguito le nozioni di nomi liberi e nomi legati di uno stato. Definizione 3.6 (Nomi liberi e nomi legati di uno stato) Sia S ∈ S uno stato tale che S = (P roc, B, env, R). Indichiamo con:

• f n(S) i nomi liberi di S tale che f n(S) = [

P ∈hP roc,envi

f n(P ) \ [

χ∈LabR

• nr(S) i nomi ristretti di S tale che nr(S) = [ P ∈P roc nr(P ) ∪ [ χ∈LabR R(χ)

• var(S) le variabili legate di S tale che var(S) = [

P ∈P roc

var(P )

• bn(S) i nomi legati di S tale che

bn(S) = var(S) ∪ nr(S)

Ordinamento e unione tra stati. Prima di dare le definizione di ordi- namento e di unione tra stati ricordiamo l’ordinamento punto a punto delle funzioni e definiamo il minimo dei maggioranti e il massimo dei minoranti di un insieme di funzioni.

Definizione 3.7 (Ordinamento puntuale delle funzioni) Sia (B, vB) un

ordinamento parziale e siano f, g : A → B due funzioni totali. Si ha che f vF g se e solo se ∀x ∈ A : f (x) vB g(x).

Definizione 3.8 (Lub di un insieme di funzioni) Siano F = {f1, f2, . . .}

un insieme di funzioni fi : A → B e (B, vB) un ordinamento parziale tale

che ogni suo sottoinsieme ha lub. Il minimo maggiorante dell’insieme F `e definito in modo puntuale, ovvero

( G i F fi)(x) = G i B fi(x).

Definizione 3.9 (Glb di un insieme di funzioni) Siano F = {f1, f2, . . .}

un insieme di funzioni fi : A → B e (B, vB) un ordinamento parziale tale

che ogni suo sottoinsieme ha glb. Il massimo minorante dell’insieme F `e definito in modo puntuale, ovvero

( \ i F fi)(x) = \ i B fi(x).

Le Definizioni 3.7 e 3.8 sono usate rispettivamente per l’ordinamento e l’u- nione degli stati, definite entrambi componente per componente.

Definiamo di seguito gli ordinamenti dei codomini delle funzioni che com- pongono lo stato.

I codomini delle funzioni appartenenti a B e di quelle appartenenti ad R sono ordinati secondo la relazione di inclusione tra insiemi ⊆, mentre il codomi- nio delle funzioni appartenenti ad EN V, ovvero eN⊥,>, `e ordinato secondo la

seguente relazione: ∀n ∈ eN⊥,> : ⊥v n ∧ n v n ∧ n v >.

Poich`e (℘(V), ⊆) `e un ordinamento parziale `e possibile usare la Definizione 3.7 per ordinare due funzioni B1, B2 ∈ B. `E facile verificare che la stessa defini-

zione pu`o essere applicata anche per ordinare due funzioni env1, env2 ∈ EN V

e due funzioni R1, R2 ∈ R, dato che anche ( eN⊥,>, v) e (℘(N ), ⊆) sono ordi-

namenti parziali.

Di seguito usiamo la seguente notazione:

• B∅ per indicare la minima funzione B ∈ B, che mappa ogni etichetta a

∅, ovvero ∀β ∈ LabI _{: B}

∅(β) = ∅.

• env⊥ per indicare la minima funzione env ∈ EN V, che mappa ogni

nome a ⊥, ovvero ∀n ∈ eN : env⊥(n) =⊥.

• R∅ per indicare la minima funzione R ∈ R, che mappa ogni etichetta

a ∅, ovvero ∀χ ∈ LabR _{: R}

∅(χ) = ∅.

Inoltre, `e facile verificare che per ognuno degli ordinamenti parziali (℘(V), ⊆), ( eN⊥,>, v) e (℘(N ), ⊆), vale che ogni loro sottoinsieme ammette lub. Pertan-

to, secondo la Definizione 3.8, `e sempre possibile calcolare il minimo dei maggioranti rispettivamente di un insieme di funzioni {Bi|Bi ∈ B}, un insie-

me di funzioni {envi|envi ∈ EN V} e un insieme di funzioni {Ri|Ri ∈ R}.

Sulla base di queste propriet`a definiamo l’inclusione e l’unione tra stati. Definizione 3.10 (Ordinamento sugli stati) Siano (P roc, B, env, R) e (P roc0_{, B}0_{, env}0_{, R}0_{) due stati. Diciamo che}

se e solo se

• P roc ⊆ P roc0

• B vF B0

• env vF env0

• R vF R0

dove per le funzioni si considera l’ordinamento punto a punto e per l’elemento P roc si considera l’ordinamento tra multi-insiemi, definito in modo standard. Di seguito diamo la definizione di unione tra stati.

Definizione 3.11 (Unione tra stati) Siano (P roc1, B1, env1, R1) e

(P roc2, B2, env2, R2) due stati. Abbiamo

(P roc1, B1, env1, R1) ∪s(P roc2, B2, env2, R2) = (P roc, B, env, R)

dove

• P roc = P roc1∪ P roc2

• B = B1tF B2

• env = env1tF env2

• R = R1tF R2

Per l’elemento P roc consideriamo l’unione tra multi-insiemi, definito in modo standard.

Stati ben-etichettati. Poich´e siamo interessati solo a stati che rappresen- tano processi ben-etichettati, introduciamo la nozione di stato ben-etichettato. Definizione 3.12 (Stato ben-etichettato) Uno stato S = (P roc, B, env, R) `e ben-etichettato se e solo se:

1. le variabili legate di S sono diverse:

(a) da tutte le altre variabili legate dello stato

(b) dalle variabili appartenenti ai nomi liberi dello stato

(c) dalle variabili libere non valutate dei processi presenti nella com- ponente P roc di S

2. i nomi ristretti di S sono diversi:

(a) da tutti gli altri nomi ristretti dello stato S

(b) dai nomi liberi di S

3. la funzione env dello stato S `e tale che

(a) ∀n ∈ N : env(n) =⊥ ∨ env(n) = n

(b) ∀x ∈ eN : env(x) 6= >

(c) ∀x ∈ dom(env) : env(x) ∈ dom(env).

Di seguito usiamo SE per indicare l’insieme degli stati ben-etichettati.