March Docs

Actor.Theory

Actor.Theory: a model of an actor's mailbox, and laws about it.

The mailbox lives in the runtime (C, compiled) and the interpreter (OCaml); no March function implements it, so these laws are about this MODEL (lemmas design §4.2). They say what the runtime promises in specs/lang/actors.md, stated so they can be proved:

A1  one sender's messages are received in the order it sent them, and no
    other sender, deferral (a hot-deploy epoch hold), stash or a call
    waiting inside a handler reorders them;
A2  `Actor.call` takes only its own reply: a late reply to an earlier
    call cannot answer it;
A3  a monitor's `Down` is delivered at most once, and a full mailbox
    never drops it.

Senders, payloads, monitor refs and call ids are Ints. The runtime is tied to the model by trace conformance (design M8), which is what makes a guarantee proved (model) · tested (runtime) and never more.

The names are prefixed (ActorEnv, EnvMsg, QEnd, ...): March has one global type namespace, so a stdlib type named like a user's would collide.

Types

typeActorEnvActorEnv = EnvMsg(Int, Int) | EnvDown(Int) | EnvReply(Int, Int)#

What arrives in a mailbox: a message (sender, payload), a monitor's Down (monitor ref), or a reply to an Actor.call (call id, value).

typeActorQueueActorQueue = QEnd | QThen(ActorEnv, ActorQueue)#

A mailbox, oldest first.

typeActorMonsActorMons = MonEnd | MonThen(Int, ActorMons)#

The monitor refs still registered.

Functions

fnbounded_enqbounded_enq(limit : Int, q : ActorQueue, e : ActorEnv) : ActorQueue#

Enqueue into a mailbox holding at most limit messages: a full mailbox drops an ordinary message, never a Down.

fncall_keeps_otherscall_keeps_others(s : Int, id : Int, q : ActorQueue)#

A1c. A call waiting inside a handler takes only its reply: every sender's messages stay, in order.

fncall_replycall_reply(id : Int, q : ActorQueue) : Option(Int)#

The value of the first reply to call id, if one is queued.

fncall_reply_catcall_reply_cat(id : Int, xs : ActorQueue, ys : ActorQueue)#

A2. Once our reply is queued, nothing arriving later changes which reply we take.

fncall_reply_latercall_reply_later(id : Int, xs : ActorQueue, ys : ActorQueue)#

A2. With no reply of ours queued yet, the reply we take is the first among later arrivals.

fncall_succeedscall_succeeds(deadline : Int, t_reply : Int) : Bool#

A call with deadline deadline whose reply arrives at t_reply returns the reply.

fndeadline_lawdeadline_law(deadline : Int, t_reply : Int)#

A2. A call returns its reply only if the reply came by the deadline.

fndeath_qdeath_q(q : ActorQueue, ms : ActorMons, r : Int) : ActorQueue#

The watched actor dies: a registered monitor r gets its Down (past any mailbox limit).

fndown_at_most_oncedown_at_most_once(q : ActorQueue, ms : ActorMons, r : Int)#

A3. A monitor's Down is delivered at most once: delivering it removes the monitor, so a second death adds nothing.

fndown_never_droppeddown_never_dropped(limit : Int, q : ActorQueue, r : Int)#

A3. A full mailbox never drops a Down.

fndownsdowns(r : Int, q : ActorQueue) : Int#

How many Downs for monitor r are queued.

fndowns_catdowns_cat(r : Int, xs : ActorQueue, ys : ActorQueue)#

Downs in two queues add up.

fnenq_otherenq_other(s : Int, q : ActorQueue, f : {Int | _ != s}, p : Int)#

A1. Another sender's message does not change what s will receive, or its order.

fnenq_selfenq_self(s : Int, q : ActorQueue, p : Int)#

A1. A sender's new message is received after everything it sent before.

fnfrom_catfrom_cat(s : Int, xs : ActorQueue, ys : ActorQueue)#

A sender's messages in two queues, one after the other, are its messages in each, one after the other.

fnfrom_senderfrom_sender(s : Int, q : ActorQueue) : ActorQueue#

The messages from sender s, in queue order.

fnis_downis_down(e : ActorEnv) : Bool#

Whether an envelope is a monitor's Down.

fnmonitoredmonitored(ms : ActorMons, r : Int) : Bool#

Whether monitor r is still registered.

Laws

  • !monitored(unmonitor(ms, r), r) (lemma unmonitor_gone) proved
fnpayloadspayloads(q : ActorQueue) : List(Int)#

The messages' payloads, oldest first (what a conformance test compares with what was sent).

fnqcatqcat(xs : ActorQueue, ys : ActorQueue) : ActorQueue#

xs followed by ys.

Laws

  • qcat(xs, QEnd) == xs (lemma qcat_end) proved
fnqcat_endqcat_end(xs : ActorQueue) : {Unit | qcat(xs, QEnd) == xs}#

Appending nothing changes nothing.

fnqenqqenq(q : ActorQueue, e : ActorEnv) : ActorQueue#

Enqueue e at the back.

fnqlenqlen(q : ActorQueue) : Int#

How many envelopes are queued.

fnreplayreplay(held : ActorQueue, q : ActorQueue) : ActorQueue#

Replay messages set aside (a hot-deploy epoch hold, or a stash on become): they go in front, in the order they were set aside.

fnreplay_orderreplay_order(s : Int, held : ActorQueue, q : ActorQueue)#

A1b. Replaying held messages keeps each sender's order: the held ones first, then the rest.

fnstale_reply_ignoredstale_reply_ignored(id : Int, c : {Int | _ != id}, v : Int, q : ActorQueue)#

A2. A reply to another call, ahead of ours, is not taken as ours.

fnunmonitorunmonitor(ms : ActorMons, r : Int) : ActorMons#

Monitor r removed (demonitor, or the death path after delivering its Down).

Laws

  • !monitored(unmonitor(ms, r), r) (lemma unmonitor_gone) proved
fnunmonitor_goneunmonitor_gone(ms : ActorMons, r : Int) : {Unit | !monitored(unmonitor(ms, r), r)}#

A removed monitor is gone.

fnwithout_replywithout_reply(id : Int, q : ActorQueue) : ActorQueue#

The queue after a waiting call takes its reply: only that reply leaves; everything else stays, in arrival order.