6.7. Components and decomposition
The statements of this section are in Logic/Compose.lean and
Logic/ComposeD1*.lean. They concern descriptions only; the symbol
\parallel below is the composite of descriptions, not the library's
parallel product.
-
Component[complete] -
Component.RulesOk[complete] -
Component.AgentOk[complete] -
Disjoint[complete] -
agentPar[complete] -
RuleD.par[complete] -
compose[complete] -
CompStep[complete]
A component P is a list of rules on data, each with a tag (none, written
\tau, or an action p!m, p?m on a port p, or a visible action), a
list of ports, a set of controls it owns, and for each control the ports its
nodes are linked to. Its rules are good when each is checked and linear, each
root of a redex has a node as child, each site of a redex lies under a node,
only owned controls occur, and every port of a node is linked to the outer
name its control prescribes. An agent of P is good when it is checked,
has one region, no sites and no inner names, its nodes are owned and
linked as prescribed, and its outer names are exactly the ports of P. P and Q are disjoint when no control is owned
by both.
For a list H of names, the composite agent is
a_1 \parallel_H a_2 \;=\; \mathrm{close}_{\mathrm d}(H;\, \mathrm{merge}_{\mathrm d}(a_1 \parallel_{\mathrm d} a_2)) .
The product r_1 \parallel_{\mathrm d} r_2 of two rules puts the two redexes side by
side as one wide redex, and likewise the reacta. The composite
P \parallel_K Q, for a list K of ports kept, hides every other port
(H_K), keeps each rule of either side whose tag is not an action on a
hidden port, and adds r_1 \parallel_{\mathrm d} r_2 with tag \tau for each rule
r_1 of P tagged p!m and r_2 of Q tagged p?m (or the
reverse) on a shared port p. A composite step with tag t from
(a_1, a_2) to (a_1', a_2') is: a reaction a_1 \to a_1' of P
tagged t, not an action on a hidden port, with a_2' = a_2; or the same
for Q; or t = \tau and reactions of P and Q tagged p!m and
p?m on a shared port.
Class: Component, Component.RulesOk, Component.AgentOk, RuleD.par, CompStep NEW; Disjoint FROM SOURCE; agentPar, compose UNBRIDGED.
Lean code for Definition6.7.1●8 definitions
Associated Lean declarations
-
Component[complete]
-
Component.RulesOk[complete]
-
Component.AgentOk[complete]
-
Disjoint[complete]
-
agentPar[complete]
-
RuleD.par[complete]
-
compose[complete]
-
CompStep[complete]
-
Component[complete] -
Component.RulesOk[complete] -
Component.AgentOk[complete] -
Disjoint[complete] -
agentPar[complete] -
RuleD.par[complete] -
compose[complete] -
CompStep[complete]
-
structuredefined in Logic/Compose.leancomplete
structure Component (M α Ctrl : Type) : Type
structure Component (M α Ctrl : Type) : Type
**NEW** (no counterpart in the sources; a tagged rule list with bookkeeping, needed to state which rules of two systems are joined). A component: a tagged rule set (half-rules carry port tags), its ports (the outer names of its agents), the controls it owns, and the FIXED PORT LINKING `portOf c`: the outer name each port of a `c`-node is linked to, in every agent and every rule of the component. The signature is shared (one control type), so disjointness of two components is a hypothesis on `own` (`Disjoint`), not a typing fact. Why the fixed linking: a redex's outer names are matched up to renaming, so a half-rule's name `p` says nothing about WHICH port it meets in a component's agent; only when the halves are put side by side (`RuleD.par`) does `p` get identified across them. With `portOf` the name `p` of a half-rule can only meet port `p`, so the identification is the agents' own, and D1 can hold. The price: a component has no internal links (every link is a port). Lifting this is future work.
Fields
rules : TRules (PAct M α) Ctrl
ports : List Nat
own : Ctrl → Bool
portOf : Ctrl → List Nat
-
defdefined in Logic/Compose.leancomplete
def RulesOk {M α Ctrl : Type} (S : Sig Ctrl) (C : Component M α Ctrl) : Bool
def RulesOk {M α Ctrl : Type} (S : Sig Ctrl) (C : Component M α Ctrl) : Bool
**Good rules**: each rule checked (linear), G1, sites under nodes, every control of redex and reactum owned by the component, ports linked as `portOf` says.
-
defdefined in Logic/Compose.leancomplete
def AgentOk {M α Ctrl : Type} (S : Sig Ctrl) (C : Component M α Ctrl) (a : BD Ctrl) : Bool
def AgentOk {M α Ctrl : Type} (S : Sig Ctrl) (C : Component M α Ctrl) (a : BD Ctrl) : Bool
**A good agent of the component**: checked, one region, no sites, no inner names, outer names exactly the ports, every control owned, ports linked as `portOf` says.
-
defdefined in Logic/Compose.leancomplete
def Disjoint {M α Ctrl : Type} (P Q : Component M α Ctrl) : Prop
def Disjoint {M α Ctrl : Type} (P Q : Component M α Ctrl) : Prop
**Disjoint control sets** (Birkedal et al. 2006, Def 1, ⊥): no control is owned by both.
-
defdefined in Logic/Compose.leancomplete
def agentPar {Ctrl : Type} (hide : List Nat) (a₁ a₂ : BD Ctrl) : BD Ctrl
def agentPar {Ctrl : Type} (hide : List Nat) (a₁ a₂ : BD Ctrl) : BD Ctrl
**UNBRIDGED** (built from `ppar`, `merge`, `close`). The composite agent: one region, the names `hide` closed.
-
defdefined in Logic/Compose.leancomplete
def par {Ctrl : Type} (r₁ r₂ : RuleD Ctrl) : RuleD Ctrl
def par {Ctrl : Type} (r₁ r₂ : RuleD Ctrl) : RuleD Ctrl
**NEW** (no counterpart in TR-580 or Milner's book: a product of two reaction rules; needed to make one rule out of an emitting and a receiving half-rule) and **UNBRIDGED** (uses `ppar`). The synchronisation of two half-rules: the wide redex `R₁ ∥ R₂`, the reactum `R₁′ ∥ R₂′`, and `η₁ ++ (η₂ shifted by m₁)`.
-
defdefined in Logic/Compose.leancomplete
def compose {M α : Type} [DecidableEq M] [DecidableEq α] {Ctrl : Type} (P Q : Component M α Ctrl) (keep : List Nat) : Component M α Ctrl
def compose {M α : Type} [DecidableEq M] [DecidableEq α] {Ctrl : Type} (P Q : Component M α Ctrl) (keep : List Nat) : Component M α Ctrl
**NEW** (a construction on rule lists; no counterpart in the sources). Synchronised composition `P ∥ Q` with the ports `keep` kept (all others closed). Theorems about it are about the rule list it produces.
-
defdefined in Logic/Compose.leancomplete
def CompStep {M α : Type} [DecidableEq M] [DecidableEq α] {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (P Q : Component M α Ctrl) (keep : List Nat) (t : Option (PAct M α)) {J₁ J₂ : Face} (a₁ a₁' : BigH S Face.origin J₁) (same₁ : Prop) (a₂ a₂' : BigH S Face.origin J₂) (same₂ : Prop) : Prop
def CompStep {M α : Type} [DecidableEq M] [DecidableEq α] {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (P Q : Component M α Ctrl) (keep : List Nat) (t : Option (PAct M α)) {J₁ J₂ : Face} (a₁ a₁' : BigH S Face.origin J₁) (same₁ : Prop) (a₂ a₂' : BigH S Face.origin J₂) (same₂ : Prop) : Prop
**One composite step, on the components**: `P` moves alone (tag kept), `Q` moves alone, or they synchronise on a shared port (`p!m` against `p?m`, either way round), tag τ. The idle side's data is unchanged.
-
D1Refute.d1_refuted[complete] -
D1Statement[complete]
REFUTED as first stated. The decomposition statement D1 says: for disjoint
components with good rules and good agents a_1, a_2, and every tag
t, the reactions tagged t of
\llbracket a_1 \parallel_{H_K} a_2 \rrbracket under the rules of
P \parallel_K Q are, up to \bumpeq, exactly the
\llbracket a_1' \parallel_{H_K} a_2' \rrbracket for the composite steps
from (a_1, a_2) to (a_1', a_2').
\neg\, \mathrm{D1} .
The countermodel has a \tau rule of P whose redex has an edge with no
port on it, and an agent of Q with such an edge: the composite reacts
and a_1 does not.
Rests on UNBRIDGED: agentPar, compose, hiddenPorts; NEW: BD.Fits, BD.outFace, CompStep, Component, Component.AgentOk, Component.RulesOk, D1Refute.sig, PAct and 1 more; not audited: D1Refute.K, agentAt.
Lean code for Theorem6.7.2●2 declarations
Associated Lean declarations
-
D1Refute.d1_refuted[complete]
-
D1Statement[complete]
-
D1Refute.d1_refuted[complete] -
D1Statement[complete]
-
theoremdefined in Logic/ComposeD1Refute.leancomplete
theorem d1_refuted : ¬D1Statement D1Refute.sig Unit Unit
theorem d1_refuted : ¬D1Statement D1Refute.sig Unit Unit
**D1 is REFUTED as stated.**
-
defdefined in Logic/Compose.leancomplete
def D1Statement {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : Prop
def D1Statement {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : Prop
**(D1) Decomposition** (OPEN; the bigraph content of option A; prior-art §6 "D1", APPARENTLY NEW for BRS, template Baldan et al. 2008 Lemma 3.3). For components with DISJOINT control sets (needed so that a rule of `P` cannot match a node of `Q`: every redex node then lies in one side), good rules (linear, G1, sites under nodes, own controls only, fixed port linking `portOf`) and good agents `a₁`, `a₂`, the tagged library reactions of the composite agent `⟦a₁ ∥ a₂⟧` under the composite rules are exactly the `CompStep`s, up to ≏: every composite reaction is ≏ to `⟦a₁′ ∥ a₂′⟧` for a component step `a₁ → a₁′`, `a₂ → a₂′` of that shape, and every such pair of component steps gives a composite reaction ≏ to `⟦a₁′ ∥ a₂′⟧`.
-
redexNoEdge[complete] -
redexNamesUsed[complete] -
Component.RedexOk[complete] -
D1Statement'[complete]
The redexes of a component are good when no redex has an edge and every
outer name of a redex is on a port of one of its nodes. The restatement
D1′ is D1 with the added hypotheses that the redexes of P and Q are
good and that \mathrm{faceOk}(a_1), \mathrm{faceOk}(a_2) hold, and, in
the direction from composite steps to reactions, that
\mathrm{faceOk}(a_1'), \mathrm{faceOk}(a_2') hold. D1′ is OPEN; each
added hypothesis is forced by a countermodel, TESTED by compiled evaluation
(Logic/Examples/D1Test.lean). The two theorems that follow are its
content for one rule at a time, for any list H of names. What remains
between them and D1′ is the bookkeeping of tags and rule lists: a rule of the
composite tagged t is a rule of P or of Q whose tag is not an action
on a hidden port, or t = \tau and the product of dual half-rules on a
shared port.
Class: redexNoEdge, redexNamesUsed, Component.RedexOk NEW; D1Statement' not audited.
Lean code for Definition6.7.3●4 definitions
Associated Lean declarations
-
redexNoEdge[complete]
-
redexNamesUsed[complete]
-
Component.RedexOk[complete]
-
D1Statement'[complete]
-
redexNoEdge[complete] -
redexNamesUsed[complete] -
Component.RedexOk[complete] -
D1Statement'[complete]
-
defdefined in Logic/ComposeD1.leancomplete
def redexNoEdge {Ctrl : Type} (r : RuleD Ctrl) : Bool
def redexNoEdge {Ctrl : Type} (r : RuleD Ctrl) : Bool
**The redex has no edge.** Under `portsFixed` every port is on an outer name, so an edge of a redex is IDLE; the library matches an idle redex edge to any idle edge of the agent, and the composite agent has idle edges the component does not (an idle edge of the other side; a hidden port no node is on).
-
defdefined in Logic/ComposeD1.leancomplete
def redexNamesUsed {Ctrl : Type} (r : RuleD Ctrl) : Bool
def redexNamesUsed {Ctrl : Type} (r : RuleD Ctrl) : Bool
**Every outer name of the redex is on a port of a redex node.** An outer name of the redex that is on no port (an idle name) is matched by the library to ANY link of the agent, so the fixed port linking does not constrain it: in the composite it can meet a link of the other side.
-
defdefined in Logic/ComposeD1.leancomplete
def RedexOk {M α Ctrl : Type} (C : Component M α Ctrl) : Bool
def RedexOk {M α Ctrl : Type} (C : Component M α Ctrl) : Bool
**Good redexes** of a component: no edge, no idle outer name.
-
defdefined in Logic/ComposeD1.leancomplete
def D1Statement' {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : Prop
def D1Statement' {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : Prop
**(D1′) Decomposition, restated** (OPEN). As `D1Statement`, with good redexes (`RedexOk`), `faceOk` agents, and `faceOk` successors in the second half.
-
localRule[complete] -
LocalRuleStatement[complete] -
RReact[complete]
A rule of one side in the composite agent. Let P, Q be disjoint with
good rules and good redexes, a_1, a_2 good agents with
\mathrm{faceOk}, and A = \llbracket a_1 \parallel_H a_2 \rrbracket.
Write \longrightarrow_r for reaction by the single rule r. For every
rule r of P:
A \longrightarrow_r A' \;\Longrightarrow\; \exists a_1'.\;\; \llbracket a_1 \rrbracket \longrightarrow_r \llbracket a_1' \rrbracket \;\wedge\; A' \bumpeq \llbracket a_1' \parallel_H a_2 \rrbracket ,
\llbracket a_1 \rrbracket \longrightarrow_r \llbracket a_1' \rrbracket \;\wedge\; \mathrm{faceOk}(a_1') \;\Longrightarrow\; \exists A'.\;\; A \longrightarrow_r A' \;\wedge\; A' \bumpeq \llbracket a_1' \parallel_H a_2 \rrbracket ,
In the first line the a_1' given is checked and fits the outer face of
a_1, and a_1' \parallel_H a_2 is checked and fits the face of A; in
the second line these four facts are assumed of a_1'. The same holds for
every rule of Q, with a_2 in place of a_1.
Rests on UNBRIDGED: agentPar; NEW: BD.Fits, BD.faceOk, BD.outFace, Component, Component.AgentOk, Component.RedexOk, Component.RulesOk, PAct and 2 more; not audited: agentAt.
Lean code for Theorem6.7.4●3 declarations
Associated Lean declarations
-
localRule[complete]
-
LocalRuleStatement[complete]
-
RReact[complete]
-
localRule[complete] -
LocalRuleStatement[complete] -
RReact[complete]
-
theoremdefined in Logic/ComposeD1Local.leancomplete
theorem localRule {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : LocalRuleStatement S M α
theorem localRule {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : LocalRuleStatement S M α
**A rule of one side in the composite agent** (`LocalRuleStatement`, PROVED).
-
defdefined in Logic/ComposeD1.leancomplete
def LocalRuleStatement {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : Prop
def LocalRuleStatement {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : Prop
**A rule of one side in the composite agent** (OPEN). For a rule `r` of `P` (any tag): the reactions of `⟦a₁ ∥ a₂⟧` by `r` are, up to ≏, the `⟦a₁′ ∥ a₂⟧` for the reactions `a₁ → a₁′` of `⟦a₁⟧` by `r`; and likewise for a rule of `Q` (the second pair). The splitting half needs disjoint controls (the redex's nodes are `P`'s), `sitesUnderNodes` (the parameter is `P`'s), `RedexOk` (no idle edge or name to meet `Q`).
-
abbrevdefined in Logic/ComposeD1.leancomplete
abbrev RReact {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (r : RuleD Ctrl) {J : Face} (a a' : BigH S Face.origin J) : Prop
abbrev RReact {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (r : RuleD Ctrl) {J : Face} (a a' : BigH S Face.origin J) : Prop
The library reaction by the single rule `r`.
The synchronisation rule in the composite agent. With the hypotheses and
notation of Theorem 6.7.4, for every rule r_1 of P and
r_2 of Q:
A \longrightarrow_{r_1 \parallel_{\mathrm d} r_2} A' \;\Longrightarrow\; \exists a_1'\, a_2'.\;\; \llbracket a_1 \rrbracket \longrightarrow_{r_1} \llbracket a_1' \rrbracket \;\wedge\; \llbracket a_2 \rrbracket \longrightarrow_{r_2} \llbracket a_2' \rrbracket \;\wedge\; A' \bumpeq \llbracket a_1' \parallel_H a_2' \rrbracket ,
\llbracket a_1 \rrbracket \longrightarrow_{r_1} \llbracket a_1' \rrbracket \;\wedge\; \llbracket a_2 \rrbracket \longrightarrow_{r_2} \llbracket a_2' \rrbracket \;\wedge\; \mathrm{faceOk}(a_1') \;\wedge\; \mathrm{faceOk}(a_2') \;\Longrightarrow\; \exists A'.\;\; A \longrightarrow_{r_1 \parallel_{\mathrm d} r_2} A' \;\wedge\; A' \bumpeq \llbracket a_1' \parallel_H a_2' \rrbracket ,
In the first line the a_1', a_2' given are checked and fit the outer
faces of a_1, a_2, and a_1' \parallel_H a_2' is checked and fits
the face of A; in the second line these facts are assumed.
Rests on UNBRIDGED: agentPar; NEW: BD.Fits, BD.faceOk, BD.outFace, Component, Component.AgentOk, Component.RedexOk, Component.RulesOk, PAct and 3 more; not audited: agentAt.
Lean code for Theorem6.7.5●2 declarations
Associated Lean declarations
-
syncRule[complete]
-
SyncRuleStatement[complete]
-
syncRule[complete] -
SyncRuleStatement[complete]
-
theoremdefined in Logic/ComposeD1Sync4.leancomplete
theorem syncRule {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : SyncRuleStatement S M α
theorem syncRule {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : SyncRuleStatement S M α
**The synchronisation rule in the composite agent** (`SyncRuleStatement`, PROVED).
-
defdefined in Logic/ComposeD1.leancomplete
def SyncRuleStatement {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : Prop
def SyncRuleStatement {Ctrl : Type} [DecidableEq Ctrl] (S : Sig Ctrl) (M α : Type) [DecidableEq M] [DecidableEq α] : Prop
**The synchronisation rule in the composite agent** (OPEN; the rule level of D1, for redexes WITH SITES). For a rule `r₁` of `P` and a rule `r₂` of `Q` (any tags): the reactions of `⟦a₁ ∥ a₂⟧` by `RuleD.par r₁ r₂` are, up to ≏, the `⟦a₁′ ∥ a₂′⟧` for the pairs of reactions `a₁ → a₁′` by `r₁` and `a₂ → a₂′` by `r₂`. First half: SPLITTING (an occurrence of the wide redex restricts to each side; the parameter `d` splits as `d₁ ∥ d₂` along `η₁ ++ (η₂ + m₁)`). Second half: JOINING.