Ugo de’Liguoro
Università di Torino, Dipartimento di Informatica, Torino, Italy deligu@di.unito.it
https://orcid.org/0000-0003-4609-2783
Luca Padovani
Università di Torino, Dipartimento di Informatica, Torino, Italy luca.padovani@unito.it
https://orcid.org/0000-0001-9097-1297 Abstract
We propose a type system for reasoning on protocol conformance and deadlock freedom in net-works of processes that communicate through unordered mailboxes. We model these netnet-works in the mailbox calculus, a mild extension of the asynchronous π-calculus with first-class mailboxes and selective input. The calculus subsumes the actor model and allows us to analyze networks with dynamic topologies and varying number of processes possibly mixing different concurrency abstractions. Well-typed processes are deadlock free and never fail because of unexpected mes-sages. For a non-trivial class of them, junk freedom is also guaranteed. We illustrate the expres-siveness of the calculus and of the type system by encoding instances of non-uniform, concurrent objects, binary sessions extended with joins and forks, and some known actor benchmarks.
2012 ACM Subject Classification Theory of computation → Type structures, Theory of com-putation → Process calculi, Software and its engineering → Concurrent programming structures, Software and its engineering → Message passing
Keywords and phrases actors, concurrent objects, first-class mailboxes, unordered communica-tion protocols, behavioral types, protocol conformance, deadlock freedom, junk freedom
Digital Object Identifier 10.4230/LIPIcs.ECOOP.2018.15
Related Version Proofs and additional examples are found in the related technical report [17], https://arxiv.org/abs/1801.04167.
Acknowledgements The authors are grateful to the anonymous reviewers for their valuable feedback. The second author misses his beloved cat Arturo, who passed away on January 8, 2018. Much of this paper was written next to Arturo during the last weeks of his long illness.
1
Introduction
Message passing is a key mechanism used to coordinate concurrent processes. The order in which a process consumes messages may coincide with the order in which they arrive at destination (ordered processing) or may depend on some intrinsic property of the messages themselves, such as their priority, their tag, or the shape of their content (out-of-order or selective processing). Ordered message processing is common in networks of processes connected by point-to-point channels. Out-of-order message processing is common in networks of processes using mailboxes, into which processes concurrently store messages and from which one process selectively receives messages. This communication model is typically found in the various implementations of actors [26, 1] such as Erlang [3], Scala and Akka actors [24], CAF [8] and Kilim [52]. Non-uniform, concurrent objects [50, 48, 15] are also
© Ugo de’Liguoro and Luca Padovani;
1 c l a s s A c c o u n t (var b a l a n c e : D o u b l e ) e x t e n d s S c a l a A c t o r [ A n y R e f ] { 2 p r i v a t e val s e l f = t h i s 3 o v e r r i d e def p r o c e s s ( msg : A n y R e f ) { 4 msg m a t c h { 5 c a s e dm : D e b i t M e s s a g e = > 6 b a l a n c e += dm . a m o u n t 7 val s e n d e r = dm . s e n d e r . a s I n s t a n c e O f [ A c c o u n t ] 8 s e n d e r . s e n d ( R e p l y M e s s a g e . O N L Y ) 9 c a s e cm : C r e d i t M e s s a g e = > 10 b a l a n c e -= cm . a m o u n t 11 val s e n d e r = cm . s e n d e r . a s I n s t a n c e O f [ S c a l a A c t o r [ A n y R e f ]] 12 val r e c i p i e n t = cm . r e c i p i e n t . a s I n s t a n c e O f [ A c c o u n t ] 13 r e c i p i e n t . s e n d (new D e b i t M e s s a g e ( self , cm . a m o u n t )) 14 r e c e i v e { 15 c a s e rm : R e p l y M e s s a g e = > 16 s e n d e r . s e n d ( R e p l y M e s s a g e . O N L Y ) 17 } 18 c a s e _ : S t o p M e s s a g e = > e x i t () 19 c a s e m e s s a g e = > 20 val ex = new I l l e g a l A r g u m e n t E x c e p t i o n ( " U n s u p p o r t e d ␣ m e s s a g e " ) 21 ex . p r i n t S t a c k T r a c e ( S y s t e m . err ) 22 } 23 } 24 }
Listing 1 An example of Scala actor taken from the Savina benchmark suite [32].
examples of out-of-order message processors. For example, a busy lock postpones the processing of anyacquiremessage until it is released by its current owner. Out-of-order message processing adds further complexity to the challenging task of concurrent and parallel application development: storing a message into the wrong mailbox or at the wrong time, forgetting a message in a mailbox, or relying on the presence of a particular message that is not guaranteed to be found in a mailbox are programming mistakes that are easy to do and hard to detect without adequate support from the language and its development tools.
The Scala actor in Listing 1, taken from the Savina benchmark suite [32], allows us to illustrate some of the subtle pitfalls that programmers must carefully avoid when dealing with out-of-order message processing. Theprocess method matches messages found in the actor’s mailbox according to their type. If a message of typeDebitMessageis found, then balance is incremented by the deposited amount and the actor requesting the operation is notified with a ReplyMessage(lines 5–8). If a message of type CreditMessage is found, balanceis decremented by the amount that is transferred torecipient(lines 9–13). Since the operation is meant to be atomic, the actor temporarily changes its behavior and waits for aReplyMessagefromrecipientsignalling that the transfer is complete, before notifying senderin turn (lines 14–17). A message of typeStopMessageterminates the actor (line 18).
Note how the correct execution of this code depends on some key assumptions:
ReplyMessageshould be stored in the actor’s mailbox only when the actor is involved in a transaction, or else the message would trigger the “catch all” clause that throws a “unsupported message” exception (lines 19–21).
No debit or credit message should be in the actor’s mailbox by the time it receives StopMessage, or else some critical operations affecting the balance would not be performed.
Two distinct accounts should not try to simultaneously initiate a transaction with each other. If this were allowed, each account could consume the credit message found in its own mailbox and then deadlock waiting for a reply from the other account (lines 14–17). Static analysis techniques that certify the validity of assumptions like these can be valuable for developers. For example, session types [29] have proved to be an effective formalism for the enforcement of communication protocols and have been applied to a variety of programming paradigms and languages [2], including those based on mailbox communications [41, 7, 19, 43]. However, session types are specifically designed to address point-to-point, ordered interactions over channels [27]. Retrofitting them to a substantially different communication model calls for some inevitable compromises on the network topologies that can be addressed and forces programmers to give up some of the flexibility offered by unordered message processing.
Another aspect that complicates the analysis of actor systems is that the pure actor model as it has been originally conceived [26, 1] does not accurately reflect the actual practice of actor programming. In the pure actor model, each actor owns a single mailbox and the only synchronization mechanism is message reception from such mailbox. However, it is a known fact that the implementation of complex coordination protocols in the pure actor model is challenging [54, 53, 33, 9]. These difficulties have led programmers to mix the actor model with different concurrency abstractions [31, 53], to extend actors with controlled forms of synchronization [54] and to consider actors with multiple/first-class mailboxes [23, 33, 9]. In fact, popular implementations of the actor model feature disguised instances of multiple/first-class mailbox usage, even if they are not explicitly presented as such: in Akka, the messages that an actor is unable to process immediately can be temporarily stashed into a different mailbox [23]; in Erlang, hot code swapping implies transferring at runtime the input capability on a mailbox from a piece of code to a different one [3].
In summary, there is still a considerable gap between the scope of available approaches used to analyze mailbox-based communicating systems and the array of features used in programming these systems. To help narrowing this gap, we make the following contributions: We introduce mailbox types, a new kind of behavioral types with a simple and intuitive semantics embodying the unordered nature of mailboxes. Mailbox types allow us to de-scribe mailboxes subject to selective message processing as well as mailboxes concurrently accessed by several processes. Incidentally, mailbox types also provide precise information on the size of mailboxes that may lead to valuable code optimizations.
We develop a mailbox type system for the mailbox calculus, a mild extension of the asynchronous π-calculus [51] featuring tagged messages, selective inputs and first-class mailboxes. The mailbox calculus allows us to address a broad range of systems with dynamic topology and varying number of processes possibly using a mixture of concurrency models (including multi-mailbox actors) and abstractions (such as locks and futures). We prove three main properties of well-typed processes: the absence of failures due to unexpected messages (mailbox conformance); the absence of pending activities and messages in irreducible processes (deadlock freedom); for a non-trivial class of processes, the guarantee that every message can be eventually consumed (junk freedom).
We illustrate the expressiveness of mailbox types by presenting well-typed encodings of known concurrent objects (locks and futures) and actor benchmarks (atomic transactions and master-workers parallelism) and of binary sessions extended with forks and joins. In discussing these examples, we emphasize the impact of out-of-order message processing and of first-class mailboxes.
Structure of the paper. We start from the definition of the mailbox calculus and of the properties we expect from well-typed processes (Section 2). We introduce mailbox types (Section 3.1) and dependency graphs (Section 3.2) for tracking mailbox dependencies in processes that use more than one. Then, we present the typing rules (Section 3.3) and the soundness results of the type system (Section 3.4). In the latter part of the paper, we discuss a few more complex examples (Section 4), related work (Section 5) and ideas for further developments (Section 6).
2
The Mailbox Calculus
We assume given an infinite set of variables x, y, an infinite set of mailbox names a, b, a set of tagsmand a finite set of process variables X. We let u, v range over variables and mailbox names without distinction. Throughout the paper we write e for possibly empty sequences e1, . . . , en of various entities. For example, u stands for a sequence u1, . . . , un of names and
{u} for the corresponding set.
The syntax of the mailbox calculus is shown below:
Process P, Q ::= done | u!m[v] | G | P | Q | (νa)P | X[u] Guard G, H ::= fail u | free u.P | u?m(x).P | G + H
The term done represents the terminated process that performs no action. The term u!m[v] represents a message stored in mailbox u. The message has tagmand arguments v. A guarded process G is a composition of actions offered on a mailbox. Actions will be described in a moment. We assume that all actions in the same guard refer to the same mailbox u. The term P | Q represents the parallel composition of P and Q and (νa)P represents a restricted mailbox a with scope P . The termX[u] represents the invocation of the process namedX
with parameters u. For each process variableX we assume that there is a corresponding global process definition of the formX(x), P . The actionfailu represents the process that fails with an error for having received an unexpected message from mailbox u. The action
freeu.P represents the process that deletes the mailbox u if u is empty and then continues as P . The action u?m(x).P represents the process that receives an m-tagged message from mailbox u and then continues as P with x replaced by the message’s arguments. A compound guard G + H offers all the actions offered by G and H. The notions of free and bound names of a process P are standard and respectively denoted by fn(P ) and bn(P ).
The operational semantics of the mailbox calculus is mostly conventional. We use the structural congruence relation ≡ defined below to rearrange equivalent processes:
faila + G ≡ G G + H ≡ H + G G + (H + H0) ≡ (G + H) + H0
done| P ≡ P P | Q ≡ Q | P P | (Q | R) ≡ (P | Q) | R
(νa)(νb)P ≡ (νb)(νa)P (νa)P | Q ≡ (νa)(P | Q) if a 6∈ fn(Q) Structural congruence captures the usual commutativity and associativity laws of guard and process composition, withfail anddoneacting as the respective units. Additionally, the order of mailbox restrictions is irrelevant and the scope of a mailbox may shrink or extend dynamically. The reduction relation → is inductively defined by the rules
[r-read] a!m[c] | a?m(x).P + G → P {c/x} [r-free] (νa)(free a.P + G) → P
[r-def] X[c] → P {c/x} ifX(x), P [r-par] P | R → Q | R if P → Q [r-new] (νa)P → (νa)Q if P → Q
where P {c/x} denotes the usual capture-avoiding replacement of the variables x with the mailbox names c. Rule[r-read]models the selective reception of anm-tagged message from mailbox a, which erases all the other actions of the guard. Rule[r-free]is triggered when the process is ready to delete the empty mailbox a and no more messages can be stored in a because there are no other processes in the scope of a. Rule[r-def]models a process invocation by replacing the process variableX with the corresponding definition. Finally, rules[r-par], [r-new] and [r-struct] close reductions under parallel compositions, name restrictions and structural congruence. We write →∗ for the reflexive and transitive closure of →, we write P X→∗Q if not P →∗Q and P X→ if P X→ Q for all Q.
Hereafter, we will occasionally use numbers and conditionals in processes. These and other features can be either encoded or added to the calculus without difficulties.
IExample 1 (lock). In this example we model a lock as a process that waits for messages from a self mailbox in which acquisition and release requests are stored. The lock is either free or busy. When in state free, the lock nondeterministically consumes anacquiremessage from self . This message indicates the willingness to acquire the lock by another process and carries a reference to a mailbox into which the lock stores areply notification. When in state busy, the lock waits for areleasemessage indicating that it is being released:
FreeLock(self ),free self .done
+ self ?acquire(owner ).BusyLock[self , owner ] + self ?release.failself
BusyLock(self , owner ), owner!reply[self ] | self ?release.FreeLock[self ]
Note the presence of thefreeself guard in the definition ofFreeLockand the lack thereof inBusyLock. In the former case, the lock manifests the possibility that no process is willing to acquire the lock, in which case it deletes the mailbox and terminates. In the latter case, the lock manifests its expectation to be eventually released. Also note thatFreeLock fails if it receives areleasemessage. In this way, the lock manifests the fact that it can be released only if it is currently owned by a process. A system where two users alice and carol compete for acquiring lock can be modeled as the process
(νlock)(νalice)(νcarol)(FreeLock[lock] |User[alice, lock] |User[carol, lock]) (1) where
User(self , lock), lock!acquire[self ] | self ?reply(l).(l!release|free self .done) Note that Useruses the reference l – as opposed to lock – to release the acquired lock. As we will see in Section 3.3, this is due to the fact that it is this particular reference to the lock’s mailbox – and not lock itself – that carries the capability to release the lock.
IExample 2 (future variable). A future variable is a one-place buffer that stores the result of an asynchronous computation. The content of the future variable is resolved once and for all by the producer once the computation completes. After that, its content can be retrieved any number of times by the consumers. If a consumer attempts to retrieve the content of the future variable beforehand, the consumer suspends until the variable is resolved. We can model a future variable thus:
Future(self ), self ?put(x).Present[self , x]
Present(self , x) ,free self .done
+ self ?get(sender ).(sender !reply[x] |Present[self , x]) + self ?put.fail self
The processFuturerepresents an unresolved future variable, which waits for aputmessage from the producer. Once the variable has been resolved, it behaves as specified byPresent, namely it satisfies an arbitrary number ofgetmessages from consumers but it no longer acceptsputmessages.
IExample 3 (bank account). Below we see the process definition corresponding to the actor shown in Listing 1. The structure of the term follows closely that of the Scala code:
Account(self , balance) , self ?debit(amount, sender ).
(sender !reply|Account[self , balance + amount]) + self ?credit(amount, recipient, sender ).
(recipient!debit[amount, self ] |
self ?reply.(sender !reply|Account[self , balance + amount])) + self ?stop.free self .done
+ self ?reply.failself
The last term of the guarded process, which results in a failure, corresponds to the catch-all clause in Listing 1 and models the fact that areply message is not expected to be found in the account’s mailbox unless the account is involved in a transaction. Thereply message is received and handled appropriately in thecredit-guarded term.
We can model a deadlock in the case two distinct bank accounts attempt to initiate a transaction with one another. Indeed, we have
Account[alice, 8] | alice!credit[2, carol, bank] |
Account[carol, 9] | carol!credit[5, alice, bank] →
∗carol!debit[2, alice] | alice?reply. . . | alice!debit[5, carol] | carol?reply. . . where both alice and carol ignore the incomingdebitmessages, whence the deadlock.
We now provide operational characterizations of the properties enforced by our typing discipline. We begin with mailbox conformance, namely the property that a process never fails because of unexpected messages. To this aim, we define a process contextC as a process in which there is a single occurrence of an unguarded hole [ ]:
C ::= [ ] | C | P | P | C | (νa)C
The hole is “unguarded” in the sense that it does not occur prefixed by an action. As usual, we writeC [P ] for the process obtained by replacing the hole in C with P . Names may be captured by this replacement. A mailbox conformant process never reduces to a state in which the only action of a guard isfail:
IDefinition 4. We say that P is mailbox conformant if P X→∗C [faila] for allC and a. Looking at the placement of the fail u actions in earlier examples we can give the following interpretations of mailbox conformance: a lock is never released unless it has been acquired beforehand (Example 1); a future variable is never resolved twice (Example 2); an account will not be notified of a completed transaction (with areply message) unless it is involved in an ongoing transaction (Example 3).
We express deadlock freedom as the property that all irreducible residuals of a process are (structurally equivalent to) the terminated process:
IDefinition 5. We say that P is deadlock free if P →∗Q
X→ implies Q ≡done.
According to Definition 5, if a deadlock-free process halts we have that: (1) there is no sub-process waiting for a message that is never produced; (2) every mailbox is empty. Clearly, this is not the case for the transaction between alice and carol in Example 3.
IExample 6 (deadlock). Below is another example of deadlocking process usingFuturefrom Example 2, obtained by resolving a future variable with the value it does not contain yet:
(νf )(νc)(Future[f ] | f !get[c] | c?reply(x).freec.f !put[x]) (2) Notice that attempting to retrieve the content of a future variable not knowing whether it has been resolved is legal. Indeed,Futuredoes not fail if agetmessage is present in the future variable’s mailbox before it is resolved. Thus, the deadlocked process above is mailbox conformant but also an instance of undesirable process that will be ruled out by our static analysis technique (cf. Example 21). We will need dependency graphs in addition to types to flag this process as ill typed.
A property stronger than deadlock freedom is fair termination. A fairly terminating process is a process whose residuals always have the possibility to terminate. Formally:
IDefinition 7. We say that P is fairly terminating if P →∗Q implies Q →∗done. An interesting consequence of fair termination is that it implies junk freedom (also known as lock freedom [34, 44]) namely the property that every message can be eventually consumed. Our type system does not guarantee fair termination nor junk freedom in general, but it does so for a non-trivial sub-class of well-typed processes that we characterize later on.
3
A Mailbox Type System
In this section we detail the type system for the mailbox calculus. We start from the syntax and semantics of mailbox types (Section 3.1) and of dependency graphs (Section 3.2), the mechanism we use to track mailbox dependencies. Then we present the typing rules (Section 3.3) and the properties of well-typed processes (Section 3.4).
3.1
Mailbox Types
The syntax of mailbox types and patterns is shown below: Mailbox Type τ, σ ::= ?E | !E
Pattern E, F ::= 0 | 1 | m[τ ] | E + F | E · F | E∗ (3) Patterns are commutative regular expressions [11] describing the configurations of messages stored in a mailbox. An atom m[τ ] describes a mailbox containing a single message with tag m and arguments of type τ . We let M range over atoms and abbreviate m[τ ] with m when τ is the empty sequence. Compound patterns are built using sum (E + F ), product (E · F ) and exponential (E∗). The constants 1 and 0 respectively describe the empty and the unreliable mailbox. There is no configuration of messages stored in an unreliable mailbox, not even the empty one. We will use the 0 pattern for describing mailboxes from which an unexpected message has been received. Let us look at a few simple examples. The pattern A+Bdescribes a mailbox that contains either anAmessage or aBmessage, but not both, whereas the patternA+ 1 describes a mailbox that either contains aAmessage or is empty. The patternA·Bdescribes a mailbox that contains both anAmessage and also aBmessage. Note thatAandBmay be equal, in which case the mailbox contains twoAmessages. Finally, the patternA∗ describes a mailbox that contains an arbitrary number (possibly zero) ofA messages. We adopt the usual conventions on the priority of connectives, whereby∗ binds stronger than · which, in turn, binds stronger than +.
A mailbox type consists of a capability (either ? or !) paired with a pattern. The capability specifies whether the pattern describes messages to be received from (?) or stored in (!) the mailbox. Here are some examples: A process using a mailbox of type !Amust store anA message into the mailbox, whereas a process using a mailbox of type ?Aexpects to receive anAmessage from the mailbox. A process using a mailbox of type !(A+ 1) may store anA message into the mailbox, but is not obliged to do so. A process using a mailbox of type !(A+B) decides whether to store anAmessage or aBmessage in the mailbox, whereas a process using a mailbox of type ?(A+B) must be ready to receive both kinds of messages. A process using a mailbox of type ?(A·B) expects to receive both an Amessage and a B message and may decide in which order to do so. A process using a mailbox of type !(A·B) must store bothAandBinto the mailbox. A process using a mailbox of type !A∗ decides how manyAmessages to store in the mailbox, whereas a process using a mailbox of type ?A∗ must be prepared to receive an arbitrary number ofAmessages.
To cope with possibly infinite types we interpret the productions in (3) coinductively and consider as types the regular trees [13] built using those productions. We require every infinite branch of a type tree to go through infinitely many atoms. This strengthened contractiveness condition allows us to define functions inductively on the structure of patterns, provided that these functions do not recur into argument types (cf. Definitions 8 and 14).
The semantics of a pattern is a set of multisets of atoms. Because patterns include types, the given semantics is parametric in the subtyping relation, which will be defined next:
IDefinition 8 (subpattern). The configurations of E are inductively defined by the following equations, where A and B range over multisets hM i of atoms and ] denotes multiset union:
J0K def = ∅ J1K def = {hi} JE + F K def = JE K ∪ JF K JE · F K def = {A ] B | A ∈JE K, B ∈ JF K} JM K def = {hM i} JE ∗ K def = J1K ∪ JE K ∪ JE · E K ∪ · · · Given a preorder relation R on types, we write E vR F if hmi[τi]ii∈I ∈ JE K implies hmi[σi]ii∈I ∈JF K and τiR σi for every i ∈ I. We write 'R for vR∩ wR.
For example,JA+BK = {hAi, hBi} andJA·BK = {hA,Bi}. It is easy to see that vR is a pre-congruence with respect to all the connectives and that 'R includes all the known laws of commutative Kleene algebra [11]: both + and · are commutative and associative, + is idempotent and has unit 0, · distributes over +, it has unit 1 and is absorbed by 0. Also observe that vR is related covariantly toR, that is τ R σ impliesm[τ ] vRm[σ].
We now define subtyping. As types may be infinite, we resort to coinduction:
IDefinition 9 (subtyping). We say thatR is a subtyping relation if τ R σ implies either
1. τ = ?E and σ = ?F and E vR F , or
2. τ = !E and σ = !F and F vRE.
We write 6 for the largest subtyping relation and say that τ is a subtype of σ (and σ a supertype of τ ) if τ 6 σ. We write ≶ for 6 ∩ >, v for v6 and ' for '6.
Items 1 and 2 respectively correspond to the usual covariant and contravariant rules for channel types with input and output capabilities [47]. For example, !(A+B)6 !Abecause a mailbox of type !(A+B) is more permissive than a mailbox of type !A. Dually, ?A6 ?(A+B) because a mailbox of type ?Aprovides stronger guarantees than a mailbox of type ?(A+B). Note that !(A·B)≶ !(B·A) and ?(A·B)≶ ?(B·A), to witness the fact that the order in which messages are stored in a mailbox is irrelevant.
Mailbox types whose patterns are in particular relations with the constants 0 and 1 will play special roles, so we introduce some corresponding terminology.
IDefinition 10 (type and name classification). We say that (a name whose type is) τ is: relevant if τ 66 !1 and irrelevant otherwise;
reliable if τ 66 ?0 and unreliable otherwise; usable if !0 66 τ and unusable otherwise.
A relevant name must be used, whereas an irrelevant name may be discarded because not storing any message in the mailbox it refers to is allowed by its type. All mailbox types with input capability are relevant. A reliable mailbox is one from which no unexpected message has been received. All names with output capability are reliable. A usable name can be used, in the sense that there exists a construct of the mailbox calculus that expects a name with that type. All mailbox types with input capability are usable, but ?(A· 0) is unreliable. Both !Aand !(1 +A) are usable. The former type is also relevant because a process using a mailbox with this type must (eventually) store anAmessage in it. On the contrary, the latter type is irrelevant, since not using the mailbox is a legal way of using it.
Henceforth we assume that all types are usable and that all argument types are also reliable. That is, we ban all types like !0 or !(0 ·m) and all types like ?m[?0] or !m[?0].
I Example 11 (lock type). The mailbox used by the lock (Example 1) will have several different types, depending on the viewpoint we take (either the lock itself or one of its users) and on the state of the lock (whether it is free or busy). As we can see from the definition of
FreeLock, a free lock waits for anacquiremessage which is supposed to carry a reference to another mailbox into which the capability to release the lock is stored. Since the lock is meant to have several concurrent users, it is not possible in general to predict the number of acquiremessages in its mailbox. Therefore, the mailbox of a free lock has type
?acquire[!reply[!release]]∗
from the viewpoint of the lock itself. When the lock is busy, it expects to find onerelease message in its mailbox, but in general the mailbox will also contain acquire messages corresponding to pending acquisition requests. So, the mailbox of a busy lock has type
?(release·acquire[!reply[!release]]∗)
indicating that the mailbox contains (or will eventually contain) a singlereleasemessage along with arbitrarily manyacquiremessages.
Prospective owners of the lock may have references to the lock’s mailbox with type !acquire[!reply[!release]] or !acquire[!reply[!release]]∗ depending on whether they acquire the lock exactly once (just like alice and carol in Example 1) or several times. Other intermediate types are possible in the case of users that acquire the lock a bounded number of times. The current owner of the lock will have a reference to the lock’s mailbox of type !release. This type is relevant, implying that the owner must eventually release the lock.
3.2
Dependency Graphs
We use dependency graphs for tracking dependencies between mailboxes. Intuitively, there is a dependency between u and v if either v is the argument of a message in mailbox u or v occurs in the continuation of a process waiting for a message from u. Dependency graphs have names as vertices and undirected edges. However, the usual representation of graphs does not account for the fact that mailbox names may be restricted and that the multiplicity of dependencies matters. Therefore, we define dependency graphs using the syntax below:
{u, v}−−−→ ∅u−v [g-axiom] ϕ−−−→ ϕu−v 0 ϕ t ψ−−−→ ϕu−v 0t ψ [g-left] ψ−−−→ ψu−v 0 ϕ t ψ−−−→ ϕ t ψu−v 0 [g-right] ϕ−−−→ ψu−v a 6= u, v
(νa)ϕ−−−→ (νa)ψu−v [g-new]
ϕ−−−→ ψu−w ψ−−−→ ϕw−v 0
ϕ−−−→ ϕu−v 0 [g-trans]
Figure 1 Labelled transitions of dependency graphs.
The term ∅ represents the empty graph which has no vertices and no edges. The unordered pair {u, v} represents the graph made of a single edge connecting the vertices u and v. The term ϕ t ψ represents the union of ϕ and ψ whereas (νa)ϕ represents the same graph as ϕ except that the vertex a is restricted. The usual notions of free and bound names apply to dependency graphs. We write fn(ϕ) for the free names of ϕ.
To define the semantics of a dependency graph we use the labelled transition system of Table 1. A label u − v represents a path connecting u with v. So, a relation ϕ−−−→ ϕu−v 0 means that u and v are connected in ϕ and ϕ0 describes the residual edges of ϕ that have not been used for building the path between u and v. The paths of ϕ are built from the edges of ϕ (cf. [g-axiom]) connected by shared vertices (cf. [g-trans]). Restricted names cannot be observed in labels, but they may contribute in building paths in the graph (cf. [g-new]).
IDefinition 12 (graph acyclicity and entailment). Let dep(ϕ)def= {(u, v) | ∃ϕ0 : ϕ−−−→ ϕu−v 0} be the dependency relation generated by ϕ. We say that ϕ is acyclic if dep(ϕ) is irreflexive. We say that ϕ entails ψ, written ϕ ⇒ ψ, if dep(ψ) ⊆ dep(ϕ).
Note that t is commutative, associative and has ∅ as unit with respect to dep(·). These properties of dependency graphs are key to prove that typing is preserved by structural congruence on processes. Note also that t is not idempotent. Indeed, {u, v} t {u, v} is cyclic whereas {u, v} is not. The following example motivates the reason why the multiplicity of dependencies is important.
IExample 13 (multiplicity of dependencies). Even though we have not presented the typing rules yet, we can use the above intuition on how dependencies are established to argue that the process below yields a cyclic dependency graph:
P def= (νa)(νb)(a!A[b] | a!B[b] | a?A(x).a?B(y).freea.x!m[y]) →∗(νb)b!m[b]X→
Observe that P stores two messages in the mailbox a, each containing a reference to the mailbox b. Thus, the same dependency {a, b} arises twice, resulting in a cyclic dependency involving a and b. By reducing the process, we note that the two variables x and y, which were syntactically different in P , are unified into b in the reduct, which is deadlocked.
3.3
Typing Rules
We use type environments for tracking the type of free names occurring in processes. A type environment is a partial function from names to types written as u : τ or u1: τ1, . . . , un : τn.
We let Γ and ∆ range over type environments, we write dom(Γ) for the domain of Γ and Γ, ∆ for the union of Γ and ∆ when dom(Γ) ∩ dom(∆) = ∅. We say that Γ is reliable if so are all the types in its range.
Typing rules for processes Γ ` P :: ϕ
∅ `done:: ∅ [t-done]
X: (x : τ ; ϕ)
u : τ `X[u] :: ϕ{u/x} [t-def]
Γ, a : ?1 ` P :: ϕ
Γ ` (νa)P :: (νa)ϕ [t-new]
u : !m[τ ], v : τ ` u!m[v] :: {u, {v}} [t-msg]
u : ?E, Γ ` G E
u : ?E, Γ ` G :: {u, dom(Γ)} [t-guard] Γi` Pi:: ϕi (i=1,2)
Γ1k Γ2` P1| P2:: ϕ1t ϕ2 [t-par]
∆ ` P :: ψ Γ6 ∆ ϕ ⇒ ψ Γ ` P :: ϕ [t-sub]
Typing rules for guards Γ ` G
u : ?0, Γ `fail u [t-fail]
Γ ` P :: ϕ
u : ?1, Γ `freeu.P [t-free] u : ?E, Γ, x : τ ` P :: ϕ
u : ?(m[τ ] · E), Γ ` u?m(x).P [t-in]
u : ?Ei, Γ ` Gi (i=1,2)
u : ?(E1+ E2), Γ ` G1+ G2
[t-branch]
Figure 2 Typing rules.
Judgments for processes have the form Γ ` P :: ϕ, meaning that P is well typed in Γ and yields the dependency graph ϕ. Judgments for guards have the form Γ ` G, meaning that G is well typed in Γ. We say that a judgment Γ ` P :: ϕ is well formed if fn(ϕ) ⊆ dom(Γ) and ϕ is acyclic. Each process typing rule has an implicit side condition requiring that its conclusion be well formed. For each global process definition X(x) , P we assume that there is a corresponding global process declaration of the form X: (x : τ ; ϕ). We say that the definition is consistent with the corresponding declaration if x : τ ` P :: ϕ, where we require the dependency graph yielded by P to be the same ϕ associated with the definition. Hereafter, all process definitions are assumed to be consistent. We now discuss the typing rules in detail, introducing auxiliary notions and notation as we go along.
Terminated process. According to the rule[t-done], the terminated process done is well typed in the empty type environment and yields no dependencies. This is motivated by the fact that done does not use any mailbox. Later on we will introduce a subsumption rule [t-sub]that allows us to typedone in any type environment with irrelevant names.
Message. Rule [t-msg] establishes that a message u!m[v] is well typed provided that the mailbox u allows the storing of an m-tagged message with arguments of type τ and the types of v are indeed τ . The subsumption rule[t-sub]will make it possible to use arguments whose type is a subtype of the expected ones. A message u!m[v] establishes dependencies between the target mailbox u and all of the arguments v. We write {u, {v1, . . . , vn}} for the
dependency graph {u, v1} t · · · t {u, vn} and use ∅ for the empty graph union.
Names with output capability are introduced by the k operator that combines type environments and that will be defined later on, when discussing rule[t-par].
Process invocation. The typing rule for a process invocationX[u] checks that there exists a global definition forX which expects exactly the given number and type of parameters. Again, rule[t-sub]will make it possible to use parameters whose types are subtypes of the expected ones. A process invocation yields the same dependencies as the corresponding process definition, with the appropriate substitutions applied.
Guards. Guards are used to match the content of a mailbox and retrieve messages from it. According to rule[t-fail], the actionfailu matches a mailbox u with type ?0, indicating that an unexpected message has been found in the mailbox. The type environment may contain arbitrary associations, since thefail u action causes a runtime error. Rule[t-free] states that the actionfree u.P matches a mailbox u with type ?1, indicating that the mailbox is empty. The continuation is well typed in the residual type environment Γ. An input action u?m(x).P matches a mailbox u with type ?(m[τ ] · E) that guarantees the presence of an m-tagged message possibly along with other messages as specified by E. The continuation P must be well typed in an environment where the mailbox has type ?E, which describes the content of the mailbox after the m-tagged message has been removed. Associations for the received arguments x are also added to the type environment. A compound guard G1+ G2 offers the actions offered by G1 and G2and therefore matches a mailbox u with type ?(E1+ E2), where Ei is the pattern that describes the mailbox matched by Gi. Note
that the residual type environment Γ is the same in both branches, indicating that the type of other mailboxes used by the guard cannot depend on that of u.
The judgments for guards do not yield any dependency graph. This is compensated by the rule[t-guard], which we describe next.
Guarded processes. Rule [t-guard] is used to type a guarded process G, which matches some mailbox u of type ?E and possibly retrieves messages from it. As we have seen while discussing guards, E is supposed to be a pattern of the form E1+ · · · + En where each Ei
is either 0, 1 or of the form M · F . However, only the patterns E that are in normal form (defined below) are suitable to be used in this typing rule and the side condition E checks that this is indeed the case. Before defining the notion of pattern normal form we motivate its need by means of a simple example.
Suppose that our aim is to type a process u?A.P + u?B.Q that consumes either an A message or aB message from u, whichever of these two messages is matched first in u, and then continues as P or Q correspondingly. Suppose also that the type of u is ?E with Edef=A·C+B·A, which allows the rules for guards to successfully type check the process. As we have seen while discussing rule[t-in], P and Q must be typed in an environment where the type of u has been updated so as to reflect the fact that the consumed message is no longer in the mailbox. In this particular case, we might be tempted to infer that the type of u in P is ?Cand that the type of u in Q is ?A. Unfortunately, the type ?Cdoes not accurately describe the content of the mailbox afterA has been consumed because, according to E, theAmessage may be accompanied by either aBmessage or by aCmessage, whereas ?C only accounts for the second possibility. Thus, the appropriate pattern to be used for typing this process isA· (B+C) +B·A, where the fact thatBmay be found after consumingAis made explicit. This pattern and E are equivalent as they generate exactly the same set of valid configurations. Yet,A· (B+C) +B·Ais in normal form whereas E is not. In general the normal form is not unique. For example, also the patternsB·A+C·AandA· (B+C) are in normal form and equivalent to E and can be used for typing processes that consume messages from u in different orders or with different priorities.
The first ingredient for defining the notion of pattern normal form is that of pattern residual E/M , which describes the content of a mailbox that initially contains a configuration of messages described by E and from which we remove a single message with type M :
IDefinition 14 (pattern residual). The residual of a pattern E with respect to an atom M , written E/M , is inductively defined by the following equations:
0/M = 1/M def= 0 (E∗)/M def= E/M · E∗ m[τ ]/m[σ]def= 1 if τ 6 σ m[τ ]/m0[σ]def= 0 ifm6=m0 (E + F )/M def= E/M + F/M (E · F )/M def= E/M · F + E · F/M If we take the pattern E discussed earlier we have E/A= 1 ·C+A· 0 + 0 · 1 +B· 1 'B+C. The pattern residual operator is closely related to Brzozowski’s derivative in a commutative Kleene algebra [4, 28]. Unlike Brzozowski’s derivative, the pattern residual is a partial operator: E/m[σ] is defined provided that the σ are supertypes of all types τ found in m-tagged atoms within E. This condition has a natural justification: when choosing the message to remove from a mailbox containing a configuration of messages described by E, only the tag m of the message – and not the type of its arguments – matters. Thus, σ faithfully describe the received arguments provided that they are supertypes of all argument types of all m-tagged message types in E. For example, assumingnat6int, we have that (m[int] +m[nat])/m[int] is defined whereas (m[int] +m[nat])/m[nat] is not.
We use the notion of pattern residual to define pattern normal forms:
IDefinition 15 (pattern normal form). We say that a pattern E is in normal form, written E, if E E is derivable by the following axioms and rules:
E 0 E 1 F ' E/M E M · F
E F1 E F2 E F1+ F2
Essentially, the judgment E verifies that E is expressed as a sum of 0, 1 and M · F terms where F is (equivalent to) the residual of E with respect to M .
A guarded process yields all the dependencies between the mailbox u being used and the names occurring free in the continuations, because the process will not be able to exercise the capabilities on these names until the message from u has been received.
Parallel composition. Rule[t-par]deals with parallel compositions of the form P1| P2. This rule accounts for the fact that the same mailbox u may be used in both P1 and P2according to different types. For example, P1 might store an Amessage into u and P2 might store aB message into u. In the type environment for the parallel composition as a whole we must be able to express with a single type the combined usages of u in P1and P2. This is accomplished by introducing an operator that combines types:
IDefinition 16 (type combination). We write τ k σ for the combination of τ and σ, where k is the partial symmetric operator defined as follows:
!E k !F def= !(E · F ) !E k ?(E · F )def= ?F ?(E · F ) k !Edef= ?F
Continuing the previous example, we have !Ak !B= !(A·B) because storing oneAmessage and oneBmessage in u means storing an overall configuration of messages described by the patternA·B. When u is used for both input and output operations, the combined type of u describes the overall balance of the mailbox. For example, we have !Ak ?(A·B) = ?B: if we combine a process that stores anAmessage into u with another process that consumes both
anAmessage and aBmessage from the same mailbox in some unspecified order, then we end up with a process that consumes aBmessage from u.
Notice that k is a partial operator in that not all type combinations are defined. It might be tempting to relax k in such a way that !(A·B) k ?A= !B, so as to represent the fact that the combination of two processes results in an excess of messages that must be consumed by some other process. However, this would mean allowing different processes to consume messages from the same mailbox, which is not safe in general (see Example 17). For the same reason, the combination of ?E and ?F is always undefined regardless of E and F . Operators akin to k for the combination of channel types are commonly found in substructural type systems for the (linear) π-calculus [51, 44]. Unlike these systems, in our case the combination concerns also the content of a mailbox in addition to the capabilities for accessing it.
IExample 17. Suppose that we extend the type combination operator so that ?(E · F ) = ?E k ?F . To see why this extension would be dangerous, consider the process
(u!A[True] | u?A(x).(system!print_bool[x] |freeu.done)) | (u!A[2] | u?A(y).(system!print_int[y] |freeu.done))
Overall, this process stores into u a combination of messages that matches the pattern A[bool] ·A[int] and retrieves from u the same combination of messages. Apparently, u is used in a balanced way. However, there is no guarantee that the u!A[True] message is received by the process at the top and that the u!A[2] message is received by the process at the bottom. In fact, the converse may happen because only the tag of a message – not the type or value of its arguments – is used for matching messages in the mailbox calculus.
We now extend type combination to type environments in the expected way:
IDefinition 18 (type environment combination). We write Γ k ∆ for the combination of Γ and ∆, where k is the partial operator inductively defined by the equations:
Γ k ∆def= Γ, ∆ if dom(Γ) ∩ dom(∆) = ∅ (u : τ, Γ) k (u : σ, ∆)def= u : τ k σ, (Γ k ∆) With this machinery in place, rule [t-par] is straightforward to understand and the dependency graph of P1| P2is simply the union of the dependency graphs of P1and P2. Mailbox restriction. Rule[t-new]establishes that the process creating a new mailbox a with scope P is well typed provided that the type of a is ?1. This means that every message stored in the mailbox a by (a sub-process of) P is also consumed by (a sub-process of) P . The dependency graph of the process is the same as that of P , except that a is restricted. Subsumption. As we have anticipated earlier in a few occasions, the subsumption rule[t-sub] allows us to rewrite types in the type environment and to introduce associations for irrelevant names. The rule makes use of the following notion of subtyping for type environments:
IDefinition 19 (subtyping for type environments). We say that Γ is a subtype environment of ∆ if Γ6 ∆, where 6 is the least preorder on type environments such that:
u : !1, Γ 6 Γ
τ 6 σ u : τ, Γ 6 u : σ, Γ
Intuitively, Γ 6 ∆ means that Γ provides more capabilities than ∆. For example, u : !(A+B), v : !16 u : !Asince a process that is well typed in the environment u : !Astores
anAmessage into u, which is also a valid behavior in the environment u : !(A+B), v : !1 where u has more capabilities (it is also possible to store aBmessage into u) and there is an irrelevant name v not used by the process.
Rule[t-sub]also allows us to replace the dependency graph yielded by P with another one that generates a superset of dependencies. In general, the dependency graph should be kept as small as possible to minimize the possibility of yielding mutual dependencies (see[t-par]). The replacement allowed by[t-sub]is handy for technical reasons, but not necessary. The point is that the residual of a process typically yields fewer dependencies than the process itself, so we use[t-sub]to enforce the invariance of dependency graphs across reductions.
IExample 20. We show the full typing derivation for FreeLock andBusyLock defined in Example 1. Our objective is to show the consistency of the global process declarations
FreeLock: (self : τ ; ∅) BusyLock: (self : τ, owner : ρ; {self , owner })
where τ def= ?acquire[ρ]∗ and ρ def= !reply[!release]. In the derivation trees below we rename self as x and owner and y to resonably fit the derivations within the page limits. We start from the body of BusyLock, which is simpler, and obtain
[t-msg] x : !release, y : ρ ` y!reply[x] :: {y, x}
[t-def] x : τ `FreeLock[x] :: ∅ [t-in] x : σ ` x?release.FreeLock[x] [t-guard] x : σ ` x?release.FreeLock[x] :: ∅ [t-par] x : τ, y : ρ ` y!reply[x] | x?release.Lock[x] :: {y, x} t ∅
where σdef= ?(release·acquire[ρ]∗).
Concerning FreeLock, the key step is rewriting the pattern of τ in a normal form that matches the branching structure of the process. To this aim, we use the property E∗ ' 1 + E · E∗ and the fact that 0 is absorbing for the product connective:
.. . [t-fail] x : ?0 `fail x [t-guard] x : ?0 `fail x :: ∅ [t-in] x : ?(release· 0) ` x?release.fail x
[t-branch] x : ?(1 +acquire[ρ] ·acquire[ρ]∗+release· 0) ` · · · + x?release.failx
[t-guard] x : ?(1 +acquire[ρ] ·acquire[ρ]∗+release· 0) ` · · · + x?release.failx :: ∅
[t-sub] x : τ `free x.done+ · · · + x?release.failx :: ∅
The elided sub-derivation concerns the first two branches of FreeLockand is as follows: [t-done] ∅ `done:: ∅ [t-free] x : ?1 `freex.done [t-def] x : τ, y : ρ `BusyLock[x, y] :: {x, y}
x : ?acquire[ρ] ·acquire[ρ]∗` x?acquire(y).BusyLock[x, y] x : ?(1 +acquire[ρ] ·acquire[ρ]∗) `free x.done+ x?acquire(y).BusyLock[x, y] The process (1), combining an instance of the lock and the users alice and carol, is also well typed. As we will see at the end of Section 3.4, this implies that both alice and carol are able to acquire the lock, albeit in some unspecified order.
IExample 21. In this example we show that the process (2) of Example 6 is ill typed. In order to do so, we assume the global process declaration
Future: (self : ?(put[int] ·get[!reply[int]]∗); ∅)
which can be shown to be consistent with the given definition forFuture. In the derivation below we use the pattern F def= put[int] ·get[ρ]∗ and the types τ def= !put[int], σ def= ?(reply[int] · 1) and ρdef= !reply[int]:
f : !get[ρ], c : ρ ` f !get[c] :: {f , c}
f : τ, x :int` f !put[x] :: ∅ f : τ, c : ?1, x :int`free c.f !put[x] f : τ, c : ?1, x :int`freec.f !put[x] :: {c, f }
f : τ, c : σ ` c?reply(x).free c.f !put[x] f : τ, c : σ ` c?reply(x).free c.f !put[x] :: {c, f } f : !(get[ρ] ·put[int]), c : ?1 ` f !get[c] | c?reply(x).free c.f !put[x] :: −
[t-sub] f : !F, c : ?1 ` f !get[c] | c?reply(x).freec.f !put[x] :: −
f : !F ` (νc)(f !get[c] | c?reply(x).freec.f !put[x]) :: −
In attempting this derivation we have implicitly extended the typing rules so that names with typeintdo not contribute in generating any significant dependency. The critical point of the derivation is the application of[t-par], where we are composing two parallel processes that yield a circular dependency between c and f . In the process on the left hand side, the dependency {f , c} arises because c is sent as a reference in a message targeted to f . In the process on the right hand side, the dependency {c, f } arises because there are guards concerning the mailbox c that block an output operation on the mailbox f .
IExample 22 (non-deterministic choice). The same input action can occur multiple times in the same guarded process. This feature can be used to encode in the mailbox calculus the non-deterministic choice between P1 and P2 as the process
(νa)(freea.P1+free a.P2) (4)
provided that Γ ` Pi:: ϕi for i = 1, 2. That is, P1 and P2 must be well typed in the same type environment. Below is the typing derivation for (4)
Γ ` P1:: ϕ1 [t-free] Γ, a : ?1 `freea.P1 Γ ` P2:: ϕ2 [t-free] Γ, a : ?1 `freea.P2 [t-branch] Γ, a : ?(1 + 1) `freea.P1+free a.P2
[t-guard] Γ, a : ?(1 + 1) `freea.P1+free a.P2:: ϕ
[t-sub] Γ, a : ?1 `free a.P1+free a.P2:: ϕ
[t-new] Γ ` (νa)(freea.P1+freea.P2) :: (νa)ϕ
where ϕ def= {a, dom(Γ)}. The key step is the application of [t-sub], which exploits the idempotency of + (in patterns) to rewrite 1 as the equivalent pattern 1 + 1.
3.4
Properties of well-typed processes
In this section we state the main properties enjoyed by well-typed processes. As usual, subject reduction is instrumental for all of the results that follow as it guarantees that typing is preserved by reductions:
ITheorem 23. If Γ is reliable and Γ ` P :: ϕ and P → Q, then Γ ` Q :: ϕ.
Interestingly, Theorem 23 seems to imply that the types of the mailboxes used by a process do not change. In sharp contrast, other popular behavioral typing disciplines (session types in particular), are characterized by a subject reduction result in which types reduce along with processes. Theorem 23 also seems to contradict the observations made earlier concerning the fact that the mailboxes used by a process may have different types (Example 11). The type preservation guarantee assured by Theorem 23 can be explained by recalling that the type environment Γ in a judgment Γ ` P :: ϕ already takes into account the overall balance between the messages stored into and consumed from the mailbox used by P (see Definition 18). In light of this observation, Theorem 23 simply asserts that well-typed processes are steady state: they never produce more messages than those that are consumed, nor do they ever try to consume more messages than those that are produced.
A practically relevant consequence of Theorem 23 is that, by looking at the type ?E of the mailbox a used by a guarded process P (rule[t-guard]), it is possible to determine bounds to the number of messages that can be found in the mailbox as P waits for a message to receive. In particular, if every configuration of E contains at most k m-tagged atoms, then at runtime a contains at mostm-tagged messages. As a special case, a mailbox of type ?1 is guaranteed to be empty and can be statically deallocated. Note that the bounds may change after P receives a message. For example, a free lock is guaranteed to have norelease messages in its mailbox, and will have at most one when it is busy (see Example 20).
The main result concerns the soundness of the type system, guaranteeing that well-typed (closed) processes are both mailbox conformant and deadlock free (Definitions 4 and 5):
ITheorem 24. If ∅ ` P :: ϕ, then P is mailbox conformant and deadlock free.
Fair termination and junk freedom are not enforced by our typing discipline in general. The usual counterexamples include processes that postpone indefinitely the use of a mailbox with a relevant type. For instance, themmessage in the well-typed process (νa)(a!m|X[a]) where X(x) , X[x] is never consumed because a is never used for an input operation. Nevertheless, fair termination is guaranteed for the class of finitely unfolding processes:
ITheorem 25. We say that P is finitely unfolding if all maximal reductions of P use[r-def] finitely many times. If ∅ ` P :: ϕ and P is finitely unfolding, then P is fairly terminating.
The class of finitely unfolding processes obviously includes all finite processes (those not using process invocations) but also many recursive processes. For example, every process of the form (νa)(a!m| · · · | a!m|X[a]) whereX(x), x?m.X[x] +freex.done is closed, well typed and finitely unfolding regardless of the number of mmessages stored in a, hence is fairly terminating and junk free by Theorem 25.
4
Examples
In this section we discuss a few more examples that illustrate the expressiveness of the mailbox calculus and of its type system. We consider a variant of the bank account shown in Listing 1 (Section 4.1), the case of master-workers parallelism (Section 4.2) and the encoding of binary sessions extended with forks and joins (Sections 4.3 and 4.4).
4.1
Actors using futures
Many Scala programs combine actors with futures [53]. As an example, Listing 2 shows an alternative version of the Account actor in Akka that differes from Listing 1 in the
1 c l a s s A c c o u n t (var b a l a n c e : D o u b l e ) e x t e n d s A k k a A c t o r [ A n y R e f ] { 2 o v e r r i d e def p r o c e s s ( msg : A n y R e f ) { 3 msg m a t c h { 4 c a s e dm : D e b i t M e s s a g e = > 5 b a l a n c e += dm . a m o u n t 6 s e n d e r () ! R e p l y M e s s a g e . O N L Y 7 c a s e cm : C r e d i t M e s s a g e = > 8 b a l a n c e -= cm . a m o u n t 9 val r e c i p i e n t = cm . r e c i p i e n t . a s I n s t a n c e O f [ A c t o r R e f ]
10 val f u t u r e = ask ( r e c i p i e n t , new D e b i t M e s s a g e ( self , cm . a m o u n t )) 11 A w a i t . r e s u l t ( future , D u r a t i o n . Inf ) 12 s e n d e r () ! R e p l y M e s s a g e . O N L Y 13 c a s e _ : S t o p M e s s a g e = > e x i t () 14 c a s e m e s s a g e = > 15 val ex = new I l l e g a l A r g u m e n t E x c e p t i o n ( " U n s u p p o r t e d ␣ m e s s a g e " ) 16 ex . p r i n t S t a c k T r a c e ( S y s t e m . err ) 17 } 18 } 19 }
Listing 2 An Akka actor using futures from the Savina benchmark suite [32].
handling of CreditMessages(lines 10–11). The future variable created here is initialized asynchronously with the result of the debit operation invoked onrecipient. To make sure that each transaction is atomic, the actor waits for the variable to be resolved (line 11) before notifyingsenderthat the operation has been completed.
This version ofAccount is arguably simpler than the one in Listing 1, if only because the actor has a unique top-level behavior. One way of modeling this implementation ofAccount in the mailbox calculus is to useFuture, discussed in Example 2. A simpler modeling stems from the observation thatfuturein Listing 2 is used for a one-shot synchronization. A future variable with this property is akin to a mailbox from which the value of the resolved variable is retrieved exactly once. Following this approach we obtain the process below:
Account(self , balance) , self ?debit(amount, sender ).
sender !reply|Account[self , balance + amount] + self ?credit(amount, recipient, sender ).
(νfuture)
recipient!debit[amount, future] | future?reply.freefuture.
(sender !reply|Account[self , balance − amount])
+ self ?stop.freeself .done
+ self ?reply.fail self
Compared to the process in Example 3, here the notification from the recipient account is received from the mailbox future, which is created locally during the handling of thecredit message. The rest of the process is the same as before. This definition ofAccountand the one in Example 3 can both be shown to be consistent with the declaration
Account: (self : ?(debit[int, ρ]∗·credit[int, !debit[int, ρ], ρ]∗+stop), balance :int; ∅) where ρdef= !reply. In particular, the dependencies between self and future that originate in this version ofAccountare not observable from outsideAccountitself.
The use of multiple mailboxes and the interleaving of blocking operations on them may increase the likelyhood of programming mistakes causing mismatched communications and/or deadlocks. However, these errors can be detected by a suitable typing discipline such the one proposed in this paper. Types can also be used to mitigate the runtime overhead resulting from the use of multiple mailboxes. Here, for example, the typing of future guarantees that this mailbox is used for receiving a single message and that future is empty by the timefreefuture is performed. A clever compiler can take advantage of this information to statically optimize both the allocation and the deallocation of this mailbox.
4.2
Master-workers parallelism
In this example we model a master process that receives tasks to perform from a client. For each task, the master creates a pool of workers and assigns each worker a share of work. The master waits for all partial results from the workers before sending the final result back to the client and making itself available again. The number of workers may depend on some quantity possibly related to the task to be performed and that is known at runtime only.
Below we define three processes corresponding to the three states in which the master process can be, and we leaveWorkerunspecified:
Available(self ), self ?task(client).(νpool)CreatePool[self , pool, client] +free self .done
CreatePool(self , pool, client),ifmore workers neededthen
(νworker )(worker !work[pool] |Worker[worker ]) |
CreatePool[self , pool, client]
else
CollectResults[self , pool, client]
CollectResults(self , pool, client), pool?result.CollectResults[self , pool, client] +free pool.(client!result|Available[self ])
The “ifconditionthenP elseQ” form used here can be encoded in the mailbox calculus and is typed similarly to the non-deterministic choice of Example 22. These definitions can be shown to be consistent with the following declarations:
Available: (self : ?task[!result]∗; ∅)
CreatePool,CollectResults: (self : ?task[!result]∗, pool : ?result∗, client : !result; {pool, self } t {pool, client})
The usual implementation of this coordination pattern requires the programmer to keep track of the number of active workers using a counter that is decremented each time a partial result is collected [32]. When the counter reaches zero, the master knows that all the workers have finished their job and notifies the client. In the mailbox calculus, we can model the counter using a dedicated mailbox pool from which the partial results are collected: when pool becomes disposable, it means that no more active workers remain.
4.3
Encoding of binary sessions
Session types [27, 29] have become a popular formalism for the specification and enforcement of structured protocols through static analysis. A session is a private communication channel shared by processes that interact through one of its endpoints. Each endpoint is associated with a session type that specifies the type, direction and order of messages that are supposed
to be exchanged through that endpoint. A typical syntax for session types in the case of binary sessions (those connecting exactly two peer processes) is shown below:
T, S ::= end | ?[τ ].T | ![τ ].T | T & S | T ⊕ S
A session type ?[τ ].T describes an endpoint used for receiving a message of type τ and then according to T . Dually, a session type ![τ ].T describes an endpoint used for sending a message of type τ and then according to T . An external choice T & S describes an endpoint used for receiving a selection (eitherleftorright) and then according to the corresponding continuation (either T or S). Dually, an internal choice T ⊕ S describes an endpoint used for making a selection and then according to the corresponding continuation. Communication safety and progress of a binary session are guaranteed by the fact that its two endpoints are linear resources typed by dual session types, where the dual of T is obtained by swapping inputs with outputs and internal with external choices.
In this example we encode sessions and session types using mailboxes and mailbox types. We encode a session as a non-uniform, concurrent object. The object is “concurrent” because it is accessed concurrently by the two peers of the session. It is “non-uniform” because its interface changes over time, as the session progresses. The object uses a mailbox self and its behavior is defined by the equations forSessionT(self ) shown below, where T is the session
type according to which it must be used by one of the peers:
Sessionend(self ),free self .done
Session?[τ ].T(self ), self ?send(x, s).self ?receive(r).
(s!reply[self ] | r!reply[x, self ] |SessionT[self ])
Session![τ ].T(self ),Session?[τ ].T[self ]
SessionT &S(self ), self ?left(s).self ?receive(r).
(s!reply[self ] | r!left[self ] |SessionT[self ])
+ self ?right(s).self ?receive(r).
(s!reply[self ] | r!right[self ] |SessionS[self ])
SessionT ⊕S(self ),SessionT &S[self ]
To grasp the intuition behind the definition ofSessionT(self ), it helps to recall that each
stage of a session corresponds to an interaction between the two peers, where one process plays the role of “sender” and its peer that of “receiver”. Both peers manifest their willingness to interact by storing a message into the session’s mailbox. The receiver always stores a receivemessage, while the sender stores eithersend, left orright according to T . All messages contain a reference to the mailbox owned by sender and receiver (respectively s and r) where they will be notified once the interaction is completed. Asendmessage also carries actual payload x being exchanged. The role ofSessionT(self ) is simply to forward
each message from the sender to the receiver. The notifications stored in s and r contain a reference to the session’s mailbox so that its type reflects the session’s updated interface corresponding to the rest of the conversation.
Interestingly, the encoding of a session with type T is undistinguishable from that of a session with the dual type T . This is natural by recalling that each stage of a session corresponds to a single interaction between the two peers: the order in which they store the respective messages in the session’s mailbox is in general unpredictable but also unimportant, for both messages are necessary to complete each interaction.
As an example, suppose we want to model a system whereAliceasksCarolto compute the sum of two numbers exchanged through a session s. Alice andCaroluse the session ac-cording to the session types Tdef= ![int].![int].?[int].endand T def= ?[int].?[int].![int].end,
