Metodi formali nel progetto dell’interazione

Anna Labella

Due aspetti

• La struttura del tempo• Il tipo di interazione

Tempo discretoTempo continuo a gradiniTempo continuo

la struttura del tempo

Qual’è più “facile” e quale più utile?

HandshakingBroadcasting“a braccetto”ControlloRilevamento di segnaleRendez-vous ecc.

Il tipo di interazione

Esempi tratti dall’interazione

Combinazione di diversi processi Per mezzo di rendez-vous

Esempi tratti dall’interazioneInterfacce come tipici esempi di coesistenza di diversi “tipi di tempo”

Cosa ci interessa e cosa no

Eventi istantaneiEventi a distanza sempre più ravvicinata

Eventi che si svolgono e/o si evolvono in un intervallo di tempoEventi che devono aspettare input dall’esternoLatenze in informatica musicaleInterpretazione legata alle durate (es. doppio click)

Il problema cruciale: l’interpretazione

Riconoscimento di comportamento

Una possibile soluzione:diversi livelli di astrazione

Mieke Massink Giorgio P. Faconti,A reference framework for continuous interaction

UAIS, 1 (2002) 237-251http://www.springerlink.com/index/10.1007/s10209-002-0027-5

• fisico• percettivo• proposizionale• concettuale• di gruppo

Linee guida per disegnare interfacce ibride continue

Gestire l’interazione trasformando l’informazione dai sensori agli effettori

Philip Barnard, Jon May, David Duke, David DuceSystems, interactions, and macrotheory ACM TOCHI,7 (2000) 222--262

http://doi.acm.org/10.1145/353485.353490

Gli automi ibridi Una soluzione?

Automa ibrido <X,(V,E), init, inv, flow, jump, , E >

X n-uple di variabili reali, (V,E) grafo di controllo, modalità ed interruttori init, inv, flow condizioni che etichettano le modalità jump condizione che etichetta gli interruttori eventi

Thomas A. Henzinger,The Theory of Hybrid Automata,Proc. 11th LICS Conf. (1996) 278-292

Gli automi ibridi Una soluzione?

Sistema di transizione temporizzato <Q,Q0,A, >

Q,Q0 V Rn, (v,x)Q sse inv(v)[X:=x] vero(v,x)Q0 sse inv(v)[X:=x] e init(v)[X:=x] veri

A=R+ eventi e durate

:(v,x) (v’,x’) sse c’è e E v v’ jump(e)[X,X’:=x,x’] event(e)=

:(v,x) (v,x’) sse c’è f:[0, ] Rn differenziabile f(0) = x f() = x’inv(v) [X:= f() ] 0 ≤ ≤ flow(v ) [X, •X:= f(), •f()] veri

Thomas A. Henzinger,The Theory of Hybrid Automata,Proc. 11th LICS Conf. (1996) 278-292

Marionette virtuali

Il sistema

All’esterno è un processo veramente continuo, almeno a tratti, che viene rilevato secondo certi intervalli di tempo dai sensori.

Questi innescano delle procedure all’interno costanti, ma su intervalli di tempo reali (almeno in prima approssimazione).

Esistono uno o più sistemi temporali sia interni che esterni.

Descrizione del sistema interno

Usare soltanto durate e corrispondenze temporali

Non ci domandiamo perché e come accadano certe transizioni,Ma le osserviamo

Osservabilità e nondeterminismo

Un processo può essere descritto osservando il suo comportamento dall’esterno.Non è detto che la stessa osservazione porti nello stesso statoÈ suggerita una struttura ad albero

a

b c

d a

b c

La nozione di processo

a.P a PPi a Qi

P1+P2 a Qi

ed altri operatori…..

Il tempo discreto

N01

32

4

A = {a,b,c,d,…}

aacb

Alberi discreti

N0

1

3

2

Set

≤≤

≤

Il tempo continuo a gradini

A = {a,b,c,d,…}

(a,r1 ) (a,r2 - r1 ) (c, r3 - r2 ) (b, r4 - r3 )

R+

0

r1

r2

r3

r4

Il tempo continuo

F = {f,g,h,k,…}

(f |r1 ) (f |r2 - r1 ) (h |r3 - r2 ) (g |r4 - r3 )

R+

0

r1

r2

r3

r4

Alberi continui

SetR+

0

r1

r2

r3

r4

Le categorie di alberi

Un albero è un insieme di cammini etichettati ed incollati lungo un’etichetta che è un prefisso comune.

Questo significa che, a sua volta un albero è una categoria arricchita su una 2-categoria localmente posetale L

Un morfismo di L-alberi è un L-funtore: una funzione tra cammini che rispetta strettamente l’etichettatura e può far crescere l’incollamento, cioè una simulazione che tende a diminuire il non determinismo

t = (X, e, d) :

i. un insieme di cammini: X

ii. una funzione etichettatura e: X L,

ii. una funzione incollamento d : X X L

t.c. per ogni x, y, z in X,

- d (x, x) = e(x)- d(x, y) ≤ e (x) ˙ e (y)- d(x, y) ˙ d(y, z) ≤d(x, z)- d (x, y) = d (y, x)

Gli alberi

Un morfismo f : t1 t2

è una funzione f : X1 X2 tale che

i. e2 (f(x)) = e1 (x)

ii. d1 (x, y) ≤ d2 (f(x), f(y))

a

cb c bb

a a

b cc

b

a

a

Operazioni tra alberiSomma:

t1 + t2 = < X, e, d> , dove

- X = X1 X2

- e (x1) = e1 (x1) - e (x2) = e2 (x2)

di (x, y) se x, y Xi

- d ( x, y) = altrimenti

•0 = <Ø , Ø, Ø> è l’unità

Esempio

Operazioni tra alberi

Concatenazione:

t1 t2 = < X, e, d> , dove

- X = X1 X2

- e (< x1, x2 >) = e1 (x1) . e2 (x2)

d1 (x1, y1).d2 (x2, y2) se x1 = y1

- d (< x1, x2 >, < y1, y2 >) = d1 (x1, y1) altrimenti

•1 = <{ x } , e (x) = , d (x, x) = > is l’elemento neutro•Tree(A) monoidale chiusa a destra•La concatenazione distribuisce a destra sulla somma

Esempio

Esempi di 2-categorie di base: le strutture temporali

•A* monoide libero sull’alfabeto A, funzioni parziali da N ad A

•CA funzioni parziali costanti a gradino da R+ ad A

•CF funzioni parziali continue a tratti

•TA monoide a tracce, ecc.

In generale: L monoide che sia anche un inf-semireticolo

Più in generale sistemi di tracce con rendez-vous (vedremo più avanti)

Etichettatura con tracce di Mazurkiewicz: A*/IParole con possibilità di invertire certe lettere [a,b]

Il tempo non completamente ordinato

c

b[a,b]

c

Sincronizzazione e fusione

Tempo globale: SincronizzazioneTempi relativi: Rendez-vous

Sincronizzazione

Definiamo una tabella di sincronizzazione per coppie di mosse “contemporanee” e costruiamo l’albero che viene etichettato con i risultati.

La sicronizzazione può essere: handshaking, a braccetto, ecc.

t1 ※ t2 = < X, e, d> , dove

- X X1 X2

- e (< x1, x2 >) = e1 (x1) * e2 (x2)

- d (< x1, x2 >, < y1, y2 >) = (e1 (x1) * e2 (x2)) (e1 (y1) * e2 (y2))

Tagliato eventualmente alla lunghezza minima tra d1(x1, y1) e d2(x2, y2) altrimenti

Esempio

※

db

a a

a

a

b

cd

d

a

b

a

Fusione

Etichettatura sui prefissi,ma incollamento su opportuni sottoinsiemi:

Ogni sottoprocesso ha il suo tempo

Una nuova struttura di frecce tra le parole

(X, e, d) (X’, e’, d’) :

i. un insieme di cammini: X X’

ii. una funzione etichettatura e e’: X X’ A *,

ii. una funzione incollamento : X X’ ANNNN

t.c. per ogni x, y in X, x’, y’ in X’

- (x,x’) s.i. consistente di e(x) e di e(x’)- d (y, x) (x,x’) (y,x’) - (x,x’) d’(x’, y’) (x,y’) - (x, x’) = (x’, x)

Fusione tra alberi (caso discreto)

Notare l’analogia con la nozione di alberoIn realtà sono cambiate soltanto le frecce della categoria di base:

Gli oggetti continuano ad essere prefissi, le frecce sono soltanto insiemi consistenti

x y

e(x) e(y)

a(x,y)

Arricchimenti doppi

Coesistenza di due tipi di tempoLoro sincronizzazione per prefisso

Caso di comportamento ibrido

t = (X, e, d) :

i. un insieme di cammini: X

ii. una funzione etichettatura e: X CF CA,

cioè e-: X CF ed e+: X CA

iii. per ogni x, y in X una funzione incollamento monotona

dx,y : [e-(x), e-(y) ] [e+(x), e+(y) ]

t.c. per ogni x, y, z in X,-dx,x [e-(x), e-(x) ] [e+(x), e+(x) ] rispetta il massimo

- d(x, y) ≤ e (x) ˙ e (y)- dx,y ˙ dy,z ≤dx,z

- dx,y = dy,x

Attenzione!la situazione non è simmetrica rispetto alle due etichettature

Da una parte dobbiamo prendere tutti i prefissi comuni, dall’altra no:questo vuol dire che abbiamo nondeterminismo soltanto a destra.

Si potrebbe generalizzare prendendo relazioni al posto di funzioni

Esempio

x

dx,x [e-(x), e-(x) ] [e+(x), e+(x) ] potrebbe essere indottadalla funzione sugli istanti di tempo {ri} {si}, così

dx,y [e-(x), e-(y) ] [e+(x), e+(y) ]

e-(x) = (f |r1 ) (f |r2 - r1 ) (h |r3 - r2 ) (g |r4 - r3 )e+(x) = (a,s1 ) (a,s2 - s1 ) (c, s3 - s2 ) (b, s4 - s3 )

e-(x) e+(x)

e-(y) = (f |r1 ) (f |r2 - r1 ) (h |r’3 - r2 ) (k |r’4 - r’3)e+(y) = (a,s1 ) (a,s2 - s1 ) (c, s’3 - s2 ) (d, s’4 - s’3 )

y

e-(y) e+(y)

A che servono i metodi formali?

A che servono i metodi formali?

Servono a capire

Vengono prima o dopo la pratica?

Si intercalano