Introduction
In October 2026 I gave a talk at an Elixir/Erlang meetup at Meta in Stockholm about the types that we are designing for the processes and the modules of Elixir. One of my examples was a server written with the standard library of Elixir, and a couple of people in the audience pointed out that in real servers the type of the reply usually depends on the type of the request. The natural answer is to give an intersection type to the function that computes the replies, and the question becomes how to make the clients of the server aware of this type. A couple of days later Daniel Gorín, of Meta, sent me an email that described a small Erlang server written in the way most Erlang code is written, and that concluded:1
“This one is IMO the main typing gap in Erlang atm: eqwalizer (or any other type-checker) can’t ensure the types of api and implementation are in sync. I consider this one the main gap, as most actual Erlang code is written this way, by implementing behaviours like gen_server and not that much sending/receiving messages directly, which are more like low-level primitives.”
Erlang is the language in which the servers of Meta’s WhatsApp are written, and eqWAlizer, the type checker that the email mentions, has been developed at Meta to type the code of WhatsApp [59 ] : so when a gap is called “the main typing gap in Erlang” by somebody who works with this code, it is worth taking it seriously.
The problem, which I explain in detail in § 5 , is the following. In Erlang and in Elixir a server is a process that answers requests. The programmer does not write the process: a library supplies it, provided that the programmer writes a function, handle_call (a “callback” for this library), that computes the reply to each request. Clients use another function of the library, call, that sends a request to the server and waits for the reply. The reply usually depends on the request, so the type of handle_call is overloaded. Thanks to the work of Mario Coppo, Mariangiola Dezani-Ciancaglini, and Simona Ronchi Della Rocca, and also of John Reynolds (not exactly minor figures, all four), this overloading can be expressed as an intersection of arrows, one for each kind of request; Erlang programmers already write such types, as we will see. But nothing relates this type to the type of call, whose result has the type of all values (the top type in a subtyping hierarchy): a client may expect an integer where the server can reply with an undefined value, and no checker will notice.
The solution, which I describe in Sections 6–8, is made of old pieces. When I tried to understand what the type of a server that answers requests of different kinds should be (what I ended up calling an “overloaded process”), I realized that the answer was in a paper that Mariangiola Dezani-Ciancaglini, Daniele Varacca and I wrote twenty years ago [14 ] ,2 and that it rests on a law that Barendregt, Coppo and Dezani-Ciancaglini stated in 1983 for their filter λ \lambda λ -model [2 ] :
( σ → τ ) ∧ ( σ → ρ ) ≤ σ → ( τ ∧ ρ ) (1) (\sigma\to\tau) \land(\sigma\to\rho) \le\sigma\to(\tau\land\rho) \tag*{(1)} ( σ → τ ) ∧ ( σ → ρ ) ≤ σ → ( τ ∧ ρ ) (1)
where σ \sigma σ , τ \tau τ and ρ \rho ρ denote types, σ ∧ τ \sigma\land\tau σ ∧ τ is the intersection of σ \sigma σ and τ \tau τ , and ≤ \le ≤ is subtyping. In words: a function that maps σ \sigma σ into τ \tau τ and maps σ \sigma σ into ρ \rho ρ maps σ \sigma σ into values that are both in τ \tau τ and in ρ \rho ρ .3 As we showed in Castagna et al. [14 ] , this law is lost when functions are encoded as processes; the solution that I propose here consists in applying the law before the encoding.
This is the reason why I chose this problem to celebrate the eightieth birthdays of Mario Coppo, Mariangiola Dezani-Ciancaglini and Simona Ronchi Della Rocca: it is the perfect excuse to tell how a law born in the study of the models of λ \lambda λ -calculus may end up typing the servers of WhatsApp, and to show how much the practical typing of Erlang and Elixir owes to their work.
The essay is informal. It relies on work in progress on the typing of processes [24 ] and of modules [6 , 5 ] in Elixir, and I state results as claims with sketches of proofs. The reader who wants the details will find them in Appendix A, a technical companion to Sections 5–8 drawn from the note from which this essay originated.
Plan of the article. The essay is organized as a journey, and its first stops are historical. Section 2 starts in Turin in 1978, with the intersection types that Coppo and Dezani-Ciancaglini introduced to characterize the strongly normalizing λ \lambda λ -terms, and stops at the filter model, where our law first appears. Section 3 adds unions and negations, and shows how semantic subtyping turned the laws of intersection and union types into properties of sets of values. Section 4 arrives in Elixir and Erlang, where functions defined by several clauses are typed by intersections. The second part of the essay is about servers. Section 5 is a primer for the λ \lambda λ -calculus who never wrote a server in Erlang or Elixir: it explains what processes and servers are, how they can be typed, and what the gap pointed out by Daniel is. Section 6 shows that the natural way of typing a server, that is, translating the type of handle_call as one translates functions into processes, loses the law, and recalls how we diagnosed this loss twenty years ago. Section 7 defines the operator that restores the law, and Section 8 shows that this operator is not ad hoc, since it is what polymorphism yields, by way of the expansions of Coppo, Dezani-Ciancaglini and Venneri and of the explicitly typed intersections of Ronchi Della Rocca. Section 9 goes back to Erlang and lists what is still missing. The essay has thus two keys of reading: the reader interested only in the history can stop at the end of Section 4; the reader interested only in servers can start from Section 4, going back to Section 3 for the notation of set-theoretic types. Table 1 lists the stops of the journey and the sections where each one is discussed.
Table 1. The journey of the axiom ( → ∧ ) (\to\wedge) ( → ∧ ) .
Several functional characters
Let me start at the beginning (how original, I know). Curry’s theory of functionality assigns simple types to λ \lambda λ -terms: if M M M has type σ → τ \sigma\to\tau σ → τ and N N N has type σ \sigma σ , then M N MN M N has type τ \tau τ . Types are preserved by reduction but not by expansion, and many terms in normal form, such as λ x . x x \lambda x.xx λ x . xx , have no type. Coppo and Dezani-Ciancaglini (1978, 1980) extended the theory with an intersection σ ∧ τ \sigma\wedge\tau σ ∧ τ , the type of the terms that have both type σ \sigma σ and type τ \tau τ , so that, for instance, λ x . x x \lambda x.xx λ x . xx has type ( σ ∧ ( σ → τ ) ) → τ (\sigma\wedge(\sigma\to\tau)) \to\tau ( σ ∧ ( σ → τ )) → τ . A type describes a functional behavior of a term, one of its “functional characters” (Curry’s words, which Coppo et al. (1981) kept in the title of their paper on solvable terms) and the novelty is that a term may have several of them at once, as x x x has in λ x . x x \lambda x.xx λ x . xx . In the resulting system the typable terms are exactly the strongly normalizing ones [27 , 50 ] .
Then came the model. Barendregt et al. (1983) ordered the types, which by then included a universal type ω \omega ω that every term has, by a preorder ≤ \leq ≤ (a subtyping relation, in today’s terms) for which ω \omega ω is the largest type, ∧ \wedge ∧ is the greatest lower bound, the arrow is contravariant in its domain and covariant in its codomain, ω ≤ ω → ω \omega\leq\omega\to\omega ω ≤ ω → ω , and ( → ∧ ) (\to\wedge) ( → ∧ ) holds. A filter is a set of types that contains ω \omega ω and is closed upwards with respect to ≤ \leq ≤ and under ∧ \wedge ∧ . The filter model interprets a term as the filter of its types; an application M N MN M N is then interpreted as the application F ⋅ G F \cdot G F ⋅ G . of the filter F F F of M M M to the filter G G G of N N N , defined as
F ⋅ G = { τ ∣ σ → τ ∈ F for some σ ∈ G } F \cdot G = \{\tau\mid\sigma\to\tau\in F\text{ for some }\sigma\in G\} F ⋅ G = { τ ∣ σ → τ ∈ F for some σ ∈ G }
This is where ( → ∧ ) (\to\land) ( → ∧ ) enters the scene: it is what makes F ⋅ G F \cdot G F ⋅ G closed under intersection (that F ⋅ G F \cdot G F ⋅ G contains ω \omega ω and is closed upwards follows from ω ≤ ω → ω \omega\leq\omega\to\omega ω ≤ ω → ω and from covariance). To see why, take τ 1 \tau_1 τ 1 and τ 2 \tau_2 τ 2 in F ⋅ G F \cdot G F ⋅ G ; if they are there it is because σ 1 → τ 1 \sigma_1 \to\tau_1 σ 1 → τ 1 and σ 2 → τ 2 \sigma_2 \to\tau_2 σ 2 → τ 2 are in F F F for some σ 1 , σ 2 ∈ G \sigma_1, \sigma_2 \in G σ 1 , σ 2 ∈ G . Then σ 1 ∧ σ 2 \sigma_1 \land\sigma_2 σ 1 ∧ σ 2 is in G G G , contravariance puts σ 1 ∧ σ 2 → τ 1 \sigma_1 \land\sigma_2 \to\tau_1 σ 1 ∧ σ 2 → τ 1 and σ 1 ∧ σ 2 → τ 2 \sigma_1 \land\sigma_2 \to\tau_2 σ 1 ∧ σ 2 → τ 2 in F F F , hence their intersection, and ( → ∧ ) (\to\land) ( → ∧ ) puts σ 1 ∧ σ 2 → τ 1 ∧ τ 2 \sigma_1 \land\sigma_2 \to\tau_1 \land\tau_2 σ 1 ∧ σ 2 → τ 1 ∧ τ 2 in F F F , so that τ 1 ∧ τ 2 \tau_1 \land\tau_2 τ 1 ∧ τ 2 is in F ⋅ G F \cdot G F ⋅ G . With this model, Barendregt, Coppo and Dezani-Ciancaglini proved that type assignment is complete for the interpretation of types as sets of elements of a λ \lambda λ -model, where σ ∧ τ \sigma\land\tau σ ∧ τ denotes the intersection of the sets and σ → τ \sigma\to\tau σ → τ the set of the elements that map every element of σ \sigma σ into τ \tau τ ; from this result they deduced the completeness of simple type assignment, which solved an open problem of Scott [56 ] . In this interpretation ( → ∧ ) (\to\land) ( → ∧ ) is an equality between sets, which is a first hint of what will come: once types are sets, the laws of intersection types become properties of sets.
The same group studied type inference, and this is where Simona Ronchi Della Rocca enters our story. A term has infinitely many types, and a principal type is one from which all the others can be obtained. For intersection types substitutions are not enough: one also needs expansions , which duplicate a part of a type into an intersection of copies. Coppo et al. [27 ] introduced principal type schemes with expansions, Ronchi Della Rocca and Venneri [54 ] extended them to the type theory of Barendregt, Coppo and Dezani-Ciancaglini, and Ronchi Della Rocca [52 ] studied unification for intersection types, from which she obtained a semialgorithm for type inference. We will meet expansions again in § 8 , where they explain how polymorphism produces the type of a server.
Two ideas of this period will travel all the way to the servers of WhatsApp: types denote sets, with intersection as set intersection; and an intersection of arrows describes a function with several behaviors (an overloaded function in modern lingo), which ( → ∧ ) (\to\land) ( → ∧ ) combines when they concern the same arguments.
Unions, negations, and types as sets of values
Unions came next. MacQueen et al. [45 ] interpreted types as ideals of a domain and gave a rule to eliminate unions,4 and Barbanera et al. [1 ] gave intersection and union types for the λ \lambda λ -calculus a syntax and a semantics. The union σ ∨ τ \sigma\lor\tau σ ∨ τ is the type of the terms that have type σ \sigma σ or type τ \tau τ , and their type theory contains, besides the distributivity of ∧ \land ∧ over ∨ \lor ∨ , the law
( σ → ρ ) ∧ ( τ → ρ ) ≤ ( σ ∨ τ ) → ρ (\sigma\to\rho) \land(\tau\to\rho) \leq(\sigma\lor\tau) \to\rho ( σ → ρ ) ∧ ( τ → ρ ) ≤ ( σ ∨ τ ) → ρ
an axiom that states that a function that maps σ \sigma σ into ρ \rho ρ and maps τ \tau τ into ρ \rho ρ maps σ ∨ τ \sigma\lor\tau σ ∨ τ into ρ \rho ρ . As for ( → ∧ ) (\to\land) ( → ∧ ) , the converse inequality holds, here by contravariance, so the law is an equation.
Intersection and union types then entered programming languages: intersection types with Forsythe (Reynolds [51 ] ) and the thesis of Pierce [49 ] , union types with Pierce [48 ] . But there is a catch. These languages, like the system of Barbanera, Dezani-Ciancaglini and de’Liguoro, have no construct that tests the type of a value at run time, and without one a function cannot select its behavior according to the type of its argument: a type such as ( σ 1 → τ 1 ) ∧ ( σ 2 → τ 2 ) (\sigma_1 \to\tau_1) \land(\sigma_2 \to\tau_2) ( σ 1 → τ 1 ) ∧ ( σ 2 → τ 2 ) does not describe two behaviors, it refines the description of a single one, a form of ad hoc polymorphism known as coherent overloading (Pierce [49 ] ; Reynolds [51 ] ). To behave differently on arguments of different types, a function must be able to test the type of its argument (Castagna et al. [12 , 13 ] ; Castagna (2024)), and this is what the functions of CDuce (discussed in the next paragraph), as well as those of Erlang and Elixir, can do.
The last step was to take sets as primary, which is what semantic subtyping does. Hosoya and Pierce [40 ] defined the subtyping relation of XDuce as the inclusion of sets of values, for first-order types that describe XML documents. Frisch et al. [38 , 39 ] extended the approach to functions and to negation, for the language CDuce, whose functional core is a λ \lambda λ -calculus with run-time type tests and set-theoretic types. A type t t t denotes a set of values; union, intersection and negation ¬ t \neg t ¬ t denote set-theoretic union, intersection and complement; 0 0 0 is the empty type, 1 1 1 the type of all values, t ∖ s t \setminus s t ∖ s stands for t ∧ ¬ s t \land\neg s t ∧ ¬ s ; and t ≤ s t \le s t ≤ s holds if and only if the set denoted by t t t is included in the set denoted by s s s . To break the circularity between the subtyping of arrows and the typing of functions, types are interpreted in a domain that does not depend on the terms of the language. For cardinality reasons, this domain cannot contain all the relations on itself; but, as in the graph model of Scott [57 ] , finite approximations suffice: arrow types are interpreted as sets of finite relations, which induce the same subtyping relation as sets of arbitrary relations would [39 ] . As a consequence, the laws (→ ∧ \to\land → ∧ ) and (∨ → \lor\to ∨ → ) are no longer axioms but properties of the interpretation. And although defined semantically, subtyping is decidable [39 ] .
In a sense, semantic subtyping reverses the construction of Barendregt, Coppo and Dezani-Ciancaglini: there, a model of the λ \lambda λ -calculus is built from a subtyping relation; here, a subtyping relation is built from a model of the types. The two approaches meet, and once more Mariangiola is at the meeting point: with Frisch, Giovannetti and Motohama she showed that the subtyping relation of CDuce restricted to arrows, unions and intersections coincides with the relevant entailment of the logic B + \mathrm{B}_{+} B + [30 ] .
Finally, Castagna and Lanvin (2017), Castagna et al. [20 ] and Lanvin [41 ] extended set-theoretic types to gradual typing, with a type for the values whose type is checked at run time. This is the theory on which the type system of Elixir is built, and part of the theory of Lanvin [41 ] is also used in eqWAlizer (which is not surprising, since Victor Lanvin is currently at Meta in charge of eqWAlizer).
Intersection types in Erlang and Elixir
So much for the theory: let us now see where these types landed. Erlang was designed at Ericsson in the 1980s for telecommunication systems, and its programs run on a virtual machine called the BEAM. Elixir, created by José Valim, runs on the same virtual machine and uses the same libraries. Both are dynamically typed functional languages whose values include integers, atoms,5 tuples { v 1 , … , v n } \{v_1, \ldots, v_n\} { v 1 , … , v n } , lists, maps (such as %{current: 42} that associates the key current with the value 42), functions, and process identifiers. Functions are defined by clauses, each with a pattern and possibly a guard, which are tried in order:
def negate(x) when is_integer(x), do: -x
def negate(x) when is_boolean(x), do: not x
An application negate(e e e ) executes the first clause whose pattern (here the simple capture variable x x x ) and guard accept the result of the evaluation of e e e , and fails if there is none. A guard is a test on the variables of the pattern, written after when: here is_integer(x) and is_boolean(x) test the type of x x x at run time, which is precisely the test that, as we saw in § 3 , a function needs in order to behave differently on arguments of different types. A definition by several clauses is thus a type-case (Castagna and Duboc, 2026), and the natural type of negate is an intersection:6
( integer ( ) → integer ( ) ) ∧ ( boolean ( ) → boolean ( ) ) (\operatorname{integer}() \to\operatorname{integer}()) \land(\operatorname{boolean}() \to\operatorname{boolean}()) ( integer ( ) → integer ( )) ∧ ( boolean ( ) → boolean ( ))
where integer() and boolean() are the types of integers and of Booleans in Elixir. From now on I abbreviate them as int and bool, I write types with the connectives of Section 3, and I use singleton types for atoms: the type :ok contains only the atom :ok.
The type system of Elixir ([22 , 31 ] (Castagna and Duboc 2026)) is a gradual system with set-theoretic types, based on the theory of Section 3. It has been included in the compiler since version 1.17 (June 2024); its latest version (v1.20 of June 2026) covers all constructs of the language and infers intersection types for functions defined by several clauses ([32 , 33 ] ). For negate it infers the type above, and thus it deduces that negate(e e e ) is an integer whenever e e e is, and likewise for Booleans ((Castagna and Duboc, 2026)).
Erlang programmers, for their part, have been writing intersection types for years, whether they call them so or not. A specification (a spec , in Erlang jargon) of an Erlang function may have several clauses, one for each clause of the function, and programmers call it an overloaded spec . In his email, Daniel specified the callback of the server of § 5 as follows:
-spec handle_call
(get_int, gen_server:from(), state()) -> {reply, integer(), state()};
({set_int, integer()}, gen_server:from(), state()) -> {reply, ok, state()}.
This is an intersection of two arrows in Erlang syntax: what Coppo, Dezani-Ciancaglini and Venneri called the several functional characters of a term is, at WhatsApp, one spec clause for each function clause. As Daniel’s email notes, one can write such a spec today for eqWAlizer. Dialyzer ([43 ] ), the traditional analyzer for Erlang, uses specs in an optimistic way and reports only code that is sure to fail; eqWAlizer is a type checker that uses part of the theory of gradual set-theoretic types of Lanvin [41 ] (§ 3 ).
Servers, for lambda-calculists
If you know the π \pi π -calculus, then you already know most of what you need to understand the servers of Erlang and Elixir. Let me fill in the details.
Processes. A process of the BEAM (the virtual machine on which Erlang and Elixir run) is a lightweight thread with a mailbox, identified by a process identifier, or pid . The expression spawn(f f f ) creates a process that runs the function f f f (a zero-ary function) and returns its pid; send(p p p , e e e ) puts the result of the evaluation of the expression e e e in the mailbox of the process identified by p p p and continues, since sends are asynchronous; receive expressions such as
receive do
{:add, k} when is_integer(k) -> k + 42
:stop -> 42
end
take from the mailbox of the running process the first message that matches one of the patterns and satisfies its guard, as for the clauses of a function (here, a pair formed by the atom :add and an integer k k k , or the atom :stop alone), waiting if there is none, and execute the corresponding branch. A process can read only its own mailbox. In the π \pi π -calculus terms, pids are channel names on which everybody can write but only one process, their owner, can read: the BEAM implements a local π \pi π -calculus ([46 ] ).
Pid types. To type processes I use the types of Castagna et al. [24 ] : pid ( t ) \operatorname{pid}(t) pid ( t ) is the type of the pids of the processes that accept the messages of type t t t . It is the type ch − ( t ) \operatorname{ch}^{-}(t) ch − ( t ) of the channels on which values of type t t t can be written, which Castagna et al. [15 ] introduced in their semantic subtyping for the π \pi π -calculus. Pid types satisfy the following laws [24 ] :
pid ( t ) ≤ pid ( s ) ⟺ s ≤ t (2) \operatorname{pid}(t) \le\operatorname{pid}(s) \Longleftrightarrow s \le t \tag*{(2)} pid ( t ) ≤ pid ( s ) ⟺ s ≤ t (2)
pid ( t 1 ) ∧ pid ( t 2 ) = pid ( t 1 ∨ t 2 ) (3) \operatorname{pid}(t_1) \land\operatorname{pid}(t_2) = \operatorname{pid}(t_1 \lor t_2) \tag*{(3)} pid ( t 1 ) ∧ pid ( t 2 ) = pid ( t 1 ∨ t 2 ) (3)
pid ( t ) ≤ ⋁ n ∈ N pid ( s n ) ⟺ s n ≤ t for some n ∈ N (4) \operatorname{pid}(t) \le\bigvee_{n \in\mathbb{N}} \operatorname{pid}(s_n) \Longleftrightarrow s_n \le t \text{ for some } n \in\mathbb{N} \tag*{(4)} pid ( t ) ≤ n ∈ N ⋁ pid ( s n ) ⟺ s n ≤ t for some n ∈ N (4)
The first law is contravariance: a pid that accepts all the messages in t t t can be used where only messages in some s ≤ t s \le t s ≤ t are sent. In particular pid ( 0 ) \operatorname{pid}(0) pid ( 0 ) , which I write pid ( ) \operatorname{pid}() pid ( ) as in Elixir, contains every pid, and no message can be sent safely to a pid of this type.
The second law says that a pid that accepts the messages in t 1 t_1 t 1 and those in t 2 t_2 t 2 accepts the messages in t 1 ∨ t 2 t_1 \lor t_2 t 1 ∨ t 2 : an intersection of pid types is the type of a process that handles several kinds of messages. It allows a process to share only a partial view of its mailbox with each of its clients, a view being a factor of the intersection.
The third law, which I call the union law , says that a pid type is included in a union of pid types only if it is included in one of them. Intuitively, pid ( t ) \operatorname{pid}(t) pid ( t ) contains the pid of a process that accepts exactly the messages in t t t , and this pid is in pid ( s n ) \operatorname{pid}(s_n) pid ( s n ) only if s n ≤ t s_n \le t s n ≤ t . It is the law that determines the type of a reply in Sections 6 and 7.
Behaviours and GenServer. Actually, Erlang programs rarely use send and receive directly. They use behaviours (sic: Erlang uses the British spelling), generic components of the OTP library (the Open Telecom Platform) that are parameterized by a callback module written by the programmer. The most common one is the generic server, gen_server in Erlang and GenServer in Elixir [36 , 35 ] . The library provides the server process; the programmer provides a function init, which computes the initial state of the server from an argument, and a function handle_call, which, given a request, the return address of the client and the current state, returns the reply and the new state. Stripped of tags, monitors, timeouts and of the other callbacks, the library is the following code, where m is the callback module:
def start_link(m, v) do
{:ok, s} = m.init(v)
{:ok, spawn(fn -> loop(&m.handle_call/3, s) end)}
end
def loop(h, s) do
receive do
{c, w} -> # a request c and a return address w
{:reply, r, s2} = h.(c, w, s)
send(w, r)
loop(h, s2)
end
end
def call(p, c) do
w = alias() # a fresh return address
send(p, {c, w})
receive_on(w) # wait for the reply sent to w
end
The function start_link computes the initial state with init, spawns the server process, which runs loop on the function handle_call of the module, and returns its pid. OTP does the same: when a server starts, it extracts the function handle_call from the module, and its loop applies this function (see Appendix A.7). For the reader who does not speak Elixir: = is pattern matching, so {:ok, s} = m.init(v) binds s, and fails if m.init(v) does not return a pair tagged by :ok; a module is a value, so m.init(v) calls the function init of the module bound to m; the capture operator & turns a function of a module into a value, so that &m.handle_call/3 denotes the function handle_call of arity 3 of m; fn -> e end is the abstraction λ ( ) . e \lambda().e λ ( ) . e , the zero-ary function that spawn expects; and h.(c, w, s) applies the function h, the dot marking the application of a function value (rather than a named function).
A client obtains a reply by evaluating call(p, c), where p is the pid of the server and c the call’s request. This function runs in the client process: it creates a fresh return address w, sends the pair {c, w} to the server, and blocks until a message arrives at w; this message, the reply, is the result of call. On the other side, loop receives the pair sent by the client call, computes the reply r and the new state s2 with h—i.e., with handle_call—, sends r to w, and starts again with s2. Here alias() stands for Process.alias(), which returns a new address whose messages arrive in the mailbox of the process that created it, and receive_on (which is not an Elixir primitive) stands for what the library does: receive_on(w) takes from this mailbox the first message sent to w, and returns it. The address is fresh so that the client cannot take for the reply another message of its mailbox, for instance the late reply to an earlier call.7
A λ \lambda λ -calculist will recognize the encoding of functions as processes of Milner [47 ] : the server encodes a λ \lambda λ -abstraction, a process that receives an argument together with a return channel and sends the result on it, and call encodes an application, which creates a fresh channel, sends it with the argument and waits on it. GenServer just adds a state, which the loop passes from a request to the next. In other terms, Erlang and Elixir programmers use Milner’s encoding of the λ \lambda λ -calculus into the π \pi π -calculus daily, packaged in a library.
An example. Here is the server of Daniel’s email, translated into Elixir. It stores an integer, and its module also contains the public interface (the API) that clients use:
defmodule MyServer do
use GenServer # MyServer is a GenServer callback module
def init(v), do: {:ok, %{current: v}} # initial state is a map with field current
def handle_call(:get_int, _from, s), do: {:reply, s.current, s}
def handle_call({:set_int, v}, _from, s), do: {:reply, :ok, %{s | current: v}}
# public API
def start_link(v), do: GenServer.start_link(MyServer, v)
def get_int(p), do: GenServer.call(p, :get_int)
def set_int(p, v), do: GenServer.call(p, {:set_int, v})
end
The state is a map with one field, current; s.current reads the field and %{s | current: v} updates it. The server accepts two kinds of requests, and handle_call has one clause for each, selected by pattern matching on its first argument, the request. The first clause handles the request :get_int, an atom with no payload; it replies with the stored integer and leaves the state unchanged. The second handles {:set_int, v}, a pair formed by the tag :set_int and a payload v, the new integer: it replies :ok and stores v in the state. Both clauses ignore the return address (the underscore in _from marks an unused variable), since the library itself sends the reply to it, and both return a triple {:reply, r, s2} with the reply r and the new state s2, as loop expects. The functions of the API hide the requests: get_int(p) and set_int(p, v) build the request and pass it to GenServer.call, and clients use the server only through them (GenServer.start_link and GenServer.call are the functions start_link and call above, qualified by the name of their module). Here is a typical client session, where s is the pid of the server:
{:ok, s} = MyServer.start_link(42)
MyServer.get_int(s) # 42
MyServer.set_int(s, 24) # :ok
MyServer.get_int(s) + 1 # 25
The callback has the intersection type of the overloaded spec of § 4 :
handle_call : ( ( :get_int , pid ( ) , state ) → { :reply , int , state } ) ∧ ( ( { :set_int , int } , pid ( ) , state ) → { :reply , :ok , state } ) \texttt{handle\_call} : ((\texttt{:get\_int}, \texttt{pid}(), \texttt{state}) \to\{\texttt{:reply}, \texttt{int}, \texttt{state}\}) \\
\land((\{\texttt{:set\_int}, \texttt{int}\}, \texttt{pid}(), \texttt{state}) \to\{\texttt{:reply}, \texttt{:ok}, \texttt{state}\}) handle_call : (( :get_int , pid ( ) , state ) → { :reply , int , state }) ∧ (({ :set_int , int } , pid ( ) , state ) → { :reply , :ok , state })
where ( t 1 , t 2 , t 3 ) → t (t_1,t_2,t_3) \to t ( t 1 , t 2 , t 3 ) → t is the type of the functions of three arguments, { t 1 , … , t n } \{t_1,\ldots,t_n\} { t 1 , … , t n } is the type of the tuples whose components have types t 1 , … , t n t_1,\ldots,t_n t 1 , … , t n , and state is the type of the state, that is, of the maps whose field current is an integer (i.e., %{current: integer()}). The second argument, the return address, has type pid() because no clause uses it. The API is meant to have the types get_int : s → int and set_int : (s, int) → :ok, for some type s s s of the server.
Typing call. What is the type s s s of a server, that is, of the pid of the process spawned by start_link (the s of the client session above), which is the first argument of call? This process runs loop: if it accepts requests of type c c c (for call , the name that GenServer gives to the requests that expect a reply) and it replies with values of type r r r (for reply ), then it receives pairs formed by a request and by a return address that accepts r r r . I write server ( c , r ) \operatorname{server}(c,r) server ( c , r ) for the type of its pid:
server ( c , r ) = pid ( c × pid ( r ) ) \operatorname{server}(c,r) = \operatorname{pid}(c \times\operatorname{pid}(r)) server ( c , r ) = pid ( c × pid ( r ))
where c × t c \times t c × t is the type of the pairs formed by a request of type c c c and a return address of type t t t . server ( c , r ) \operatorname{server}(c,r) server ( c , r ) is an abbreviation, not a new type constructor: precisely, server ( c , r ) \operatorname{server}(c,r) server ( c , r ) is the type of the processes to which one can send a request of type c c c together with an address on which values of type r r r can be sent. Since the return address in a request has type pid ( r ) \operatorname{pid}(r) pid ( r ) , the server can send on it only values of type r r r : the type does not promise that the server replies, but that, if it replies, the reply has type r r r . By the contravariance law (1), applied twice, server \operatorname{server} server is contravariant in c c c and covariant in r r r , as the arrow c → r c \to r c → r : for c ′ ≠ 0 c' \ne0 c ′ = 0 , server ( c , r ) ≤ server ( c ′ , r ′ ) \operatorname{server}(c,r) \le\operatorname{server}(c',r') server ( c , r ) ≤ server ( c ′ , r ′ ) if and only if c ′ ≤ c c' \le c c ′ ≤ c and r ≤ r ′ r \le r' r ≤ r ′ . A server is a function that one applies by sending a message.
The function call is then polymorphic:
call : ∀ c , r . ( server ( c , r ) , c ) → r \texttt{call} : \forall c,r.\,(\operatorname{server}(c,r),c) \to r call : ∀ c , r . ( server ( c , r ) , c ) → r
Given the pid p of a server for requests c c c and replies r r r , and a request c c c of type c c c , call(p, c) returns a value of type r r r . The client owns the fresh address w, so it can give it the type pid ( r ) \operatorname{pid}(r) pid ( r ) ; the pair {c, w} then has type c × pid ( r ) c \times\operatorname{pid}(r) c × pid ( r ) , which is what p accepts; and since only values of type r r r can be sent to w, receive_on(w) returns a value of type r r r (see Theorem 1 in Appendix § 12 ). The type of the result of call is thus fixed by the type of the server: call is exactly as precise as the type given to p.
The gap. Today the library types the pid of a server as pid() and the result of call as ⊥, the type of all values (term() in Erlang and in Elixir). The API of MyServer is therefore not checked: a spec get_int : (pid()) → int is taken on trust. Daniel’s email shows the danger. Suppose that the stored value may now be nil, so that the first arrow of handle_call becomes
( :get_int , pid ( ) , s t a t e ) → { :reply , i n t ∨ n i l , s t a t e } (\texttt{:get\_int}, \operatorname{pid}(), \mathit{state}) \to\{\texttt{:reply}, \mathit{int} \lor\mathit{nil}, \mathit{state}\} ( :get_int , pid ( ) , state ) → { :reply , int ∨ nil , state }
and that the programmer forgets to update the API. Nothing complains, but a client that evaluates MyServer.get_int(s) + 1 crashes when the server holds nil. As Daniel puts it, a sound checker “MUST catch this” (the capitals are his). He also added: “My intuition is that using a union of LHS-types and a union of RHS-types won’t be enough to capture this, as you need to keep the ‘valid’ LHS/RHS pairs somehow in sync”. His intuition is right: typing the server, before the change, as server(:get_int ∨ {:set_int, int}, int ∨ :ok), with the union of the requests and the union of the replies, is sound, but then call returns int ∨ :ok on :get_int, and the pairs are lost. The type of a server must keep the correspondence between requests and replies that the intersection type of handle_call expresses.
Functions as processes, or how an axiom gets lost
Since GenServer is Milner’s encoding of functions, the natural idea is to type the server by the translation of types that accompanies this encoding: the Milner–Turner translation MT [55 ] . As defined by Castagna et al. (2006, §4.1), it maps an arrow to the type of the channels that receive an argument together with a return channel for the result,
M T ( c → r ) = pid ( c × pid ( r ) ) = server ( c , r ) \mathrm{MT}(c \to r) = \operatorname{pid}(c \times\operatorname{pid}(r)) = \operatorname{server}(c,r) MT ( c → r ) = pid ( c × pid ( r )) = server ( c , r )
and commutes with the other type constructors, so that the translation of an intersection of arrows is the intersection of their translations. Leaving aside the state and the return address, which play no role here (see Appendix § 12 .§ 1 ), the type of handle_call is an intersection ⋀ i ∈ I ( c i → r i ) \bigwedge_{i \in I}(c_i \to r_i) ⋀ i ∈ I ( c i → r i ) , one arrow for each kind of request, and MT translates it into the intersection of servers ⋀ i ∈ I server ( c i , r i ) \bigwedge_{i \in I}\operatorname{server}(c_i,r_i) ⋀ i ∈ I server ( c i , r i ) .
Let us try it on MyServer, where ( : g e t _ i n t → i n t ) ∧ ( { : s e t _ i n t , i n t } → : o k ) (:\mathtt{get\_int} \to\mathtt{int}) \wedge(\{\mathtt{:set\_int},\mathtt{int}\} \to\mathtt{:ok}) ( : get_int → int ) ∧ ({ : set_int , int } → : ok ) is the type we obtain for handle_call leaving aside state and return address. Its translation gives the type:
server ( : g e t _ i n t , i n t ) ∧ server ( { : s e t _ i n t , i n t } , : o k ) = pid ( ( : g e t _ i n t × pid ( i n t ) ) ∨ ( { : s e t _ i n t , i n t } × pid ( : o k ) ) ) \begin{aligned}
\operatorname{server}(:\mathtt{get\_int},\mathtt{int}) \wedge\operatorname{server}(\{\mathtt{:set\_int},\mathtt{int}\},\mathtt{:ok}) \\
&= \operatorname{pid}((:\mathtt{get\_int} \times\operatorname{pid}(\mathtt{int})) \vee(\{\mathtt{:set\_int},\mathtt{int}\} \times\operatorname{pid}(\mathtt{:ok})))
\end{aligned} server ( : get_int , int ) ∧ server ({ : set_int , int } , : ok ) = pid (( : get_int × pid ( int )) ∨ ({ : set_int , int } × pid ( : ok )))
where the equality is given by the law in (3) . To type call(p, :get_int) we look for an r r r such that this type is below server ( : g e t _ i n t , r ) = pid ( : g e t _ i n t × pid ( r ) ) \operatorname{server}(:\mathtt{get\_int},r) = \operatorname{pid}(:\mathtt{get\_int} \times\operatorname{pid}(r)) server ( : get_int , r ) = pid ( : get_int × pid ( r )) . By contravariance this holds if and only if : g e t _ i n t × pid ( r ) ≤ ( : g e t _ i n t × pid ( i n t ) ) ∨ ( { : s e t _ i n t , i n t } × pid ( : o k ) ) :\mathtt{get\_int} \times\operatorname{pid}(r) \le(:\mathtt{get\_int} \times\operatorname{pid}(\mathtt{int})) \vee(\{\mathtt{:set\_int},\mathtt{int}\} \times\operatorname{pid}(\mathtt{:ok})) : get_int × pid ( r ) ≤ ( : get_int × pid ( int )) ∨ ({ : set_int , int } × pid ( : ok )) , that is, since the two requests are disjoint, if and only if pid ( r ) ≤ pid ( i n t ) \operatorname{pid}(r) \le\operatorname{pid}(\mathtt{int}) pid ( r ) ≤ pid ( int ) , that is, i n t ≤ r \mathtt{int} \le r int ≤ r . The least solution is r = i n t r = \mathtt{int} r = int , so call returns an integer and get_int type-checks. After Daniel’s change the least solution is r = i n t ∨ n i l r = \mathtt{int} \vee\mathtt{nil} r = int ∨ nil , so call returns a value of type i n t ∨ n i l \mathtt{int} \vee\mathtt{nil} int ∨ nil , and the declared result i n t \mathtt{int} int of get_int is rejected, as Daniel wants. So far, so good: the translation settles Daniel’s example.
But it does not settle every server, because the requests of different arrows may overlap. Consider a callback of type
h : ( : a ∨ : b → i n t ∨ n i l ) ∧ ( : b ∨ : c → i n t ∨ : o k ) (5) h : (:\mathtt{a} \vee:\mathtt{b} \to\mathtt{int} \vee\mathtt{nil}) \wedge(:\mathtt{b} \vee:\mathtt{c} \to\mathtt{int} \vee:\mathtt{ok}) \tag*{(5)} h : ( : a ∨ : b → int ∨ nil ) ∧ ( : b ∨ : c → int ∨ : ok ) (5)
Applied to :b, h h h returns an integer: by contravariance h h h has type : b → i n t ∨ n i l :\mathtt{b} \to\mathtt{int} \vee\mathtt{nil} : b → int ∨ nil and type : b → i n t ∨ : o k :\mathtt{b} \to\mathtt{int} \vee:\mathtt{ok} : b → int ∨ : ok , hence, by ( → ∧ ) (\to\wedge) ( → ∧ ) , type : b → ( i n t ∨ n i l ) ∧ ( i n t ∨ : o k ) = : b → i n t :\mathtt{b} \to(\mathtt{int} \vee\mathtt{nil}) \wedge(\mathtt{int} \vee:\mathtt{ok}) = :\mathtt{b} \to\mathtt{int} : b → ( int ∨ nil ) ∧ ( int ∨ : ok ) =: b → int . The translation gives server ( : a ∨ : b , i n t ∨ n i l ) ∧ server ( : b ∨ : c , i n t ∨ : o k ) \operatorname{server}(:\mathtt{a} \vee:\mathtt{b},\mathtt{int} \vee\mathtt{nil}) \wedge\operatorname{server}(:\mathtt{b} \vee:\mathtt{c},\mathtt{int} \vee:\mathtt{ok}) server ( : a ∨ : b , int ∨ nil ) ∧ server ( : b ∨ : c , int ∨ : ok ) , and call on : b :\mathtt{b} : b now requires pid ( r ) ≤ pid ( i n t ∨ n i l ) ∨ pid ( i n t ∨ : o k ) \operatorname{pid}(r) \le\operatorname{pid}(\mathtt{int} \vee\mathtt{nil}) \vee\operatorname{pid}(\mathtt{int} \vee:\mathtt{ok}) pid ( r ) ≤ pid ( int ∨ nil ) ∨ pid ( int ∨ : ok ) , which by the union law (4) holds if and only if i n t ∨ n i l ≤ r \mathtt{int} \vee\mathtt{nil} \le r int ∨ nil ≤ r or i n t ∨ : o k ≤ r \mathtt{int} \vee:\mathtt{ok} \le r int ∨ : ok ≤ r . There are two incomparable minimal solutions, and neither of them is i n t \mathtt{int} int . The point is that the client sends a single return address, and the union of the two kinds of pairs offers either an address for i n t ∨ n i l \mathtt{int} \vee\mathtt{nil} int ∨ nil or an address for i n t ∨ : o k \mathtt{int} \vee:\mathtt{ok} int ∨ : ok , never one address for their intersection.
The reason is general: MT respects ( ∨ → ) (\vee\to) ( ∨ → ) but not ( → ∧ ) (\to\wedge) ( → ∧ ) . By (2) and the distributivity of products over unions,
MT ( ( σ → ρ ) ∧ ( τ → ρ ) ) = pid ( ( σ × pid ( ρ ) ) ∨ ( τ × pid ( ρ ) ) ) = pid ( ( σ ∨ τ ) × pid ( ρ ) ) = MT ( ( σ ∨ τ ) → ρ ) \begin{aligned}
\operatorname{MT}((\sigma\to\rho) \wedge(\tau\to\rho)) = \operatorname{pid}((\sigma\times\operatorname{pid}(\rho)) \vee(\tau\times\operatorname{pid}(\rho))) \\
&= \operatorname{pid}((\sigma\vee\tau) \times\operatorname{pid}(\rho)) = \operatorname{MT}((\sigma\vee\tau) \to\rho)
\end{aligned} MT (( σ → ρ ) ∧ ( τ → ρ )) = pid (( σ × pid ( ρ )) ∨ ( τ × pid ( ρ ))) = pid (( σ ∨ τ ) × pid ( ρ )) = MT (( σ ∨ τ ) → ρ )
MT ( ( σ → τ ) ∧ ( σ → ρ ) ) = pid ( σ × ( pid ( τ ) ∨ pid ( ρ ) ) ) \operatorname{MT}((\sigma\to\tau) \wedge(\sigma\to\rho)) = \operatorname{pid}(\sigma\times(\operatorname{pid}(\tau) \vee\operatorname{pid}(\rho))) MT (( σ → τ ) ∧ ( σ → ρ )) = pid ( σ × ( pid ( τ ) ∨ pid ( ρ )))
MT ( σ → τ ∧ ρ ) = pid ( σ × pid ( τ ∧ ρ ) ) \operatorname{MT}(\sigma\to\tau\wedge\rho) = \operatorname{pid}(\sigma\times\operatorname{pid}(\tau\wedge\rho)) MT ( σ → τ ∧ ρ ) = pid ( σ × pid ( τ ∧ ρ ))
For σ ≠ 0 \sigma\ne0 σ = 0 , by contravariance MT ( ( σ → τ ) ∧ ( σ → ρ ) ) ≤ MT ( σ → τ ∧ ρ ) \operatorname{MT}((\sigma\to\tau) \land(\sigma\to\rho)) \le\operatorname{MT}(\sigma\to\tau\land\rho) MT (( σ → τ ) ∧ ( σ → ρ )) ≤ MT ( σ → τ ∧ ρ ) holds if and only if pid ( τ ∧ ρ ) ≤ pid ( τ ) ∨ pid ( ρ ) \operatorname{pid}(\tau\land\rho) \le\operatorname{pid}(\tau) \lor\operatorname{pid}(\rho) pid ( τ ∧ ρ ) ≤ pid ( τ ) ∨ pid ( ρ ) , which by the union law holds if and only if τ ≤ ρ \tau\le\rho τ ≤ ρ or ρ ≤ τ \rho\le\tau ρ ≤ τ . In words, the translation maps the two sides of ( → ∧ ) (\to\land) ( → ∧ ) , which are equivalent types, to different types whenever τ \tau τ and ρ \rho ρ are incomparable.
Twenty years ago, Mariangiola Dezani-Ciancaglini, Daniele Varacca and I met this very problem when we were trying to encode the λ \lambda λ -calculus with semantic subtyping (i.e., CDuce) into the π \pi π -calculus with semantic subtyping, called Cπ \pi π [14 ] (at the time, I confess, Erlang servers were not on our minds, and WhatsApp was still three years away). We singled out the equation ( σ → τ ) ∧ ( σ → τ ′ ) = σ → τ ∧ τ ′ (\sigma\to\tau) \land(\sigma\to\tau') = \sigma\to\tau\land\tau' ( σ → τ ) ∧ ( σ → τ ′ ) = σ → τ ∧ τ ′ , the form that ( → ∧ ) (\to\land) ( → ∧ ) takes in CDuce, as “for the goals of this work an utmostly interesting equation”, and observed that “the Milner-Turner translation of arrow types respects the subtyping relation in the context of the simply typed λ \lambda λ -calculus, but it breaks down in the presence of intersection types”. We also gave the operational reason, which we called output-driven overloading . A process that receives a request together with a return channel can choose its reply not only according to the type of the request, but also according to the type of the return channel it received, which the π \pi π -calculus of Castagna et al. [15 ] can test: if it replies with a τ \tau τ on a channel of type pid ( τ ) \operatorname{pid}(\tau) pid ( τ ) and with a τ ′ \tau' τ ′ on a channel of type pid ( τ ′ ) \operatorname{pid}(\tau') pid ( τ ′ ) , then it has type MT ( ( σ → τ ) ∧ ( σ → τ ′ ) ) \operatorname{MT}((\sigma\to\tau) \land(\sigma\to\tau')) MT (( σ → τ ) ∧ ( σ → τ ′ )) but not type MT ( σ → τ ∧ τ ′ ) \operatorname{MT}(\sigma\to\tau\land\tau') MT ( σ → τ ∧ τ ′ ) , unless τ ≤ τ ′ \tau\le\tau' τ ≤ τ ′ or τ ′ ≤ τ \tau' \le\tau τ ′ ≤ τ [14 §4.2] .
Our solution was to scramble the return channel. The return channel of the encoding has the type of a λ \lambda λ -channel
ch λ ( t ) = ( ¬ pid ( ¬ t ) ∨ pid ( 1 ) ) ∧ pid ( 0 ) \operatorname{ch}^{\lambda}(t) = (\lnot\operatorname{pid}(\lnot t) \lor\operatorname{pid}(1)) \land\operatorname{pid}(0) ch λ ( t ) = ( ¬ pid ( ¬ t ) ∨ pid ( 1 )) ∧ pid ( 0 )
which contains pid ( t ) \operatorname{pid}(t) pid ( t ) together with “noise”, the channels that accept neither all of t t t nor all of ¬ t \lnot t ¬ t . Thanks to the noise, λ \lambda λ -channels satisfy ch λ ( t 1 ∧ t 2 ) = ch λ ( t 1 ) ∨ ch λ ( t 2 ) \operatorname{ch}^{\lambda}(t_1 \land t_2) = \operatorname{ch}^{\lambda}(t_1) \lor\operatorname{ch}^{\lambda}(t_2) ch λ ( t 1 ∧ t 2 ) = ch λ ( t 1 ) ∨ ch λ ( t 2 ) : as we wrote, the return channel “must be scrambled by introducing some noise at the type level so that the receiver cannot gain information by testing the type of the return channel”. The resulting encoding of CDuce into the π \pi π -calculus preserves typing, subtyping, and reduction [14 ] .
Unfortunately, this solution is not available on the BEAM. To reply on a λ \lambda λ -channel, a process must first check that the channel is a genuine pid ( r ) \operatorname{pid}(r) pid ( r ) , and the encoding contains a branch, the “functional garbage”, that receives the noise and does nothing [14 §5.3] . A BEAM pid carries no type at run time, so this check cannot be programmed, and a server typed with λ \lambda λ -channels could reply only where λ \lambda λ -channels add no noise, that is, where they coincide with pid types (see Appendix § 12 .9.6). For the same reason, output-driven overloading cannot be programmed either, but the types cannot exclude it: the law pid ( t 1 ∧ t 2 ) ≤ pid ( t 1 ) ∨ pid ( t 2 ) \operatorname{pid}(t_1 \land t_2) \le\operatorname{pid}(t_1) \lor\operatorname{pid}(t_2) pid ( t 1 ∧ t 2 ) ≤ pid ( t 1 ) ∨ pid ( t 2 ) that would restore ( → ∧ ) (\to\land) ( → ∧ ) is false, since a pid that accepts only the atom :foo is in pid ( int ∧ bool ) = pid ( 0 ) \operatorname{pid}(\operatorname{int} \land\operatorname{bool}) = \operatorname{pid}(0) pid ( int ∧ bool ) = pid ( 0 ) but neither in pid ( int ) \operatorname{pid}(\operatorname{int}) pid ( int ) nor in pid ( bool ) \operatorname{pid}(\operatorname{bool}) pid ( bool ) .
However, there is one more idea in Castagna et al. [14 ] , and it is the one we need. The rule that types functions requires the arrows of their interfaces to have disjoint domains, a restriction that “is necessary (but not sufficient) in order to avoid the problem of output-driven overloading”. It causes no loss of generality, since every interface can be put in this form by iterating the rewriting
( σ h → τ h ) ∧ ( σ k → τ k ) ⇝ ( σ h ∧ σ k → τ h ∧ τ k ) ∧ ( σ k ∖ σ h → τ k ) ∧ ( σ h ∖ σ k → τ h ) (\sigma_h \to\tau_h) \land(\sigma_k \to\tau_k) \leadsto(\sigma_h \land\sigma_k \to\tau_h \land\tau_k) \land(\sigma_k \setminus\sigma_h \to\tau_k) \land(\sigma_h \setminus\sigma_k \to\tau_h) ( σ h → τ h ) ∧ ( σ k → τ k ) ⇝ ( σ h ∧ σ k → τ h ∧ τ k ) ∧ ( σ k ∖ σ h → τ k ) ∧ ( σ h ∖ σ k → τ h )
for every pair of arrows whose domains intersect. The rewriting applies ( → ∧ ) (\to\land) ( → ∧ ) to the common part of the two domains, and the next section applies it to the type of handle_call.
Overloaded servers, or how the axiom is regained
So let us apply the law before the encoding. Let the type of the handle_call of a module m m m be ⋀ i ∈ I ( c i → r i ) \bigwedge_{i \in I}(c_i \to r_i) ⋀ i ∈ I ( c i → r i ) . For every nonempty P ⊆ I P \subseteq I P ⊆ I , let
C P = ⋀ i ∈ P c i ∨ ⋁ j ∈ I ∖ P c j R P = ⋀ i ∈ P r i C_P = \bigwedge_{i \in P} c_i \;\lor\; \bigvee_{j \in I \setminus P} c_j
\qquad
R_P = \bigwedge_{i \in P} r_i C P = i ∈ P ⋀ c i ∨ j ∈ I ∖ P ⋁ c j R P = i ∈ P ⋀ r i
The region C P C_P C P contains the requests that are in the domains of exactly the arrows in P P P , and R P R_P R P is the reply that these arrows guarantee together. The regions are pairwise disjoint, and c i = ⋁ P ∋ i C P c_i = \bigvee_{P\ni i} C_P c i = ⋁ P ∋ i C P for every i i i . Hence, by ( ∨ → ) (\vee\to) ( ∨ → ) and then by ( → ∧ ) (\to\wedge) ( → ∧ ) ,
⋀ i ∈ I ( c i → r i ) = ⋀ i ∈ I ⋀ P ∋ i ( C P → r i ) = ⋀ P ⋀ i ∈ P ( C P → r i ) = ⋀ P ( C P → R P ) \bigwedge_{i\in I}(c_i\to r_i)=\bigwedge_{i\in I}\bigwedge_{P\ni i}(C_P\to r_i)=\bigwedge_P\bigwedge_{i\in P}(C_P\to r_i)=\bigwedge_P(C_P\to R_P) i ∈ I ⋀ ( c i → r i ) = i ∈ I ⋀ P ∋ i ⋀ ( C P → r i ) = P ⋀ i ∈ P ⋀ ( C P → r i ) = P ⋀ ( C P → R P )
This is the normal form that the rewriting of Castagna et al. [14 ] computes: its domains, the regions, are pairwise disjoint, and the last equality above, which uses ( → ∧ ) (\to\wedge) ( → ∧ ) , gathers in R P R_P R P the replies that all the arrows of P P P guarantee on C P C_P C P .
Consider now a server started from m m m , that is, the process spawned by start_link(m, v), whose pid start_link returns. I write server_of(m) for the type of this pid, and I define it as the translation of the normal form ⋀ P ( C P → R P ) \bigwedge_P(C_P\to R_P) ⋀ P ( C P → R P ) of the type of handle_call, where the empty regions can be dropped.8
server_of ( m ) = MT ( ⋀ P ( C P → R P ) ) = ⋀ P : C P ≠ 0 server ( C P , R P ) \operatorname{server\_of}(m)=\operatorname{MT}\left(\bigwedge_P(C_P\to R_P)\right)=\bigwedge_{P:C_P\ne0}\operatorname{server}(C_P,R_P) server_of ( m ) = MT ( P ⋀ ( C P → R P ) ) = P : C P = 0 ⋀ server ( C P , R P )
The order of the two steps is the point. The translation cannot apply ( → ∧ ) (\to\wedge) ( → ∧ ) afterwards: as we saw in § 6 , for incomparable τ \tau τ and ρ \rho ρ it maps ( σ → τ ) ∧ ( σ → ρ ) (\sigma\to\tau)\wedge(\sigma\to\rho) ( σ → τ ) ∧ ( σ → ρ ) to the type of a server that accepts a return address for τ \tau τ or one for ρ \rho ρ , but not one for τ ∧ ρ \tau\wedge\rho τ ∧ ρ . Applying ( → ∧ ) (\to\wedge) ( → ∧ ) first computes the intersections R P R_P R P while they are still intersections of replies, and leaves to the translation arrows with disjoint domains, on which, as we shall see, it loses nothing. Thus start_link, applied to m m m , returns a value of type {:ok, server_of(m)}, a type that depends on m m m and that the module types of Bretagne [6 ] and Boussaa et al. [5 ] can express (see Appendix § 12 .§ 2 ).
Take a module m m m whose handle_call has the type of h h h in equation (5) of § 6 . The regions are :a (in the first domain only), :b (in both) and :c (in the second only), and
server_of ( m ) = server ( : a , int ∨ nil ) ∧ server ( : b , int ) ∧ server ( : c , int ∨ : o k ) \operatorname{server\_of}(m)=\operatorname{server}(:a,\operatorname{int}\vee\operatorname{nil})\wedge\operatorname{server}(:b,\operatorname{int})\wedge\operatorname{server}(:c,\operatorname{int}\vee:ok) server_of ( m ) = server ( : a , int ∨ nil ) ∧ server ( : b , int ) ∧ server ( : c , int ∨ : o k )
and call on :b returns an integer, as h h h applied to :b does. For MyServer, and in general when the domains are pairwise disjoint (one arrow per clause with pairwise disjoint request patterns, which is the common case), the regions are the clauses and server_of(m) is the translation ⋀ i server ( c i , r i ) \bigwedge_i\operatorname{server}(c_i,r_i) ⋀ i server ( c i , r i ) of § 6 .
Two claims justify the definition. First, server_of is exact : if the C j C_j C j (j ∈ J j\in J j ∈ J ) are pairwise disjoint, then
⋀ j ∈ J ( C j → R j ) ≤ c → r ⟺ ⋀ j ∈ J server ( C j , R j ) ≤ server ( c , r ) \bigwedge_{j\in J}(C_j\to R_j)\le c\to r\quad\Longleftrightarrow\quad\bigwedge_{j\in J}\operatorname{server}(C_j,R_j)\le\operatorname{server}(c,r) j ∈ J ⋀ ( C j → R j ) ≤ c → r ⟺ j ∈ J ⋀ server ( C j , R j ) ≤ server ( c , r )
because both sides hold if and only if c ≤ ⋁ j ∈ J C j c\le\bigvee_{j\in J}C_j c ≤ ⋁ j ∈ J C j and R j ≤ r R_j\le r R j ≤ r for every j j j such that c ∧ C j ≠ 0 c\wedge C_j\ne0 c ∧ C j = 0 : on the left by the decomposition of arrows of Frisch et al. [39 ] , on the right by the decomposition of products and the union law. The regions are pairwise disjoint, so the equivalence applies to them, and its right-hand side is server_of(m) ≤ server ( c , r ) \le\operatorname{server}(c,r) ≤ server ( c , r ) . Consequently call, on a request of type c ≤ ⋁ i c i c\le\bigvee_i c_i c ≤ ⋁ i c i , returns exactly ⋁ P : c ∧ C P ≠ 0 R P \bigvee_{P:c\wedge C_P\ne0}R_P ⋁ P : c ∧ C P = 0 R P , the type of the application of handle_call to c c c (see Claim 1 in Appendix § 12 ); and on a request outside the domain of handle_call, call is rejected, as it should be. Second, server_of is optimal : server_of(m) is below the translation of every intersection of arrows equivalent to the type of handle_call, so it is the most precise type that the translation of such an intersection can give to the server (see Claim 2 in Appendix § 12 ).9
Exactness is what checks the API against the implementation. The API declares the type of the server, either as server_of(MyServer) or by hand, and start_link checks that server_of(m) is below it. A type written by hand with the old reply, server(:get_int, int)∧· · ·, is rejected after Daniel’s change: since the two requests are disjoint, exactness reduces server_of(MyServer) ≤ server(:get_int, int) to int ∨ nil ≤ int, which is false.
What is, then, an overloaded process? Appendix D of the extended version of Castagna et al. [14 ] translates channel types back into function types, reading pid(t) as t → u n i t t \to\mathrm{unit} t → unit , the type of a continuation, and Castagna et al. [24 ] build pid types on this reading. Then server(c, r) reads ( c × ( r → u n i t ) ) → u n i t (c \times(r \to\mathrm{unit})) \to\mathrm{unit} ( c × ( r → unit )) → unit , the type of c → r c \to r c → r in continuation-passing style. Law (2), read on continuations, becomes ⋀ i ( t i → u n i t ) = ( ⋁ i t i ) → u n i t \bigwedge_i(t_i \to\mathrm{unit}) = (\bigvee_i t_i) \to\mathrm{unit} ⋀ i ( t i → unit ) = ( ⋁ i t i ) → unit ; applied with t i = c i × ( r i → u n i t ) t_i = c_i \times(r_i \to\mathrm{unit}) t i = c i × ( r i → unit ) , it turns the translation of an intersection of arrows into a single arrow:
⋀ i ∈ I server ( c i , r i ) = ⋀ i ∈ I ( ( c i × ( r i → u n i t ) ) → u n i t ) = ( ⋁ i ∈ I ( c i × ( r i → u n i t ) ) ) → u n i t \bigwedge_{i\in I}\operatorname{server}(c_i,r_i) = \bigwedge_{i\in I}((c_i \times(r_i \to\mathrm{unit})) \to\mathrm{unit}) = \left(\bigvee_{i\in I}(c_i \times(r_i \to\mathrm{unit}))\right) \to\mathrm{unit} i ∈ I ⋀ server ( c i , r i ) = i ∈ I ⋀ (( c i × ( r i → unit )) → unit ) = ( i ∈ I ⋁ ( c i × ( r i → unit )) ) → unit
A process is therefore never overloaded on its result: its overloading lies in its domain ⋁ i ∈ I ( c i × ( r i → u n i t ) ) \bigvee_{i\in I}(c_i \times(r_i \to\mathrm{unit})) ⋁ i ∈ I ( c i × ( r i → unit )) , a union of products in which the type of the request determines the type of the continuation. Applied to a request in c 1 ∧ c 2 c_1 \land c_2 c 1 ∧ c 2 , a function returns a value of type r 1 ∧ r 2 r_1 \land r_2 r 1 ∧ r 2 ; a process receives the request with a single continuation, which this union requires to accept all of r 1 r_1 r 1 or all of r 2 r_2 r 2 . The regions add the summand C { 1 , 2 } × ( ( r 1 ∧ r 2 ) → u n i t ) C_{\{1,2\}} \times((r_1 \land r_2) \to\mathrm{unit}) C { 1 , 2 } × (( r 1 ∧ r 2 ) → unit ) , which restores the intersection.
A real handle_call may also reply later. In a second email (received when most of this essay was already written), Daniel pointed out that this is common: the server may not have the answer yet, because it waits for another message, or the answer may be expensive to compute, and the server hands the request to a worker process. The clause then returns {:noreply, s} and keeps the return address from, in its state or in the message to the worker, and eventually some process calls GenServer.reply(from, v), which sends the reply v to from and makes it the result of the client’s GenServer.call. The type of from must then carry the type of the reply, “or else we can get unsoundness again”, as Daniel wrote: today GenServer.reply accepts any reply. In our setting the type of from does carry it: the arrow of such a clause types from as pid(r_i), so that GenServer.reply(from, v) type-checks only if v has type r i r_i r i , wherever from has been stored or sent (see Appendix § 12 .§ 4 ). Daniel’s email speaks of a phantom type, and pid(r_i) is one.10
What matters about this phantom type is its variance. A clause of handle_call that does not use from is typed by an arrow that types from as pid(), as in § 5 , so the address of a client that waits for an integer, of type pid(int), must also have type pid(). Contravariance gives exactly this: pid(int) ≤ \le ≤ pid() since 0 ≤ i n t 0 \le\mathrm{int} 0 ≤ int , but pid(int) ≰ \not\le ≤ pid(1). If pid() were covariant this would be unsound: pid(int) would be a subtype of pid(1), an address for integers would be an address for any value, and GenServer.reply(from, :foo) would type-check even if the client waits for an integer. An invariant parameter would be sound but too rigid: pid(int) would not be a subtype of pid(), and such a clause could not accept the address. With disjoint domains the pid(r_i) form gives server_of(m) again; with overlapping domains it gives only ⋀ i server ( c i , r i ) \bigwedge_i \operatorname{server}(c_i,r_i) ⋀ i server ( c i , r i ) , unless the programmer also declares the arrows of the regions that are lost (see Appendix § 12 .§ 4 ).
server_of for free: expansions and intersections à la Church
At this point a skeptical reader may object that server_of is an ad hoc operator, tailored for GenServer: the checker must know it, read the type of handle_call, compute the regions and build a server type, and another behaviour would need another operator. It is not: server_of need not be defined, since it is what polymorphism gives to the function that starts a server, provided that instantiation may produce intersections. The library only has to declare how the type of a callback determines the type of a server, and an ordinary polymorphic type suffices for this. Take the function serve that starts a server from the callback itself and from the initial state, that is, start_link with the callback in place of the module and without init.11
def serve(h, s), do: spawn(fn -> loop(h, s) end)
where loop is the loop of § 5 . Its type is
s e r v e : ∀ c , r , s . ( ( ( c , pid ( ) , s ) → { : r e p l y , r , s } ) , s ) → server ( c , r ) \mathop{\mathrm{serve}} : \forall c,r,s.\ \left(((c,\operatorname{pid}(),s) \to\{:reply,r,s\}),s\right) \to\operatorname{server}(c,r) serve : ∀ c , r , s . ( (( c , pid ( ) , s ) → { : r e pl y , r , s }) , s ) → server ( c , r )
and it says nothing about regions: a callback for requests c c c and replies r r r gives a server for requests c c c and replies r r r . The regions come from the instantiation. In the polymorphic set-theoretic types of Castagna et al. [18 ] , an application may instantiate a polymorphic function with a set of type substitutions, and the function then has the intersection of the corresponding instances. This is how one deduces, for instance, that the polymorphic identity function id, of type ∀ α . α → α \forall\alpha.\ \alpha\to\alpha ∀ α . α → α , also has type ( int → int ) ∧ ( bool → bool ) (\operatorname{int} \to\operatorname{int}) \land(\operatorname{bool} \to\operatorname{bool}) ( int → int ) ∧ ( bool → bool ) : instantiating α \alpha α with int gives int → int \operatorname{int} \to\operatorname{int} int → int , instantiating α \alpha α with bool gives bool → bool \operatorname{bool} \to\operatorname{bool} bool → bool , and since id has all the types of its instances, it has their intersection. The same type is obtained by expanding the polymorphic type, in the sense of § 2 , into ∀ α 1 , α 2 . ( α 1 → α 1 ) ∧ ( α 2 → α 2 ) \forall\alpha_1,\alpha_2.\ (\alpha_1 \to\alpha_1) \land(\alpha_2 \to\alpha_2) ∀ α 1 , α 2 . ( α 1 → α 1 ) ∧ ( α 2 → α 2 ) , and then instantiating the two fresh variables with int and bool. Now let us apply this to serve: take one substitution for each region, [ c : = C P , r : = R P , s : = s t a t e ] [c := C_P,\ r := R_P,\ s := state] [ c := C P , r := R P , s := s t a t e ] , and give serve the intersection of the instances that these substitutions produce:
s e r v e : ⋀ P ( ( ( C P , pid ( ) , s t a t e ) → { r e p l y , R P , s t a t e } ) , s t a t e ) → server ( C P , R P ) \mathop{\mathrm{serve}} : \bigwedge\nolimits_P\left(((C_P,\operatorname{pid}(),state) \to\{\mathop{\mathrm{reply}},R_P,state\}),state\right) \to\operatorname{server}(C_P,R_P) serve : ⋀ P ( (( C P , pid ( ) , s t a t e ) → { reply , R P , s t a t e }) , s t a t e ) → server ( C P , R P )
The type of handle_call is equivalent to ⋀ P ( ( C P , pid ( ) , s t a t e ) → { r e p l y , R P , s t a t e } ) \bigwedge\nolimits_P((C_P,\operatorname{pid}(),state) \to\{\mathop{\mathrm{reply}},R_P,state\}) ⋀ P (( C P , pid ( ) , s t a t e ) → { reply , R P , s t a t e }) , so it is below the first component of every domain of this intersection, and, for an initial state s s s of type s t a t e state s t a t e , serve(handle_call, s) has type ⋀ P server ( C P , R P ) \bigwedge\nolimits_P\operatorname{server}(C_P,R_P) ⋀ P server ( C P , R P ) , that is, server_of(m).12 No other set of substitutions does better: every valid set gives a supertype of server_of(m) (see Appendix § 12 .§ 3 ).
Therefore server_of(m) need not be defined: it is the type that the rule for polymorphic application gives to serve(handle_call, s) with the best set of substitutions. What is specific to GenServer is only the type of serve, that is, the protocol, which the library declares once and the checker trusts, since the library is untyped. The regions are not specific to GenServer: they are the normalization of an overloaded arrow into arrows with disjoint domains, a property of set-theoretic types, and they apply in the same way to any other signature that derives the type of a server from the type of a callback from requests to replies. The checker must still find the substitutions, but this is a generic problem, to which I come back below. A new behaviour then needs a new signature, not a new operator in the checker.
Sets of substitutions have a history, and this is where Simona’s work comes into play. Castagna et al. [18 ] describe the problem of choosing them as an instance of “the problem of determining expansions for intersection type systems”, with a reference to Coppo et al. (1980): the instantiation of serve at the regions is an expansion of its type, which duplicates the type into one copy for each region before substituting in each copy. The calculus of Castagna et al. [18 ] is explicitly typed, and its related work compares it with the explicitly typed calculi for intersection types of Simona Ronchi Della Rocca. In Ronchi Della Rocca [53 ] , typing derivations are written as terms, and the typed versions of the same untyped term are joined by an intersection; Liquori and Ronchi Della Rocca [44 ] separate the computational content, an untyped term with marks, from the logical content, a proof term. In the style of Ronchi Della Rocca [53 ] , serve(handle_call, s) would be typed as the intersection of one typed copy of serve for each region; Castagna et al. [18 ] decorate a single copy with the set of substitutions [ c : = C P , r : = R P , s : = s t a t e ] P [c := C_P, r := R_P, s := state]_P [ c := C P , r := R P , s := s t a t e ] P . The two lines that Castagna et al. [18 ] join, explicitly typed intersections and semantic subtyping, had already met once: Simona’s paper and the paper on the relevance of semantic subtyping of § 3 appeared in the same volume, the proceedings of ITRS 2002. Finally, to infer such substitutions the type reconstruction of Castagna et al. [19 ] solves tallying problems, which play for set-theoretic types the role that unification ([52 ] ) plays for intersection types.
One obstacle remains: unlike serve, start_link does not receive handle_call but a module. With the module types of Bretagne [6 ] and Boussaa et al. [5 ] , the behaviour GenServer is a module type with parameters, among which the type of the requests and the type of the replies, and a module has this type only at its declared parameters, here V i c i V_i c_i V i c i and V i r i V_i r_i V i r i , since parameters are invariant (see the types for reply: and call_msg: in the code of Appendix § 12 .§ 1 ). The only valid instantiation then gives server(V i c i , V i r i V_i c_i, V_i r_i V i c i , V i r i ), the union that Daniel’s intuition rejected. Typing start_link by quantifying over the types of the callbacks of the module, rather than over the parameters of the behaviour, or changing the typing of applications, so that a module is accepted at every instance of the behaviour that its declarations satisfy, restores the instantiation at the regions, and then start_link does not need server_of either; but these are sketches that I have not yet checked against the module calculus (see Appendix § 12 .§ 8 ). Until they are checked, start_link keeps the type of § 7 , with server_of, which polymorphism explains but does not yet replace.
Back to WhatsApp
So, can an Erlang checker close the gap? Nothing in the solution is specific to Elixir, and a checker such as eqWAlizer needs:
the intersection type of handle_call, which programmers already write as overloaded specs;
a type server(c , r c, r c , r ) for the pids of servers, and the polymorphic type of gen_server:call;
a type for the pid returned by start_link: server_of of the callback module, or a server type declared by the API and checked against it;
the laws of pid types of § 5 , union law included.
eqWAlizer is not built on the set-theoretic types of § 3 : it uses part of the theory of Lanvin [41 ] , but only for its gradual typing. These ingredients, therefore, do not all belong to the theory that eqWAlizer currently implements, but they are not too far from it, and none of them requires a change in the code of gen_server: besides the specs that programmers write, they concern the signatures of the library, that is, those of start_link, call and reply, which the checker must trust since the library is untyped, and the checker itself (see Appendix § 12 .§ 7 ). In the common case in which the request types of the arrows are pairwise disjoint (one arrow per clause, with disjoint patterns), moreover, no region has to be computed: server_of(m m m ) is then the plain intersection ⋀ i server ( c i , r i ) \bigwedge_i \operatorname{server}(c_i,r_i) ⋀ i server ( c i , r i ) , which can be read directly from the overloaded spec.
Of course, some gaps remain (see Appendix § 12 .§ 5 ). The main one in practice is that servers are usually registered under a name (an atom, often the name of the module, that the runtime associates with the pid), and the API calls GenServer.call with the name instead of the pid, so that the pid of type server_of(m m m ) returned by start_link never reaches the API; giving types to names would close this gap, for instance through a typed name: option. Calls on a pid obtained from whereis, which returns the pid registered under a name, are untyped, and a hot code upgrade, which replaces the code of a running server, must preserve the type of the server: the server type of the new code must be below that of the old one, and code_change, the callback that converts the state, must map the old state into the new state type. The other callbacks (handle_cast, for requests without reply, and handle_info, for the other messages) raise no new question. The generic state machine gen_statem (Ericsson, [37 ] ) does: besides its data, which plays the role of the state of a GenServer, it keeps a control state that determines how each event is handled, so its replies depend on this state: its servers would need types indexed by states, closer to the session types that Mario Coppo and Mariangiola Dezani-Ciancaglini have studied in the last twenty years ([29 , 4 ] ) than to intersections. But this is another story, maybe for the next birthday.
Conclusion
All these pages tell a very simple story. GenServer is a library to create servers that implement functions. For that it provides two functions: serve ( f ) \operatorname{serve}(f) serve ( f ) , which creates a server that implements the function f f f (it is the function serve of § 8 , stripped of the specificities of GenServer), and call ( p , e ) \operatorname{call}(p,e) call ( p , e ) , which sends the argument e e e to the server p p p and returns the server’s result (it is the apply function for servers rather than for functions). GenServer implements the “functions as processes” transformation of Robin Milner [47 ] : the server serve ( f ) \operatorname{serve}(f) serve ( f ) is an address on which you deposit a request together with an address on which the server puts its answer; call ( p , e ) \operatorname{call}(p,e) call ( p , e ) handles the protocol for you, as it sends to the server p p p the request e e e with a fresh return address, and returns the result it reads on the latter. In an untyped setting this is all you need.
In a typed world, your f f f ’s have a type and your servers have typed mailboxes: pid ( t ) \operatorname{pid}(t) pid ( t ) is the type of the addresses that accept the messages of type t t t . If f f f is of type c → r c \to r c → r , from calls to replies, then serve ( f ) \operatorname{serve}(f) serve ( f ) is an address of type pid ( c × pid ( r ) ) \operatorname{pid}(c \times\operatorname{pid}(r)) pid ( c × pid ( r )) : you deposit in it a request of type c c c and an address that accepts r r r ; and since serve works not just with one function but with any function, and call not just with one server but with any server, they have polymorphic types: serve : ∀ c , r . ( c → r ) → pid ( c × pid ( r ) ) \operatorname{serve} : \forall c,r.\ (c \to r) \to\operatorname{pid}(c \times\operatorname{pid}(r)) serve : ∀ c , r . ( c → r ) → pid ( c × pid ( r )) and call : ∀ c , r . ( pid ( c × pid ( r ) ) , c ) → r \operatorname{call} : \forall c,r.\ (\operatorname{pid}(c \times\operatorname{pid}(r)),c) \to r call : ∀ c , r . ( pid ( c × pid ( r )) , c ) → r . If you are in a simply typed world, this is all you need: your calls to a server are typed as the applications of the function that the server implements.
But in the world of GenServer, your f f f ’s are overloaded: the type of the result depends on the type of the request. Transposed into the world of Mario, Mariangiola and Simona, your f f f has an intersection type as in Coppo and Dezani-Ciancaglini (1978, 1980), and it is defined by multiple clauses, one for each arrow, as in the multiply typed copies that Ronchi Della Rocca (2002) joins in an intersection. If f f f is of type ⋀ i ( c i → r i ) \bigwedge_i(c_i \to r_i) ⋀ i ( c i → r i ) , then, by the magic of expansion (Coppo et al., 1980), which turns the type of serve into the intersection of its instances ( c i → r i ) → pid ( c i × pid ( r i ) ) (c_i \to r_i) \to\operatorname{pid}(c_i \times\operatorname{pid}(r_i)) ( c i → r i ) → pid ( c i × pid ( r i )) , serve ( f ) \operatorname{serve}(f) serve ( f ) has type ⋀ i pid ( c i × pid ( r i ) ) \bigwedge_i \operatorname{pid}(c_i \times\operatorname{pid}(r_i)) ⋀ i pid ( c i × pid ( r i )) , that is, by (2), pid ( ⋁ i ( c i × pid ( r i ) ) ) \operatorname{pid}(\bigvee_i(c_i \times\operatorname{pid}(r_i))) pid ( ⋁ i ( c i × pid ( r i ))) . If all c i c_i c i are pairwise disjoint, then call ( p , e ) \operatorname{call}(p,e) call ( p , e ) , with p p p of this type and e e e of type c k c_k c k , has type r k r_k r k , as the application of f f f to e e e does. If the c i c_i c i are not pairwise disjoint, this is no longer true: with a request in both c h c_h c h and c k c_k c k , the server accepts a return address for r h r_h r h or one for r k r_k r k , never one for r h ∧ r k r_h \wedge r_k r h ∧ r k , which is the type of the reply of f f f . The encoding has lost the axiom ( → ∧ ) (\to\wedge) ( → ∧ ) , as Mariangiola, Daniele and I found twenty years ago.
But the heroes of this story come once more to the rescue: we can split each arrow of ⋀ i ( c i → r i ) \bigwedge_i(c_i \to r_i) ⋀ i ( c i → r i ) by the law ( ∨ → ) (\vee\to) ( ∨ → ) , so that any two arrows have either disjoint domains or the same domain, and then use ( → ∧ ) (\to\wedge) ( → ∧ ) to merge the arrows with the same domain, so that all the domains are pairwise disjoint. So all you have to do is to expand the type of serve into one copy for each of these new arrows, rather than for each arrow of f f f (for start_link, which receives a module, the operator server_of applies the two laws directly), and let union, intersection and expansion do the rest: the server gets the type that makes every call as precise as the corresponding application of f f f . Both born in the 1980s, Erlang and the axiom ( → ∧ ) (\to\wedge) ( → ∧ ) finally meet in WhatsApp.
Acknowledgments
My first thanks go to Mario, Mariangiola and Simona, whose work this essay has followed from Turin to WhatsApp. For their sixtieth birthdays, Rocco De Nicola, Daniele Varacca and I contributed the semantic subtyping of the π \pi π -calculus [15 ] , whose channel types are now the types of pids in the type system that we are designing for Elixir; this essay is its sequel. With Mariangiola I have written several papers, and she has always inspired me. Together we encoded the λ \lambda λ -calculus into the π \pi π -calculus, both with semantic subtyping [14 ] , the paper on which a large part of this one rests. We jointly supervised Elena Giachino, and with her and Luca Padovani we wrote Foundations of session types [16 ] . With Luca Padovani, Mariangiola and I studied global types and multiparty sessions [17 ] . Earlier, as an editor of Information and Computation, she had handled the paper by Gang Chen and me on dependent types with subtyping. It was the first time that all the reports on one of my papers were of such quality, and we dared to thank her in the paper “for such a wise choice” of reviewers [9 ] (I was young). At 80, Mariangiola is still an indefatigable young researcher.
I also thank Daniel Gorín for the problem and for the permission to quote his emails; Luca Padovani and Daniele Varacca, with whom the typing of processes in Elixir is being developed; Aghilas Boussaa, Antonin Bretagne, and José Valim, for the module types; Guillaume Duboc and again José Valim for the type system of Elixir. Finally, I thank Victor Lanvin, who put me in touch with Roberto Aloi, and Roberto, who invited me to the Stockholm meetup that he was organizing: this essay was born from the discussions at that meetup. Roberto Aloi, Mickaël Laurent and José Valim gave me useful suggestions on a draft version of this essay.
Happy eightieth birthday, Mario, Mariangiola and Simona.
Paris, le 3 novembre 2026
Technical development
This appendix is a technical companion to § 5 –§ 8 : it gives the definitions, the claims and their proofs that the main text only states, and a minimal model of GenServer in which the claims become theorems. I assume that the reader has read the main text.
The running example is the server MyServer of § 5 , decorated with type annotations. Appendix § 12 .§ 1 presents it, together with the problem; Appendix § 12 .§ 2 defines server_of and states its properties, and Appendix § 12 .§ 3 relates it to polymorphism; Appendix § 12 .§ 4 deals with the clauses that reply later, and Appendix § 12 .§ 5 lists the conditions under which all this works. Appendix § 12 .§ 6 fixes a minimal model of the gen-server loop on which the claims become theorems, Appendix § 12 .§ 7 compares this model with OTP, and Appendix § 12 .§ 8 lists the questions that I leave open. Appendix § 12 .§ 9 gives the proofs and the technical details.
The running example and the problem
Today the server MyServer of § 5 is “typed” with one spec per clause of handle_call, that is, with an intersection type, and with pid() for the server, so that nothing relates its API to its implementation. Here is the same server with the types that a programmer should write:
defmodule MyServer do
$behaviour GenServer[init_arg: integer(),
reply: integer() or :ok,
call_msg: :get_int or {:set_int, integer()}]
$opaque state = %{current: integer()}
def init(v), do: {:ok, %{current: v}}
$ ((:get_int, pid(), state) -> {:reply, integer(), state}) and
(({:set_int, integer()}, pid(), state) -> {:reply, :ok, state})
def handle_call(:get_int, _from, s), do: {:reply, s.current, s}
def handle_call({:set_int, v}, _from, s), do: {:reply, :ok, %{s | current: v}}
# public API
$type server = GenServer.server_of(MyServer)
# = GenServer.server(:get_int, integer())
# and GenServer.server({:set_int, integer()}, :ok)
$ (integer()) -> {:ok, server}
def start_link(v), do: GenServer.start_link(MyServer, v)
$ (server) -> integer()
def get_int(pid), do: GenServer.call(pid, :get_int) # r = integer()
$ (server, integer()) -> :ok
def set_int(pid, v), do: GenServer.call(pid, {:set_int, v}) # r = :ok
end
{:ok, s} = MyServer.start_link(42)
MyServer.get_int(s) # 42
:ok = MyServer.set_int(s, 24)
MyServer.get_int(s) + 1 # 25
In the code, purple marks the syntax that is not in Elixir today, which comes from two proposals. A line $ t declares the type t t t of the function definition that follows: it is the syntax of the type signatures of Castagna et al. [22 ] , which the roadmap of Elixir plans to introduce [34 ] . The type of handle_call is an intersection, written and, of two arrows, one for each kind of request, whose domains list the types of the three arguments (or, in the other lines, is union). The other constructs come from the module types of Bretagne [6 ] and Boussaa et al. [5 ] . In them a behaviour is a module type with type parameters, and $behaviour GenServer[p: t, ...] declares that the module implements the behaviour GenServer, with its parameters p instantiated at the types t: the type init_arg of the argument of init, the type reply of the replies, and the type call_msg of the requests. $opaque state = ... defines state, the type of the internal state of the server, as an abstract type: inside the module it denotes the maps whose field current is an integer; outside, it is opaque, so that clients cannot inspect the state. $type defines a type: here server, the type of the pids of the servers started from MyServer, which the operator GenServer.server_of computes from the type of handle_call (Appendix § 12 .§ 2 ). The comment under it gives the result, written with the type GenServer.server(c, r), a parameterized type that the library declares, written server(c, r) below, and the comments of the API give the type r at which call is instantiated.
In general, the reply of a server depends on the request, and handle_call has an intersection type
⋀ i ∈ I ( ( c i , pid ( ) , s t a t e ) → { : r e p l y , r i , s t a t e } ) (6) \bigwedge_{i\in I} ((c_i,\ \operatorname{pid}(),\ state) \to\{:reply,\ r_i,\ state\}) \tag*{(6)} i ∈ I ⋀ (( c i , pid ( ) , s t a t e ) → { : r e pl y , r i , s t a t e }) (6)
where c i c_i c i is a call’s request type and r i r_i r i the corresponding reply type: for MyServer, c 1 = :get_int c_1 = \texttt{:get\_int} c 1 = :get_int and r 1 = int r_1 = \texttt{int} r 1 = int , c 2 = {:set_int, int} c_2 = \texttt{\{:set\_int, int\}} c 2 = {:set_int, int} and r 2 = :ok r_2 = \texttt{:ok} r 2 = :ok . We want call to return r i r_i r i on a request of type c i c_i c i , so that the API is checked against the implementation: if the reply of a request changes and the API does not, the checker must reject the API. This excludes the simplest type for the server, the one with the union of the requests and the union of the replies: it is sound, but with call on :get_int returns int ∨ :ok (§ 5 ). This was also pointed out in Daniel’s message: “using a union of LHS-types and a union of RHS-types won’t be enough to capture this, as you need to keep the ‘valid’ LHS/RHS pairs somehow in sync”. The second argument of handle_call is the return address from. Until Appendix § 12 .§ 4 every arrow types it as pid(), that is, pid(0), the largest pid type, which suits the clauses that do not use from, such as those of MyServer, whose replies the library sends (no message can be sent to a pid of this type). Then the return address and the state play no role in the type of the server: what matters are the request types c i c_i c i and the reply types r i r_i r i . Appendix § 12 .§ 4 deals with the clauses that do use from.
Let me recall that pid(t) is the type of the pids that accept the messages of type t t t , and that it satisfies the laws (1) (contravariance), (2) (interface views), and (3) (the union law), stated in § 5 . The pid of a server that accepts requests of type c c c and replies of type r r r , and the function call of the library, have the types
server ( c , r ) = pid ( c × pid ( r ) ) \operatorname{server}(c,r) = \operatorname{pid}(c \times\operatorname{pid}(r)) server ( c , r ) = pid ( c × pid ( r ))
call : ∀ c , r . ( server ( c , r ) , c ) → r \operatorname{call} : \forall c,r.\ (\operatorname{server}(c,r),c) \to r call : ∀ c , r . ( server ( c , r ) , c ) → r
In OTP the request also carries the atom :"$gen_call", the return address a fresh reference, and start_link may also return :ignore or an error; as in § 5 , I omit them until Appendix § 12 .§ 7 , which restores them.
The requirement. Daniel’s email continues with a requirement. The stored value may now be nil (Erlang’s undefined); the implementation is updated, but the API is not. Then a sound checker “MUST catch this” (the capitals are his), since a client that evaluates MyServer.get_int(s) + 1 crashes when the server holds nil. Here is the second version of MyServer, where both init and set_int accept nil (the clauses do not change, just the types):
$behaviour GenServer[
init_arg: integer() or nil,
reply: integer() or nil or :ok,
call_msg: :get_int or {:set_int, integer() or nil}]
$opaque state = %{current: integer() or nil}
$ ((:get_int, pid(), state) -> {:reply, integer() or nil, state}) and
({:set_int, integer() or nil}, pid(), state) -> {:reply, :ok, state})
...
$ (server) -> integer() # not updated
def get_int(pid), do: GenServer.call(pid, :get_int) # rejected
The two requests are still disjoint, so there is one region per clause (§ 7 ):
server_of ( M y S e r v e r ) = server ( : g e t _ i n t , i n t ∨ n i l ) ∧ server ( { : s e t _ i n t , i n t ∨ n i l } , : o k ) \operatorname{server\_of}(\mathit{MyServer}) = \operatorname{server}(\mathord{:}\mathit{get\_int},\mathit{int} \mathbin{\vee} \mathit{nil}) \mathbin{\wedge} \operatorname{server}(\{\mathord{:}\mathit{set\_int},\mathit{int} \mathbin{\vee} \mathit{nil}\},\mathord{:}\mathit{ok}) server_of ( MyServer ) = server ( : get_int , int ∨ nil ) ∧ server ({ : set_int , int ∨ nil } , : ok )
Therefore call on :get_int returns int ∨ nil, which is not a subtype of the declared result integer() of get_int: this function is rejected, and the expression MyServer.get_int(s) + 1 cannot crash on nil. The function set_int, instead, is still accepted: its requests {:set_int, v}, with v an integer, are in the region of the second arrow, whose reply is :ok.
There are two ways to fix this second version. The first one updates the API, declaring for get_int the type $ (server) -> integer() or nil $: then get_int is accepted, and the error moves to the client, where MyServer.get_int(s) + 1 is rejected, since + does not accept nil. The second one keeps the API and changes the server, so that get_int waits while the stored value is nil: this is the third version of the example, that we discuss in Appendix § 12 .§ 4 .
The operator server_of
Forget the return address _from and the state s: through handle_call, a server started from a module m implements a function of type ⋀ i ∈ I ( c i → r i ) \bigwedge_{i\in I}(c_i \mathbin{\to} r_i) ⋀ i ∈ I ( c i → r i ) from requests to replies, and we want call to return what an application of this function returns. § 6 shows that the Milner–Turner translation ⋀ i ∈ I server ( c i , r i ) \bigwedge_{i\in I}\operatorname{server}(c_i,r_i) ⋀ i ∈ I server ( c i , r i ) may fail to do it when the c i c_i c i overlap (see also the paragraph “Overlapping domains” below), and § 7 that applying ( → ∧ ) (\to\mathbin{\wedge}) ( → ∧ ) before the translation repairs it: we split the requests into regions, map each region to the intersection of the replies of the arrows whose domains contain it, and only then translate.
For P ⊆ I P \subseteq I P ⊆ I nonempty, let C P C_P C P be the requests in the domains of exactly the arrows in P P P , and R P R_P R P the reply they guarantee:
C P = ⋀ i ∈ P c i \ ⋁ j ∈ I ∖ P c j R P = ⋀ i ∈ P r i server_of ( m ) = ⋀ P : C P ≠ ∅ server ( C P , R P ) C_P = \bigwedge_{i\in P}c_i \mathbin{\backslash} \bigvee_{j\in I\setminus P}c_j \qquad R_P = \bigwedge_{i\in P}r_i \qquad\operatorname{server\_of}(m) = \bigwedge_{P:C_P\ne\varnothing}\operatorname{server}(C_P,R_P) C P = i ∈ P ⋀ c i \ j ∈ I ∖ P ⋁ c j R P = i ∈ P ⋀ r i server_of ( m ) = P : C P = ∅ ⋀ server ( C P , R P )
where m m m is the module whose handle_call has the type (5) of Appendix § 12 .§ 1 .13 The regions C P C_P C P are pairwise disjoint and form a partition of the request domain ⋁ i ∈ I c i \bigvee_{i\in I}c_i ⋁ i ∈ I c i of handle_call: every request in this domain is in exactly one region, and a server of type server_of(m) replies to a request in a region C P C_P C P with a value of type R P R_P R P , exactly as an application of $m.handle_callwould do. Claim 2 below shows thatserver_of(m)is the *most precise* type that the Milner–Turner translation can give to such a server, when it translates an intersection of arrows equivalent to the type ofhandle_call` (the restriction to intersections of arrows matters: see Footnote 9).
Then start_link returns server_of(m):
s t a r t _ l i n k : ∀ a . ( m : : GenServer [ i n i t _ a r g : a ] , a ) → { : o k , server_of ( m ) } \mathit{start\_link} : \forall a.\ (m :: \operatorname{GenServer}[\mathit{init\_arg}:a],a) \to\{\mathord{:}\mathit{ok},\operatorname{server\_of}(m)\} start_link : ∀ a . ( m :: GenServer [ init_arg : a ] , a ) → { : ok , server_of ( m )}
This signature uses the module types of Appendix § 12 .§ 1 : GenServer[init_arg: a] is the type of the modules that implement GenServer with the parameter init_arg instantiated at a, whatever the other two. A behaviour is a type only when all its parameters are instantiated: a parameter that a signature does not mention stands for a type variable, quantified by the signature and occurring nowhere else. The binder m :: T says that the first argument has type T and gives it the name m, which the result type uses: server_of(m) is computed from the type of handle_call of m, which differs from module to module, so start_link has a dependent type, the type of a function whose result type depends on the module it receives (it depends only on the type of this module, which is known statically). The dependency cannot be avoided by writing the result type with the variables of the parameters call_msg and reply: since parameters are invariant, this gives only server ( ⋁ i c i , ⋁ i r i ) \operatorname{server}(\bigvee_i c_i,\bigvee_i r_i) server ( ⋁ i c i , ⋁ i r i ) , the type with the union of the requests and the union of the replies of Appendix § 12 .§ 1 (see Appendix § 12 .§ 3 ).
The first property of server_of is that the translation loses nothing on arrows with pairwise disjoint domains.
Claim 1. Let J ≠ ∅ J \ne\emptyset J = ∅ , and let the C j C_j C j (j ∈ J j \in J j ∈ J ) be pairwise disjoint. Then the following conditions are equivalent:
(i) ⋀ j ∈ J ( C j → R j ) ≤ c → r \bigwedge_{j\in J}(C_j \to R_j) \le c \to r ⋀ j ∈ J ( C j → R j ) ≤ c → r ;
(ii) ⋀ j ∈ J server ( C j , R j ) ≤ server ( c , r ) \bigwedge_{j\in J}\operatorname{server}(C_j,R_j) \le\operatorname{server}(c,r) ⋀ j ∈ J server ( C j , R j ) ≤ server ( c , r ) ;
(iii) c ≤ ⋁ j ∈ J C j c \le\bigvee_{j\in J} C_j c ≤ ⋁ j ∈ J C j , and R j ≤ r R_j \le r R j ≤ r for every j ∈ J j \in J j ∈ J such that c ∧ C j ≠ 0 c \land C_j \ne0 c ∧ C j = 0 .
In words, the subtyping inequalities (i) and (ii) both say what (iii) states: the C j C_j C j cover c c c , and every C j C_j C j that c c c meets guarantees a reply in r r r .
Let us see the claim at work on the second version of MyServer of Appendix § 12 .§ 1 , that is the one with the type of handle_call updated with the nil reply. Suppose that the API had written the type server by hand, with the old reply that does not include nil:
server ( :get_int , int ) ∧ server ( { :set_int , int } , :ok ) \operatorname{server}(\texttt{:get\_int},\texttt{int}) \land\operatorname{server}(\{\texttt{:set\_int},\texttt{int}\},\texttt{:ok}) server ( :get_int , int ) ∧ server ({ :set_int , int } , :ok )
Then the error moves to start_link, which checks that server_of(MyServer) is below this type, hence below server ( :get_int , int ) \operatorname{server}(\texttt{:get\_int},\texttt{int}) server ( :get_int , int ) . The regions of the second version are C 1 = :get_int C_1 = \texttt{:get\_int} C 1 = :get_int and C 2 = { :set_int , int ∨ nil } C_2 = \{\texttt{:set\_int},\texttt{int} \lor\texttt{nil}\} C 2 = { :set_int , int ∨ nil } , with replies R 1 = int ∨ nil R_1 = \texttt{int} \lor\texttt{nil} R 1 = int ∨ nil and R 2 = :ok R_2 = \texttt{:ok} R 2 = :ok ; the request :get_int \texttt{:get\_int} :get_int meets C 1 C_1 C 1 only, so the claim reduces server_of ( MyServer ) ≤ server ( :get_int , int ) \operatorname{server\_of}(\texttt{MyServer}) \le\operatorname{server}(\texttt{:get\_int},\texttt{int}) server_of ( MyServer ) ≤ server ( :get_int , int ) to int ∨ nil ≤ int \texttt{int} \lor\texttt{nil} \le\texttt{int} int ∨ nil ≤ int , which is false. The claim is needed here: the contravariance of the return address alone, server ( :get_int , int ∨ nil ) ≰ server ( :get_int , int ) \operatorname{server}(\texttt{:get\_int},\texttt{int} \lor\texttt{nil}) \not\le\operatorname{server}(\texttt{:get\_int},\texttt{int}) server ( :get_int , int ∨ nil ) ≤ server ( :get_int , int ) , would not suffice to reject the type written by hand, since an intersection may be below a type even if none of its components is.
To use the claim on the type of handle_call, we need it in region form. As § 7 shows, the function from requests to replies is equivalent to the intersection of the arrows of its regions, whose domains are pairwise disjoint:
⋀ i ∈ I ( c i → r i ) = ⋀ P : C P ≠ 0 ( C P → R P ) (7) \bigwedge_{i\in I}(c_i \to r_i) = \bigwedge_{P:C_P\ne0}(C_P \to R_P) \tag*{(7)} i ∈ I ⋀ ( c i → r i ) = P : C P = 0 ⋀ ( C P → R P ) (7)
The same holds for the type of handle_call, whose domains are triples with the same second and third components:
⋀ i ∈ I ( ( c i , pid ( ) , state ) → { :reply , r i , state } ) = ⋀ P : C P ≠ 0 ( ( C P , pid ( ) , state ) → { :reply , R P , state } ) (8) \begin{aligned}
\bigwedge_{i\in I}\bigl((c_i,\operatorname{pid}(),\operatorname{state}) \to\{\texttt{:reply},r_i,\operatorname{state}\}\bigr) \\
= \bigwedge_{P:C_P\ne0}\bigl((C_P,\operatorname{pid}(),\operatorname{state}) \to\{\texttt{:reply},R_P,\operatorname{state}\}\bigr) \tag*{(8)}
\end{aligned} i ∈ I ⋀ ( ( c i , pid ( ) , state ) → { :reply , r i , state } ) = P : C P = 0 ⋀ ( ( C P , pid ( ) , state ) → { :reply , R P , state } ) (8)
where the domains ( C P , pid ( ) , state ) (C_P,\operatorname{pid}(),\operatorname{state}) ( C P , pid ( ) , state ) are pairwise disjoint.
We can now compute what call returns. Let p p p be a server of type server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) and c c c a request of type c c c . The application call ( p , c ) \operatorname{call}(p,c) call ( p , c ) can be given the type r r r if and only if server_of ( m ) ≤ server ( c , r ) \operatorname{server\_of}(m) \le\operatorname{server}(c,r) server_of ( m ) ≤ server ( c , r ) , that is, by Claim 1 applied to the regions, if and only if c ≤ ⋁ i c i c \le\bigvee_i c_i c ≤ ⋁ i c i and R P ≤ r R_P \le r R P ≤ r for every P P P such that c ∧ C P ≠ 0 c \land C_P \ne0 c ∧ C P = 0 . Therefore, on a request of type c ≤ ⋁ i c i c \le\bigvee_i c_i c ≤ ⋁ i c i , call returns the least such r r r ,
⋁ P : c ∧ C P ≠ 0 R P \bigvee_{P:c\land C_P\ne0} R_P P : c ∧ C P = 0 ⋁ R P
and on a request outside the domain of handle_call it is rejected. This is exactly the result of applying the function ⋀ P ( C P → R P ) \bigwedge_P(C_P \to R_P) ⋀ P ( C P → R P ) to c c c : when the domains are pairwise disjoint, the type of an application is the union of the codomains of the arrows whose domain meets the argument (a special case of the type of applications in semantic subtyping: cf. (Castagna, 2020, §4.4.3)).
The second property of server_of is optimality.
Claim 2. Let m m m be a module whose handle_call has the type (5), so that its function from requests to replies has type ⋀ i ∈ I ( c i → r i ) \bigwedge_{i\in I}(c_i \to r_i) ⋀ i ∈ I ( c i → r i ) . If ⋀ j ∈ J ( d j → s j ) \bigwedge_{j\in J}(d_j \to s_j) ⋀ j ∈ J ( d j → s j ) is equivalent to ⋀ i ∈ I ( c i → r i ) \bigwedge_{i\in I}(c_i \to r_i) ⋀ i ∈ I ( c i → r i ) , then server_of ( m ) ≤ MT ( ⋀ j ∈ J ( d j → s j ) ) \operatorname{server\_of}(m) \le\operatorname{MT}\left(\bigwedge_{j\in J}(d_j \to s_j)\right) server_of ( m ) ≤ MT ( ⋀ j ∈ J ( d j → s j ) ) .
In other terms, Claim 2 says that server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) is the best type that MT can give to the server from an intersection of arrows equivalent to the type of handle_call, and Claim 1 says that on this type MT is faithful with respect to server types, which are all that call and start_link compare.
Overlapping domains. Without the regions, exactness fails. Take the callback h h h of (4) (§ 6 ), of type ( : a ∨ : b → i n t ∨ n i l ) ∧ ( : b ∨ : c → i n t ∨ : o k ) (:a \mathbin{\lor} :b \mathbin{\to} \mathrm{int} \mathbin{\lor} \mathrm{nil}) \mathbin{\land} (:b \mathbin{\lor} :c \mathbin{\to} \mathrm{int} \mathbin{\lor} :ok) ( : a ∨ : b → int ∨ nil ) ∧ ( : b ∨ : c → int ∨ : o k ) : applied to : b :b : b it returns an integer, by ( → ∧ ) (\mathbin{\to} \mathbin{\land}) ( → ∧ ) . With the plain translation server(:a ∨ :b, int ∨ nil) ∧ server(:b ∨ :c, int ∨ :ok), by the union law call on : b :b : b has two incomparable minimal solutions for r r r , int ∨ nil and int ∨ :ok, while server_of(m) contains the region server(:b, int), and call returns int (§ 7 ). The loss is one of precision only, and it occurs only on such regions.
Claim 3. Let T m = ⋀ i ∈ I server ( c i , r i ) T_m = \bigwedge_{i \in I} \operatorname{server}(c_i,r_i) T m = ⋀ i ∈ I server ( c i , r i ) . Then server_of ( m ) ≤ T m \operatorname{server\_of}(m) \leq T_m server_of ( m ) ≤ T m ; for every nonempty region C P C_P C P , T m ≤ server ( C P , R P ) T_m \leq\operatorname{server}(C_P,R_P) T m ≤ server ( C P , R P ) if and only if r i = R P r_i = R_P r i = R P for some i ∈ P i \in P i ∈ P ; hence server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) and T m T_m T m are equivalent if and only if every nonempty region has such an i i i .
Typing the server with the plain translation is thus sound, and so is every solution for r r r that it gives to call. Since R P ≤ r i R_P \leq r_i R P ≤ r i for every i ∈ P i \in P i ∈ P , it is coarser than server_of(m) exactly on the nonempty regions C P C_P C P such that R P < r i R_P < r_i R P < r i for every i ∈ P i \in P i ∈ P , where the arrows of P P P guarantee together strictly more than each of them alone, such as the region : b :b : b of h h h . Overlapping domains are thus not enough for the two types to differ: for ( : a ∨ : b → i n t ) ∧ ( : b ∨ : c → i n t ∨ n i l ) (:a \mathbin{\lor} :b \mathbin{\to} \mathrm{int}) \mathbin{\land} (:b \mathbin{\lor} :c \mathbin{\to} \mathrm{int} \mathbin{\lor} \mathrm{nil}) ( : a ∨ : b → int ) ∧ ( : b ∨ : c → int ∨ nil ) the region : b :b : b has R P = i n t = r 1 R_P = \mathrm{int} = r_1 R P = int = r 1 , and the two types coincide. With pairwise disjoint domains every nonempty region is some C { i } = c i C_{\{i\}} = c_i C { i } = c i , with R { i } = r i R_{\{i\}} = r_i R { i } = r i , and the two types coincide.
server_of from polymorphism, and why start_link still needs it
Making server_of less ad hoc. As defined in Appendix A.2, server_of is a primitive operator that reads the type of handle_call: it occurs in the type server of the API (Appendix A.1) and in the signature of start_link. So it seems tied to GenServer: another behaviour (e.g., gen_statem, a user-defined server) would need a new operator, hence a change of the checker. The aim of this section is to eliminate this operator, in two steps. First, I consider the function serve of § 8 , which starts a server from the callback handle_call instead of a module: it needs no operator, since its polymorphic type, instantiated at the regions, gives the type server_of(m). Then I discuss how to do the same for start_link, whose problem is that it receives a module instead of the callback, and that the behaviour, as the type of this module, exposes only its parameters, which are invariant. For the moment this second step fails, so start_link keeps server_of, and the remedies that I propose are only sketches.
A function that takes the callback. § 8 obtains server_of(m) by polymorphism, from the function that starts a server from the callback itself and from the initial state:
def serve(h, s), do: spawn(fn -> loop(h, s) end)
where loop is the loop of § 5 . Let me recall the argument. When from is typed pid(),
serve : ∀ c , r , s . ( ( c , pid ( ) , s ) → { : reply , r , s } , s ) → server ( c , r ) \operatorname{serve} : \forall c,r,s.\; ((c,\operatorname{pid}(),s) \to\{:\operatorname{reply},r,s\},s) \to\operatorname{server}(c,r) serve : ∀ c , r , s . (( c , pid ( ) , s ) → { : reply , r , s } , s ) → server ( c , r )
and the application rule of Castagna et al. [18 ] can instantiate it with the set of substitutions [ c : = C P , r : = R P , s : = state ] [c := C_P,\ r := R_P,\ s := \operatorname{state}] [ c := C P , r := R P , s := state ] , one for each nonempty region, which gives serve the intersection of the instances:
serve : ⋀ P ( ( ( C P , pid ( ) , state ) → { : reply , R P , state } , state ) → server ( C P , R P ) ) \operatorname{serve} : \bigwedge_P (((C_P,\operatorname{pid}(),\operatorname{state}) \to\{:\operatorname{reply},R_P,\operatorname{state}\},\operatorname{state}) \to\operatorname{server}(C_P,R_P)) serve : P ⋀ ((( C P , pid ( ) , state ) → { : reply , R P , state } , state ) → server ( C P , R P ))
By (7), the type of handle_call is below the first component of the domain of every instance, so, for an initial state s s s of type state \operatorname{state} state , serve(handle_call, s) has type ⋀ P server ( C P , R P ) = server_of ( m ) \bigwedge_P \operatorname{server}(C_P,R_P) = \operatorname{server\_of}(m) ⋀ P server ( C P , R P ) = server_of ( m ) . This computes the type, but does not prove it sound: with processes, instantiating a function with a set of substitutions is unsound in general, since the instances describe different processes while the application spawns only one, whose mailbox receives the messages of all of them.14 For serve the type is sound, as Theorem 2 shows by typing the loop directly. Moreover, no other set of substitutions does better: every set whose instances all accept handle_call and the initial state gives a supertype of server_of(m) (Theorem 6 (c)).
The two parts of server_of. The polymorphic reading splits server_of in two parts, only one of which is specific to a library (§ 8 ). Let me give the details for serve; start_link comes in the next paragraph.
The protocol is specific: the shape server(c, r) (the tag, the return address, the reference) and the relation between a callback type and a server type. The author of the library states it once, with a parametric $type and the signatures of serve and call, in the form of the model (I omit the bodies):
$type server(c, r) = pid({c, pid(r)})
$ ((c, pid(), s) -> {:reply, r, s}, s) -> server(c, r)
when c: term(), r: term(), s: term()
def serve(h, s) do: ...
$ (server(c, r), c) -> r when c: term(), r: term()
def call(p, c) do: ...
In a signature, when c: term(), r: term() quantifies the type variables c c c and r r r over all types, so that $ t when c: term(), r: term() is the type ∀ c , r . t \forall c,r.\,t ∀ c , r . t , written as in Castagna et al. [22 ] . Appendix § 12 .§ 7 gives the OTP form of server(c, r). The checker cannot verify these signatures, since OTP is untyped: they are trusted, like those of a foreign function. No operator appears in them: the checker needs only parametric types and the application rule with sets of substitutions. A new behaviour started from its callback is then a new signature, together with a proof that its instantiation at the regions is sound, which does not follow from the signature (for serve, it is Theorem 2).
The regions are not specific: they depend only on the arrows of the callback. For any protocol constructor F ( c , r ) F(c,r) F ( c , r ) (here server), the type of the server started from the callback is ⋁ P F ( C P , R P ) \bigvee_P F(C_P,R_P) ⋁ P F ( C P , R P ) , and P ↦ ( C P , R P ) P \mapsto(C_P,R_P) P ↦ ( C P , R P ) is the normalization of an overloaded arrow into disjoint domains, a property of set-theoretic types alone. So the checker would offer this normalization once (or the inference of the set of substitutions would find it: here we only exhibit it), and server_of is the instance of a generic construction at F = s e r v e r F = server F = ser v er .
Through start_link it fails. start_link does not receive handle_call but a module. Typed like serve, it would be
start_link : ∀ a , c , r . ( GenServer [ init_arg : a , call_msg : c , reply : r ] , a ) → { : ok , server ( c , r ) } \operatorname{start\_link} : \forall a,c,r.\;(\operatorname{GenServer}[\operatorname{init\_arg}:a,\operatorname{call\_msg}:c,\operatorname{reply}:r],a)\to\{\colon\operatorname{ok},\operatorname{server}(c,r)\} start_link : ∀ a , c , r . ( GenServer [ init_arg : a , call_msg : c , reply : r ] , a ) → { : ok , server ( c , r )}
In the module types of Bretagne [6 ] and Boussaa et al. [5 ] , parameters are, for the moment, invariant: a module m m m has the type GenServer[..., call_msg: c, reply: r] only when c c c and r r r are equivalent to its declared parameters, that is, to ⋁ i c i \bigvee_i c_i ⋁ i c i and ⋁ i r i \bigvee_i r_i ⋁ i r i when the declaration agrees with the arrows of handle_call; for the first version of MyServer, get_int or {set_int, integer()} and integer() or ok. The instance at a region would require the parameters C P C_P C P and R P R_P R P , which the module does not have unless they are equivalent to ⋁ i c i \bigvee_i c_i ⋁ i c i and ⋁ i r i \bigvee_i r_i ⋁ i r i . The only valid set of substitutions is then the singleton, and the result is server(∨ᵢ cᵢ, ∨ᵢ rᵢ) (Proposition 7 ): sound, but it loses the correspondence between requests and replies (Appendix § 12 .§ 1 ). This is why the signature of start_link in Appendix § 12 .§ 2 uses server_of(m), a type that depends on the module argument m m m :
$ (m :: GenServer[init_arg: a], a) -> {:ok, server_of(m)} when a: term()
def start_link(m, v) do: ...
This failure concerns the derivation of server_of($m$) from the parameters, not server_of($m$) itself: with this signature, a start_link that receives __MODULE__ or the name of the module gets the regions, since the type of the module shows the intersection type of handle_call. Only a function that receives a module typed by the behaviour loses them (Appendix § 12 .§ 5 ).
So, for start_link, polymorphism explains server_of but does not yet replace it, and a new behaviour started from a module still needs an operator like server_of in its signature. Quantifying over the types of the callbacks of the module, rather than over the parameters of the behaviour, or changing the typing of applications, so that a module is accepted at every instance of the behaviour that its declarations satisfy, would restore the instantiation at the regions and remove server_of from the signature. I outline these two remedies in the paragraph “A start_link without server_of” of Appendix § 12 .§ 8 , though at this stage they are just working hypotheses, since they require further investigation in the module calculus.
Deferred replies
So far, the clauses of handle_call reply at once, by returning {:reply, r, s}. § 7 explains why a clause may instead return {:noreply, s}, keep the return address from, and let some process reply later through GenServer.reply(from, v), and why the type of from must then carry the type of the reply, with a contravariant index. Here I give the details.
The type of GenServer.reply. In the model of § 5 , the return address is a pid and GenServer.reply(w, v) is just send(w, v) (in OTP the reply also carries a tag: Appendix § 12 .§ 7 ). So we give GenServer.reply the input type of a send:
GenServer.reply : ∀ r . ( pid ( r ) , r ) → : ok \operatorname{GenServer.reply} : \forall r.\,(\operatorname{pid}(r), r) \to:\operatorname{ok} GenServer.reply : ∀ r . ( pid ( r ) , r ) →: ok
Let us see what this type allows. If w has type pid(t), the instance at r r r applies if and only if pid(t) \le pid(r), that is, by (1), contravariance, r ≤ t r \le t r ≤ t , and then v must have type r r r : so the call type-checks exactly when v has type t t t (take r = t r=t r = t ). With pid() = pid(0) the only instances are at r = 0 r=0 r = 0 , and no value has type 0: a body that calls GenServer.reply on a from of type pid() is rejected. A clause that uses from therefore declares pid(r_i) for it, and handle_call has type
⋀ i ∈ I ( ( c i , pid ( r i ) , s t a t e ) → { : reply , r i , s t a t e } ∨ { : noreply , s t a t e } ) \bigwedge_{i\in I}\bigl((c_i,\operatorname{pid}(r_i),state)\to\{:\operatorname{reply},r_i,state\}\lor\{:\operatorname{noreply},state\}\bigr) i ∈ I ⋀ ( ( c i , pid ( r i ) , s t a t e ) → { : reply , r i , s t a t e } ∨ { : noreply , s t a t e } )
so that GenServer.reply(from, v) type-checks only if v has type r i r_i r i , wherever from has been stored or sent. I call this type the pid(r_i) form, and the type of Appendix § 12 .§ 1 the pid() form. The programmer may mix the two, one arrow per kind of request, as in the example below.
The third version of the example. This gives the second fix of the second version of MyServer (Appendix § 12 .§ 1 ), the one that keeps the API: get_int waits while the stored value is nil, instead of replying nil. The server keeps the return addresses of the waiting clients in its state, and set_int wakes them when it receives an integer. Here are the parts that change (the $behaviour line and the API are those of the second version):
$opaque state = %{current: integer() or nil, waiting: [pid(integer())]}
def init(v), do: {:ok, %{current: v, waiting: []}}
$ ((:get_int, pid(integer()), state)
-> {:reply, integer(), state} or {:noreply, state}) and
(({:set_int, integer()} or nil, pid(), state)
-> {:reply, :ok, state})
def handle_call(:get_int, from, %{current: nil} = s),
do: {:noreply, %{s | waiting: [from | s.waiting]}} # no value yet: keep "from"
def handle_call(:get_int, _from, %{current: v} = s) when is_integer(v),
do: {:reply, v, s}
def handle_call({:set_int, v}, _from, s) do
for w <- s.waiting, do: GenServer.reply(w, v) # rejected
{:reply, :ok, %{s | current: v, waiting: []}}
end
The state now has a second field, waiting, the list of the return addresses of the clients that wait for an integer, which has type [pid(integer())]. The first arrow is in the pid(r_i) form, since the first clause stores from to reply later, and its result is the union of an immediate and a deferred reply; the second arrow is in the pid() form, since the clauses for set_int do not use from.
The last clause handles the requests of the second arrow, so in its body v has type integer() or nil and s has type state. Then s.waiting has type [pid(integer())], and in the comprehension w <- s.waiting the variable w has type pid(integer()). By the type of GenServer.reply, the call GenServer.reply(w, v) type-checks only if v has type integer(); since integer() or nil is not a subtype of integer(), the clause is rejected. It must be: with today’s spec of GenServer.reply, which accepts any reply, it would be accepted, and a request {:set_int, nil}, which the server accepts, would wake the clients waiting in get_int with nil. The fix is a clause for {:set_int, nil} that leaves them waiting, before the last clause, which is then guarded by is_integer(v), so that in its body v has type integer() and the call type-checks:
def handle_call({:set_int, nil}, _from, s),
do: {:reply, :ok, %{s | current: nil}} # clients keep waiting
def handle_call({:set_int, v}, _from, s) when is_integer(v) do
for w <- s.waiting, do: GenServer.reply(w, v) # accepted
{:reply, :ok, %{s | current: v, waiting: []}}
end
The two requests are disjoint, so there is one region per arrow, and the server has the type
server_of ( M y S e r v e r ) = server ( : g e t _ i n t , i n t ) ∧ server ( { : s e t _ i n t , i n t ∨ n i l } , : o k ) \operatorname{server\_of}(\mathit{MyServer}) = \operatorname{server}(:\mathit{get\_int},\mathit{int}) \mathbin{\wedge} \operatorname{server}(\{:\mathit{set\_int},\mathit{int}\mathbin{\vee}\mathit{nil}\},:\mathit{ok}) server_of ( MyServer ) = server ( : get_int , int ) ∧ server ({ : set_int , int ∨ nil } , : ok )
The API of the second version, with $ ( s e r v e r ) → integer ( ) \$(\mathit{server}) \mathbin{\to} \operatorname{integer}() $ ( server ) → integer ( ) for get_int (here server is the type defined in the API of Appendix A.1, not to be confused with the parameterized type server(c, r)), is thus accepted: deferring the reply lets the stored value be nil without changing the API, and the checker verifies that no nil reaches a client of get_int, neither through the reply of the loop (the second clause replies v only when it is an integer) nor through GenServer.reply.
The type of the server in the pid(r_i) form. The pid() form is the more precise one for server_of (Appendix A.2), the pid(r_i) form is the one that lets the body use from. Let us see what the second one costs. Write H m r H_m^r H m r for the type of handle_call in the pid(r_i) form, and K r K_r K r for \{:reply,r,state\} \mathbin{\vee} \{:noreply,state\}. Typed like handle_call,
serve : ∀ c , r , s . ( ( c , pid ( r ) , s ) → { :reply , r , s } ∨ { :noreply , s } , s ) → server ( c , r ) \operatorname{serve} : \forall c,r,s.\; ((c,\operatorname{pid}(r),s) \mathbin{\to} \{\operatorname{:reply},r,s\} \mathbin{\vee} \{\operatorname{:noreply},s\},s) \mathbin{\to} \operatorname{server}(c,r) serve : ∀ c , r , s . (( c , pid ( r ) , s ) → { :reply , r , s } ∨ { :noreply , s } , s ) → server ( c , r )
and a substitution [ c : = c ′ , r : = r ′ , s : = s t a t e ] [c := c',\ r := r',\ s := state] [ c := c ′ , r := r ′ , s := s t a t e ] is valid for the callback handle_call if H m r ≤ ( c ′ , pid ( r ′ ) , s t a t e ) → K r ′ H_m^r \leq(c',\operatorname{pid}(r'),state) \mathbin{\to} K_{r'} H m r ≤ ( c ′ , pid ( r ′ ) , s t a t e ) → K r ′ . The substitutions at the arrows, [ c : = c i , r : = r i , s : = s t a t e ] [c := c_i,\ r := r_i,\ s := state] [ c := c i , r := r i , s := s t a t e ] , are valid whatever the domains, since each of these arrows is a component of H m r H_m^r H m r ; so serve ( h a n d l e _ c a l l , s ) : ⋀ i server ( c i , r i ) \operatorname{serve}(\mathit{handle\_call},s) : \bigwedge_i \operatorname{server}(c_i,r_i) serve ( handle_call , s ) : ⋀ i server ( c i , r i ) . The substitutions at the regions are another matter.
Claim 4. Let C P ≠ 0 C_P \ne0 C P = 0 and s t a t e ≠ 0 state \ne0 s t a t e = 0 . Then H m r ≤ ( C P , pid ( R P ) , s t a t e ) → K R P H_m^r \leq(C_P,\operatorname{pid}(R_P),state) \mathbin{\to} K_{R_P} H m r ≤ ( C P , pid ( R P ) , s t a t e ) → K R P if and only if r i = R P r_i = R_P r i = R P for some i ∈ P i \in P i ∈ P .
The client of a request in C P C_P C P sends an address of type pid(R_P), and only an arrow of P P P whose address type is pid(R_P) itself can accept it. So the substitution at a region is valid exactly when one of its arrows already has the reply of the region, and then it adds nothing, since server(c_i,r_i) \le server(C_P,R_P) when C P ≤ c i C_P \le c_i C P ≤ c i and r i = R P r_i = R_P r i = R P . In the pid(r_i) form, the substitutions at the arrows and at the regions thus give only the plain translation T m = ⋀ i server ( c i , r i ) T_m = \bigwedge_i \operatorname{server}(c_i,r_i) T m = ⋀ i server ( c i , r i ) , which, by Claim 3, loses the nonempty regions C P C_P C P such that R P < r i R_P < r_i R P < r i for every i ∈ P i \in P i ∈ P . The reason is that the arguments of the arrows are independent: their intersection cannot say that on a request in C P C_P C P only values of type R P R_P R P are sent to from. Take, for instance, the callback h h h of (5) in the pid(r_i) form: on :b, the address of the client has type pid(int), while the first arrow asks for pid(int ∨ nil) and the second one for pid(int ∨ :ok). With pairwise disjoint domains nothing is lost: this is the case of MyServer, and in general of one arrow per clause with pairwise disjoint request patterns.
So, on a module whose handle_call is in the pid(r_i) form, the operator server_of of the signature of start_link computes T m T_m T m , and not the server_of(m) of Appendix A.2, which nothing justifies there; T m T_m T m is sound (the paragraph “The form H m r H^r_m H m r ” of Appendix A.9.5). For such a module to implement the behaviour GenServer, the callback that the behaviour declares for handle_call must type the return address as pid(reply), where r e p l y reply r e pl y is the parameter of the replies, and not as pid() (the paragraph “Conformance to the behaviour” of Appendix A.9.3).
Recovering a lost region. In the pid() form the programmer never writes the regions. In the pid(r_i) form a lost region C P C_P C P is recovered by declaring its arrow: adding to the type of handle_call the arrow ( C P , pid ( R P ) , s t a t e ) → K R P (C_P,\operatorname{pid}(R_P),\mathit{state}) \to K_{R_P} ( C P , pid ( R P ) , state ) → K R P , which the checker verifies against the body like the others. This changes neither the regions nor their replies (the paragraph “Recovering a lost region” of Appendix A.9.3), and the substitution at the region becomes valid by Claim 4, since the new arrow has the reply R P R_P R P . For h h h , the arrow ( : b , pid ( int ) , s t a t e ) → K int (:b,\operatorname{pid}(\operatorname{int}),\mathit{state}) \to K_{\operatorname{int}} ( : b , pid ( int ) , state ) → K int is accepted if the body type-checks on :b with from of type pid(int), and it restores server(:b,int). Since deferred replies are common, this is the price of precision when domains overlap.
Conditions
Let me gather the conditions under which the API of a server is checked against its implementation.
handle_call must be given an intersection type, whose arrows type from as pid() or as pid(r_i) (Appendix A.4). The checker verifies this signature against the clauses, taking into account that a request is handled by the first clause that matches it ((Castagna and Duboc, 2026)), so server_of always receives a valid type of handle_call. The type of the module passed to start_link must show this intersection, not only the callback type declared by $\\$behaviour. The usual pattern satisfies this condition: start_link is defined in the module itself and called on __MODULE__, as in def start_link(arg), do: GenServer.start_link(__MODULE__, arg). Otherwise, as in generic code that receives a module typed by the behaviour, server_of(m) = server(call_msg, reply), which is sound but coarse (Appendix A.8 sketches two remedies).
The clients must call the server through the pid that start_link returns. In practice this is the main limitation: a server is commonly registered under a name (name: __MODULE__) and its client API calls GenServer.call(__MODULE__, ...), so that the pid of type server_of(m) returned by start_link never reaches the client functions. Such calls, and the calls on a pid obtained from whereis, are untyped; typing them requires giving
the registered name the type server_of(m), for instance by a typed name: option or by a module attribute that declares the type of the server.
A hot code upgrade must preserve the type of the server: the server type of the new module must be below that of the old one, and code_change must map the old state into the new state type. (Asking that the new handle_call have a subtype of the type of the old one is too strong, since the two state types may differ.)
A minimal gen_server model and the statements it satisfies
This section fixes a minimal model of the gen_server loop, of start_link and of call, on which the claims of the previous sections become theorems.
The calculus
A direct-style local π \pi π -calculus in the style of Castagna et al. [24 ] : functional expressions (higher-order, since the loop receives the callback), pairs and tagged tuples, and the primitives spawn, send, receive (on the mailbox of the running process) and alias. A mailbox is a multi-set of values (the order of messages plays no role below). The expression alias() returns a fresh name w w w owned by the caller: a message sent to w w w is received by the caller with receive_on(w), never by a receive, and nobody else can receive on w w w . This is the locality of the BEAM. As in Appendix A.1, the tag :"$gen_call" and the references are omitted, and so are the process links. Types are those of this appendix. We assume:
(A1) The base system is sound: types are preserved by reduction, and no process is stuck on a receive or a match that its type excludes. This is an assumption, not a result of Castagna et al. [24 ] , whose system is monomorphic and has no aliases: the base system extends it with polymorphic functions, aliases and the rule (receive) of Appendix A.9.4.
(A2) The laws (1)–(3) of pid, recalled in Appendix A.1, union law included, and the decompositions of arrows and of products of Frisch et al. [39 ] , recalled in Appendix A.9.1.
(A3) m m m is a module with state type s t a t e ≠ 0 state \ne0 s t a t e = 0 , init : (a) → {:ok, state} (so a a a is the argument type of init, the instance of the parameter init_arg in m m m ), and handle_call typed in one of the two forms of Appendix A.4, with ⋁ i ∈ I C i ≠ 0 \bigvee_{i\in I} C_i \ne0 ⋁ i ∈ I C i = 0 :
H m p i d ( ) = ⋀ i ∈ I ( ( c i , pid ( ) , s t a t e ) → { : reply , r i , s t a t e } ) H_m^{\mathrm{pid}()} = \bigwedge_{i\in I} ((c_i,\operatorname{pid}(),state) \to\{:\operatorname{reply},r_i,state\}) H m pid ( ) = i ∈ I ⋀ (( c i , pid ( ) , s t a t e ) → { : reply , r i , s t a t e })
H m r = ⋀ i ∈ I ( ( c i , pid ( r i ) , s t a t e ) → { : reply , r i , s t a t e } ∨ { : noreply , s t a t e } ) H_m^r = \bigwedge_{i\in I} ((c_i,\operatorname{pid}(r_i),state) \to\{:\operatorname{reply},r_i,state\} \lor\{:\operatorname{noreply},state\}) H m r = i ∈ I ⋀ (( c i , pid ( r i ) , s t a t e ) → { : reply , r i , s t a t e } ∨ { : noreply , s t a t e })
An intersection that mixes the two forms is below H m r H_m^r H m r (the paragraph “Mixed forms” of Appendix A.9.3), and is treated as H m r H_m^r H m r . Moreover, the body of handle_call performs no receive and does not use self(): the only receive on the mailbox of the server is the one of the loop. (The body may call other servers, since call reads only its own alias.)
The encoding
def loop(h, s) do
receive do
{c, w} ->
case h.(c, w, s) do
{:reply, r, s2} -> send(w, r); loop(h, s2)
{:noreply, s2} -> loop(h, s2)
end
end
end
def start_link(m, v) do # GenServer.start_link
{:ok, s} = m.init(v)
{:ok, spawn(fn -> loop(&m.handle_call/3, s) end)}
end
def call(p, c) do # GenServer.call
w = alias() # fresh, owned by the caller
send(p, {c, w})
receive_on(w) # the reply, whatever process sends it
end
def reply(w, r), do: (send(w, r); :ok) # GenServer.reply
The loop is that of Section 5, extended with the clauses that do not reply: Milner’s encoding of a function, with the replicated input replaced by a recursive one that takes one request at a time and threads the state through. In the form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) the callback types from as pid(), on which nothing can be sent, and always returns {:reply, y, s}, so that the loop sends the reply itself; the :noreply branch and reply are used only in the form H m r H_m^r H m r , where the callback may call reply on from, or hand it to another process, and return {:noreply, s}.
Results
On this model the claims of the previous sections become theorems, which Appendix A.9.5 states and proves. The function call has the polymorphic type of Appendix A.1, and a call typed with the reply type r r r receives only values of type r r r (Theorem 1). In the form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) , start_link returns a pid of type server_of(m) (Theorem 2); in the form H m r H_m^r H m r , a pid of type T m T_m T m (the paragraph “The form H m r H_m^r H m r ” of Appendix A.9.5). In a program that uses the pids at these types, handle_call is never applied outside its domain (Corollary 3), and, in the form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) , a call returns the reply that handle_call computes for its request, of the type computed in Appendix A.2 (Theorem 4). Theorems 5 and 6 restate on the model Claims 1 and 2 and the computation of Appendix A.3, and Proposition 7 the failure of the instantiation through start_link.
What the model leaves out
handle_cast and handle_info; receives and self() in the body of handle_call, which (A3) excludes; the other results of handle_call ({:stop, ...}, and replies with a timeout, :hibernate or {:continue, ...}) and of init ({:stop, ...}, :ignore); the process in which init runs (the caller here, the server in OTP); the monitor that GenServer.call sets on the server; timeouts, crashes and links (so no statement on liveness: Theorem 4 is about replies that are sent, not about replies that must be sent); message order; registered names and whereis; hot code upgrade; gen_statem.
From the model to OTP: what changes in GenServer
Let me stress that nothing in this appendix requires a change in the current code of GenServer. What changes are the signatures of start_link, call and reply, which the checker trusts since the library is untyped Erlang (Elixir’s GenServer delegates to the Erlang module gen_server), and the checker, which computes server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) (Appendix § 12 .§ 2 ) or instantiates with sets of substitutions (Appendix § 12 .§ 3 ). Let us compare the model of Appendix § 12 .§ 6 with the code of OTP 29.1.1 and Elixir 1.20.4.
The loop. When a server starts, gen_server extracts the function handle_call from the module, written &m.handle_call/3 in Elixir, and its loop applies this function to each request (functions server_data/4 and try_handle_call/4 of gen_server.erl). The loop of OTP thus has the structure of the loop(h, s) of Sections 5 and A.6: the function loop/4 of gen_server.erl has among its arguments h, which is a function and not a module, and the state s of the server, which it replaces with the new state after each request. The function serve of Appendix § 12 .§ 3 starts this loop from a given h and a given initial state s. The API of gen_server has no such function, since all its functions that start a server take a module, but gen_server performs this step internally, once it has extracted handle_call and computed the initial state with init.
The return address. In the call function of the model the return address is a fresh name w : pid ( r ) w : \operatorname{pid}(r) w : pid ( r ) , on which the client waits with receive_on(w). In OTP it is a pair { pid , tag } \{\text{pid},\text{tag}\} { pid , tag } formed by the pid of the client and a fresh tag (built on a reference, a value that is unique in the running system): the request is the message {: "$gen_call", {pid, tag}, c}, the server sends the reply v to the client as the message {tag, v}, and the client waits for a message that carries tag. Since the tag is fresh, no other message can be taken for the reply: this is the guarantee that the model gives with a fresh name, and that the checker trusts. The new signatures therefore index the tag by the type of the reply:
from ( r ) = { pid ( ) , reply_tag ( r ) } server ( c , r ) = pid ( { : " $ g e n _ c a l l " , from ( r ) , c } ) \operatorname{from}(r) = \{\operatorname{pid}(),\ \operatorname{reply\_tag}(r)\}
\qquad
\operatorname{server}(c,r) = \operatorname{pid}(\{:"\$gen\_call",\operatorname{from}(r),c\}) from ( r ) = { pid ( ) , reply_tag ( r )} server ( c , r ) = pid ({ : "$ g e n _ c a l l " , from ( r ) , c })
(written from(r) and server(c, r) in Table 2 ), where reply_tag(r) is an abstract type with the three laws of pid ( r ) \operatorname{pid}(r) pid ( r ) (Appendix § 12 .§ 1 ): together with the pid, the tag is an address for the replies of type r. Since products distribute over intersections and unions, from ( r ) \operatorname{from}(r) from ( r ) has the same laws, and the claims of Appendices A.2–A.4 (with MT ( c → r ) = server ( c , r ) \operatorname{MT}(c \to r) = \operatorname{server}(c,r) MT ( c → r ) = server ( c , r ) ), which use only these laws and the decompositions of products and arrows, carry over to this definition of server ( c , r ) \operatorname{server}(c,r) server ( c , r ) . The arrows of handle_call type from as from ( ) = from ( ∅ ) \operatorname{from}() = \operatorname{from}(\varnothing) from ( ) = from ( ∅ ) , the largest type of return addresses, or as from ( r i ) \operatorname{from}(r_i) from ( r i ) ; the examples of this appendix write pid ( ) \operatorname{pid}() pid ( ) and pid ( r i ) \operatorname{pid}(r_i) pid ( r i ) , as in the model.
Table 2. The types of GenServer in Elixir 1.20.4 and the new signatures.
Today’s specs and the new signatures. Table 2 compares the specs of GenServer in Elixir 1.20.4 with the new signatures of the module GenServer, written with Elixir types. Only the types change: the functions are those of today. The type variables are quantified with when as in Appendix § 12 .§ 3 (t t t when a: term() is the type ∀ t . t \forall t.t ∀ t . t ), and m : : T m :: T m :: T is the binder of Appendix § 12 .§ 2 .
Let us see how these signatures fit together. The functions of OTP are long (monitors, timeouts, registered names, the other callbacks), so Figure 1 gives the code of the model of Appendix § 12 .§ 6 , rewritten with the messages of OTP and the results of init, and typed with the signatures of Table 2 (without the arguments options() and timeout(), since the model has neither).
The first three declarations of the figure are the types of the table. Today’s server becomes the parametric server(c, r), written GenServer.server(c, r) outside the module (Appendix § 12 .§ 1 ). The pair from(r) is the one that gen_server.erl declares, a pid and an opaque tag, with the index r added. As for the $opaque of Appendix § 12 .§ 1 , inside GenServer the type reply_tag(r) denotes its definition, an alias that accepts the pairs of a tag, of type term() since nobody inspects it, and a reply of type r r r , while outside it is abstract. This declaration goes beyond that of Appendix § 12 .§ 1 in two ways: it has a parameter, and the abstract type keeps the three laws of pid(r), which this definition satisfies (the paragraph “The model with the messages of OTP” of Appendix § 12 .9.5). The alias is what OTP uses on its main path, where the tag contains an alias and the reply is sent to this alias (functions do_call and reply of gen.erl). On the other path, a local call without timeout, the tag is a plain reference and the reply is sent to the pid of the pair: this is why the table does not give the definition, and for OTP the checker just trusts the signatures.
As in today’s Elixir, a single defmodule defines both a behaviour and the functions of the library. The behaviour is the part that each module instantiates, with three declarations that I have not explained yet: $param p declares a parameter, which a module fixes in its line $behaviour (e.g. the first three lines of the body of MyServer in Appendix § 12 .§ 1 ); $opaque state, without a definition, declares a type that each module defines, as MyServer does right after its behaviour declaration; and $callback f(t_1, \ldots, t_n) = t requires the function f f f of each module to have a type below ( t 1 , … , t n ) → t (t_1,\ldots,t_n) \to t ( t 1 , … , t n ) → t . (The dots of the table stand for the other results of OTP, which the model leaves out.) So each module gives handle_call its own intersection, ( ( c , from ( ) , state ) → { : reply , r , state } ) ((c, \text{from}(), \text{state}) \to\{:\text{reply}, r, \text{state}\}) (( c , from ( ) , state ) → { : reply , r , state }) and ..., with from(r) in the arrows of the clauses that use from (Appendix § 12 .§ 4 ), and this intersection, not the type of the callback, is what server_of takes.
The signature of start_link mentions server_of(m), which the checker computes for each module, so the body cannot be checked against it once and for all: Theorem 2 types it for each m m m (the paragraph “The model with the messages of OTP” of Appendix § 12 .9.5). The spawn declares the interface of the new process, with the syntax of Castagna et al. [24 ] : $interface t, before a spawn, says that the process accepts the messages of type t t t , and the spawn returns a pid of type pid(t). Here t t t is messages_of(m), which the checker computes together with server_of(m): it is the union of the messages { : " $ g e n c a l l " , from ( R P ) , C P } \{:"\$gen_call", \text{from}(R_P), C_P\} { : "$ g e n c a l l " , from ( R P ) , C P } of the regions, so that server_of(m) is pid(messages_of(m)) by the second law of pid. In the result of start_link only the :ok case changes. In the code the other two come from init; in OTP the errors also include a name already taken, for which start_link returns {:error, {:already_started, pid}}, where pid is the process registered under that name, whose type is not known. The function start_link
defmodule GenServer do
$opaque reply_tag(r) = pid({term(), r})
$type from(r) = {pid(), reply_tag(r)}
$type server(c, r) = pid({:"$gen_call", from(r), c})
# computed by the checker, from the regions (C_P, R_P) of m.handle_call:
# server_of(m) = the intersection of the server(C_P, R_P)
# messages_of(m) = the type t such that server_of(m) = pid(t)
# the behaviour
$param init_arg
$param call_msg
$param reply
$opaque state
$callback init(init_arg) = {:ok, state} or :ignore or {:stop, term()}
$callback handle_call(call_msg, from(reply), state) =
{:reply, reply, state} or {:noreply, state}
# the functions
$ (m :: GenServer[init_arg: a], a) ->
{:ok, server_of(m)} or :ignore or {:error, term()} when a: term()
def start_link(m, v) do
case m.init(v) do
{:ok, s} ->
$interface messages_of(m)
{:ok, spawn(fn -> loop(m, s) end)}
:ignore -> :ignore
{:stop, reason} -> {:error, reason}
end
end
$ (m :: GenServer, m.state) -> none()
defp loop(m, s) do
receive do
{:"$gen_call", {_, tag} = from, c} ->
case m.handle_call(c, from, s) do
{:reply, v, s2} -> send(tag, {tag, v}); loop(m, s2)
{:noreply, s2} -> loop(m, s2)
end
end
end
$ (server(c, r), c) -> r when c: term(), r: term()
def call(p, c) do
tag = alias() # fresh, of type reply_tag(r)
send(p, {:"$gen_call", {self(), tag}, c})
{_, v} = receive_on(tag) # the reply, whatever process sends it
v
end
$ (from(r), r) -> :ok when r: term()
def reply({_pid, tag}, v), do: (send(tag, {tag, v}); :ok)
end
Figure 1: The module GenServer of the model, with the messages of OTP and the signatures of Table 2 .
of an API such as that of MyServer declares this union as well.
In the signature of loop, the binder m :: GenServer says that the first argument is a module that implements the behaviour, whatever its parameters, m.state is the type state of this module, and none() says that the function never returns. By the convention of Appendix § 12 .§ 2 , GenServer without brackets is the instance at three type variables. This tells the callers which modules loop accepts; as for start_link, the body is typed for each m, at the type of m.handle_call and not at the callback type (the paragraph “The model with the messages of OTP” of Appendix § 12 .9.5). Since start_link applies loop to its own m, this is the module of the declaration \$interface messages_of(m). This is why loop receives the module and not, as in the model, the function h: the type of h depends on the module. The difference does not matter at run time: m.handle_call(c, from, s) calls the same function as &m.handle_call/3, and OTP keeps both the module and this function in the data of its loop (record server_data of gen_server.erl). In Castagna et al. [24 ] an arrow also has decorations, which say how the function uses the mailbox of its process; I leave them out, since the mailbox that loop reads is the one that the \$interface of its spawn declares (the paragraph “The model with the messages of OTP” of Appendix § 12 .9.5). In the pattern of loop, {_, tag} = from binds from to the return address and tag to the second component of this address.
The signature of call is where server(c, r) is used, and this type is what relates call to start_link: the pid that start_link returns has the type server_of(m), an intersection of such types, and call can be applied to this pid at c and r if and only if server_of(m) is below server(c, r), the condition computed in Appendix § 12 .§ 2 . In the body of call, the alias is created at the type reply_tag(r), where r is the reply type of the instance, and the client sends it together with its own pid, self(). This pid travels at the type pid(), to which nobody can send, so the type of the mailbox of the client need not include the replies. For the same reason reply sends on the tag: with send(pid, {tag, v}) its body would be rejected. Thus the bodies of call and reply are well typed under their signatures (the paragraph “The model with the messages of OTP” of Appendix § 12 .9.5). The client discards the tag, since receive_on reads only what is sent to the alias; in OTP the reply arrives in the mailbox of the client, which selects it by the tag (this difference shows only in the programs at the end of this section).
The code leaves out casts, the requests without reply, as the model does. They are sent as {"$gen_cast", c}: the pid returned by start_link also has the type pid({"$gen_cast", k_m}), where k m k_m k m is the domain of handle_cast, and by the second law of pid the intersection of this type and server_of(m) is the type of a process that accepts both kinds of messages. With casts, then, messages_of(m) has this further summand, and server_of(m) in the code denotes this intersection, and not only the type of the regions of Appendix § 12 .§ 2 (or T m T_m T m in the pid ( r i ) \operatorname{pid}(r_i) pid ( r i ) form), since otherwise cast could not be applied to the pid (the paragraph “The model with the messages of OTP” of Appendix § 12 .9.5); it is also the type that start_link compares with a type written by hand (Appendix § 12 .§ 5 ). For a module without handle_cast, such as MyServer, k m k_m k m is 0 0 0 and the intersection is server_of(m). Since a cast has no reply, the overloading of handle_cast plays no role. The asynchronous calls of the Erlang module gen_server (send_request and receive_response), which Elixir 1.20.4 does not wrap, are typed in the same way, by indexing the request identifier by the type of the reply. A server also accepts system messages and the messages for handle_info, which server(c,r) does not list; by contravariance this is harmless, since a process that accepts more messages has a smaller pid type.
What the signatures do not type. Calls on a registered name keep today’s type (Appendix § 12 .§ 5 ). Debugging functions such as sys:replace_state, which replace the state of a running server, escape the typing, since server(c,r) does not mention the type of the state: they are sound only if the new state has the type of the old one.
Finally, on OTP two programs that the signatures accept can put a message where a type excludes it, which cannot happen in the model. A clause in the pid(r_i) form that replies through from and also returns {:reply, v, s} sends two replies: in the model the second one stays on the alias, while in OTP it remains in the mailbox of the client after the call has returned, where a later receive of the client can take it, whatever the type of this mailbox. And since from(r) is a pair, {_, tag} = from; GenServer.reply({p, tag}, v) is well typed for every pid p: on the path without alias, OTP sends the reply to p, on which the type pid() forbids sending, and not to the caller.
We are currently working on a layer of behavioral types over the interfaces of Castagna et al. [24 ] : such a system ensures that for every request there is at most one reply and that the obligation to reply cannot be discarded, which excludes the first of these programs.
Open questions
I close with the questions that this appendix leaves open.
A start_link without server_of. What blocks the generic reading of Appendix § 12 .§ 3 for start_link is not the operator but the way start_link receives the module: module parameters are invariant, and the type of the module shows only the callback type declared by the behaviour. Making the parameters variant, contravariant in call_msg and covariant in reply as for an arrow, would not suffice: the instance at a region would need V i r i ≤ R P V_i^{r_i} \le R_P V i r i ≤ R P , that is, the type of m m m would have to show the intersection type of handle_call, and not only the callback type declared by the behaviour (the second condition of Appendix § 12 .§ 5 ). A naive solution would be to expose the callbacks, that is, to quantify over their types rather than over the parameters of the behaviour. A module is then typed by a record of its exports, open since a module exports more than its callbacks, and covariant in the type of each function. The signature of start_link becomes
s t a r t _ l i n k : ∀ a , c , r , s . { i n i t : a → { : o k , s } , h a n d l e _ c a l l : ( c , p i d ( r ) , s ) → { : r e p l y , r , s } ∨ { : n o r e p l y , s } } , a → { : o k , server ( c , r ) } \begin{aligned}
\mathop{\mathtt{start\_link}} &: \forall a,c,r,s.\\
&\quad\{\mathtt{init}:a \to\{\mathtt{:ok},s\},\ \mathtt{handle\_call}:(c,\mathtt{pid}(r),s)\to\{\mathtt{:reply},r,s\}\lor\{\mathtt{:noreply},s\}\},\ a\\
&\quad\to\{\mathtt{:ok},\operatorname{server}(c,r)\}
\end{aligned} start_link : ∀ a , c , r , s . { init : a → { : ok , s } , handle_call : ( c , pid ( r ) , s ) → { : reply , r , s } ∨ { : noreply , s }} , a → { : ok , server ( c , r )}
We instantiate it as we did for serve. Let a m a_m a m be the argument type of init in m m m . In the form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) , take the set of substitutions [ a : = a m , c : = C P , r : = R P , s : = s t a t e ] P : C P ≠ 0 [a := a_m,\ c := C_P,\ r := R_P,\ s := state]_{P:C_P\ne0} [ a := a m , c := C P , r := R P , s := s t a t e ] P : C P = 0 , one for each nonempty region. The module m m m has the type of the first argument of every instance: for handle_call by (7), since pid ( R P ) ≤ pid ( ) \operatorname{pid}(R_P) \le\operatorname{pid}() pid ( R P ) ≤ pid ( ) and { : r e p l y , R P , s t a t e } \{\mathtt{:reply},R_P,state\} { : reply , R P , s t a t e } is below the codomain of the instance, and for init by condition (A3). Therefore, applied to m m m and to an argument of type a m a_m a m , start_link returns the type ⋀ P { : o k , server ( C P , R P ) } = { : o k , server_of ( m ) } \bigwedge_P\{\mathtt{:ok},\operatorname{server}(C_P,R_P)\} = \{\mathtt{:ok},\operatorname{server\_of}(m)\} ⋀ P { : ok , server ( C P , R P )} = { : ok , server_of ( m )} . In the form H m r H_m^r H m r , take the substitutions at the arrows [ a : = a m , c : = c i , r : = r i , s : = s t a t e ] [a := a_m,\ c := c_i,\ r := r_i,\ s := state] [ a := a m , c := c i , r := r i , s := s t a t e ] : every arrow of H m r H_m^r H m r is the type of the field handle_call at one of them, and the result is { : o k , T m } \{\mathtt{:ok},T_m\} { : ok , T m } , where T m = ⋀ i server ( c i , r i ) T_m = \bigwedge_i \operatorname{server}(c_i,r_i) T m = ⋀ i server ( c i , r i ) is the plain translation of Claim 3. The behaviour instantiation GenServer[init_arg: a] can be kept on top of it, to check the argument against init. Then start_link would not need server_of either. This is a sketch: I have not checked it against the module calculus, in particular the instantiation of s s s with the opaque state of m m m , and its soundness would rest, as for serve, on Theorem 2 (in the form H m r H_m^r H m r , on the paragraph “The form H m r H_m^r H m r of Appendix § 12 .9.5). The solution also has a weakness: the variable s s s allows instances that give the state different types, which is unsound (the paragraph “Sets of substitutions and spawning” of Appendix § 12 .9.5). Moreover, the models of Boussaï et al. (2026) and Bretagne [6 ] can already type a module as the open record of its exports, but do not expose these types to programmers, so this solution requires changing this design choice.
A better but more disruptive solution would be to change the typing of applications. The body of start_link uses the module only through its callbacks, whose types it takes from the declarations of the behaviour, with the parameters instantiated. This is also what the module calculus compares when a module declares a behaviour. In Bretagne [6 ] , let D X D_X D X be the declarations of a behaviour X \mathcal{X} X that has type parameters x ‾ \overline{x} x (which thus appear free in D X D_{\mathcal{X}} D X ); a module with declarations D D D that declares X \mathcal{X} X at the types t 0 ‾ \overline{t_0} t 0 has the type { D } X [ x ‾ = t 0 ‾ ] \{D\}\mathcal{X}[\overline{x}=\overline{t_0}] { D } X [ x = t 0 ] , which is well formed only if { D } ⪯ { D X } [ x ‾ : = t 0 ‾ ] \{D\} \preceq\{D_{\mathcal{X}}\}[\overline{x}:=\overline{t_0}] { D } ⪯ { D X } [ x := t 0 ] , where ⪯ \preceq ⪯ is the subtyping relation on module types. Nothing in this comparison is tied to the types t 0 ‾ \overline{t_0} t 0 . The idea, then, is to keep the signature of Appendix § 12 .§ 3 that quantifies over the parameters, that is
s t a r t _ l i n k : ∀ a , c , r . ( G e n S e r v e r [ i n i t _ a r g : a , c a l l _ m s g : c , r e p l y : r ] , a ) → { : o k , server ( c , r ) } \mathop{\mathtt{start\_link}} : \forall a,c,r.\;(\mathop{\mathtt{GenServer}}[\mathop{\mathtt{init\_arg}}:a,\mathop{\mathtt{call\_msg}}:c,\mathop{\mathtt{reply}}:r],a)\to\{\mathtt{:ok},\operatorname{server}(c,r)\} start_link : ∀ a , c , r . ( GenServer [ init_arg : a , call_msg : c , reply : r ] , a ) → { : ok , server ( c , r )}
and to type its applications by the following rule, which I give for a function with one argument (the other arguments are typed as usual, at each instance), and where Γ \Gamma Γ is the typing environment and the σ k \sigma_k σ k are substitutions for the variables α ‾ \overline{\alpha} α :
Γ ⊢ E : ∀ α ‾ . ( N ′ : X [ x ‾ = t ‾ ] ) → t ′ Γ ⊢ N : { D } X [ x ‾ = t 0 ‾ ] Γ ⊢ { D } ⪯ { D X } [ x ‾ : = t σ k ‾ ] for every k ∈ K Γ ⊢ E ( N ) : ⋀ k ∈ K t ′ [ N / N ′ ] σ k \frac{\Gamma\vdash E:\forall\overline{\alpha}.(N':\mathcal{X}[\overline{x}=\overline{t}])\to t' \qquad\Gamma\vdash N:\{D\}\mathcal{X}[\overline{x}=\overline{t_0}] \qquad\Gamma\vdash\{D\}\preceq\{D_{\mathcal{X}}\}[\overline{x}:=\overline{t\sigma_k}]\ \text{for every }k\in K}{\Gamma\vdash E(N):\bigwedge_{k\in K}t'[N/N']\sigma_k} Γ ⊢ E ( N ) : ⋀ k ∈ K t ′ [ N / N ′ ] σ k Γ ⊢ E : ∀ α . ( N ′ : X [ x = t ]) → t ′ Γ ⊢ N : { D } X [ x = t 0 ] Γ ⊢ { D } ⪯ { D X } [ x := t σ k ] for every k ∈ K
In words, if E E E is a polymorphic function that expects a module of behaviour X \mathcal{X} X instantiated at t ‾ \overline{t} t , and N N N is a module that declares X \mathcal{X} X at t 0 ‾ \overline{t_0} t 0 , then E E E can be applied to N N N at any set of instances σ k \sigma_k σ k such that the declarations of N N N are a subtype of those of X \mathcal{X} X at the types t σ k ‾ \overline{t\sigma_k} t σ k , and the application has the intersection of the results of these instances. The module must still declare the behaviour, but the types t σ k ‾ \overline{t\sigma_k} t σ k are no longer compared with the types t 0 ‾ \overline{t_0} t 0 that it declares. For s t a r t _ l i n k \mathop{\mathtt{start\_link}} start_link , X \mathcal{X} X is G e n S e r v e r \mathop{\mathtt{GenServer}} GenServer , t ‾ \overline{t} t are the variables a , c , r a,c,r a , c , r of the signature, and t ′ t' t ′ is { : o k , server ( c , r ) } \{\mathtt{:ok},\operatorname{server}(c,r)\} { : ok , server ( c , r )} . In the form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) the substitutions at the regions [ a : = a m , c : = C P , r : = R P ] [a:=a_m,c:=C_P,r:=R_P] [ a := a m , c := C P , r := R P ] are the σ k \sigma_k σ k in the rule, they satisfy the premise by (7), and thus the rule types the result as ⋀ { : o k , server ( C P , R P ) } = { : o k , server_of ( m ) } \bigwedge\{\mathtt{:ok},\operatorname{server}(C_P,R_P)\}=\{\mathtt{:ok},\operatorname{server\_of}(m)\} ⋀ { : ok , server ( C P , R P )} = { : ok , server_of ( m )} , with server_of \operatorname{server\_of} server_of in the signature. In the form H m r H_m^r H m r the substitutions at the arrows [ a : = a m , c : = c i , r : = r i ] [a:=a_m,c:=c_i,r:=r_i] [ a := a m , c := c i , r := r i ] satisfy it, and the result is { : o k , T m } \{\mathtt{:ok},T_m\} { : ok , T m } . The programmer would keep writing behaviours, and the state would need no type variable, since D D D and D X D_{\mathcal{X}} D X both declare state and are compared at the same one. This is a rule for applications, not a rule of subtyping. It is only an idea, which we will study in the module calculus, together with its soundness.
Sets of substitutions and processes. Since instantiating with a set of substitutions a function that spawns a process is unsound in general (the paragraph “Sets of substitutions and spawning” of Appendix § 12 .9.5), a new behaviour needs, besides its signature, its own proof that the instantiation at the regions is sound, as Theorem 2 is for serve (Appendix § 12 .§ 3 ). A criterion on the signature, for instance that the instances agree on everything that the function shares between requests (the state, for serve), would spare these proofs; I have not looked for one. The same question arises for call. Take the callback h h h of (4), a server of type MT ( h ) \operatorname{MT}(h) MT ( h ) , and one instance of call for each of the two arrows of h h h . The arguments of a call on :b are in the domains of both instances, so call would return the intersection of their replies, int: the axiom ( → ∧ ) (\to\land) ( → ∧ ) would come back, applied to the arrows of call, and the regions would not be needed to type calls. But the instances share the single return address of the call, to which they give the types pid(int ∨ nil) and pid(int ∨ :ok). In the π \pi π -calculus of Castagna et al. [15 ] , where a process can test the type of a channel, this is unsound: the server that replies nil when the return address accepts int ∨ nil, and 1 otherwise, has type MT ( h ) \operatorname{MT}(h) MT ( h ) , and makes call return nil where the intersection promises int. This is the output-driven overloading of § 6 again. Whether the instantiation of call is sound on the BEAM, which cannot test the type of a pid, is open.
Proofs and technical details
This section gives the proofs and the technical details that the previous sections leave out. Appendix A.9.1 recalls the decompositions of products and of arrows, and derives from them the two lemmas on which the proofs of the claims rest. Appendices § 12 .9.2 and § 12 .9.3 prove the claims of Appendices § 12 .§ 2 and § 12 .§ 4 , restated with their numbers, and justify the facts that these sections use without proof. Appendices § 12 .9.4 and § 12 .9.5 concern the model of Appendix § 12 .§ 6 : the first lists the rules of the base system that (A1) assumes, the second states and proves the theorems announced there. Appendix § 12 .9.6 compares server_of with the translation with λ \lambda λ -channels of Castagna et al. [14 ] .
Preliminaries
Besides the laws (1)–(3) of pid, recalled in Appendix § 12 .§ 1 , the proofs use the decompositions of products and of arrows of Frisch et al. [39 ] . For a finite set J J J :
t × s ≤ ⋁ j ∈ J ( t j × s j ) ⟺ ∀ Q ⊆ J . t ≤ ⋁ j ∈ Q t j or s ≤ ⋁ j ∈ J ∖ Q s j (9) t \times s \leq\bigvee_{j\in J}(t_j \times s_j) \Longleftrightarrow\forall Q \subseteq J.\; t \leq\bigvee_{j\in Q} t_j\ \text{ or }\ s \leq\bigvee_{j\in J\setminus Q} s_j \tag*{(9)} t × s ≤ j ∈ J ⋁ ( t j × s j ) ⟺ ∀ Q ⊆ J . t ≤ j ∈ Q ⋁ t j or s ≤ j ∈ J ∖ Q ⋁ s j (9)
⋀ j ∈ J ( t j → s j ) ≤ t → s ⟺ ∀ Q ⊆ J . t ≤ ⋁ j ∈ Q t j or ( Q ≠ J and ⋀ j ∈ J ∖ Q s j ≤ s ) (10) \bigwedge_{j\in J}(t_j \to s_j) \leq t \to s \Longleftrightarrow\forall Q \subseteq J.\; t \leq\bigvee_{j\in Q} t_j\ \text{ or }\ (Q \ne J\ \text{and}\ \bigwedge_{j\in J\setminus Q} s_j \leq s) \tag*{(10)} j ∈ J ⋀ ( t j → s j ) ≤ t → s ⟺ ∀ Q ⊆ J . t ≤ j ∈ Q ⋁ t j or ( Q = J and j ∈ J ∖ Q ⋀ s j ≤ s ) (10)
where the second equivalence requires J ≠ ∅ J \ne\varnothing J = ∅ , and a union indexed by the empty set is 0 \mathbf{0} 0 . Triples are treated as pairs, ( t , p , s ) (t,p,s) ( t , p , s ) as t × ( p × s ) t \times(p \times s) t × ( p × s ) . The laws of pid and the two decompositions form the assumption (A2) of Appendix § 12 .§ 6 .
The first lemma drops the components that are the same in all the tuples of an inequality, such as the return address pid() and the state in the type of handle_call.
Lemma 1 (common components). Let J J J be finite and u ≠ 0 u \ne0 u = 0 .
(a) t × u ≤ ⋁ j ∈ J ( t j × u ) t \times u \leq\bigvee_{j\in J}(t_j \times u) t × u ≤ ⋁ j ∈ J ( t j × u ) if and only if t ≤ ⋁ j ∈ J t j t \leq\bigvee_{j\in J} t_j t ≤ ⋁ j ∈ J t j . The same holds when u u u is the first component of the pairs, and when it is one of the components of triples, the pair of the other two components playing the role of t t t .
(b) Let J ≠ ∅ J \ne\varnothing J = ∅ and p , s ≠ 0 p,s \ne0 p , s = 0 . Then ⋀ j ∈ J ( ( c j , p , s ) → { r e p l y , r j , s } ) ≤ ( c , p , s ) → { r e p l y , r , s } \bigwedge_{j\in J}((c_j,p,s) \to\{\mathsf{reply},r_j,s\}) \leq(c,p,s) \to\{\mathsf{reply},r,s\} ⋀ j ∈ J (( c j , p , s ) → { reply , r j , s }) ≤ ( c , p , s ) → { reply , r , s } if and only if ⋀ j ∈ J ( c j → r j ) ≤ c → r \bigwedge_{j\in J}(c_j \to r_j) \leq c \to r ⋀ j ∈ J ( c j → r j ) ≤ c → r .
Proof. (a). By (8), the inequality holds if and only if, for every Q ⊆ J Q \subseteq J Q ⊆ J , either t ≤ ⋁ j ∈ Q t j t \leq\bigvee_{j\in Q} t_j t ≤ ⋁ j ∈ Q t j or u ≤ ⋁ j ∈ J ∖ Q u u \leq\bigvee_{j\in J\setminus Q} u u ≤ ⋁ j ∈ J ∖ Q u . Since u ≠ 0 u \ne0 u = 0 , the second disjunct holds if and only if Q ≠ J Q \ne J Q = J , so only the condition for Q = J Q = J Q = J remains. When u u u is the first component, exchange the roles of Q Q Q and J ∖ Q J \setminus Q J ∖ Q . For triples, apply (8) to the outer pair and the case of pairs to its second disjunct.
(b). By (9), the first inequality holds if and only if, for every Q ⊆ J Q \subseteq J Q ⊆ J , either ( c , p , s ) ≤ ⋁ j ∈ Q ( c j , p , s ) (c,p,s) \leq\bigvee_{j\in Q}(c_j,p,s) ( c , p , s ) ≤ ⋁ j ∈ Q ( c j , p , s ) , or Q ≠ J Q \ne J Q = J and ⋀ j ∈ J ∖ Q { r e p l y , r j , s } ≤ { r e p l y , r , s } \bigwedge_{j\in J\setminus Q}\{\mathsf{reply},r_j,s\} \leq\{\mathsf{reply},r,s\} ⋀ j ∈ J ∖ Q { reply , r j , s } ≤ { reply , r , s } . By (a), the first disjunct is c ≤ ⋁ j ∈ Q c j c \leq\bigvee_{j\in Q} c_j c ≤ ⋁ j ∈ Q c j . Since ⋀ j ∈ J ∖ Q { r e p l y , r j , s } = { r e p l y , ⋀ j ∈ J ∖ Q r j , s } \bigwedge_{j\in J\setminus Q}\{\mathsf{reply},r_j,s\} = \{\mathsf{reply},\bigwedge_{j\in J\setminus Q}r_j,s\} ⋀ j ∈ J ∖ Q { reply , r j , s } = { reply , ⋀ j ∈ J ∖ Q r j , s } , by (a) the second one is Q ≠ J Q \ne J Q = J and ⋀ j ∈ J ∖ Q r j ≤ r \bigwedge_{j\in J\setminus Q}r_j \leq r ⋀ j ∈ J ∖ Q r j ≤ r . These are the conditions that (9) gives for the second inequality. □
Regions. Let C P C_P C P and R P R_P R P be as in Appendix § 12 .§ 2 . By definition, the regions are pairwise disjoint, C P ≤ c i C_P \leq c_i C P ≤ c i if i ∈ P i \in P i ∈ P and C P ∧ c i = 0 C_P \wedge c_i = 0 C P ∧ c i = 0 otherwise, c i = ⋁ P ∋ i C P c_i = \bigvee_{P\ni i} C_P c i = ⋁ P ∋ i C P , and R P ≤ r i R_P \leq r_i R P ≤ r i if i ∈ P ‘ ( x r e f ‘ S e c t i o n 7 ‘ ) . I n ( 6 ) t h e e m p t y r e g i o n s c a n b e d r o p p e d , s i n c e $ 0 → t i \in P` ({xref}`Section 7`). In (6) the empty regions can be dropped, since \$0 \to t i ∈ P ‘ ( x r e f ‘ S ec t i o n 7‘ ) . I n ( 6 ) t h ee m pt y r e g i o n sc anb e d r o pp e d , s in ce $0 → t is the largest arrow type. By Lemma 1(b), applied to each arrow of either side with p = pid ( ) p = \operatorname{pid}() p = pid ( ) and s = state s = \operatorname{state} s = state , which is not empty by (A3), (6) gives (7) (the lemma applies since J J J is not empty and, as ⋁ i c i ≠ 0 \bigvee_i c_i \ne0 ⋁ i c i = 0 , neither is the set of the nonempty regions), whose domains ( C P , pid ( ) , state ) (C_P,\operatorname{pid}(),\operatorname{state}) ( C P , pid ( ) , state ) are pairwise disjoint, and nonempty when C P C_P C P is.
The second lemma is the pattern of all the proofs on server types: an intersection of server types is below server(c,r) if and only if the components whose reply is in r r r cover c c c .
Lemma 2 (server types). Let J J J be finite, and let J r = { j ∈ J ∣ r j ≤ r } J_r = \{j \in J \mid r_j \leq r\} J r = { j ∈ J ∣ r j ≤ r } . Then
c × pid ( r ) ≤ ⋁ j ∈ J ( c j × pid ( r j ) ) ⟺ c ≤ ⋁ j ∈ J r c j . c \times\operatorname{pid}(r) \leq\bigvee_{j\in J}(c_j \times\operatorname{pid}(r_j)) \Longleftrightarrow c \leq\bigvee_{j\in J_r} c_j. c × pid ( r ) ≤ j ∈ J ⋁ ( c j × pid ( r j )) ⟺ c ≤ j ∈ J r ⋁ c j . Hence, for J ≠ ∅ J \ne\varnothing J = ∅ , ⋀ j ∈ J server ( c j , r j ) ≤ server ( c , r ) \bigwedge_{j\in J}\operatorname{server}(c_j,r_j) \leq\operatorname{server}(c,r) ⋀ j ∈ J server ( c j , r j ) ≤ server ( c , r ) if and only if c ≤ ⋁ j ∈ J r c j c \leq\bigvee_{j\in J_r} c_j c ≤ ⋁ j ∈ J r c j .
Proof. By (9) , the first inequality holds if and only if, for every Q ⊆ J Q \subseteq J Q ⊆ J , either c ≤ ⋁ j ∈ Q c j c \le\bigvee_{j\in Q} c_j c ≤ ⋁ j ∈ Q c j or pid ( r ) ≤ ⋁ j ∈ J ∖ Q pid ( r j ) \operatorname{pid}(r) \le\bigvee_{j\in J\setminus Q}\operatorname{pid}(r_j) pid ( r ) ≤ ⋁ j ∈ J ∖ Q pid ( r j ) . By the union law (4) , the second disjunct holds if and only if r j ≤ r r_j \le r r j ≤ r for some j ∈ J ∖ Q j \in J\setminus Q j ∈ J ∖ Q , that is, if and only if J r ⊈ Q J_r \not\subseteq Q J r ⊆ Q . So the inequality holds if and only if c ≤ ⋁ j ∈ Q c j c \le\bigvee_{j\in Q}c_j c ≤ ⋁ j ∈ Q c j for every Q ⊇ J r Q \supseteq J_r Q ⊇ J r , that is, for Q = J r Q=J_r Q = J r , which implies the other cases. The second equivalence follows, since ⋀ j ∈ J server ( c j , r j ) = pid ( ⋁ j ∈ J ( c j × pid ( r j ) ) ) \bigwedge_{j\in J}\operatorname{server}(c_j,r_j)=\operatorname{pid}\left(\bigvee_{j\in J}(c_j \times\operatorname{pid}(r_j))\right) ⋀ j ∈ J server ( c j , r j ) = pid ( ⋁ j ∈ J ( c j × pid ( r j )) ) by (3) , and pid \operatorname{pid} pid is contravariant (2) .
For a single component and c ≠ 0 c \ne0 c = 0 , this is the variance of server stated in § 5 .
Proofs of the claims on server_of
This section proves Claims 1–3 of Appendix § 12 .§ 2 , justifies the type that call returns, which Appendix § 12 .§ 2 uses without proof, and characterizes the solutions that the plain translation gives to call.
Claim 1. Let J ≠ ∅ J \ne\varnothing J = ∅ , and let the C j C_j C j (j ∈ J j \in J j ∈ J ) be pairwise disjoint. Then the following conditions are equivalent:
(i) ⋀ j ∈ J ( C j → R j ) ≤ c → r \bigwedge_{j\in J}(C_j \to R_j) \le c \to r ⋀ j ∈ J ( C j → R j ) ≤ c → r ;
(ii) ⋀ j ∈ J server ( C j , R j ) ≤ server ( c , r ) \bigwedge_{j\in J}\operatorname{server}(C_j,R_j) \le\operatorname{server}(c,r) ⋀ j ∈ J server ( C j , R j ) ≤ server ( c , r ) ;
(iii) c ≤ ⋁ j ∈ J C j c \le\bigvee_{j\in J}C_j c ≤ ⋁ j ∈ J C j , and R j ≤ r R_j \le r R j ≤ r for every j ∈ J j \in J j ∈ J such that c ∧ C j ≠ 0 c \wedge C_j \ne0 c ∧ C j = 0 .
Proof. (ii) ⟺ \Longleftrightarrow ⟺ (iii). By Lemma 2, (ii) holds if and only if c ≤ ⋁ j ∈ J r C j c \le\bigvee_{j\in J_r}C_j c ≤ ⋁ j ∈ J r C j , where J r = { j ∈ J ∣ R j ≤ r } J_r=\{j\in J\mid R_j\le r\} J r = { j ∈ J ∣ R j ≤ r } . Since the C j C_j C j are pairwise disjoint, this holds if and only if c ≤ ⋁ j ∈ J C j c\le\bigvee_{j\in J}C_j c ≤ ⋁ j ∈ J C j and c ∧ C j = 0 c\wedge C_j=0 c ∧ C j = 0 for every j ∉ J r j\notin J_r j ∈ / J r , which is (iii).
(i)⇒ \Rightarrow ⇒ (iii). By (10) , which applies since J ≠ ∅ J\ne\varnothing J = ∅ , (i) holds if and only if, for every Q ⊆ J Q\subseteq J Q ⊆ J , either c ≤ ⋁ j ∈ Q C j c\le\bigvee_{j\in Q}C_j c ≤ ⋁ j ∈ Q C j , or Q ≠ J Q\ne J Q = J and ⋀ j ∈ J ∖ Q R j ≤ r \bigwedge_{j\in J\setminus Q}R_j\le r ⋀ j ∈ J ∖ Q R j ≤ r . For Q = J Q=J Q = J this gives c ≤ ⋁ j ∈ J C j c\le\bigvee_{j\in J}C_j c ≤ ⋁ j ∈ J C j . For Q = J ∖ { j } Q=J\setminus\{j\} Q = J ∖ { j } with c ∧ C j ≠ 0 c\wedge C_j\ne0 c ∧ C j = 0 , the first disjunct fails, since C j C_j C j is disjoint from the other C k C_k C k ; hence R j ≤ r R_j\le r R j ≤ r .
(iii)⇒ \Rightarrow ⇒ (i). Let Q ⊆ J Q\subseteq J Q ⊆ J be such that c ≰ ⋁ j ∈ Q C j c\not\le\bigvee_{j\in Q}C_j c ≤ ⋁ j ∈ Q C j . Since c ≤ ⋁ j ∈ J C j c\le\bigvee_{j\in J}C_j c ≤ ⋁ j ∈ J C j , there is j ∉ Q j\notin Q j ∈ / Q such that c ∧ C j ≠ 0 c\wedge C_j\ne0 c ∧ C j = 0 ; hence Q ≠ J Q\ne J Q = J and ⋀ k ∈ J ∖ Q R k ≤ R j ≤ r \bigwedge_{k\in J\setminus Q}R_k\le R_j\le r ⋀ k ∈ J ∖ Q R k ≤ R j ≤ r .
The hypothesis J ≠ ∅ J\ne\varnothing J = ∅ excludes a degenerate case: for J = ∅ J=\varnothing J = ∅ , (i) and (ii) are false, since the empty intersection 1 1 1 is neither an arrow type nor a pid type, while (iii) holds for c = 0 c=0 c = 0 .
What call returns. In Appendix § 12 .§ 2 , call(p, c), with p : server_of ( m ) p:\operatorname{server\_of}(m) p : server_of ( m ) and c : c c:c c : c , can be given the type r r r if and only if server_of ( m ) ≤ server ( c , r ) \operatorname{server\_of}(m)\le\operatorname{server}(c,r) server_of ( m ) ≤ server ( c , r ) : instantiating the request variable of call at a type c ′ c' c ′ requires c ≤ c ′ c\le c' c ≤ c ′ and server_of ( m ) ≤ server ( c ′ , r ) \operatorname{server\_of}(m)\le\operatorname{server}(c',r) server_of ( m ) ≤ server ( c ′ , r ) , and c ′ = c c'=c c ′ = c is the best choice, since server is contravariant in its first argument. Claim 1 applies to the nonempty regions, of which there is at least one since ⋁ i c i ≠ 0 \bigvee_i c_i\ne0 ⋁ i c i = 0 .
Claim 2. Let m m m be a module whose handle_call has the type (5), so that its function from requests to replies has type ⋀ i ∈ I ( c i → r i ) \bigwedge_{i\in I}(c_i\to r_i) ⋀ i ∈ I ( c i → r i ) . If ⋀ j ∈ J ( d j → s j ) \bigwedge_{j\in J}(d_j\to s_j) ⋀ j ∈ J ( d j → s j ) is equivalent to ⋀ i ∈ I ( c i → r i ) \bigwedge_{i\in I}(c_i\to r_i) ⋀ i ∈ I ( c i → r i ) , then server_of ( m ) ≤ MT ( ⋀ j ∈ J ( d j → s j ) ) \operatorname{server\_of}(m)\le\operatorname{MT}\left(\bigwedge_{j\in J}(d_j\to s_j)\right) server_of ( m ) ≤ MT ( ⋀ j ∈ J ( d j → s j ) ) .
Proof. Let j ∈ J j\in J j ∈ J . Since the two intersections are equivalent, ⋀ i ∈ I ( c i → r i ) ≤ d j → s j \bigwedge_{i\in I}(c_i\to r_i)\le d_j\to s_j ⋀ i ∈ I ( c i → r i ) ≤ d j → s j , hence, by (7) , ⋀ P ( C P → R P ) ≤ d j → s j \bigwedge_{P}(C_P\to R_P)\le d_j\to s_j ⋀ P ( C P → R P ) ≤ d j → s j , where P P P ranges over the nonempty regions, of which there is at least one since ⋁ i c i ≠ 0 \bigvee_i c_i\ne0 ⋁ i c i = 0 . By (i)⇒ \Rightarrow ⇒ (ii) of Claim 1, server_of ( m ) = ⋀ P server ( C P , R P ) ≤ server ( d j , s j ) \operatorname{server\_of}(m)=\bigwedge_P\operatorname{server}(C_P,R_P)\le\operatorname{server}(d_j,s_j) server_of ( m ) = ⋀ P server ( C P , R P ) ≤ server ( d j , s j ) . Hence
server_of ( m ) ≤ ⋀ j ∈ J server ( d j , s j ) = MT ( ⋀ j ∈ J ( d j → s j ) ) \operatorname{server\_of}(m)\le\bigwedge_{j\in J}\operatorname{server}(d_j,s_j)=\operatorname{MT}\left(\bigwedge_{j\in J}(d_j\to s_j)\right) server_of ( m ) ≤ j ∈ J ⋀ server ( d j , s j ) = MT j ∈ J ⋀ ( d j → s j ) since MT \operatorname{MT} MT commutes with intersections. □
The proof uses only one half of the equivalence: server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) is below the translation of every intersection of arrows that is a supertype of the type of handle_call.
Claim 3. Let T m = ⋀ i ∈ I server ( c i , r i ) T_m = \bigwedge_{i\in I} \operatorname{server}(c_i,r_i) T m = ⋀ i ∈ I server ( c i , r i ) . Then server_of ( m ) ≤ T m \operatorname{server\_of}(m) \leq T_m server_of ( m ) ≤ T m ; for every nonempty region C P C_P C P , T m ≤ server ( C P , R P ) T_m \leq\operatorname{server}(C_P,R_P) T m ≤ server ( C P , R P ) if and only if r i = R P r_i = R_P r i = R P for some i ∈ P i \in P i ∈ P ; hence server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) and T m T_m T m are equivalent if and only if every nonempty region has such an i i i .
Proof. Below, P P P and P ′ P' P ′ range over the nonempty regions, of which server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) is the intersection.
server_of ( m ) ≤ T m \operatorname{server\_of}(m) \leq T_m server_of ( m ) ≤ T m . Let i ∈ I i \in I i ∈ I . By Lemma 2, server_of ( m ) ≤ server ( c i , r i ) \operatorname{server\_of}(m) \leq\operatorname{server}(c_i,r_i) server_of ( m ) ≤ server ( c i , r i ) if and only if c i ≤ ⋁ P ′ : R P ′ ≤ r i C P ′ c_i \leq\bigvee_{P':R_{P'}\leq r_i} C_{P'} c i ≤ ⋁ P ′ : R P ′ ≤ r i C P ′ , which holds since c i = ⋁ P ′ ∋ i C P ′ c_i = \bigvee_{P'\ni i} C_{P'} c i = ⋁ P ′ ∋ i C P ′ and R P ′ ≤ r i R_{P'} \leq r_i R P ′ ≤ r i when i ∈ P ′ i \in P' i ∈ P ′ .
T m ≤ server ( C P , R P ) T_m \leq\operatorname{server}(C_P,R_P) T m ≤ server ( C P , R P ) . By Lemma 2, this holds if and only if C P ≤ ⋁ i : r i ≤ R P c i C_P \leq\bigvee_{i:r_i\leq R_P}c_i C P ≤ ⋁ i : r i ≤ R P c i . Since C P C_P C P is nonempty, below c i c_i c i for i ∈ P i \in P i ∈ P and disjoint from c i c_i c i for i ∉ P i \notin P i ∈ / P , this holds if and only if r i ≤ R P r_i \leq R_P r i ≤ R P for some i ∈ P i \in P i ∈ P , that is, since R P ≤ r i R_P \leq r_i R P ≤ r i , if and only if r i = R P r_i = R_P r i = R P .
Equivalence. By the first part, server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) and T m T_m T m are equivalent if and only if T m ≤ server ( C P , R P ) T_m \leq\operatorname{server}(C_P,R_P) T m ≤ server ( C P , R P ) for every P P P ; conclude by the second part.
The solutions with the plain translation. By Claim 3, every solution for r r r that the plain translation gives to call is sound. By Lemma 2, T m ≤ server ( c , r ) T_m \leq\operatorname{server}(c,r) T m ≤ server ( c , r ) if and only if c ≤ ⋁ i : r i ≤ r c i c \leq\bigvee_{i:r_i\leq r}c_i c ≤ ⋁ i : r i ≤ r c i , that is, since c i = ⋁ P ∋ i C P c_i = \bigvee_{P\ni i}C_P c i = ⋁ P ∋ i C P and the regions are pairwise disjoint, if and only if c ≤ ⋁ i c i c \leq\bigvee_i c_i c ≤ ⋁ i c i and every region C P C_P C P that c c c meets has an arrow i ∈ P i \in P i ∈ P with r i ≤ r r_i \leq r r i ≤ r . So the solutions are the supertypes of the unions ⋁ P : c ∧ C P ≠ 0 r φ ( P ) \bigvee_{P:c\wedge C_P\neq0}r_{\varphi(P)} ⋁ P : c ∧ C P = 0 r φ ( P ) , for the functions φ \varphi φ that choose an arrow φ ( P ) ∈ P \varphi(P) \in P φ ( P ) ∈ P in each region met by c c c , while the exact result is ⋁ P : c ∧ C P ≠ 0 R P \bigvee_{P:c\wedge C_P\neq0}R_P ⋁ P : c ∧ C P = 0 R P . The two coincide when c c c meets only regions with ∣ P ∣ = 1 |P|=1 ∣ P ∣ = 1 ; otherwise a minimal solution replaces R P R_P R P , on each region with ∣ P ∣ ≥ 2 |P|\geq2 ∣ P ∣ ≥ 2 that c c c meets, by the reply r φ ( P ) r_{\varphi(P)} r φ ( P ) of a single arrow of $P.
Proofs of the claims on deferred replies
This section proves Claim 4 of Appendix A.4, and justifies three facts that Appendices A.4 and A.6 use: an intersection that mixes the two forms is below the pid ( r i ) \operatorname{pid}(r_i) pid ( r i ) form; declaring the arrow of a lost region changes neither the regions nor their replies; and a module in the pid ( r i ) \operatorname{pid}(r_i) pid ( r i ) form conforms to GenServer only if the behaviour types the return address as pid ( r e p l y ) \operatorname{pid}(reply) pid ( r e pl y ) .
Mixed forms. By contravariance of the domain and covariance of the codomain,
( c , pid ( ) , s ) → { :reply , r , s } ≤ ( c , pid ( r ) , s ) → { :reply , r , s } ∨ { :noreply , s } (c,\operatorname{pid}(),s)\to\{\text{:reply},r,s\}
\leq
(c,\operatorname{pid}(r),s)\to\{\text{:reply},r,s\}\vee\{\text{:noreply},s\} ( c , pid ( ) , s ) → { :reply , r , s } ≤ ( c , pid ( r ) , s ) → { :reply , r , s } ∨ { :noreply , s }
since pid ( r ) ≤ pid ( ) \operatorname{pid}(r) \leq\operatorname{pid}() pid ( r ) ≤ pid ( ) by (2) : an arrow in the pid ( ) \operatorname{pid}() pid ( ) form is below the corresponding arrow in the pid ( r i ) \operatorname{pid}(r_i) pid ( r i ) form, so an intersection that mixes the two forms, as in the third version of MyServer (Appendix A.4), is below the pid ( r i ) \operatorname{pid}(r_i) pid ( r i ) form.
Claim 4. Let C P ≠ 0 C_P \neq0 C P = 0 and s t a t e ≠ 0 state \neq0 s t a t e = 0 . Then H m r ≤ ( C P , pid ( R P ) , s t a t e ) → K R P H^r_m \leq(C_P,\operatorname{pid}(R_P),state)\to K_{R_P} H m r ≤ ( C P , pid ( R P ) , s t a t e ) → K R P if and only if r i = R P r_i = R_P r i = R P for some i ∈ P i \in P i ∈ P .
Proof. Let D = ( C P , pid ( R P ) , s t a t e ) D=(C_P,\operatorname{pid}(R_P),state) D = ( C P , pid ( R P ) , s t a t e ) and E i = ( c i , pid ( r i ) , s t a t e ) E_i=(c_i,\operatorname{pid}(r_i),state) E i = ( c i , pid ( r i ) , s t a t e ) . For every Q ⊆ I Q\subseteq I Q ⊆ I ,
D ≤ ⋁ i ∈ Q E i ⟺ r i ≤ R P for some i ∈ Q ∩ P . (11) D \leq\bigvee_{i\in Q}E_i \Longleftrightarrow r_i\leq R_P\text{ for some }i\in Q\cap P. \tag*{(11)} D ≤ i ∈ Q ⋁ E i ⟺ r i ≤ R P for some i ∈ Q ∩ P . (11)
Indeed, by Lemma 1(a), which drops the component s t a t e ≠ 0 state\neq0 s t a t e = 0 , and by Lemma 2, the left-hand side holds if and only if C P ≤ ⋁ i ∈ Q : r i ≤ R P c i C_P \leq\bigvee_{i\in Q:r_i\leq R_P}c_i C P ≤ ⋁ i ∈ Q : r i ≤ R P c i , that is, if and only if some i ∈ Q ∩ P i\in Q\cap P i ∈ Q ∩ P has r i ≤ R P r_i\leq R_P r i ≤ R P , since C P C_P C P is nonempty, below c i c_i c i for i ∈ P i\in P i ∈ P and disjoint from c i c_i c i for i ∉ P i\notin P i ∈ / P . By (10) , with I ≠ ∅ I\neq\varnothing I = ∅ , H m r ≤ D → K R P H^r_m\leq D\to K_{R_P} H m r ≤ D → K R P if and only if, for every Q ⊆ I Q\subseteq I Q ⊆ I , either D ≤ ⋁ i ∈ Q E i D\leq\bigvee_{i\in Q}E_i D ≤ ⋁ i ∈ Q E i , or Q ≠ I Q\neq I Q = I and ⋀ i ∈ I ∖ Q K r i ≤ K R P \bigwedge_{i\in I\setminus Q}K_{r_i}\leq K_{R_P} ⋀ i ∈ I ∖ Q K r i ≤ K R P .
Only if. For Q = I Q=I Q = I the second disjunct is excluded, so (†) gives an i ∈ P i\in P i ∈ P with r i ≤ R P r_i\leq R_P r i ≤ R P , hence r i = R P r_i=R_P r i = R P , since R P ≤ r i R_P\leq r_i R P ≤ r i .
If. Let i 0 ∈ P i_0\in P i 0 ∈ P with r i 0 = R P r_{i_0}=R_P r i 0 = R P , and let Q ⊆ I Q\subseteq I Q ⊆ I . If i 0 ∈ Q i_0\in Q i 0 ∈ Q , the first disjunct holds by (†). Otherwise Q ≠ I Q\neq I Q = I and ⋀ i ∈ I ∖ Q K r i ≤ K r i 0 = K R P \bigwedge_{i\in I\setminus Q}K_{r_i}\leq K_{r_{i_0}}=K_{R_P} ⋀ i ∈ I ∖ Q K r i ≤ K r i 0 = K R P .
In particular, when the claim fails for a nonempty region, H m r H^r_m H m r is not below the arrow of that region: the equation (8) has no counterpart in the pid ( r i ) \operatorname{pid}(r_i) pid ( r i ) form.
Recovering a lost region. Adding to H m H_m H m the arrow ( C P , pid ( R P ) , state ) → K R P (C_P,\operatorname{pid}(R_P),\operatorname{state}) \to K_{R_P} ( C P , pid ( R P ) , state ) → K R P (Appendix § 12 .§ 4 ) changes neither the regions nor their replies, since the new domain C P C_P C P is included in every c i c_i c i with i ∈ P i \in P i ∈ P and disjoint from the others: the region C P C_P C P is now in the domains of the arrows of P P P and of the new one, and its reply is R P ∧ R P = R P R_P \land R_P = R_P R P ∧ R P = R P .
Conformance to the behaviour. A module implements a behaviour when its type is a subtype of the type of the behaviour. By contravariance of the domain, an arrow that asks for pid ( r i ) \operatorname{pid}(r_i) pid ( r i ) is not below an arrow that offers only pid ( ) \operatorname{pid}() pid ( ) : for a module whose handle_call is in the pid ( r i ) \operatorname{pid}(r_i) pid ( r i ) form to implement GenServer, the callback that the behaviour declares for handle_call must therefore type the return address as pid ( r e p l y ) \operatorname{pid}(\mathit{reply}) pid ( reply ) , where r e p l y \mathit{reply} reply is the parameter of the replies. With the callback type
( c a l l _ m s g , pid ( r e p l y ) , s t a t e ) → { : r e p l y , r e p l y , s t a t e } ∨ { : n o r e p l y , s t a t e } (\mathit{call\_msg},\operatorname{pid}(\mathit{reply}),\mathit{state}) \to\{\mathit{:reply},\mathit{reply},\mathit{state}\} \lor\{\mathit{:noreply},\mathit{state}\} ( call_msg , pid ( reply ) , state ) → { : reply , reply , state } ∨ { : noreply , state }
both forms conform, since r i ≤ r e p l y r_i \leq\mathit{reply} r i ≤ reply gives pid ( r e p l y ) ≤ pid ( r i ) ≤ pid ( ) \operatorname{pid}(\mathit{reply}) \leq\operatorname{pid}(r_i) \leq\operatorname{pid}() pid ( reply ) ≤ pid ( r i ) ≤ pid ( ) ; and with only this callback type the server gets server ( c a l l _ m s g , r e p l y ) \operatorname{server}(\mathit{call\_msg},\mathit{reply}) server ( call_msg , reply ) , as in Appendix § 12 .§ 5 .
The base system
The proofs of Appendix § 12 .9.5 use the following rules and properties of the base system of (A1): rules for the primitives on processes, (send) to (receive); rules for the functional part, (case) to (progress); and two properties of names, (names) and (opacity); the second is used only in the proof of Theorem 4 and in the paragraph “The model with the messages of OTP”.
(send) send(p, v) is well typed if p : pid ( t ) p : \operatorname{pid}(t) p : pid ( t ) and v : t v : t v : t for some t t t .
(spawn) spawn(f) has type pid ( M ) \operatorname{pid}(M) pid ( M ) if the body of f f f is well typed in a process whose mailbox has type M M M , that is, whose receives expect messages of type M M M .
(alias) alias() creates a name of type pid ( t ) \operatorname{pid}(t) pid ( t ) , for a t t t chosen by the caller at creation, and then receive_on on this name has type t t t , the type of creation, in the caller, the only process that can receive on it. (A polymorphic receive_on of type ∀ t . pid ( t ) → t \forall t.\operatorname{pid}(t) \to t ∀ t . pid ( t ) → t would be unsound, by contravariance.)
(receive) A receive on a mailbox of type M = ⋁ k t k M = \bigvee_k t_k M = ⋁ k t k , a union of products, types its branch once for each summand t k t_k t k , with the variables of the pattern at the components of t k t_k t k . This is sound since a message is a value, which belongs to one of the summands, provided that a value can be given every type that contains it; for names, this means that a name created at pid ( t ) \operatorname{pid}(t) pid ( t ) has the type pid ( s ) \operatorname{pid}(s) pid ( s ) for every s ≤ t s \leq t s ≤ t and the type ¬ pid ( s ) \neg\operatorname{pid}(s) ¬ pid ( s ) for every s ≰ t s \not\leq t s ≤ t , as in the semantic reading of pid types (§ 5 ). This rule is not the one of Castagna et al. [24 ] , which types the variables of the pattern by projection.
(case) A branch of a case whose pattern is disjoint from the type of the scrutinee is never taken, and is not typed.
(app) An application of a function whose type is an intersection of arrows to an argument in the domain of one of the arrows has the type of the codomain of this arrow (by subsumption, then application of one arrow). When the domains D k D_k D k of the arrows are pairwise disjoint and the argument has a type D ≤ ⋁ k D k D \leq\bigvee_k D_k D ≤ ⋁ k D k , the application has the type ⋁ k : D ∧ D k ≠ ∅ T k \bigvee_{k:D\wedge D_k\ne\varnothing} T_k ⋁ k : D ∧ D k = ∅ T k , where T k T_k T k is the codomain of the k k k -th arrow (a special case of the type of applications of (Castagna, 2020, §4.4.3)).
(inst) A polymorphic function is instantiated by one substitution at a time, and an occurrence is instantiated by the same substitution in every typing of the enclosing body (when the body is typed several times, against the arrows of an intersection or the summands of (receive)). Sets of substitutions appear only in Theorem 6(b) and (c), which compute types with them but do not claim them sound.
(progress) An application of a function defined by clauses, whose declared type is checked against the clauses, to an argument in the domain of this type matches one of the clauses.
(names) If a name (a pid created by spawn, an alias created by alias) created at type pid ( t ) \operatorname{pid}(t) pid ( t ) is used at a type pid ( s ) \operatorname{pid}(s) pid ( s ) , in any process and at any step of any run, then pid ( t ) ≤ pid ( s ) \operatorname{pid}(t) \le\operatorname{pid}(s) pid ( t ) ≤ pid ( s ) , that is, s ≤ t s \le t s ≤ t : this is how subject reduction types names.
(opacity) Code in which a name n n n is bound to a variable of type pid ( ) \operatorname{pid}() pid ( ) , and whose every route to n n n (variables, closure environments, received messages, results of functions, state) carries n n n only at type pid ( ) \operatorname{pid}() pid ( ) , never sends on n n n , and neither do the processes to which it passes n n n . The reason is that no run-time test tells which messages a pid accepts (is_pid only gives $\operatorname{pid}()`), so the code must also work with a pid that accepts no message, on which nothing can be sent. This is a parametricity property, not a consequence of soundness.
Statements on the model
This section states and proves the results announced in Appendix A.6, with the rules of Appendix A.9.4; its last two paragraphs treat the form H m r H^{r}_{m} H m r and the code of Appendix A.7. Let C P C_{P} C P , R P R_{P} R P and server_of(m) be as in Appendix A.2, and let D P D_{P} D P denote the triple ( C P , pid ( ) , state ) (C_{P}, \operatorname{pid}(), \operatorname{state}) ( C P , pid ( ) , state ) , so that, by (7), H m pid ( ) = Λ P : C P ≠ ∅ ( D P → { : reply , R P , state } ) H^{\operatorname{pid}()}_{m} = \Lambda_{P:C_{P}\ne\varnothing}(D_{P} \to\{:\operatorname{reply}, R_{P}, \operatorname{state}\}) H m pid ( ) = Λ P : C P = ∅ ( D P → { : reply , R P , state }) with pairwise disjoint domains D P D_{P} D P . In the proofs, P P P ranges over the nonempty regions.
Theorem 1 (call is well typed). ⊢ call : ∀ c , r . ( server ( c , r ) , c ) → r \vdash\texttt{call} : \forall c,r.\,(\operatorname{server}(c,r),c) \to r ⊢ call : ∀ c , r . ( server ( c , r ) , c ) → r . In particular , if call(p, c), with c : c c : c c : c , is typed with the instance ( server ( c , r ) , c ) → r (\operatorname{server}(c,r),c) \to r ( server ( c , r ) , c ) → r of this type, then every value sent to its alias, hence every value that it returns, in any run of any well-typed program, has type r r r .
Sketch. Typing. Let p : server ( c , r ) p : \operatorname{server}(c,r) p : server ( c , r ) and c : c c : c c : c . By (alias), w = alias ( ) w = \texttt{alias}() w = alias ( ) creates a name of type pid ( r ) \operatorname{pid}(r) pid ( r ) , and receive_on(w) : r r r ; by (inst), each instance of call creates its alias at the r r r of the instance. Then { c , w } : c × pid ( r ) \{c,w\} : c \times\operatorname{pid}(r) { c , w } : c × pid ( r ) , and send(p, {c, w}) is well typed by (send), since server ( c , r ) = pid ( c × pid ( r ) ) \operatorname{server}(c,r) = \operatorname{pid}(c \times\operatorname{pid}(r)) server ( c , r ) = pid ( c × pid ( r )) . So the body has type r r r , for all c c c and r r r .
Runs. By (A1), the processes of a run of a well-typed program stay well typed. A process that sends a value v v v on w w w does it by (send), at a type pid ( t ) \operatorname{pid}(t) pid ( t ) of w w w , with v : t v : t v : t ; by (names), pid ( r ) ≤ pid ( t ) \operatorname{pid}(r) \le\operatorname{pid}(t) pid ( r ) ≤ pid ( t ) , so t ≤ r t \le r t ≤ r by (1), and v : r v : r v : r . The call returns the value of receive_on(w), which was sent on w w w .
Theorem 2 (start_link is well typed). Under (A3), in the form H m pid ( ) H^{\operatorname{pid}()}_{m} H m pid ( ) , for v : a v : a v : a we have ⊢ start_link ( m , v ) : { : ok , server_of ( m ) } \vdash\texttt{start\_link}(m,v) : \{:\operatorname{ok},\operatorname{server\_of}(m)\} ⊢ start_link ( m , v ) : { : ok , server_of ( m )} .
Sketch. Let M = ⋁ P ( C P × pid ( R P ) ) M = \bigvee_{P}(C_{P} \times\operatorname{pid}(R_{P})) M = ⋁ P ( C P × pid ( R P )) , so that pid ( M ) = ⋀ P server ( C P , R P ) = server_of ( m ) \operatorname{pid}(M) = \bigwedge_{P}\operatorname{server}(C_{P},R_{P}) = \operatorname{server\_of}(m) pid ( M ) = ⋀ P server ( C P , R P ) = server_of ( m ) by (2). We type the body of start_link, and then the body of loop by the rule for recursive functions, that is, under the hypothesis that loop(h, s') is well typed, for h : H m pid ( ) h : H^{\operatorname{pid}()}_{m} h : H m pid ( ) and every s ′ : state s' : \operatorname{state} s ′ : state , in a process whose mailbox has type M M M .
{ : ok , s } = m.init(v) \{:\operatorname{ok},s\} = \texttt{m.init(v)} { : ok , s } = m.init(v) By (A3), m.init(v) : { : ok , state } \{:\operatorname{ok},\operatorname{state}\} { : ok , state } , so the match binds s : state s : \operatorname{state} s : state .
spawn(fn → loop(&m.handle_call/3, s) end) The capture has the declared type H m pid ( ) H^{\operatorname{pid}()}_{m} H m pid ( ) of handle_call. By (spawn), the expression has type pid ( M ) \operatorname{pid}(M) pid ( M ) if loop(h, s), with h : H m pid ( ) h : H^{\operatorname{pid}()}_{m} h : H m pid ( ) and s : state s : \operatorname{state} s : state , is well typed in a process whose mailbox has type M M M . Hence the result { : ok , pid ( M ) } = { : ok , server_of ( m ) } \{:\operatorname{ok},\operatorname{pid}(M)\} = \{:\operatorname{ok},\operatorname{server\_of}(m)\} { : ok , pid ( M )} = { : ok , server_of ( m )} .
receive do {c, w} → ... By (receive), the branch is typed once for each P P P , with c : C P c : C_{P} c : C P and w : pid ( R P ) w : \operatorname{pid}(R_{P}) w : pid ( R P ) . h.(c, w, s) (c, w, s) : (C_P, \operatorname{pid}(R_P), \mathit{state}) \le D_P, since pid ( R P ) ≤ pid ( ) \operatorname{pid}(R_P) \le\operatorname{pid}() pid ( R P ) ≤ pid ( ) by (1), and this triple is disjoint from the other domains D P ′ D_{P'} D P ′ . By (app), h.(c, w, s) : {:reply, R_P, state}.
case The pattern {:noreply, s2} is disjoint from this type, so its branch is not typed (case). The pattern {:reply, r, s2} binds r : R_P and s2 : state.
send(w, r); loop(h, s2) The send is well typed by (send), since w : pid(R_P) and r : R_P; the recursive call by the hypothesis on loop, since s2 : state.
The receive of the loop is the only receive on the mailbox of the server, since the body of handle_call performs none (A3). Without this hypothesis a clause such as handle_call(:a, _, s) -> receive n -> {:reply, n, s} end could take another request for its reply.
Corollary 3 (no run-time type error). Consider a program, well typed under (A1), whose servers are started by start_link and whose pids are used only at the types given by Theorem 2 (or by Proposition 8 , in the form H m r H_m^r H m r ), with call used at the types of Theorem 1. In every run of this program: (i) handle_call is applied only to requests in its domain ⋁ i c i \bigvee_i c_i ⋁ i c i (no function_clause error, the error raised when no clause matches); (ii) every message sent to the alias of a call used at type r r r has type r r r .
Sketch. (i). The pid q q q of the server is created at type pid ( M ) \operatorname{pid}(M) pid ( M ) , with M M M as in the proof of Theorem 2. Every message that the loop receives was sent by (send) at some type pid ( t ) \operatorname{pid}(t) pid ( t ) of q q q with a value of type t t t ; by (names), pid ( M ) ≤ pid ( t ) \operatorname{pid}(M) \le\operatorname{pid}(t) pid ( M ) ≤ pid ( t ) , so t ≤ M t \le M t ≤ M by (1): every message received has type M M M . By induction on the number of consumed requests, the state passed to the loop has type s t a t e \mathit{state} state : the initial one by (A3), and the next one, s2, by the proof of Theorem 2. So each application of handle_call has its arguments in some ( C P , pid ( R P ) , s t a t e ) ≤ D P (C_P, \operatorname{pid}(R_P), \mathit{state}) \le D_P ( C P , pid ( R P ) , state ) ≤ D P , below the domain of H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) , and by (progress) some clause matches.
(ii). Theorem 1.
Theorem 4 (adequacy of the loop, form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) ). Let q q q be the pid of the server. In every run of every program that satisfies the hypotheses of Corollary 3, let ( x 1 , w 1 ) , ( x 2 , w 2 ) , … (x_1,w_1),(x_2,w_2),\ldots ( x 1 , w 1 ) , ( x 2 , w 2 ) , … be the requests consumed by the loop, in the order of consumption, and let {:reply, y_k, s_k} be the value returned by the k k k -th application of handle_call, if it returns. If the k k k -th request was sent by a call call(q, x_k), then the loop sends y k y_k y k to w k w_k w k after consuming the request, and nothing else is sent to w k w_k w k . Hence a call call(q, c) on a request of type c ≤ ⋁ i c i c \le\bigvee_i c_i c ≤ ⋁ i c i returns a value of type ⋁ P : c ∧ C P ≠ 0 R P \bigvee_{P:c\wedge C_P\ne0} R_P ⋁ P : c ∧ C P = 0 R P : the result of applying handle_call to c (Appendix A.2).
Sketch. Step 1: the loop sends y k y_k y k to w k w_k w k , and nothing else. In the form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) the callback returns only :reply triples, so the loop, after consuming the k k k -th request, takes the branch {:reply, r, s2} with r = y_k and s2 = s_k, and sends y k y_k y k to w k w_k w k ; this is its only send.
Step 2: no other process sends on w j w_j w j , for a request sent by call(q, x_j). The name w j w_j w j is held by the client, which creates it in call, sends it only to q q q , and only receives on it; by the loop, which takes it from its mailbox (no other code of the server receives, by (A3)) and passes it only to handle_call; and by the body of handle_call, together with the processes to which this body passes it, directly or through further messages. The body is typed with its declared type H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) , so in it from has type pid ( ) \operatorname{pid}() pid ( ) , whatever the loop passes, and every route from the body to w j w_j w j carries it at type pid ( ) \operatorname{pid}() pid ( ) : by (opacity), neither the body nor these processes send on it. If the body sends w j w_j w j back to a server, inside a request, then this request, whose address has type pid ( ) \operatorname{pid}() pid ( ) , is in a region with R P = 0 R_P = 0 R P = 0 , on which handle_call returns no reply, so the loop does not send on it either. Hence the only value sent to w j w_j w j is y j y_j y j , and the call that created w j w_j w j returns y j y_j y j .
Step 3: the type of y j y_j y j . Let x j x_j x j have type c ≤ ⋁ i c i = ⋁ P C P c \le\bigvee_i c_i = \bigvee_P C_P c ≤ ⋁ i c i = ⋁ P C P . Then ( c , pid ( ) , s t a t e ) ≤ ⋁ P D P (c,\operatorname{pid}(),\mathit{state}) \le\bigvee_P D_P ( c , pid ( ) , state ) ≤ ⋁ P D P , and this triple meets D P D_P D P if and only if c c c meets C P C_P C P , since pid ( ) \operatorname{pid}() pid ( ) and s t a t e \mathit{state} state are not empty. By (app), applied to H m pid ( ) = ⋀ P ( D P → { :reply , R P , s t a t e } ) H_m^{\operatorname{pid}()} = \bigwedge_P(D_P \to\{\text{:reply}, R_P, state\}) H m pid ( ) = ⋀ P ( D P → { :reply , R P , s t a t e }) , the result of handle_call has type ⋁ P : c ∧ C P ≠ 0 { :reply , R P , s t a t e } \bigvee_{P:c\wedge C_P\ne0}\{\text{:reply}, R_P, state\} ⋁ P : c ∧ C P = 0 { :reply , R P , s t a t e } , and its second component, y j y_j y j , has the stated type.
The restriction to the calls on q q q is necessary: a process p ′ p' p ′ of type server ( c , r ) \operatorname{server}(c,r) server ( c , r ) may forward the request { x , w } \{x,w\} { x , w } of a client to q q q and also send on w w w a value of its own, so that w w w receives two values.
Theorem 5 (exactness of server_of, Claim 1). Under (A2) and (A3), form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) , for all closed types c , r c,r c , r :
server_of ( m ) ≤ server ( c , r ) ⟺ H m pid ( ) ≤ ( c , pid ( ) , s t a t e ) → { :reply , r , s t a t e } . \operatorname{server\_of}(m) \le\operatorname{server}(c,r) \iff H_m^{\operatorname{pid}()} \le(c,\operatorname{pid}(),state) \to\{\text{:reply},r,state\}. server_of ( m ) ≤ server ( c , r ) ⟺ H m pid ( ) ≤ ( c , pid ( ) , s t a t e ) → { :reply , r , s t a t e } . Hence, for a type T = ⋀ j ∈ J server ( d j , s j ) T = \bigwedge_{j\in J}\operatorname{server}(d_j,s_j) T = ⋀ j ∈ J server ( d j , s j ) written by hand, server_of ( m ) ≤ T \operatorname{server\_of}(m) \le T server_of ( m ) ≤ T if and only if every arrow ( d j , pid ( ) , s t a t e ) → { :reply , s j , s t a t e } (d_j,\operatorname{pid}(),state) \to\{\text{:reply},s_j,state\} ( d j , pid ( ) , s t a t e ) → { :reply , s j , s t a t e } is a supertype of H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) : this is what start_link checks against the API.
Proof. By (7), H m pid ( ) = ⋀ P ( D P → { :reply , R P , s t a t e } ) H_m^{\operatorname{pid}()} = \bigwedge_P(D_P \to\{\text{:reply},R_P,state\}) H m pid ( ) = ⋀ P ( D P → { :reply , R P , s t a t e }) , where P P P ranges over the nonempty regions, of which there is at least one since ⋁ i c i ≠ 0 \bigvee_i c_i\ne0 ⋁ i c i = 0 (A3). By Lemma 1(b), with p = pid ( ) p=\operatorname{pid}() p = pid ( ) and s = s t a t e s=state s = s t a t e , which are not empty (A3), the right-hand side is equivalent to ⋀ P ( C P → R P ) ≤ c → r \bigwedge_P(C_P \to R_P) \le c \to r ⋀ P ( C P → R P ) ≤ c → r , hence, the C P C_P C P being pairwise disjoint, by (i) ⟺ \iff ⟺ (ii) of Claim 1, to ⋀ P server ( C P , R P ) ≤ server ( c , r ) \bigwedge_P\operatorname{server}(C_P,R_P) \le\operatorname{server}(c,r) ⋀ P server ( C P , R P ) ≤ server ( c , r ) , the left-hand side. The second part follows, since a type is below an intersection if and only if it is below each of its components.
Theorem 6 (optimality of server_of, Claim 2). Under (A2) and (A3), form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) , call a set of substitutions for serve valid when handle_call and the initial state, of type s t a t e state s t a t e , are in the domain of every instance. Then:
(a) if ⋀ j ∈ J ( d j → s j ) ≡ ⋀ i ∈ I ( c i → r i ) \bigwedge_{j\in J}(d_j\to s_j)\equiv\bigwedge_{i\in I}(c_i\to r_i) ⋀ j ∈ J ( d j → s j ) ≡ ⋀ i ∈ I ( c i → r i ) then server_of ( m ) ≤ MT ( ⋀ j ∈ J ( d j → s j ) ) \operatorname{server\_of}(m)\le\operatorname{MT}(\bigwedge_{j\in J}(d_j\to s_j)) server_of ( m ) ≤ MT ( ⋀ j ∈ J ( d j → s j )) ;
(b) let serve : ∀ c , r , s . ( ( c , pid ( ) , s ) → { :reply , r , s } , s ) → server ( c , r ) \forall c,r,s.\ ((c,\operatorname{pid}(),s)\to\{\text{:reply},r,s\},s)\to\operatorname{server}(c,r) ∀ c , r , s . (( c , pid ( ) , s ) → { :reply , r , s } , s ) → server ( c , r ) be the function of Appendix A.3, which spawns the loop on a callback and an initial state. Instantiating it with the set of substitutions [ c : = C P , r : = R P , s : = s t a t e ] P : C P ≠ 0 [c:=C_P,r:=R_P,s:=state]_{P:C_P\ne0} [ c := C P , r := R P , s := s t a t e ] P : C P = 0 (Castagna et al. [18 ] ) is valid when the callback is handle_call, and gives server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) ;
(c) if [ c : = c k , r : = r k , s : = S k ] k ∈ K [c:=c_k,r:=r_k,s:=S_k]_{k\in K} [ c := c k , r := r k , s := S k ] k ∈ K is any valid set of substitutions, then server_of ( m ) ≤ ⋀ k ∈ K server ( c k , r k ) \operatorname{server\_of}(m)\le\bigwedge_{k\in K}\operatorname{server}(c_k,r_k) server_of ( m ) ≤ ⋀ k ∈ K server ( c k , r k ) .
Sketch. (a). Claim 2.
(b). The rule of Castagna et al. [18 ] gives a polymorphic function instantiated with a set of substitutions the intersection of its instances, and then applies the rule for intersections of arrows. The instance of P P P is ( D P → { :reply , R P , s t a t e } , s t a t e ) → server ( C P , R P ) (D_P\to\{\text{:reply},R_P,state\},state)\to\operatorname{server}(C_P,R_P) ( D P → { :reply , R P , s t a t e } , s t a t e ) → server ( C P , R P ) . By (7), H m pid ( ) ≤ D P → { :reply , R P , s t a t e } H_m^{\operatorname{pid}()}\le D_P\to\{\text{:reply},R_P,state\} H m pid ( ) ≤ D P → { :reply , R P , s t a t e } for every P P P , and the initial state has type s t a t e state s t a t e : the arguments are in the domain of every instance. Since ⋀ k ( σ k → τ k ) ≤ ( ⋀ k σ k ) → ⋀ k τ k \bigwedge_{k}(\sigma_k\to\tau_k)\le(\bigwedge_k\sigma_k)\to\bigwedge_k\tau_k ⋀ k ( σ k → τ k ) ≤ ( ⋀ k σ k ) → ⋀ k τ k (by contravariance of the domains, then by ( → ∧ ) (\to\wedge) ( → ∧ ) ), the application has type ⋀ P server ( C P , R P ) = server_of ( m ) \bigwedge_P\operatorname{server}(C_P,R_P)=\operatorname{server\_of}(m) ⋀ P server ( C P , R P ) = server_of ( m ) .
(c). The validity of the k k k -th substitution is s t a t e ≤ S k state\le S_k s t a t e ≤ S k and H m pid ( ) ≤ ( c k , pid ( ) , S k ) → { :reply , r k , S k } H_m^{\operatorname{pid}()}\le(c_k,\operatorname{pid}(),S_k)\to\{\text{:reply},r_k,S_k\} H m pid ( ) ≤ ( c k , pid ( ) , S k ) → { :reply , r k , S k } . If c k = 0 c_k=0 c k = 0 , then server ( c k , r k ) = pid ( ) \operatorname{server}(c_k,r_k)=\operatorname{pid}() server ( c k , r k ) = pid ( ) , which is above server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) . Otherwise (9), for Q Q Q the set of all the regions, gives ( c k , pid ( ) , S k ) ≤ ⋁ P D P = ( ⋁ P C P , pid ( ) , s t a t e ) (c_k,\operatorname{pid}(),S_k)\le\bigvee_P D_P=(\bigvee_P C_P,\operatorname{pid}(),state) ( c k , pid ( ) , S k ) ≤ ⋁ P D P = ( ⋁ P C P , pid ( ) , s t a t e ) , hence S k ≤ s t a t e S_k\le state S k ≤ s t a t e , since c k c_k c k and pid ( ) \operatorname{pid}() pid ( ) are not empty. So S k ≅ s t a t e S_k\cong state S k ≅ s t a t e , the validity is the right-hand side of Theorem 5 for c k c_k c k and r k r_k r k , and server_of ( m ) ≤ server ( c k , r k ) \operatorname{server\_of}(m)\le\operatorname{server}(c_k,r_k) server_of ( m ) ≤ server ( c k , r k ) .
Item (b) computes the type, but does not prove it sound (the paragraph “Sets of substitutions and spawning” of Appendix A.9.5). Without the initial state in the definition of validity, (c) would be false: the substitution [ c : = :foo , r : = 0 , s : = 0 ] [c:=\text{:foo},r:=0,s:=0] [ c := :foo , r := 0 , s := 0 ] has the empty domain ( :foo , pid ( ) , 0 ) (\text{:foo},\operatorname{pid}(),0) ( :foo , pid ( ) , 0 ) , so handle_call is in it, but server ( :foo , 0 ) \operatorname{server}(\text{:foo},0) server ( :foo , 0 ) is not above server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) when :foo is not a request of handle_call.
Sets of substitutions and spawning. Instantiating with a set of substitutions a function that spawns a process is unsound in general: the process has one mailbox for all the instances. For example, the function that spawns a process of interface α \alpha α that receives two messages and sends their pair to its argument p p p has type ∀ α . pid ( α × α ) → pid ( α ) \forall\alpha.\ \operatorname{pid}(\alpha\times\alpha) \to\operatorname{pid}(\alpha) ∀ α . pid ( α × α ) → pid ( α ) , but with one instance for each spawn, not the intersection of several. Instantiated at both int and bool, and applied to p : pid ( ( int × int ) ∨ ( bool × bool ) ) p : \operatorname{pid}((\operatorname{int} \times\operatorname{int}) \lor(\operatorname{bool} \times\operatorname{bool})) p : pid (( int × int ) ∨ ( bool × bool )) , which is below both pid ( int × int ) \operatorname{pid}(\operatorname{int} \times\operatorname{int}) pid ( int × int ) and pid ( bool × bool ) \operatorname{pid}(\operatorname{bool} \times\operatorname{bool}) pid ( bool × bool ) by (1), it would give a process of type pid ( int ) ∧ pid ( bool ) = pid ( int ∨ bool ) \operatorname{pid}(\operatorname{int}) \land\operatorname{pid}(\operatorname{bool}) = \operatorname{pid}(\operatorname{int} \lor\operatorname{bool}) pid ( int ) ∧ pid ( bool ) = pid ( int ∨ bool ) , which may receive 1 and true and send to p p p the pair { 1 , true } \{1,\operatorname{true}\} { 1 , true } , which p p p does not accept. For serve the type is sound, because the substitutions agree on s s s and the loop handles each request independently, given the state: this is what the proof of Theorem 2 shows, by typing the loop directly. With two types for s s s , the state produced by a request of one instance could reach a clause of the other.
Proposition 7 (module parameters). Let
start_link : ∀ a , c , r . ( GenServer [ init_arg : a , call_msg : c , reply : r ] , a ) → { : ok , server ( c , r ) } \operatorname{start\_link} : \forall a,c,r.\;(\operatorname{GenServer}[\operatorname{init\_arg}:a,\operatorname{call\_msg}:c,\operatorname{reply}:r],a)\to\{\mathord{:}\operatorname{ok},\operatorname{server}(c,r)\} start_link : ∀ a , c , r . ( GenServer [ init_arg : a , call_msg : c , reply : r ] , a ) → { : ok , server ( c , r )} with invariant parameters. A module m m m whose declared parameters are ⋁ i c i \bigvee_i c_i ⋁ i c i and ⋁ i r i \bigvee_i r_i ⋁ i r i is accepted only at c ≃ ⋁ i c i c \simeq\bigvee_i c_i c ≃ ⋁ i c i and r ≃ ⋁ i r i r \simeq\bigvee_i r_i r ≃ ⋁ i r i , so the result is server ( ⋁ i c i , ⋁ i r i ) \operatorname{server}(\bigvee_i c_i,\bigvee_i r_i) server ( ⋁ i c i , ⋁ i r i ) . In the form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) , server_of ( m ) ≤ server ( ⋁ i c i ; ⋁ i r i ) \operatorname{server\_of}(m) \le\operatorname{server}(\bigvee_i c_i;\bigvee_i r_i) server_of ( m ) ≤ server ( ⋁ i c i ; ⋁ i r i ) , and the inequality is strict for the first version of MyServer .
Proof. Step 1: eq(t) ≤ \le ≤ eq(t ′ t' t ′ ) if and only if t ≃ t ′ t \simeq t' t ≃ t ′ . In the encoding of Boussaa et al. [5 ] , the type of a module records each parameter instantiated at t t t as eq ( t ) = ( t ∨ { ℧ } ) × ( ¬ t ∨ { ℧ } ) \operatorname{eq}(t)=(t\lor\{\mho\})\times(\lnot t\lor\{\mho\}) eq ( t ) = ( t ∨ { ℧ }) × ( ¬ t ∨ { ℧ }) , where ℧ \mho ℧ is a distinguished constant that, like the element Ω \Omega Ω of Frisch et al. [39 ] , does not belong to the domain of values: no type of the language contains it, not even term ( ) \operatorname{term}() term ( ) . The “if” part is immediate. For the “only if” part, both products contain the pair ( ℧ , ℧ ) (\mho,\mho) ( ℧ , ℧ ) , so they are nonempty, and (8) reduces the inequality to its components: t ∨ { ℧ } ≤ t ′ ∨ { ℧ } t\lor\{\mho\}\le t'\lor\{\mho\} t ∨ { ℧ } ≤ t ′ ∨ { ℧ } and ¬ t ∨ { ℧ } ≤ ¬ t ′ ∨ { ℧ } \lnot t\lor\{\mho\}\le\lnot t'\lor\{\mho\} ¬ t ∨ { ℧ } ≤ ¬ t ′ ∨ { ℧ } , that is, t ∖ t ′ ≤ { ℧ } t\setminus t'\le\{\mho\} t ∖ t ′ ≤ { ℧ } and t ′ ∖ t ≤ { ℧ } t'\setminus t\le\{\mho\} t ′ ∖ t ≤ { ℧ } (since ¬ t ∖ ¬ t ′ = t ′ ∖ t \lnot t\setminus\lnot t'=t'\setminus t ¬ t ∖ ¬ t ′ = t ′ ∖ t ). Since ℧ \mho ℧ belongs to no type of the language, t ∖ t ′ = 0 t\setminus t'=0 t ∖ t ′ = 0 and t ′ ∖ t = 0 t'\setminus t=0 t ′ ∖ t = 0 .
Step 2: the instance. The module m m m has the type of the first argument only if eq ( ⋁ i c i ) ≤ eq ( c ) \operatorname{eq}(\bigvee_i c_i)\le\operatorname{eq}(c) eq ( ⋁ i c i ) ≤ eq ( c ) and eq ( ⋁ i r i ) ≤ eq ( r ) \operatorname{eq}(\bigvee_i r_i)\le\operatorname{eq}(r) eq ( ⋁ i r i ) ≤ eq ( r ) , that is, by Step 1, c ≃ ⋁ i c i c\simeq\bigvee_i c_i c ≃ ⋁ i c i and r ≃ ⋁ i r i r\simeq\bigvee_i r_i r ≃ ⋁ i r i .
Step 3: the inequality. By covariance of the codomains and the law ( ∨ → ) (\lor\to) ( ∨ → ) ,
H m pid ( ) ≤ ⋀ i ( ( c i , pid ( ) , state ) → { : reply , ⋁ j r j , state } ) = ( ⋁ i c i , pid ( ) , state ) → { : reply , ⋁ j r j , state } H_m^{\operatorname{pid}()} \le\bigwedge_i ((c_i,\operatorname{pid}(),\operatorname{state})\to\{\mathord{:}\operatorname{reply},\bigvee_j r_j,\operatorname{state}\})
= (\bigvee_i c_i,\operatorname{pid}(),\operatorname{state})\to\{\mathord{:}\operatorname{reply},\bigvee_j r_j,\operatorname{state}\} H m pid ( ) ≤ i ⋀ (( c i , pid ( ) , state ) → { : reply , j ⋁ r j , state }) = ( i ⋁ c i , pid ( ) , state ) → { : reply , j ⋁ r j , state }
so that server_of ( m ) ≤ server ( ⋁ i c i ; ⋁ i r i ) \operatorname{server\_of}(m)\le\operatorname{server}(\bigvee_i c_i;\bigvee_i r_i) server_of ( m ) ≤ server ( ⋁ i c i ; ⋁ i r i ) by Theorem 5.
Step 4: strictness. For the first version of MyServer , server_of ( m ) ≤ server ( : get_int , int ) \operatorname{server\_of}(m)\le\operatorname{server}(\mathord{:}\operatorname{get\_int},\operatorname{int}) server_of ( m ) ≤ server ( : get_int , int ) by Claim 1, since : get_int \mathord{:}\operatorname{get\_int} : get_int meets only the region C 1 = : get_int C_1=\mathord{:}\operatorname{get\_int} C 1 = : get_int , whose reply is R 1 = int R_1=\operatorname{int} R 1 = int . Instead, server ( : get_int ∨ { : set_int , int } , int ∨ : ok ) \operatorname{server}(\mathord{:}\operatorname{get\_int}\lor\{\mathord{:}\operatorname{set\_int},\operatorname{int}\},\operatorname{int}\lor\mathord{:}\operatorname{ok}) server ( : get_int ∨ { : set_int , int } , int ∨ : ok ) is not below server ( : get_int , int ) \operatorname{server}(\mathord{:}\operatorname{get\_int},\operatorname{int}) server ( : get_int , int ) , by Lemma 2, since int ∨ : ok ≰ int \operatorname{int}\lor\mathord{:}\operatorname{ok}\not\le\operatorname{int} int ∨ : ok ≤ int and : get_int ≠ ∅ \mathord{:}\operatorname{get\_int}\ne\varnothing : get_int = ∅ . This is the type with the union of the requests and the union of the replies of Appendix A.1. □
The form H m r H_m^r H m r . Let T m = ⋀ i ∈ I server ( c i , r i ) T_m=\bigwedge_{i\in I}\operatorname{server}(c_i,r_i) T m = ⋀ i ∈ I server ( c i , r i ) .
Proposition 8 (form H m r H_m^r H m r ). Under (A3), in the form H m r H_m^r H m r :
(a) ⊢ start_link ( m , v ) : { : ok , T m } \vdash\operatorname{start\_link}(m,v):\{\mathord{:}\operatorname{ok},T_m\} ⊢ start_link ( m , v ) : { : ok , T m } for v : a v:a v : a ;
(b) Corollary 3 holds.
Sketch. (a). As for Theorem 2, with M = ⋁ i ( c i × pid ( r i ) ) M=\bigvee_i(c_i\times\operatorname{pid}(r_i)) M = ⋁ i ( c i × pid ( r i )) , so that pid ( M ) = T m \operatorname{pid}(M)=T_m pid ( M ) = T m by (2), and with the following changes. By (receive), the branch is typed once for each i i i , with c : c i c:c_i c : c i and w : pid ( r i ) w:\operatorname{pid}(r_i) w : pid ( r i ) . Then ( c , w , s ) (c,w,s) ( c , w , s ) is in the domain of the i i i -th arrow of H m r H_m^r H m r , so, by (app), h ( c , w , s ) : \operatorname{h}(c,w,s): h ( c , w , s ) : { :reply , r i , s t a t e } ∨ { :noreply , s t a t e } \{\texttt{:reply}, r_i, state\} \mathbin{\vee} \{\texttt{:noreply}, state\} { :reply , r i , s t a t e } ∨ { :noreply , s t a t e } . Both branches of the case are typed: { :reply , r , s 2 } \{\texttt{:reply}, r, s_2\} { :reply , r , s 2 } binds r : r i r : r_i r : r i and s 2 : s t a t e s_2 : state s 2 : s t a t e , and send(w, r) is well typed since w : p i d ( r i ) w : pid(r_i) w : p i d ( r i ) ; { :noreply , s 2 } \{\texttt{:noreply}, s_2\} { :noreply , s 2 } binds s 2 : s t a t e s_2 : state s 2 : s t a t e .
(b). As for Corollary 3, with this M M M : a message of type M M M is in one summand c i × p i d ( r i ) c_i \times pid(r_i) c i × p i d ( r i ) , so the arguments of handle_call are in the domain of its i i i -th arrow, and both branches of the case give s 2 : s t a t e s_2 : state s 2 : s t a t e .
When the c i c_i c i are pairwise disjoint, the nonempty regions are the nonempty c i c_i c i and T m = s e r v e r _ o f ( m ) T_m = server\_of(m) T m = ser v er _ o f ( m ) (the other components of T m T_m T m are s e r v e r ( 0 , r i ) = p i d ( ) server(0, r_i) = pid() ser v er ( 0 , r i ) = p i d ( ) ); otherwise Claim 3 shows where T m T_m T m is coarser than s e r v e r _ o f ( m ) server\_of(m) ser v er _ o f ( m ) , and Appendix A.4 how the programmer recovers the lost regions. In (b), that a message lies in one summand is the justification of (receive); projections would not suffice, since ( π 1 M , π 2 M , s t a t e ) (\pi_1 M, \pi_2 M, state) ( π 1 M , π 2 M , s t a t e ) contains triples that are in no domain ( c i , p i d ( r i ) , s t a t e ) (c_i, pid(r_i), state) ( c i , p i d ( r i ) , s t a t e ) . Theorem 4 holds only in part: a call may never return, since a clause may return { :noreply , s t a t e } \{\texttt{:noreply}, state\} { :noreply , s t a t e } and never reply, and it may return a value sent through from instead of y k y_k y k , since a clause may reply through from and also return { :reply , y k , s k } \{\texttt{:reply}, y_k, s_k\} { :reply , y k , s k } . What remains is Corollary 3(ii): if w k w_k w k was created by a call (on q q q , or on a process that forwards the request to q q q ), every value sent to w k w_k w k has the type r r r of that call; in general, it has the type of creation of w k w_k w k , by (names).
The model with the messages of OTP. The code of fig:1 differs from the model of Appendix A.6 in the messages and in the results of init, and loop receives the module instead of the function handle_call. The tag plays the role of the return address, so that the proofs of Theorems 1 and 2 carry over. Let r e p l y _ t a g ( r ) = p i d ( 1 × r ) reply\_tag(r) = pid(1 \times r) r e pl y _ t a g ( r ) = p i d ( 1 × r ) , f r o m ( r ) = { p i d ( ) , r e p l y _ t a g ( r ) } from(r) = \{pid(), reply\_tag(r)\} f r o m ( r ) = { p i d ( ) , r e pl y _ t a g ( r )} and s e r v e r ( c , r ) = p i d ( { :"$gen_call" , f r o m ( r ) , c } ) server(c, r) = pid(\{\texttt{:"\$gen\_call"}, from(r), c\}) ser v er ( c , r ) = p i d ({ :"$gen_call" , f r o m ( r ) , c }) .
Lemma 3 (laws of reply_tag and from). The laws (1)–(3) hold with reply_tag, and with from, in place of pid. In particular, f r o m ( r ) ≤ f r o m ( ) from(r) \le from() f r o m ( r ) ≤ f r o m ( ) and f r o m ( ) ≠ 0 from() \ne0 f r o m ( ) = 0 .
Proof. By Lemma 1(a), 1 × s ≤ 1 × t 1 \times s \le1 \times t 1 × s ≤ 1 × t if and only if s ≤ t s \le t s ≤ t . Hence, by (1), r e p l y _ t a g ( t ) ≤ r e p l y _ t a g ( s ) reply\_tag(t) \le reply\_tag(s) r e pl y _ t a g ( t ) ≤ r e pl y _ t a g ( s ) if and only if s ≤ t s \le t s ≤ t ; by (2), and since products distribute over unions, r e p l y _ t a g ( t 1 ) ∧ r e p l y _ t a g ( t 2 ) = p i d ( ( 1 × t 1 ) ∨ ( 1 × t 2 ) ) = r e p l y _ t a g ( t 1 ∨ t 2 ) reply\_tag(t_1) \wedge reply\_tag(t_2) = pid((1 \times t_1) \vee(1 \times t_2)) = reply\_tag(t_1 \vee t_2) r e pl y _ t a g ( t 1 ) ∧ r e pl y _ t a g ( t 2 ) = p i d (( 1 × t 1 ) ∨ ( 1 × t 2 )) = r e pl y _ t a g ( t 1 ∨ t 2 ) ; and by (3), r e p l y _ t a g ( t ) ≤ ⋁ n ∈ N r e p l y _ t a g ( s n ) reply\_tag(t) \le\bigvee_{n \in N} reply\_tag(s_n) r e pl y _ t a g ( t ) ≤ ⋁ n ∈ N r e pl y _ t a g ( s n ) if and only if 1 × s n ≤ 1 × t 1 \times s_n \le1 \times t 1 × s n ≤ 1 × t , that is, s n ≤ t s_n \le t s n ≤ t , for some n ∈ N n \in N n ∈ N . For from: products distribute over intersections and unions, and, by Lemma 1(a) with u = p i d ( ) u = pid() u = p i d ( ) , f r o m ( t ) ≤ ⋁ n ∈ N f r o m ( s n ) from(t) \le\bigvee_{n \in N} from(s_n) f r o m ( t ) ≤ ⋁ n ∈ N f r o m ( s n ) if and only if r e p l y _ t a g ( t ) ≤ ⋁ n ∈ N r e p l y _ t a g ( s n ) reply\_tag(t) \le\bigvee_{n \in N} reply\_tag(s_n) r e pl y _ t a g ( t ) ≤ ⋁ n ∈ N r e pl y _ t a g ( s n ) .
Outside GenServer the checker knows of reply_tag(r) only these laws, so a program that type-checks with the abstract type also type-checks with this definition, which the next proposition uses.
Proposition 9 (the code with the messages of OTP). Let (A3) hold with f r o m ( ) from() f r o m ( ) and f r o m ( r i ) from(r_i) f r o m ( r i ) in place of p i d ( ) pid() p i d ( ) and p i d ( r i ) pid(r_i) p i d ( r i ) in the arrows of handle_call, and with init : (a) \to \{\texttt{:ok}, state\} \vee \texttt{:ignore} \vee \{\texttt{:stop}, 1\}$. Then the bodies of call, replyandstart_linkin Figure 1 are well typed under their signatures, where $server\_of(m)$ is $server\_of(m)$ in the form $H_m^{pid()}$ and $T_m$ in the form $H_m^r$, and the second part of Theorem 1 holds for thiscall`.
Sketch. call. Let p : s e r v e r ( c , r ) p : server(c, r) p : ser v er ( c , r ) and c : c c : c c : c . By (alias) at the type 1 × r 1 \times r 1 × r , tag = alias() creates a name of type r e p l y _ t a g ( r ) reply\_tag(r) r e pl y _ t a g ( r ) , and receive_on(tag) : 1 \times r$, so that the match binds $v : r$. The value of self()is the pid of the running process, whose type is below $pid()$ by (1), whatever the type of its mailbox, so that $\{self(), tag\} : from(r)$, and the send is well typed by (send). The second part of Theorem 1 follows as there: by (names), a value sent ontaghas type $1 \times r$, so the second component of the value thatreceive_on(tag)` returns has type r r r .
reply. Let tag : reply_tag(r) and v : r v : r v : r . Then { t a g , v } : 1 × r \{tag, v\} : 1 \times r { t a g , v } : 1 × r , and the send is well typed by (send). start_link and loop. The region form (7) holds as before, since from ( ) ≠ 0 \operatorname{from}() \ne0 from ( ) = 0 . In the form H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) , the proof of Theorem 2 applies with M = ⋁ P ∈ I { : " $ g e n c a l l " , from ( R P ) , C P } M = \bigvee_{P \in I}\{:"\$gen_call",\operatorname{from}(R_P),C_P\} M = ⋁ P ∈ I { : "$ g e n c a l l " , from ( R P ) , C P } , the type messages_of(m), so that pid ( M ) = server_of ( m ) \operatorname{pid}(M) = \operatorname{server\_of}(m) pid ( M ) = server_of ( m ) by (2). By (spawn), the body of the spawn is typed in a process whose mailbox has type M M M , as the $interface declares; there loop is applied to the module m m m of start_link, so that m.handle_call has the type H m pid ( ) H_m^{\operatorname{pid}()} H m pid ( ) and s : s t a t e s : state s : s t a t e . By (receive), the branch is typed once for each P P P , with the variables of the pattern, the nested ones included, at the components of the summand: from : from ( R P ) \operatorname{from}(R_P) from ( R P ) , tag : reply_tag ( R P ) \operatorname{reply\_tag}(R_P) reply_tag ( R P ) and c : C P C_P C P . Since from ( R P ) ≤ from ( ) \operatorname{from}(R_P) \le\operatorname{from}() from ( R P ) ≤ from ( ) , the arguments of m.handle_call are in the domain of the arrow of the region, so that, by (app), m.handle_call(c,from,s) : { : reply , R P , s t a t e } \{:\operatorname{reply},R_P,state\} { : reply , R P , s t a t e } , and send(tag, {tag, v}) is well typed by (send), with v : R P v : R_P v : R P . The other two branches of the case of start_link return :ignore and { : error , r e a s o n } \{:\operatorname{error}, reason\} { : error , r e a so n } , with r e a s o n : 1 reason : 1 r e a so n : 1 , by the type of init, and both are in the declared result. The form H m r H_m^r H m r is treated in the same way, with M = ⋁ i ∈ I { : " $ g e n c a l l " , from ( r i ) , c i } M = \bigvee_{i \in I}\{:"\$gen_call",\operatorname{from}(r_i),c_i\} M = ⋁ i ∈ I { : "$ g e n c a l l " , from ( r i ) , c i } , as in Proposition 8.
Three remarks on this code. In call, the route to the pid of the caller through self() carries it only at the type pid(), so that, as in (opacity), it adds no sender: a body of handle_call may still call other servers, as (A3) says, although call uses self(). In reply, the first component of from cannot take the place of the tag: it has type pid() = pid(0), and no value has type 0 0 0 . The signature of loop has no decorations. Castagna et al. [24 ] its arrow would have those that say that it sends nothing to the mailbox of its process and that it reads messages of type M M M . The body alone does not determine them (it is typed, for instance, at any mailbox type disjoint from its pattern) and (receive) needs the summands of M M M , so they come from the $interface of the spawn. The loop sends directly, as in the model, and does not call the polymorphic reply: by (inst), that occurrence would have one instance r 0 r_0 r 0 for all the summands of (receive), which would require r 0 ≤ R P r_0 \le R_P r 0 ≤ R P (for from ( R P ) ≤ from ( r 0 ) \operatorname{from}(R_P) \le\operatorname{from}(r_0) from ( R P ) ≤ from ( r 0 ) ) and R P ≤ r 0 R_P \le r_0 R P ≤ r 0 (for v : R P v : R_P v : R P ) for every P P P , hence one reply type for all the regions.
Finally, casts, which the code leaves out. The type server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) alone is below pid ( { : " $ g e n c a s t " , k } ) \operatorname{pid}(\{:"\$gen_cast",k\}) pid ({ : "$ g e n c a s t " , k }) only for k = 0 k = 0 k = 0 , by (1), since the pairs tagged by :"$gen_cast" are disjoint from the triples of M M M : this is why the operator server_of \operatorname{server\_of} server_of must include the type of the casts. Let K = { : " $ g e n c a s t " , k } K = \{:"\$gen_cast",k\} K = { : "$ g e n c a s t " , k } ; then messages_of ( m ) ∨ M ∨ K \operatorname{messages\_of}(m) \vee M \vee K messages_of ( m ) ∨ M ∨ K . On the side of the server, loop needs a branch for these pairs, which applies handle_cast (a function that, like handle_call in (A3), performs no receive) and loops on the new state: (receive) types this branch on the summand K K K , and the branch of the calls on the summands of M M M , since each pattern is disjoint from the summands of the other. On the side of the client, this changes no result: let T = { : " $ g e n c a l l " , from ( r ) , c } T = \{:"\$gen_call",\operatorname{from}(r),c\} T = { : "$ g e n c a l l " , from ( r ) , c } ; by (2) and (1), server_of ( m ) ∧ pid ( K ) ≤ server ( c , r ) \operatorname{server\_of}(m) \wedge\operatorname{pid}(K) \le\operatorname{server}(c,r) server_of ( m ) ∧ pid ( K ) ≤ server ( c , r ) if and only if T ≤ M ∨ K T \le M \vee K T ≤ M ∨ K , and since T T T and K K K are disjoint, if and only if T ≤ M T \le M T ≤ M , that is, if and only if server_of ( m ) ≤ server ( c , r ) \operatorname{server\_of}(m) \le\operatorname{server}(c,r) server_of ( m ) ≤ server ( c , r ) . In the form H m r H_m^r H m r the same holds with T m T_m T m in place of $\operatorname{server_of}(m).
The translation with lambda-channels
Castagna et al. [14 ] encodes the λ \lambda λ -calculus with semantic subtyping (the functional core of CDuce) into the π \pi π -calculus with semantic subtyping. This encoding explains why server_of \operatorname{server\_of} server_of normalizes into regions, and why the extra precision of its λ \lambda λ -channels is out of reach on the BEAM. Section 6 tells the story; here I give the details.
Two translations of arrows. Castagna et al. [14 ] considers two translations of function types into channel types. Both commute with ∨ \vee ∨ , ∧ \wedge ∧ , ¬ \neg ¬ and × \times × , and translate the types under the arrows as well; here I apply them only to the arrows of the type of handle_call, and leave the request and reply types c c c , r r r unchanged. They differ on arrows:
MT ( c → r ) = pid ( c × pid ( r ) ) = server ( c , r ) LC ( c → r ) = pid ( c × ch λ ( r ) ) \operatorname{MT}(c \to r) = \operatorname{pid}(c \times\operatorname{pid}(r)) = \operatorname{server}(c,r)
\qquad
\operatorname{LC}(c \to r) = \operatorname{pid}(c \times\operatorname{ch}^{\lambda}(r)) MT ( c → r ) = pid ( c × pid ( r )) = server ( c , r ) LC ( c → r ) = pid ( c × ch λ ( r ))
MT is the Milner–Turner translation ([14 §4.1] ): the request travels with a return channel on which the reply can be written. The λ \lambda λ -channel translation LC ([14 §5.1–5.2] ) gives the return channel the type of a λ \lambda λ -channel ch λ ( t ) = ( ¬ pid ( ¬ t ) ∨ pid ( 1 ) ) ∧ pid ( 0 ) \operatorname{ch}^{\lambda}(t) = (\neg\operatorname{pid}(\neg t) \lor\operatorname{pid}(1)) \land\operatorname{pid}(0) ch λ ( t ) = ( ¬ pid ( ¬ t ) ∨ pid ( 1 )) ∧ pid ( 0 ) : it contains pid ( t ) \operatorname{pid}(t) pid ( t ) , plus “noise”, the channels that accept neither all of t t t nor all of ¬ t \neg t ¬ t ([14 §5.2] , property (c)). The property that matters is
ch λ ( t 1 ∧ t 2 ) = ch λ ( t 1 ) ∨ ch λ ( t 2 ) whereas pid ( t 1 ) ∨ pid ( t 2 ) ≤ pid ( t 1 ∧ t 2 ) (12) \operatorname{ch}^{\lambda}(t_1 \land t_2) = \operatorname{ch}^{\lambda}(t_1) \lor\operatorname{ch}^{\lambda}(t_2)
\qquad\text{whereas}\qquad
\operatorname{pid}(t_1) \lor\operatorname{pid}(t_2) \le\operatorname{pid}(t_1 \land t_2) \tag*{(12)} ch λ ( t 1 ∧ t 2 ) = ch λ ( t 1 ) ∨ ch λ ( t 2 ) whereas pid ( t 1 ) ∨ pid ( t 2 ) ≤ pid ( t 1 ∧ t 2 ) (12)
The equation is the condition that defines λ \lambda λ -channels in Castagna et al. (2006, §5.1), and it follows from (2) and De Morgan’s laws: ¬ pid ( ¬ ( t 1 ∧ t 2 ) ) = ¬ pid ( ¬ t 1 ∨ ¬ t 2 ) = ¬ ( pid ( ¬ t 1 ) ∧ pid ( ¬ t 2 ) ) = ¬ pid ( ¬ t 1 ) ∨ ¬ pid ( ¬ t 2 ) \neg\operatorname{pid}(\neg(t_1 \land t_2)) = \neg\operatorname{pid}(\neg t_1 \lor\neg t_2) = \neg(\operatorname{pid}(\neg t_1) \land\operatorname{pid}(\neg t_2)) = \neg\operatorname{pid}(\neg t_1) \lor\neg\operatorname{pid}(\neg t_2) ¬ pid ( ¬ ( t 1 ∧ t 2 )) = ¬ pid ( ¬ t 1 ∨ ¬ t 2 ) = ¬ ( pid ( ¬ t 1 ) ∧ pid ( ¬ t 2 )) = ¬ pid ( ¬ t 1 ) ∨ ¬ pid ( ¬ t 2 ) ; then ∨ pid ( 1 ) \lor\operatorname{pid}(1) ∨ pid ( 1 ) and ∧ pid ( 0 ) \land\operatorname{pid}(0) ∧ pid ( 0 ) distribute over the union. The inequality holds by contravariance (1), and it is strict exactly when t 1 t_1 t 1 and t 2 t_2 t 2 are incomparable: by the union law, pid ( t 1 ∧ t 2 ) ≤ pid ( t 1 ) ∨ pid ( t 2 ) \operatorname{pid}(t_1 \land t_2) \le\operatorname{pid}(t_1) \lor\operatorname{pid}(t_2) pid ( t 1 ∧ t 2 ) ≤ pid ( t 1 ) ∨ pid ( t 2 ) holds if and only if t 1 ≤ t 1 ∧ t 2 t_1 \le t_1 \land t_2 t 1 ≤ t 1 ∧ t 2 or t 2 ≤ t 1 ∧ t 2 t_2 \le t_1 \land t_2 t 2 ≤ t 1 ∧ t 2 , that is, t 1 ≤ t 2 t_1 \le t_2 t 1 ≤ t 2 or t 2 ≤ t 1 t_2 \le t_1 t 2 ≤ t 1 . Applied to the type of h a n d l e _ c a l l \mathtt{handle\_call} handle_call , by (2):
MT ( ⋀ i ( c i → r i ) ) = pid ( ⋁ i ( c i × pid ( r i ) ) ) = ⋀ i server ( c i , r i ) \operatorname{MT}\left(\bigwedge_i(c_i \to r_i)\right) = \operatorname{pid}\left(\bigvee_i(c_i \times\operatorname{pid}(r_i))\right) = \bigwedge_i\operatorname{server}(c_i,r_i) MT ( i ⋀ ( c i → r i ) ) = pid ( i ⋁ ( c i × pid ( r i )) ) = i ⋀ server ( c i , r i )
LC ( ⋀ i ( c i → r i ) ) = pid ( ⋁ i ( c i × ch λ ( r i ) ) ) \operatorname{LC}\left(\bigwedge_i(c_i \to r_i)\right) = \operatorname{pid}\left(\bigvee_i(c_i \times\operatorname{ch}^{\lambda}(r_i))\right) LC ( i ⋀ ( c i → r i ) ) = pid ( i ⋁ ( c i × ch λ ( r i )) )
LC needs no regions; MT does. Since c i = ⋁ P ∋ i C P c_i = \bigvee_{P \ni i} C_P c i = ⋁ P ∋ i C P , distributing × \times × over ∨ \lor ∨ gives, for any types X i X_i X i ,
⋁ i ∈ I ( c i × X i ) = ⋁ P ( C P × ⋁ i ∈ P X i ) . \bigvee_{i \in I}(c_i \times X_i) = \bigvee_P\left(C_P \times\bigvee_{i \in P}X_i\right). i ∈ I ⋁ ( c i × X i ) = P ⋁ ( C P × i ∈ P ⋁ X i ) .
With X i = ch λ ( r i ) X_i = \operatorname{ch}^{\lambda}(r_i) X i = ch λ ( r i ) , (10) turns the inner union into ch λ ( R P ) \operatorname{ch}^{\lambda}(R_P) ch λ ( R P ) , so that
LC ( ⋀ i ( c i → r i ) ) = LC ( ⋀ P ( C P → R P ) ) \operatorname{LC}\left(\bigwedge_i(c_i \to r_i)\right) = \operatorname{LC}\left(\bigwedge_P(C_P \to R_P)\right) LC ( i ⋀ ( c i → r i ) ) = LC ( P ⋀ ( C P → R P ) )
consistently with the fact that the full LC translation respects type equality ([14 §5.1] ). With X i = pid ( r i ) X_i = \operatorname{pid}(r_i) X i = pid ( r i ) , the inner union is only below pid ( R P ) \operatorname{pid}(R_P) pid ( R P ) (by contravariance, since R P ≤ r i R_P \le r_i R P ≤ r i ), so that MT maps the two equivalent function types ⋀ i ( c i → r i ) \bigwedge_i(c_i \to r_i) ⋀ i ( c i → r i ) and ⋀ P ( C P → R P ) \bigwedge_P(C_P \to R_P) ⋀ P ( C P → R P ) to ⋀ i server ( c i , r i ) \bigwedge_i\operatorname{server}(c_i,r_i) ⋀ i server ( c i , r i ) and to server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) , which Claim 3 compares. The normalization into regions is therefore required by MT, not by LC.
The rewriting of § 6 , which computes the regions, appears in Castagna et al. (2006, §3), in the discussion of the rule (abstr), whose premise requires the domains of the interface of a λ \lambda λ -abstraction to be pairwise disjoint. It serves the encoding of terms, not of types: the body of an encoded function is a choice with one branch per arrow, each the input of a pair ( x : σ i , w : pid ( τ i ) ) (x : \sigma_i, w : \operatorname{pid}(\tau_i)) ( x : σ i , w : pid ( τ i )) ; if σ h ∧ σ k ≠ 0 \sigma_h \land\sigma_k \ne0 σ h ∧ σ k = 0 , an argument in σ h ∧ σ k \sigma_h \land\sigma_k σ h ∧ σ k would select branch h h h or k k k according to the type of the return channel w w w .
Why not use LC then? ch λ ( r ) \operatorname{ch}^{\lambda}(r) ch λ ( r ) is a type of our system, since it uses only Boolean connectives over pid types, and LC is more precise than server_of \operatorname{server\_of} server_of ; but where it is more precise, a server typed with it cannot reply.
Lemma 4 (λ \lambda λ -channels). For all types t t t and s s s :
(a) pid ( t ) ≤ ch λ ( t ) \operatorname{pid}(t) \le\operatorname{ch}^{\lambda}(t) pid ( t ) ≤ ch λ ( t ) , and ch λ ( t ) ≤ pid ( t ) \operatorname{ch}^{\lambda}(t) \le\operatorname{pid}(t) ch λ ( t ) ≤ pid ( t ) if and only if t = 0 t = 0 t = 0 or t = 1 t = 1 t = 1 ;
(b) if t ≠ 1 t \ne1 t = 1 , then ch λ ( t ) ≤ pid ( s ) \operatorname{ch}^{\lambda}(t) \le\operatorname{pid}(s) ch λ ( t ) ≤ pid ( s ) if and only if s = 0 s = 0 s = 0 .
Proof. (a). pid ( t ) ≤ pid ( 0 ) \operatorname{pid}(t) \le\operatorname{pid}(0) pid ( t ) ≤ pid ( 0 ) by (1), and pid ( t ) ≤ ¬ pid ( ¬ t ) ∨ pid ( 1 ) \operatorname{pid}(t) \le\neg\operatorname{pid}(\neg t) \lor\operatorname{pid}(1) pid ( t ) ≤ ¬ pid ( ¬ t ) ∨ pid ( 1 ) because pid ( t ) ∧ pid ( ¬ t ) = pid ( t ∨ ¬ t ) = pid ( 1 ) \operatorname{pid}(t) \land\operatorname{pid}(\neg t) = \operatorname{pid}(t \lor\neg t) = \operatorname{pid}(1) pid ( t ) ∧ pid ( ¬ t ) = pid ( t ∨ ¬ t ) = pid ( 1 ) , by (2). For the equivalence, ch λ ( 0 ) = pid ( 0 ) \operatorname{ch}^{\lambda}(0) = \operatorname{pid}(0) ch λ ( 0 ) = pid ( 0 ) , and ch λ ( 1 ) = pid ( 1 ) \operatorname{ch}^{\lambda}(1) = \operatorname{pid}(1) ch λ ( 1 ) = pid ( 1 ) since ¬ pid ( 0 ) ∧ pid ( 0 ) = 0 \neg\operatorname{pid}(0) \land\operatorname{pid}(0) = 0 ¬ pid ( 0 ) ∧ pid ( 0 ) = 0 and pid ( 1 ) ≤ pid ( 0 ) \operatorname{pid}(1) \le\operatorname{pid}(0) pid ( 1 ) ≤ pid ( 0 ) . Conversely, ¬ pid ( ¬ t ) ∧ pid ( 0 ) ≤ ch λ ( t ) \neg\operatorname{pid}(\neg t) \land\operatorname{pid}(0) \le\operatorname{ch}^{\lambda}(t) ¬ pid ( ¬ t ) ∧ pid ( 0 ) ≤ ch λ ( t ) , so ch λ ( t ) ≤ pid ( t ) \operatorname{ch}^{\lambda}(t) \le\operatorname{pid}(t) ch λ ( t ) ≤ pid ( t ) gives pid ( 0 ) ≤ pid ( t ) ∨ pid ( ¬ t ) \operatorname{pid}(0) \le\operatorname{pid}(t) \lor\operatorname{pid}(\neg t) pid ( 0 ) ≤ pid ( t ) ∨ pid ( ¬ t ) , hence t = 0 t = 0 t = 0 or t = 1 t = 1 t = 1 by the union law (3).
(b). ch λ ( t ) ≤ pid ( 0 ) \operatorname{ch}^{\lambda}(t) \le\operatorname{pid}(0) ch λ ( t ) ≤ pid ( 0 ) by definition. Conversely, the pid that accepts no message is in ch λ ( t ) \operatorname{ch}^{\lambda}(t) ch λ ( t ) : it is in pid ( 0 ) \operatorname{pid}(0) pid ( 0 ) , and it is in ¬ pid ( ¬ t ) \neg\operatorname{pid}(\neg t) ¬ pid ( ¬ t ) , since it would be in pid ( ¬ t ) \operatorname{pid}(\neg t) pid ( ¬ t ) only if ¬ t ≤ 0 \neg t \le0 ¬ t ≤ 0 , that is, t = 1 t = 1 t = 1 . And it is in pid ( s ) \operatorname{pid}(s) pid ( s ) only for s = 0 s = 0 s = 0 . ▫大小规律
By contravariance (2) and Lemma 4(a),
LC ( ⋀ i ( c i → r i ) ) = pid ( ⋁ P ( C P × ch λ ( R P ) ) ) ≤ pid ( ⋁ P ( C P × pid ( R P ) ) ) = server_of ( m ) \operatorname{LC}\left(\bigwedge_i(c_i \to r_i)\right) = \operatorname{pid}\left(\bigvee_P(C_P \times\operatorname{ch}^{\lambda}(R_P))\right)
\le\operatorname{pid}\left(\bigvee_P(C_P \times\operatorname{pid}(R_P))\right) = \operatorname{server\_of}(m) LC ( i ⋀ ( c i → r i ) ) = pid ( P ⋁ ( C P × ch λ ( R P )) ) ≤ pid ( P ⋁ ( C P × pid ( R P )) ) = server_of ( m )
and, since the regions are pairwise disjoint, by (9) the converse inequality holds if and only if ch λ ( R P ) ≤ pid ( R P ) \operatorname{ch}^{\lambda}(R_P) \le\operatorname{pid}(R_P) ch λ ( R P ) ≤ pid ( R P ) for every nonempty region: the inequality is strict exactly when some R P R_P R P with C P ≠ 0 C_P \ne0 C P = 0 is neither 0 0 0 nor 1 1 1 . But on such a region a server of this type cannot reply: by Lemma 4(b), to reply on a return channel w : ch λ ( r ) w : \operatorname{ch}^{\lambda}(r) w : ch λ ( r ) , a server must first check that w : pid ( r ) w : \operatorname{pid}(r) w : pid ( r ) , and § 6 explains why this check cannot be programmed on the BEAM. So the gen_server loop, which sends every reply that handle_call returns, can be typed by LC \operatorname{LC} LC only when LC \operatorname{LC} LC adds nothing to server_of \operatorname{server\_of} server_of .
The BEAM does not make MT faithful. § 6 explains why the absence of type tests on pids does not make MT respect type equality: the gap between ⋀ i server ( c i , r i ) \bigwedge_i \operatorname{server}(c_i,r_i) ⋀ i server ( c i , r i ) and server_of ( m ) \operatorname{server\_of}(m) server_of ( m ) comes from the union law, and closing it would require the law pid ( t 1 ∧ t 2 ) ≤ pid ( t 1 ) ∨ pid ( t 2 ) \operatorname{pid}(t_1 \wedge t_2) \le\operatorname{pid}(t_1) \vee\operatorname{pid}(t_2) pid ( t 1 ∧ t 2 ) ≤ pid ( t 1 ) ∨ pid ( t 2 ) , which is false for pids. This law would also identify too many types: it gives pid ( 0 ) ≤ pid ( int × pid ( bool ) ) ∨ pid ( bool × pid ( int ) ) \operatorname{pid}(0) \le\operatorname{pid}(\operatorname{int} \times\operatorname{pid}(\operatorname{bool})) \vee\operatorname{pid}(\operatorname{bool} \times\operatorname{pid}(\operatorname{int})) pid ( 0 ) ≤ pid ( int × pid ( bool )) ∨ pid ( bool × pid ( int )) ([14 §4.3] ), that is, every pid would be a server of int → bool \operatorname{int} \to\operatorname{bool} int → bool or of bool → int \operatorname{bool} \to\operatorname{int} bool → int . In short, server_of \operatorname{server\_of} server_of is justified by Claims 2 and 1; the absence of type tests on pids only explains why the extra precision of LC \operatorname{LC} LC is out of reach.