March Docs

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

typeSessionGlobalSessionGlobal = GEnd#

A global protocol over role, label and payload ids.

typeSessionGBranchesSessionGBranches = GBNil | GBCons(Int, SessionGlobal, SessionGBranches)#

A choice's labelled branches.

typeSessionLocalSessionLocal = LEnd#

One role's view: send to or receive from a peer, choose or offer a label, loop.

typeSessionLBranchesSessionLBranches = LBNil | LBCons(Int, SessionLocal, SessionLBranches)#

A local choice's labelled branches.

typeSessionRolesSessionRoles = RoleEnd | RoleThen(Int, SessionRoles)#

The roles of a configuration (its own list type: see Session.Theory's progress note on a reflected function over the stdlib List).

typeSessionActsSessionActs = ActEnd | ActThen(SessionAct, SessionActs)#

A sequence of steps.

typeSessionPicksSessionPicks = PickEnd | PickThen(Int, SessionPicks)#

The labels to take at successive choices.

typeSessionActSessionAct = ActMsg(Int, Int, Int) | ActPick(Int, Int, Int, Int)#

One step of the whole system: a message, or a choice whose label rides on the chooser's first message (chooser, receiver, label, payload).

typeSessionCfgSessionCfg = CfgEnd | CfgRole(Int, SessionLocal, SessionCfg)#

Every role with its local type.

typeSessionCfgStepSessionCfgStep = CfgStuck | CfgMoved(SessionCfg)#

The result of a step.

typeSessionLStepSessionLStep = StepBad | StepOk(SessionLocal)#

One role's part of a step.

Functions

fnactact(r : Int, l : SessionLocal, a : SessionAct) : SessionLStep#

Role r's part in step a; a role not in it stays as it is.

fnact_fromact_from(a : SessionAct) : Int#

The sender of a.

fnact_msgact_msg(f : Int, t : {Int | _ != f}, p : Int, k : SessionGlobal, r : Int, multiparty : Bool)#

One role's part in a message step: it ends at its projection of what follows.

fnact_pickact_pick(c : Int, bs : SessionGBranches, multiparty : Bool, lab : Int, r : Int)#

One role's part in a choice step: it ends at its projection of what follows branch lab's first message.

fnact_toact_to(a : SessionAct) : Int#

The receiver of a.

fnall_doneall_done(cfg : SessionCfg) : Bool#

Every role of the configuration is done.

Laws

  • all_done(config(GEnd, rs, multiparty)) (lemma end_done) proved
fnall_sameall_same(bs : SessionLBranches, l : SessionLocal) : Bool#

Whether every branch is l.

fnall_same_dualall_same_dual(rest : SessionLBranches, first : SessionLocal)#

Duality keeps branches alike.

fnapplyapply(cfg : SessionCfg, a : SessionAct) : SessionCfgStep#

Every role takes its part in a.

fnapply_msgapply_msg(f : Int, t : {Int | _ != f}, p : Int, k : SessionGlobal, rs : SessionRoles, multiparty : Bool)#

Every role takes its part in a message step.

fnapply_pickapply_pick(c : Int, bs : SessionGBranches, rs : SessionRoles, multiparty : Bool, lab : Int)#

Every role takes its part in a choice step.

fnbinarybinary(g : SessionGlobal, a : Int, b : Int) : Bool#

Every message and choice of g is between roles a and b.

fnbinary_bsbinary_bs(bs : SessionGBranches, a : Int, b : Int) : Bool#

binary on every branch.

fnbystanders_mergedbystanders_merged(rs : SessionRoles, c : Int, bs : SessionGBranches, multiparty : Bool) : Bool#

role_ok for every role of rs.

fnchoice_okchoice_ok(c : Int, bs : SessionGBranches) : Bool#

A directed choice: branches, each beginning with a message from c to one other role.

fnchoose_stepchoose_step(l : SessionLocal, lab : Int, t : Int, p : Int) : SessionLStep#

Choose lab and send its first message.

fncollapsecollapse(rb : SessionLBranches, as_choice : Bool) : SessionLocal#

Restricted branches: one branch when all look alike, else a choice (as_choice) or an offer.

fncollapse_dualcollapse_dual(rb : SessionLBranches)#

A choice and an offer over dual branches are dual.

fncollapse_mergedcollapse_merged(rb : SessionLBranches, as_choice : Bool)#

Merged branches collapse to their first.

fncompose_msgcompose_msg(f : Int, t : Int, p : Int, k : SessionGlobal, rs : SessionRoles, multiparty : Bool, picks : SessionPicks)#

C4's message step: if what follows runs to the end, so does the message and what follows.

fncompose_pickcompose_pick(c : Int, bs : SessionGBranches, rs : SessionRoles, multiparty : Bool, picks : SessionPicks)#

C4's choice step: if what follows the chosen branch's first message runs to the end, so does the choice.

fncomposescomposes(g : SessionGlobal, rs : SessionRoles, multiparty : Bool, picks : SessionPicks) : Bool#

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.

fnconfigconfig(g : SessionGlobal, rs : SessionRoles, multiparty : Bool) : SessionCfg#

The configuration of g: every role of rs runs its projection.

Laws

  • all_done(config(GEnd, rs, multiparty)) (lemma end_done) proved
fndestdest(bs : SessionGBranches) : Int#

The receiver of a choice's first branch head (-1 when there is none).

fndirecteddirected(bs : SessionGBranches, c : Int, t : Int) : Bool#

Every branch begins with a message from c to t.

fndirected_branchdirected_branch(bs : SessionGBranches, c : Int, t : Int, lab : Int)#

In a directed choice, branch lab is the chooser's message to the receiver.

fndualdual(l : SessionLocal) : SessionLocal#

The other end of a conversation: every send a receive, every choice an offer.

Laws

  • dual(dual(l)) == l (lemma dual_dual) proved
  • lhead(dual_bs(rb)) == dual(lhead(rb)) (lemma lhead_dual) proved
fndual_bsdual_bs(bs : SessionLBranches) : SessionLBranches#

dual on every branch.

Laws

  • dual_bs(dual_bs(bs)) == bs (lemma dual_dual_bs) proved
  • merged(dual_bs(rb)) == merged(rb) (lemma merged_dual) proved
  • lhead(dual_bs(rb)) == dual(lhead(rb)) (lemma lhead_dual) proved
fndual_dualdual_dual(l : SessionLocal) : {Unit | dual(dual(l)) == l}#

C1. Duality is an involution.

fndual_dual_bsdual_dual_bs(bs : SessionLBranches) : {Unit | dual_bs(dual_bs(bs)) == bs}#

C1 on every branch.

fndual_loop_ofdual_loop_of(body : SessionLocal, after : SessionLocal)#

Duality commutes with leaving out a loop no one takes part in.

fnend_doneend_done(rs : SessionRoles, multiparty : Bool) : {Unit | all_done(config(GEnd, rs, multiparty))}#

The configuration of a finished protocol has every role done.

fneraseerase(l : SessionLocal) : SessionLocal#

l with every peer replaced by 0: a two-party conversation, where the peer is implied.

fnerase_bserase_bs(bs : SessionLBranches) : SessionLBranches#

erase on every branch.

fnerase_loop_oferase_loop_of(body : SessionLocal, after : SessionLocal)#

Erasing peers commutes with leaving out a loop no one takes part in.

fnfindfind(bs : SessionLBranches, lab : Int) : SessionLStep#

The first branch labelled lab.

fnfind_all_samefind_all_same(rest : SessionLBranches, first : SessionLocal, lab : Int)#

In branches that are all first, a lookup finds first or nothing.

fnfind_mergedfind_merged(pbs : SessionLBranches, lab : Int)#

In merged branches, a lookup finds the first branch or nothing.

fnfind_projectfind_project(bs : SessionGBranches, r : Int, multiparty : Bool, lab : Int)#

Looking up a label in a projected choice gives the projection of that branch.

fnfinishedfinished(r : SessionCfgStep) : Bool#

The run took every step and every role is done.

fnfirst_actfirst_act(g : SessionGlobal, picks : SessionPicks) : SessionAct#

The first step of the protocol's trace (a no-op message when there is none).

fnfirst_labelfirst_label(bs : SessionGBranches) : Int#

The first branch's label.

fngbranchgbranch(bs : SessionGBranches, lab : Int) : SessionGlobal#

The first branch labelled lab (GEnd when there is none).

fngcontgcont(bs : SessionGBranches, lab : Int) : SessionGlobal#

What follows branch lab's first message.

fngpaygpay(bs : SessionGBranches, lab : Int) : Int#

The payload of branch lab's first message.

fnhashas(rs : SessionRoles, r : Int) : Bool#

Whether r is in the role list.

fnhas_labelhas_label(bs : SessionGBranches, lab : Int) : Bool#

Whether some branch is labelled lab.

Laws

  • !nonempty(bs) || has_label(bs, pick(bs, picks)) (lemma pick_has) proved
fnheads_fromheads_from(bs : SessionLBranches, c : Int) : Bool#

Every branch begins with a receive from c.

fnin_fragmentin_fragment(g : SessionGlobal, rs : SessionRoles, multiparty : Bool) : Bool#

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.

fnin_fragment_bsin_fragment_bs(bs : SessionGBranches, rs : SessionRoles, multiparty : Bool) : Bool#

in_fragment on every branch.

fninformedinformed(g : SessionGlobal, r : Int, multiparty : Bool) : Bool#

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

fninformed_bsinformed_bs(bs : SessionGBranches, r : Int, multiparty : Bool) : Bool#

informed on every branch.

fnlheadlhead(bs : SessionLBranches) : SessionLocal#

The first branch's local type (LEnd when there is none).

Laws

  • lhead(dual_bs(rb)) == dual(lhead(rb)) (lemma lhead_dual) proved
fnlhead_duallhead_dual(rb : SessionLBranches) : {Unit | lhead(dual_bs(rb)) == dual(lhead(rb))}#

The first branch of the dual is the dual of the first branch.

fnloop_ofloop_of(body : SessionLocal, after : SessionLocal) : SessionLocal#

A loop's projection: no loop at all when the role takes no part in the body.

fnmergemerge(bs : SessionLBranches, multiparty : Bool) : SessionLocal#

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) (lemma merge_binary) proved
fnmerge_binarymerge_binary(bs : SessionLBranches) : {Unit | merge(bs, false) == LOffer(bs)}#

In a binary protocol a choice is always offered, never merged.

fnmerge_casesmerge_cases(pbs : SessionLBranches, multiparty : Bool)#

How a non-chooser sees a choice: merged into its first branch, or an offer.

fnmergedmerged(pbs : SessionLBranches) : Bool#

A non-empty branch list whose branches all project alike.

Laws

  • merged(dual_bs(rb)) == merged(rb) (lemma merged_dual) proved
fnmerged_dualmerged_dual(rb : SessionLBranches) : {Unit | merged(dual_bs(rb)) == merged(rb)}#

Duality keeps a choice merged.

fnmerged_restrictmerged_restrict(pbs : SessionLBranches, x : Int)#

Restricting keeps a choice merged, and commutes with taking its first branch.

fnnonemptynonempty(bs : SessionGBranches) : Bool#

Whether a choice has any branch.

Laws

  • !nonempty(bs) || has_label(bs, pick(bs, picks)) (lemma pick_has) proved
fnoffer_stepoffer_step(l : SessionLocal, lab : Int, c : Int, p : Int) : SessionLStep#

Receive the chooser's first message of branch lab: from an offer, or from a merged receive.

fnpairwisepairwise(g : SessionGlobal, rs : SessionRoles, multiparty : Bool, p : Int, q : {Int | _ != p})#

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.

fnpairwise_bspairwise_bs(bs : SessionGBranches, rs : SessionRoles, multiparty : Bool, p : Int, q : {Int | _ != p})#

C3 on every branch.

fnpairwise_choicepairwise_choice(c : Int, bs : SessionGBranches, rs : SessionRoles, multiparty : Bool, p : Int, q : {Int | _ != p})#

C3 at a choice: with each branch's restrictions dual, the choice's are.

fnpickpick(bs : SessionGBranches, picks : SessionPicks) : Int#

The label picks asks for, when there is such a branch; else the first.

Laws

  • !nonempty(bs) || has_label(bs, pick(bs, picks)) (lemma pick_has) proved
fnpick_haspick_has(bs : SessionGBranches, picks : SessionPicks) : {Unit | !nonempty(bs) || has_label(bs, pick(bs, picks))}#

The label a choice takes is one of its branches.

fnpresentpresent(cfg : SessionCfg, r : Int) : Bool#

Whether role r is in the configuration.

fnpresent_configpresent_config(g : SessionGlobal, rs : SessionRoles, multiparty : Bool, r : Int)#

A configuration has exactly the roles it was built from.

fnprogressprogress(g : SessionGlobal, rs : SessionRoles, multiparty : Bool, picks : SessionPicks)#

C5. Deadlock freedom (synchronous, the fragment): while the protocol has a next step, the configuration of the projections can take it.

fnprojectproject(g : SessionGlobal, r : Int, multiparty : Bool) : SessionLocal#

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.

fnproject_bsproject_bs(bs : SessionGBranches, r : Int, multiparty : Bool) : SessionLBranches#

project on every branch.

fnproject_dualproject_dual(a : Int, b : {Int | _ != a}, g : SessionGlobal)#

C2. A binary protocol's two projections are dual (peers erased: each has one).

fnproject_dual_bsproject_dual_bs(a : Int, b : {Int | _ != a}, bs : SessionGBranches)#

C2 on every branch.

fnprojections_composeprojections_compose(g : SessionGlobal, rs : SessionRoles, multiparty : Bool, picks : SessionPicks)#

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.

fnprojections_compose_bsprojections_compose_bs(bs : SessionGBranches, rs : SessionRoles, multiparty : Bool, lab : Int, picks : SessionPicks)#

C4 for what follows branch lab's first message.

fnrecv_steprecv_step(l : SessionLocal, f : Int, p : Int) : SessionLStep#

Receive p from f, if that is what l does next.

fnrest_picksrest_picks(picks : SessionPicks) : SessionPicks#

The rest of picks after one choice.

fnrestrictrestrict(l : SessionLocal, x : Int) : SessionLocal#

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.

fnrestrict_all_samerestrict_all_same(rest : SessionLBranches, first : SessionLocal, x : Int)#

Restricting keeps branches alike.

fnrestrict_bsrestrict_bs(bs : SessionLBranches, x : Int) : SessionLBranches#

restrict on every branch.

fnrestrict_choicerestrict_choice(c : Int, bs : SessionGBranches, r : Int, x : Int, multiparty : Bool)#

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.

fnrole_okrole_ok(c : Int, bs : SessionGBranches, r : Int, multiparty : Bool) : Bool#

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.

fnrole_ok_hasrole_ok_has(rs : SessionRoles, c : Int, bs : SessionGBranches, multiparty : Bool, r : Int)#

A role of rs takes part in a choice of the fragment correctly.

fnrunrun(cfg : SessionCfg, acts : SessionActs) : SessionCfgStep#

Run the steps in order.

fnsamesame(a : SessionLocal, b : SessionLocal) : Bool#

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) (lemma same_eq) proved
fnsame_bssame_bs(xs : SessionLBranches, ys : SessionLBranches) : Bool#

same on branch lists.

Laws

  • same_bs(xs, ys) == (xs == ys) (lemma same_eq_bs) proved
fnsame_eqsame_eq(a : SessionLocal, b : SessionLocal) : {Unit | same(a, b) == (a == b)}#

same is structural equality.

fnsame_eq_bssame_eq_bs(xs : SessionLBranches, ys : SessionLBranches) : {Unit | same_bs(xs, ys) == (xs == ys)}#

same_bs is structural equality.

fnsend_stepsend_step(l : SessionLocal, t : Int, p : Int) : SessionLStep#

Send p to t, if that is what l does next.

fnstepstep(cfg : SessionCfg, a : SessionAct) : SessionCfgStep#

One synchronous step: both parties are there and each can take its part.

fnstep_msgstep_msg(f : Int, t : {Int | _ != f}, p : Int, k : SessionGlobal, rs : SessionRoles, multiparty : Bool)#

Subject reduction for a message: its step takes the configuration of GMsg(f, t, p, k) to that of k.

fnstep_pickstep_pick(c : Int, bs : SessionGBranches, rs : SessionRoles, multiparty : Bool, lab : Int)#

Subject reduction for a choice: its step takes the configuration of the choice to that of what follows branch lab's first message.

fntoldtold(bs : SessionLBranches, c : Int) : Bool#

A role that does not choose is told the choice: its branches are all the same, or each begins with the chooser's message.

fntracetrace(g : SessionGlobal, picks : SessionPicks) : SessionActs#

The steps of g when each choice takes the label picks lists in turn (loop-free).

fntrace_bstrace_bs(bs : SessionGBranches, c : Int, t : Int, lab : Int, picks : SessionPicks) : SessionActs#

The steps of branch lab: the chooser's first message carries the label.

fntrace_bs_foundtrace_bs_found(bs : SessionGBranches, c : Int, t : Int, lab : Int, picks : SessionPicks)#

A choice's trace: the chooser's first message, carrying the label, then the branch.