Session.Theory
Session.Theory: the logic of March's protocols, and laws about it.
A protocol (protocol P do ... end) is a global type: who sends what to whom, where a role chooses, where it loops. Each role runs its projection, a local type. The compiler projects twice, in OCaml (the Chan(Role, Proto) typechecker and the @[endpoints] generator); this module is the specification both are validated against (march --check --guarantees, lemmas design ยง5.2, M6), and the laws below are proved once, here, for every protocol.
SessionRoles, labels and payload types are Int ids: the logic treats String contents as opaque, and the compiler maps names to ids when it emits a protocol as a SessionGlobal.
A loop is GLoop(body, after). The body's end is GVar(0), the loop's own back-edge (de Bruijn: the nearest enclosing loop); after is what a role that takes no part in the body does next. stop is GEnd. A choice's branches each carry the rest of the protocol (the steps after the choice are appended to every branch).
Types
A global protocol over role, label and payload ids.
A choice's labelled branches.
One role's view: send to or receive from a peer, choose or offer a label, loop.
A local choice's labelled branches.
The roles of a configuration (its own list type: see Session.Theory's progress note on a reflected function over the stdlib List).
A sequence of steps.
The labels to take at successive choices.
One step of the whole system: a message, or a choice whose label rides on the chooser's first message (chooser, receiver, label, payload).
Every role with its local type.
The result of a step.
One role's part of a step.
Functions
Role r's part in step a; a role not in it stays as it is.
The sender of a.
One role's part in a message step: it ends at its projection of what follows.
One role's part in a choice step: it ends at its projection of what follows branch lab's first message.
The receiver of a.
Every role of the configuration is done.
Laws
all_done(config(GEnd, rs, multiparty))(lemmaend_done) proved
Whether every branch is l.
Duality keeps branches alike.
Every role takes its part in a.
Every role takes its part in a message step.
Every role takes its part in a choice step.
Every message and choice of g is between roles a and b.
binary on every branch.
role_ok for every role of rs.
A directed choice: branches, each beginning with a message from c to one other role.
Choose lab and send its first message.
Restricted branches: one branch when all look alike, else a choice (as_choice) or an offer.
A choice and an offer over dual branches are dual.
Merged branches collapse to their first.
C4's message step: if what follows runs to the end, so does the message and what follows.
C4's choice step: if what follows the chosen branch's first message runs to the end, so does the choice.
C4's statement for one protocol: run on its own trace, the configuration of its projections takes every step and ends with every role done.
The configuration of g: every role of rs runs its projection.
Laws
all_done(config(GEnd, rs, multiparty))(lemmaend_done) proved
The receiver of a choice's first branch head (-1 when there is none).
Every branch begins with a message from c to t.
In a directed choice, branch lab is the chooser's message to the receiver.
The other end of a conversation: every send a receive, every choice an offer.
Laws
dual(dual(l)) == l(lemmadual_dual) provedlhead(dual_bs(rb)) == dual(lhead(rb))(lemmalhead_dual) proved
dual on every branch.
Laws
dual_bs(dual_bs(bs)) == bs(lemmadual_dual_bs) provedmerged(dual_bs(rb)) == merged(rb)(lemmamerged_dual) provedlhead(dual_bs(rb)) == dual(lhead(rb))(lemmalhead_dual) proved
C1. Duality is an involution.
C1 on every branch.
Duality commutes with leaving out a loop no one takes part in.
The configuration of a finished protocol has every role done.
l with every peer replaced by 0: a two-party conversation, where the peer is implied.
erase on every branch.
Erasing peers commutes with leaving out a loop no one takes part in.
The first branch labelled lab.
In branches that are all first, a lookup finds first or nothing.
In merged branches, a lookup finds the first branch or nothing.
Looking up a label in a projected choice gives the projection of that branch.
The run took every step and every role is done.
The first step of the protocol's trace (a no-op message when there is none).
The first branch's label.
The first branch labelled lab (GEnd when there is none).
What follows branch lab's first message.
The payload of branch lab's first message.
Whether r is in the role list.
Whether some branch is labelled lab.
Laws
!nonempty(bs) || has_label(bs, pick(bs, picks))(lemmapick_has) proved
Every branch begins with a receive from c.
g is in the fragment C3-C5 cover, over the roles rs: loop-free, every message between two different roles of rs, every choice directed with its bystanders merged.
in_fragment on every branch.
Role r learns every choice it must: in a multiparty protocol, a role whose branches differ receives the chooser's message first (a two-party offer is told by the label).
informed on every branch.
The first branch's local type (LEnd when there is none).
Laws
lhead(dual_bs(rb)) == dual(lhead(rb))(lemmalhead_dual) proved
The first branch of the dual is the dual of the first branch.
A loop's projection: no loop at all when the role takes no part in the body.
A role that does not choose sees the branches merged: in a multiparty protocol, one branch when every branch is the same (it never learns the label), else an offer.
Laws
merge(bs, false) == LOffer(bs)(lemmamerge_binary) proved
In a binary protocol a choice is always offered, never merged.
How a non-chooser sees a choice: merged into its first branch, or an offer.
A non-empty branch list whose branches all project alike.
Laws
merged(dual_bs(rb)) == merged(rb)(lemmamerged_dual) proved
Duality keeps a choice merged.
Restricting keeps a choice merged, and commutes with taking its first branch.
Whether a choice has any branch.
Laws
!nonempty(bs) || has_label(bs, pick(bs, picks))(lemmapick_has) proved
Receive the chooser's first message of branch lab: from an offer, or from a merged receive.
C3. Pairwise duality (the fragment): for two roles of a protocol, what one does with the other is the dual of what the other does with it.
C3 on every branch.
C3 at a choice: with each branch's restrictions dual, the choice's are.
The label picks asks for, when there is such a branch; else the first.
Laws
!nonempty(bs) || has_label(bs, pick(bs, picks))(lemmapick_has) proved
The label a choice takes is one of its branches.
Whether role r is in the configuration.
A configuration has exactly the roles it was built from.
C5. Deadlock freedom (synchronous, the fragment): while the protocol has a next step, the configuration of the projections can take it.
Role r's projection of g. multiparty is true for more than two roles: only then may a non-chooser merge a choice's branches.
project on every branch.
C2. A binary protocol's two projections are dual (peers erased: each has one).
C2 on every branch.
C4. The projections compose back to the protocol: run on the protocol's own trace, the configuration of every role's projection takes every step and ends with every role done.
C4 for what follows branch lab's first message.
Receive p from f, if that is what l does next.
The rest of picks after one choice.
Role x's part of l: the actions with peer x, peers erased (two parties, so the peer is implied), and a choice whose branches then all look alike is no choice.
Restricting keeps branches alike.
restrict on every branch.
A role's part of a choice, restricted to a peer: its branches restricted and collapsed, a choice for the chooser and an offer for anyone else.
Role r takes part in choice bs by c correctly: it is the chooser, the receiver of every branch head, or its branches project alike.
A role of rs takes part in a choice of the fragment correctly.
Run the steps in order.
Structural equality of local types, written out so the logic can use it (a derived Eq on a recursive type is not yet reflected).
Laws
same(a, b) == (a == b)(lemmasame_eq) proved
same on branch lists.
Laws
same_bs(xs, ys) == (xs == ys)(lemmasame_eq_bs) proved
same is structural equality.
same_bs is structural equality.
Send p to t, if that is what l does next.
One synchronous step: both parties are there and each can take its part.
Subject reduction for a message: its step takes the configuration of GMsg(f, t, p, k) to that of k.
Subject reduction for a choice: its step takes the configuration of the choice to that of what follows branch lab's first message.
A role that does not choose is told the choice: its branches are all the same, or each begins with the chooser's message.
The steps of g when each choice takes the label picks lists in turn (loop-free).
The steps of branch lab: the chooser's first message carries the label.
A choice's trace: the chooser's first message, carrying the label, then the branch.