betaFeedback

WorksComputer Science

From Strong Normalization to WhatsApp: the Journey of an Axiom

Abstract

Twenty years ago, Mariangiola Dezani-Ciancaglini, Daniele Varacca and I showed that Milner's classic encoding of functions into processes does not respect one of the laws of intersection types, the one stating that (σ→τ)∧(σ→ρ)(σ\toτ)\land(σ\toρ) is a subtype of σ→(τ∧ρ)σ\to(τ\landρ), which Barendregt, Coppo and Dezani-Ciancaglini had stated in 1983 for their filter λλ-model. In this essay I show that this observation is the key to closing what a colleague at Meta calls ``the main typing gap in Erlang''—the language in which the servers of WhatsApp are written: the type of the function that implements a server is not related to the type of the server, so that a client may expect from the server a reply that the server will never send. Actually, closing this gap is just an excuse to follow the journey of the law above, and of some of its relatives, from the study of strong normalization in the λλ-calculus to the type systems of Elixir and Erlang: a journey that shows how much the practical typing of these languages owes to the work of Mario Coppo, Mariangiola Dezani-Ciancaglini and Simona Ronchi Della Rocca, to whom this essay is dedicated for their eightieth birthdays.

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)}

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.

YearAuthorsContributionHere
1978–80Coppo, Dezani-Ciancagliniintersection types, strong normalization§ 2, § 4
1980Coppo, Dezani-Ciancaglini, Venneriprincipal type schemes, expansions§ 2, § 8
1983Barendregt, Coppo, Dezani-Ciancaglinifilter model, (→∧)(\to\wedge)§ 2–§ 7
1984, 1988Ronchi Della Rocca (and Venneri)principal types for the filter theory, unification§ 2, § 8
1992Milnerfunctions as processes§ 5, § 6
1995Barbanera, Dezani-Ciancaglini, de’Liguorounion types§ 3, § 7
2002, 2008Frisch, Castagna, Benzakensemantic subtyping§ 3, § 7
2002Dezani-Ciancaglini, Frisch, Giovannetti, Motohamarelevance of semantic subtyping§ 3
2002, 2007Ronchi Della Rocca (and Liquori)explicitly typed intersections§ 8
2006Castagna, Dezani-Ciancaglini, Varaccafunctions as processes: the encoding loses (→∧)(\to\wedge)§ 6, § 7
2008Castagna, De Nicola, Varaccasemantic subtyping for channels, hence types for processes§ 5, § 6
2014Castagna et al.polymorphic functions with set-theoretic types§ 8
2024–26Castagna, Duboc, Valimthe type system of Elixir§ 4
2026this essaytyping call from handle_call§ 7

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 MM has type σ→τ\sigma\to\tau and NN has type σ\sigma, then MNMN has type τ\tau. Types are preserved by reduction but not by expansion, and many terms in normal form, such as λx.xx\lambda 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.xx\lambda 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 xx has in λx.xx\lambda 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 MNMN is then interpreted as the application F⋅GF \cdot G. of the filter FF of MM to the filter GG of NN, defined as

F⋅G={τ∣σ→τ∈F for some σ∈G}F \cdot G = \{\tau\mid\sigma\to\tau\in F\text{ for some }\sigma\in G\}

This is where (→∧)(\to\land) enters the scene: it is what makes F⋅GF \cdot G closed under intersection (that F⋅GF \cdot G contains ω\omega and is closed upwards follows from ω≤ω→ω\omega\leq\omega\to\omega and from covariance). To see why, take τ1\tau_1 and τ2\tau_2 in F⋅GF \cdot G; if they are there it is because σ1→τ1\sigma_1 \to\tau_1 and σ2→τ2\sigma_2 \to\tau_2 are in FF for some σ1,σ2∈G\sigma_1, \sigma_2 \in G. Then σ1∧σ2\sigma_1 \land\sigma_2 is in GG, contravariance puts σ1∧σ2→τ1\sigma_1 \land\sigma_2 \to\tau_1 and σ1∧σ2→τ2\sigma_1 \land\sigma_2 \to\tau_2 in FF, hence their intersection, and (→∧)(\to\land) puts σ1∧σ2→τ1∧τ2\sigma_1 \land\sigma_2 \to\tau_1 \land\tau_2 in FF, so that τ1∧τ2\tau_1 \land\tau_2 is in F⋅GF \cdot 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) 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 tt denotes a set of values; union, intersection and negation ¬t\neg t denote set-theoretic union, intersection and complement; 00 is the empty type, 11 the type of all values, t∖st \setminus s stands for t∧¬st \land\neg s; and t≤st \le s holds if and only if the set denoted by tt is included in the set denoted by ss. 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}_{+} [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 {v1,…,vn}\{v_1, \ldots, 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(ee) executes the first clause whose pattern (here the simple capture variable xx) and guard accept the result of the evaluation of ee, 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 xx 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}())

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(ee) is an integer whenever ee 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(ff) creates a process that runs the function ff (a zero-ary function) and returns its pid; send(pp, ee) puts the result of the evaluation of the expression ee in the mailbox of the process identified by pp 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 kk, 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) is the type of the pids of the processes that accept the messages of type tt. It is the type ch⁡−(t)\operatorname{ch}^{-}(t) of the channels on which values of type tt 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⁡(t1)∧pid⁡(t2)=pid⁡(t1∨t2)(3)\operatorname{pid}(t_1) \land\operatorname{pid}(t_2) = \operatorname{pid}(t_1 \lor t_2) \tag*{(3)}
pid⁡(t)≤⋁n∈Npid⁡(sn)⟺sn≤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)}

The first law is contravariance: a pid that accepts all the messages in tt can be used where only messages in some s≤ts \le t are sent. In particular pid⁡(0)\operatorname{pid}(0), which I write pid⁡()\operatorname{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 t1t_1 and those in t2t_2 accepts the messages in t1∨t2t_1 \lor 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) contains the pid of a process that accepts exactly the messages in tt, and this pid is in pid⁡(sn)\operatorname{pid}(s_n) only if sn≤ts_n \le 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, 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}\})

References

  1. [1]Franco Barbanera, Mariangiola Dezani-Ciancaglini, and Ugo de’Liguoro. Intersection and union types: syntax and semantics. Inf. Comput., 119(2):202–230, June 1995. ISSN 0890-5401. doi: 10.1006/inco.1995.1086.DOI
  2. [2]Henk Barendregt, Mario Coppo, and Mariangiola Dezani-Ciancaglini. A filter lambda model and the completeness of type assignment. Journal of Symbolic Logic, 48(4):931–940, 1983.DOI
  3. [3]Véronique Benzaken, Giuseppe Castagna, and Alain Frisch. CDuce: an XML-centric general-purpose language. In ICFP ’03, 8th ACM International Conference on Functional Programming, pages 51–63. ACM Press, 2003. doi: 10.1145/944705.944711.DOI
  4. [4]Lorenzo Bettini, Mario Coppo, Loris D’Antoni, Marco De Luca, Mariangiola Dezani-Ciancaglini, and Nobuko Yoshida. Global Progress in Dynamically Interleaved Multiparty Sessions. In CONCUR ’08, LNCS 5201, 2008.DOI
  5. [5]Aghilas Y. Boussaa, Antonin Bretagne, and Giuseppe Castagna. Typing modules in Elixir. In preparation, 2026.
  6. [6]Antonin Bretagne. Semantic typing for Elixir’s module type system. Master’s thesis, Master Parisien de Recherche en Informatique (MPRI), ENS Paris-Saclay, September 2026. Report available at this link.
  7. [9]Giuseppe Castagna and Gang Chen. Dependent types with subtyping and late-bound overloading. Information and Computation, 168(1):1–67, 2001.DOI
  8. [12]Giuseppe Castagna, Giorgio Ghelli, and Giuseppe Longo. A calculus for overloaded functions with subtyping. In Proceedings of the 1992 ACM Conference on LISP and Functional Programming (LFP ’92), pages 182–192, San Francisco, 1992. ACM. doi: 10.1145/141471.141537.DOI
  9. [13]Giuseppe Castagna, Giorgio Ghelli, and Giuseppe Longo. A calculus for overloaded functions with subtyping. Information and Computation, 117(1):115–135, 1995. doi: 10.1006/inco.1995.1033.DOI
  10. [14]Giuseppe Castagna, Mariangiola Dezani-Ciancaglini, and Daniele Varacca. Encoding CDuce in the Cπ-calculus. In CONCUR 2006, 17th. International Conference on Concurrency Theory, number 4137 in LNCS, pages 310–326. Springer, 2006. Extended version at http://www.di.unito.it/~dezani/papers/cdv.pdf.
  11. [15]Giuseppe Castagna, Rocco De Nicola, and Daniele Varacca. Semantic subtyping for the π-calculus. Theoretical Computer Science, 398(1–3):217–242, 2008. doi: 10.1016/j.tcs.2008.01.049. Essays in honour of Mario Coppo, Mariangiola Dezani-Ciancaglini and Simona Ronchi della Rocca. Extended abstract in LICS ’05.DOI
  12. [16]Giuseppe Castagna, Mariangiola Dezani-Ciancaglini, Elena Giachino, and Luca Padovani. Foundations of session types. In PPDP’09, pages 219–230. ACM Press, 2009.
  13. [17]Giuseppe Castagna, Mariangiola Dezani-Ciancaglini, and Luca Padovani. On global types and multi-party sessions. Logical Methods in Computer Science, 8(1:24):1–45, 2012.DOI
  14. [18]Giuseppe Castagna, Kim Nguyen, Zhiwu Xu, Hyeonseung Im, Sergüei Lenglet, and Luca Padovani. Polymorphic functions with set-theoretic types. Part 1: Syntax, semantics, and evaluation. In Proceedings of the 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, pages 5–17, January 2014.
  15. [19]Giuseppe Castagna, Kim Nguyen, Zhiwu Xu, and Pietro Abate. Polymorphic functions with set-theoretic types. Part 2: local type inference and type reconstruction. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’15, pages 289–302, January 2015. doi: 10.1145/2676726.2676991.DOI
  16. [20]Giuseppe Castagna, Victor Lanvin, Tommaso Petrucciani, and Jeremy G. Siek. Gradual typing: a new perspective. Proc. ACM Program. Lang., 3(POPL), January 2019. doi: 10.1145/3290329.DOI
  17. [21]Giuseppe Castagna, Mickaël Laurent, Kim Nguyen, and Matthew Lutze. On type-cases, union elimination, and occurrence typing. Proc. ACM Program. Lang., 6(POPL), January 2022. doi: 10.1145/3498674.DOI
  18. [22]Giuseppe Castagna, Guillaume Duboc, and José Valim. The Design Principles of the Elixir Type System. The Art, Science, and Engineering of Programming, 8(2), 2024a. doi: 10.22152/programming-journal.org/2024/8/4.DOI
  19. [23]Giuseppe Castagna, Mickaël Laurent, and Kim Nguyen. Polymorphic type inference for dynamic languages. Proc. ACM Program. Lang., 8(POPL), January 2024b. doi: 10.1145/3632882.DOI
  20. [24]Giuseppe Castagna, Luca Padovani, Daniele Varacca, and Amine Nasri. You have mail: Set-theoretic types for actors. Unpublished preprint, 2026. URL https://www.irif.fr/~gc/papers/elixir-type-processes.pdf.
  21. [27]Mario Coppo, Mariangiola Dezani-Ciancaglini, and Betti Venneri. Principal type schemes and lambda-calculus semantics. In J. R. Hindley and J. P. Seldin, editors, To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism. Academic Press, 1980.
  22. [29]Mario Coppo, Mariangiola Dezani-Ciancaglini, and Nobuko Yoshida. Asynchronous Session Types and Progress for Object-Oriented Languages. In FMOODS’07, LNCS 4468. Springer, 2007.
  23. [30]Mariangiola Dezani-Ciancaglini, Alain Frisch, Elio Giovannetti, and Yoko Motohama. The relevance of semantic subtyping. Electronic Notes in Theoretical Computer Science, 70(1):88 – 105, 2002. ISSN 1571-0661. doi: 10.1016/S1571-0661(04)80492-4. ITRS ’02, Intersection Types and Related Systems.
  24. [31]Guillaume Duboc. Typing Dynamic Languages with Set-Theoretic Types: The Case of Elixir. PhD thesis, Université Paris Cité, January 2026. URL https://glduboc.github.io/assets/duboc-phd-thesis-typing-elixir.pdf.
  25. [32]Elixir. Elixir v1.17 released: set-theoretic types in patterns, calendar durations, and erlang/otp 27 support. https://elixir-lang.org/blog/2024/06/12/elixir-v1-17-0-released, 2024. Accessed June 12, 2024.
  26. [33]Elixir. Elixir v1.20 released: now a gradually typed language. https://elixir-lang.org/blog/2026/06/03/elixir-v1-20-0-released/, 2026a. Accessed October 19, 2026.
  27. [34]Elixir. Gradual set-theoretic types. https://hexdocs.pm/elixir/gradual-set-theoretic-types.html, 2026b. Section “Roadmap”. Accessed October 29, 2026.
  28. [35]Elixir. GenServer: a behaviour module for implementing the server of a client-server relation. https://hexdocs.pm/elixir/GenServer.html, 2026c.
  29. [36]Ericsson. gen_server: generic server behaviour, Erlang/OTP STDLIB reference manual. https://www.erlang.org/doc/apps/stdlib/gen_server.html, 2026a.
  30. [37]Ericsson. gen_statem: generic state machine behaviour, Erlang/OTP STDLIB reference manual. https://www.erlang.org/doc/apps/stdlib/gen_statem.html, 2026b.
  31. [38]Alain Frisch, Giuseppe Castagna, and Véronique Benzaken. Semantic Subtyping. In LICS ’02, 17th Annual IEEE Symposium on Logic in Computer Science, pages 137–146. IEEE Computer Society Press, 2002. doi: 10.1109/LICS.2002.1029823.DOI
  32. [39]Alain Frisch, Giuseppe Castagna, and Véronique Benzaken. Semantic subtyping: dealing set-theoretically with function, union, intersection, and negation types. Journal of the ACM, 55 (4):19:1–19:64, September 2008. ISSN 0004-5411. doi: 10.1145/1391289.1391293.DOI
  33. [40]Haruo Hosoya and Benjamin C. Pierce. XDuce: A statically typed XML processing language. ACM Trans. Internet Techn., 3(2):117–148, 2003. doi: 10.1145/767193.767195.DOI
  34. [41]Victor Lanvin. A Semantic Foundation for Gradual Set-Theoretic Types. PhD thesis, Université de Paris, November 2021. URL https://theses.hal.science/tel-03853222.DOI
  35. [42]Daan Leijen and Erik Meijer. Domain specific embedded compilers. In Proceedings of the 2nd Conference on Domain-Specific Languages (DSL ’99), pages 109–122. USENIX, 1999.
  36. [43]Tobias Lindahl and Konstantinos Sagonas. Practical type inference based on success typings. In ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming, pages 167–178, New York, NY, USA, 2006. Association for Computing Machinery.DOI
  37. [44]Luigi Liquori and Simona Ronchi Della Rocca. Intersection-types à la Church. Inf. Comput., 205(9):1371–1386, 2007.DOI
  38. [45]David MacQueen, Gordon Plotkin, and Ravi Sethi. An ideal model for recursive polymorphic types. Information and Control, 71(1):95–130, 1986. ISSN 0019-9958. doi: 10.1016/S0019-9958(86)80019-5.DOI
  39. [46]Massimo Merro and Davide Sangiorgi. On asynchrony in name-passing calculi. Mathematical Structures in Computer Science, 14(5):715–767, 2004.
  40. [47]Robin Milner. Functions as processes. Mathematical Structures in Computer Science, 2(2):119–141, 1992.
  41. [48]Benjamin C. Pierce. Programming with intersection types, union types, and polymorphism. Technical Report CMU-CS-91-106, Carnegie Mellon University, 1991.
  42. [49]Benjamin C. Pierce. Programming with Intersection Types and Bounded Polymorphism. PhD thesis, Carnegie Mellon University, USA, 1992. URL https://www.cis.upenn.edu/~bcpierce/papers/thesis.pdf.
  43. [50]Garrel Pottinger. A type assignment for the strongly normalizable λ-terms. In J. R. Hindley and J. P. Seldin, editors, To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, pages 561–577. Academic Press, 1980.
  44. [51]John C. Reynolds. Design of the programming language Forsythe. Technical Report CMU-CS-96-146, Carnegie Mellon University, 1996.DOI
  45. [52]Simona Ronchi Della Rocca. Principal type scheme and unification for intersection type discipline. Theoretical Computer Science, 59(1-2):181–209, 1988.DOI
  46. [53]Simona Ronchi Della Rocca. Intersection typed λ-calculus. Electronic Notes in Theoretical Computer Science, 70(1):163–181, 2002. ITRS ’02, Intersection Types and Related Systems.DOI
  47. [54]Simona Ronchi Della Rocca and Betti Venneri. Principal type schemes for an extended type theory. Theoretical Computer Science, 28(1–2):151–169, 1984.DOI
  48. [55]Davide Sangiorgi and David Walker. The π-calculus: A Theory of Mobile Processes. Cambridge University Press, 2001.DOI
  49. [56]Dana S. Scott. Open problem. In C. Böhm, editor, λ-Calculus and Computer Science Theory (Proc. Sympos., Rome, 1975), volume 37 of LNCS, page 368. Springer, 1975.
  50. [57]Dana S. Scott. Data types as lattices. SIAM Journal on Computing, 5(3):522–587, 1976. doi: 10.1137/0205037.DOI
  51. [58]Sam Tobin-Hochstadt and Matthias Felleisen. The design and implementation of Typed Scheme. In Proc. of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’08. ACM, 2008. doi: 10.1145/1328438.1328486.
  52. [59]WhatsApp. eqWAlizer: a type-checker for Erlang. https://github.com/WhatsApp/eqwalizer, 2022. Since 2026 maintained within the Erlang Language Platform.

Paper details

vlnc:W_ggv8ng82
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents