ESERCIZI Pi-CALCULUS and PICT
Esercizio 1
Giustificare l'introduzione del "new {v}-A in " nella
conclusione della regola COM nella descrizione formale
della Labelled Reduction relation a pag. 10 di [PS].
Esercizio 2
Supponiamo di estendere PICT con la comunicazione sincrona,
definita dalla seguente regola di riduzione:
c!y.P | c?w.Q --> P | Q[y/w]
Dimostrare informalmente che il processo
c!y.P | c?w.Q
con comunicazione sincrona e' equivalente al processo
new k: ^[]
c![y k] | k?[].P | c?[w k].(k![] | Q)
con comunicazione asincrona.
Esercizio 3
Programmare in PICT i tre filosofi a cena,
supponendo di avere mangia1, mangia2 e mangia3
che sono i tre processi relativi alle azioni eseguite dai tre
filosofi una volta acquisite le due forchette.
Possibile soluzione.
Esercizio 4
Esercizio 5
Esercizio 6
Definire in generale la nozione di sottotipo.
Quali sono i tipi utilizzati in PICT? Esiste in PICT la nozione
di sottotipo? In caso affermativo, come viene definita ed utilizzata?
In caso negativo, perche' tra i tipi di PICT non e' possibile definire la
nozione di sottotipo?
Esercizio 7 (a.a. 10/11 e precedenti)
Fornire sintassi e regole di riduzione del Pi-calculus fornendone
significato e giustificazione.
Esercizio 8
Si consideri il seguente programma PICT
def consumer channel:^Int =
channel?i = ( printi!i
| consumer!channel
)
def producer [channel:^Int i:Int] =
if (== i 0)
then ()
else ( channel!i
| producer![channel (dec i)]
)
new ch:^Int
run consumer!ch
run producer![ch 4]
Descrivere il suo comportamento e l'eventuale output.
Cosa sono i responsive channels in PICT? Per quale motivo sono
stati introdotti?
Esercizio 9
Cos'e' la structural congruence per i termini del pi-calcolo?
La seguente condizione, che deve essere soddisfatta dalla
structural congruence, e' scritta correttamente?
P | new x in Q ≡ new x in (P | Q)
Perche' e' indispensabile postulare la validita' di questa
condizione? qual e' il suo scopo?
Esercizio 10
Fornire un controesempio al fatto che,
nella definizione dell'LTS, non e' possible sostituire
le regole (COM) e (OPEN) semplicemente con
_
A|- P --xv-> P' A|- Q --xv-> Q'
________________________________________
A|- P|Q --τ--> P'|Q'
(e ovviamente eliminando anche la seconda premessa dalla regola (RES))
Possibile soluzione.
Esercizio 11 (non banale)
Supponiamo di avere un processo RESOURCE-proc che implementa in PICT
una risorsa leggibile o scrivibile.
Tale risorsa puo' esser letta contemporaneamente da piu' processi
lettori, ma scritta da un solo processo scrittore.
Implementare in PICT un processo controllore che gestisca gli accessi
alla risorsa da parte dei processi lettori e scrittori, implementando
schematicamente anche questi ultimi.
Per semplicita' non si richiede che il sistema goda della
proprieta' di fairness.
Una volta pero' che il controller appura la presenza di una richiesta
di scrittura, a questa vien data precedenza.
Possibile soluzione.
Esercizio 12
- define in haskell the data type of pict (simple) values
- define the data type of patterns
- define the data types of bindings
- define the pattern matching operation
Esercizio 13
Define the the subtype relation of PICT by means of a formal system
with judgments of the form S < T.
Esercizio 14
Realizzare la funzione che calcola l'n-esimo elemento della sequenza di
Fibonacci come programma Core PICT (senza utilizzare cioe' le forme
derivate, sullo stile del processo fact del testo)
Possibile soluzione (by S.Greco)
Esercizio 15
Esercizio 16
Esercizio 17
Esercizio 17
Definire la nozione di riduzione per i termini del π-calcolo.
Perche' tale relazione conviene descriverla anche come LTS (labelled transition
system)? Quali vantaggi ne derivano?
Esercizio 18
Definire la grammatica dei processi del pi-calcolo e dare formalmente
la definizione di insieme dei nomi legati di un processo, bn(P), e
dei nomi liberi, fn(P).
Esercizio 19
Supponiamo di avere un sistema composto da un processo server e due processi
client.
Il processo server riceve in continuazione dei numeri che i vari client
inviano, li incrementa di uno e rispedisce indietro il risultato.
Il primo client invia il numero 3, mentre il secondo invia 5.
Entrambi i client, una volta ricevuto il numero incrementato, lo stampano.
Ovviamente il sistema rispetta il vincolo che ogni client deve riceve indietro l'incremento del numero che lui aveva inviato, non del numero inviato dall'altro client.
Implementare in Pict due versioni differenti del sistema, una in cui il rispetto del vincolo avviene attraverso l'uso di canali privati, l'altra in cui la ricezione del risultato
avviene attraverso un canale comune ai client ed in cui
il rispetto del vincolo avviene
attraverso l'implementazione di una mutua esclusione tra i client
rispetto all'invio del numero e ricezione del risultato.
Possibile soluzione.
Esercizio 20
Input channel types e Output channel types in PICT: discuterne e fornire un
esempio di programma PICT che ne faccia uso.
Cosa va inserito al posto di "??" affinche' la seguente regola sia una
regola corretta per il subtyping di PICT? Giustificare brevemente.
S ?? T
----------
?S < ?T
Esercizio 21
Esercizio 22
Esercizio 23
PICT ed Erlang: discutere delle caratteristiche comuni e delle principali
differenze.
Esercizio 24
Il seguente programma dovrebbe stampare "ping" e "pong" alternativamente.
Ritardi nell'esecuzione di print!"ping" o print!"pong" potrebbero pero'
impedire che cio' avvenga correttamente.
Modificare il codice utilizzando il canale pr al posto di print in modo da
garantire l'alternanza di "ping" e "pong".
def ping n:Int =
if (== n 0) then
()
else
( print!"ping"
| pong!(dec n)
)
and pong n:Int =
if (== n 0) then
()
else
( print!"pong"
| ping!(dec n)
)
Ricordiamo che sul canale predefinito pr viene inviata una tupla
formata da una stringa da stampare ed un canale responsive su cui
viene inviato un segnale [] di sincronizzazione a stampa avvenuta.
Possibile soluzione.
Esercizio 25
Cosa si intende per LTS nel contesto del π-calcolo? Qual e' il vantaggio
di utilizzare un LTS per studiare il π-calcolo al posto della relazione
di riduzione? Qual e' la relazione tra LTS e relazione di riduzione per il
π-calcolo?
Esercizio 26
Dimostrare formalmente che in Pict si puo' sostituire un
canale di tipo
![T1 ![T2]]
con uno di tipo
![T1' ![T2']]
se si suppone che T1<:T1' e che T2'<:T2
Possibile soluzione.
Esercizio 27
Definire un processo Core PICT
che stampi (non necessariamente nel loro ordine) tutti i numeri
dispari.
Possibile soluzione.
Esercizio 28 i (non banale)
Assume a cigarette requires three ingredients to smoke:
Tobacco
Smoking Paper
A match
Assume there are also three chain smokers around a table,
each of whom has an infinite supply of one of the three ingredients,
one smoker has an infinite supply of tobacco, another has an infinite supply of paper,
and the third has an infinite supply of matches.
Assume there is also a non-smoking arbiter.
The arbiter enables the smokers to make their cigarettes
selecting two of the smokers with a round robin policy (the original
problem uses a non deterministic choice), taking one item out of each of their supplies,
and placing the items on the table.
He then notifies the third smoker that he has done this.
The third smoker removes the two items from the table and uses them (along with his own supply)
to make a cigarette, which he smokes for a while.
Meanwhile, the arbiter, seeing the table empty, again chooses two smokers at random and places
their items on the table. This process continues forever.
The smokers do not hoard items from the table; a smoker only begins to roll a new cigarette
once he is finished smoking the last one.
If the arbiter places tobacco and paper on the table while the match man is smoking,
the tobacco and paper will remain untouched on the table until the match man is finished
with his cigarette and collects them.
[From http://en.wikipedia.org/wiki/Cigarette_smokers_problem ]
Implementare in PICT il sistema dei cigarette smokers.
Scketch di possibile soluzione.
Esercizio 29
Nel seguente codice PICT il def increment rappresenta un server che incrementa numeri
e che invia il risultato su un canale pubblico result.
Due clienti utilizzano il server increment in mutua esclusione, utilizzando il canale
lock.
Tali clienti hanno un comportamento finito (utilizzano il numero incrementato con la parte USE(-), non meglio specificata)
e terminano.
Modificare il sistema in modo da avere i due client che,
partendo rispettivamente da 3 e da 4,
una volta utilizzato il risultato incrementato,
lo rimandano nuovamente al server per un nuovo
incremento ed un nuovo utilizzo, all'infinito.
new lock:^[]
new result:^Int
def increment n:Int =
result!(+ 1 n)
run ( lock![]
| lock?[] = ( increment!3
| result?m = ( USE(m)
| lock![]
) )
| lock?[] = ( increment!5
| result?m = ( USE(m)
| lock![]
) ) )
Possibile soluzione.
Esercizio 30
Nei testi e' riportata una frase di K.Bruce in cui si afferma
che tra i principali vantaggi dei linguaggi statically typed
c'e' quello che i tipi forniscono
"extra information that can be used in compiler optimizations".
Motivare la validita' di questa affermazione utilizzando
PICT come esempio.
Esercizio 31
Il seguente processo PICT simula il calcolo del fattoriale
eseguito dal seguente programma Haskell:
fact 0 = 1
fact n = n*(fact (n-1))
def fact [n:Int r:!Int] =
( new br:^Bool
( ==![n 0 (rchan br)]
| br?b =
if b then
r!1
else
( new nr:^Int
( -![n 1 (rchan nr)]
| nr?nMinus1 =
(new fr:^Int
( fact![nMinus1 fr]
| fr?f =
*![f n (rchan r)]
) ) ) )
Scrivere un programma PICT che simuli il calcolo del fattoriale
per ricorsione di coda, cioe' calcolato dal seguente programma Haskell
factaux 0 c = c
factaux n c = factaux (n-1) c*n
fact n = factaux n 1
Possibile soluzione.
Esercizio 32
Si considerino i due seguenti processi PICT.
run ( x!y
| x?z = z!u
| y?w = print!"Got it!"
)
run ( x!y
| x?z = a!z
| a?w = print!"Got it!"
)
Tali processi, se eseguiti isolatamente, hanno
lo stesso effetto. Giustificare tale affermazione.
Definire poi un processo PICT che si comporti in modo differente a seconda che
il primo o il secondo dei processi precedenti viene utilizzato come sottoprocesso.
Possibile soluzione.
Esercizio 33
Supponiamo di avere un processo PICT che concateni stringhe, a cui si accede
tramite il canale concat:/[String String /String].
Scrivere un processo con cui si comunica tramite un canale
pingpong:/[Int ^String Bool] che restituisce sul canale fornito
in input la concatenazione di "ping" e "pong" n volte, iniziando da "ping"
o "pong" a seconda del valore booleano inviato.
[Aiutino:utilizzare lo schema della funzione fact dove i processi simulano
chiamate ricorsive di funzioni]
Possibile soluzione.
Esercizio 34
Che cosa si intende con scope extrusion nel π-calcolo?
Come si formalizza tale nozione nella relazione di riduzione che vede
un insieme di processi come in sistema chiuso (che non ha cioe' alcuna interazione
con l'ambiente esterno)?
Esercizio 35
Si descriva un session type che rappresenti (dalla parte del server) il protocollo di interazione
con un server che permette di effettuare una votazione.
Il protocollo e' descritto informalmente nel modo seguente.
Si effettua un login inserendo stringa come password.
Se la password e' scorretta viene segnalato un errore, altrimenti si procede
dando la possibilita' di votare per l'elezione del sindaco o per quella della giunta.
La votazione procede fornendo il nome del sindaco, se si intende votare per il sindaco,
oppure con due nomi, nel caso della giunta.
Se il nome inserito non e' tra i candidati ammissibili si comunica un errore, altrimenti
viene fornito a chi vota un valore numerico che corrisponde ad una ricevuta di avvenuta votazione.
Possibile soluzione.
Esercizio 36
Supponiamo di avere un sistema composto da un processo server e due processi
client.
Il processo server riceve in continuazione dei numeri che i vari client
inviano, li incrementa di uno e rispedisce indietro il risultato.
Il primo client invia il numero 3, mentre il secondo invia 5.
Entrambi i client, una volta ricevuto il numero incrementato, lo stampano.
Ovviamente il sistema rispetta il vincolo che ogni client deve ricevere indietro l'incremento del numero che lui
aveva inviato, non del numero inviato dall'altro client.
La seguente e' una implementazione parziale in PICT.
Si completi tale soluzione.
def server [channel:^Int ack:^[]] =
channel?i = (channel!(i+1) | ack?[] = ..... )
new lock:^[]
def client [chan:^Int ack:^[] n:Int] =
lock?[] = (chan!n | chan?num = .....)
run( new ch1:^Int
new ack:^[]
lock![]
( server!....
| ...........
| ...........
)
Possibile soluzione.
Esercizio 37
Supponiamo di avere un sistema composto da un processo server e due processi
client.
Il processo server riceve in continuazione dei numeri che i vari client
inviano, li incrementa di uno e rispedisce indietro il risultato.
Il primo client invia il numero 3, mentre il secondo invia 5.
Entrambi i client, una volta ricevuto il numero incrementato, lo stampano.
Ovviamente il sistema rispetta il vincolo che ogni client deve riceve indietro l'incremento del numero che lui
aveva inviato, non del numero inviato dall'altro client.
Si consideri la seguente implementazione parziale, in cui
le comunicazione avvengono attraverso un canale comune ai client e al server,
ed in cui il rispetto del vincolo e' realizzato tramite mutua esclusione
tra i client.
def server [channel:^Int] =
channel?i = (channel!(i+1) | server!channel)
def client .................
run( new ch1:^Int
......
(server!ch1
| .....
)
Si completi il codice.
Possibile soluzione.
Esercizio XX
Possibile soluzione.