locus: Blueprint

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.

Definition6.7.1
Statement uses 2
Statement dependency previews
Preview
Definition 6.2.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
used by 1✓L∃∀N

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
  • structure(4 fields)defined in Logic/Compose.lean
    complete
    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. 
    rules : TRules (PAct M α) Ctrl
    ports : List Nat
    own : Ctrl → Bool
    portOf : Ctrl → List Nat
  • defdefined in Logic/Compose.lean
    complete
    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.lean
    complete
    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.lean
    complete
    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.lean
    complete
    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.lean
    complete
    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.lean
    complete
    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.lean
    complete
    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. 
Theorem6.7.2
uses 1used by 1✓L∃∀N

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
  • theoremdefined in Logic/ComposeD1Refute.lean
    complete
    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.lean
    complete
    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₂′⟧`. 
Definition6.7.3
Statement uses 2
Statement dependency previews
Preview
Definition 6.2.4
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 2
Reverse dependency previews
Preview
Theorem 6.7.4
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
✓L∃∀N

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
  • defdefined in Logic/ComposeD1.lean
    complete
    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.lean
    complete
    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.lean
    complete
    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.lean
    complete
    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. 
Theorem6.7.4
uses 1used by 0✓L∃∀N

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
  • theoremdefined in Logic/ComposeD1Local.lean
    complete
    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.lean
    complete
    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.lean
    complete
    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`. 
Theorem6.7.5
uses 1used by 0✓L∃∀N

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
  • theoremdefined in Logic/ComposeD1Sync4.lean
    complete
    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.lean
    complete
    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.