\n ## Formal Inference Rules: Type System Congruence Rules ### Overview The image displays a collection of formal inference rules, likely from a programming language type system or logic system. These rules define congruence relations (denoted by `⊆`) for various type and term constructors. Each rule is presented in a standard "premises over conclusion" format separated by a horizontal line, with the rule name in small caps above. The notation suggests a system dealing with subtyping, session types, or behavioral types, given the presence of labels like `inl`, `inr`, `case`, `split`, `thunk`, `force`, `ret`, `bind`, and channel types (denoted by `!` and `?`). ### Components/Axes The image is a single, dense block of mathematical text. There are no traditional axes, legends, or charts. The components are the individual inference rules themselves, arranged in a roughly grid-like pattern. **Notation Conventions Observed:** - **Judgments:** The primary judgment form appears to be `Φ ⊢ V ⊆ V' : A ⊆ A'` or `Φ | Ψ ⊢ M ⊆ M' : T ⊆ T'`, indicating that under context `Φ` (and possibly `Ψ`), term/value `V` is related to `V'` with type `A` related to `A'`. - **Contexts:** `Φ` and `Ψ` are contexts, likely typing environments or session environments. - **Types:** `A`, `B`, `T` represent types. Constructors include: - Sum types: `A₁ + A₂` - Product types: `A₁ × A₂` - Function types: `A → B` - Unit type: `1` - Zero type: `0` - Recursive/Universal types: `UB` (possibly a boxed or universal type) - Effect/Session types: `FA` (possibly a framed or effect type), `!A`, `?A` (output/input types for channels) - Tuple/Record types: `{π₁ ↦ M₁, π₂ ↦ M₂}` - **Terms/Values:** `V`, `E`, `M`, `N` represent terms or values. Constructors include: - Injections: `inl V`, `inr V` - Case analysis: `case V {x₁.E₁ | x₂.E₂}` - Pairs: `(V₁, V₂)` - Split (destructuring pairs): `split V to (x,y).E` - Lambda abstraction: `λx.A.M` - Application: `M V` - Thunk/Force: `thunk M`, `force V` - Return/Bind (monadic): `ret V`, `bind x ← M; N` - Channel operations: `π M`, `π' M` (possibly send/receive on channel π) - **Relation Symbol:** `⊆` is used throughout, suggesting a subtyping, simulation, or behavioral subtyping relation. ### Detailed Analysis: Rule-by-Rule Transcription The rules are processed in reading order (left to right, top to bottom). **Row 1:** 1. **+ICong** (Top-Left) * **Premise:** `Φ ⊢ V ⊆ V' : A₁ ⊆ A₁'` * **Conclusion:** `Φ ⊢ inl V ⊆ inl V' : A₁ + A₂ ⊆ A₁' + A₂'` * **Description:** Congruence for left injection into a sum type. 2. **+ICong** (Top-Right) * **Premise:** `Φ ⊢ V ⊆ V' : A₂ ⊆ A₂'` * **Conclusion:** `Φ ⊢ inr V ⊆ inr V' : A₁ + A₂ ⊆ A₁' + A₂'` * **Description:** Congruence for right injection into a sum type. **Row 2:** 3. **+ECong** (Left) * **Premises:** * `Φ ⊢ V ⊆ V' : A₁ + A₂ ⊆ A₁' + A₂'` * `Φ, x₁ ⊆ x₁' : A₁ ⊆ A₁' | Ψ ⊢ E₁ ⊆ E₁' : T ⊆ T'` * `Φ, x₂ ⊆ x₂' : A₂ ⊆ A₂' | Ψ ⊢ E₂ ⊆ E₂' : T ⊆ T'` * **Conclusion:** `Φ | Ψ ⊢ case V {x₁.E₁ | x₂.E₂} ⊆ case V' {x₁'.E₁' | x₂'.E₂'} : T ⊆ T'` * **Description:** Congruence for case analysis (elimination) on a sum type. 4. **0ECong** (Right) * **Premise:** `Φ ⊢ V ⊆ V' : 0 ⊆ 0` * **Conclusion:** `Φ | Ψ ⊢ abort V ⊆ abort V' : T ⊆ T'` * **Description:** Congruence for aborting from the zero (empty) type. **Row 3:** 5. **1ICong** (Left) * **Premise:** (None shown, likely an axiom) * **Conclusion:** `Φ ⊢ () ⊆ () : 1 ⊆ 1` * **Description:** Congruence for the unit value. 6. **1ECong** (Right) * **Premises:** * `Φ ⊢ V ⊆ V' : 1 ⊆ 1` * `Φ | Ψ ⊢ E ⊆ E' : T ⊆ T'` * **Conclusion:** `Φ | Ψ ⊢ split V to ().E ⊆ split V' to ().'E' : T ⊆ T'` * **Description:** Congruence for splitting (eliminating) the unit type. **Row 4:** 7. **×ICong** (Left) * **Premises:** * `Φ ⊢ V₁ ⊆ V₁' : A₁ ⊆ A₁'` * `Φ ⊢ V₂ ⊆ V₂' : A₂ ⊆ A₂'` * **Conclusion:** `Φ ⊢ (V₁, V₂) ⊆ (V₁', V₂') : A₁ × A₂ ⊆ A₁' × A₂'` * **Description:** Congruence for pair construction. 8. **→ICong** (Right) * **Premises:** * `Φ, x ⊆ x' : A ⊆ A' | Ψ ⊢ M ⊆ M' : B ⊆ B'` * **Conclusion:** `Φ | Ψ ⊢ λx.A.M ⊆ λx'.A'.M' : A → B ⊆ A' → B'` * **Description:** Congruence for lambda abstraction (function introduction). **Row 5:** 9. **×ECong** (Left) * **Premises:** * `Φ ⊢ V ⊆ V' : A₁ × A₂ ⊆ A₁' × A₂'` * `Φ, x ⊆ x' : A₁ ⊆ A₁', y ⊆ y' : A₂ ⊆ A₂' | Ψ ⊢ E ⊆ E' : T ⊆ T'` * **Conclusion:** `Φ | Ψ ⊢ split V to (x,y).E ⊆ split V' to (x',y').E' : T ⊆ T'` * **Description:** Congruence for splitting (eliminating) a pair. 10. **→ECong** (Right) * **Premises:** * `Φ | Ψ ⊢ M ⊆ M' : A → B ⊆ A' → B'` * `Φ ⊢ V ⊆ V' : A ⊆ A'` * **Conclusion:** `Φ | Ψ ⊢ M V ⊆ M' V' : B ⊆ B'` * **Description:** Congruence for function application. **Row 6:** 11. **UICong** (Left) * **Premise:** `Φ | ⊢ M ⊆ M' : B ⊆ B'` * **Conclusion:** `Φ ⊢ thunk M ⊆ thunk M' : UB ⊆ UB'` * **Description:** Congruence for creating a thunk (suspension). 12. **UECong** (Right) * **Premise:** `Φ ⊢ V ⊆ V' : UB ⊆ UB'` * **Conclusion:** `Φ | ⊢ force V ⊆ force V' : B ⊆ B'` * **Description:** Congruence for forcing a thunk. **Row 7:** 13. **FICong** (Left) * **Premise:** `Φ ⊢ V ⊆ V' : A ⊆ A'` * **Conclusion:** `Φ | ⊢ ret V ⊆ ret V' : FA ⊆ FA'` * **Description:** Congruence for the `ret` (return) operation, likely in a monadic or effectful system. 14. **FECong** (Right) * **Premises:** * `Φ | Ψ ⊢ M ⊆ M' : FA ⊆ FA'` * `Φ, x ⊆ x' : A ⊆ A' | ⊢ N ⊆ N' : B ⊆ B'` * **Conclusion:** `Φ | Ψ ⊢ bind x ← M; N ⊆ bind x' ← M'; N' : B ⊆ B'` * **Description:** Congruence for the `bind` operation, sequencing monadic/effectful computations. **Row 8:** 15. **!ICong** (Left) * **Premise:** `Φ | Ψ ⊢ {} ⊆ {} : T ⊆ T` * **Conclusion:** `Φ | Ψ ⊢ {} ⊆ {} : T ⊆ T` * **Description:** This rule appears to be an axiom or identity for an empty tuple or record. The notation is unusual; the premise and conclusion are identical. It might represent a base case for a structural rule. 16. **&ICong** (Right) * **Premises:** * `Φ | Ψ ⊢ M₁ ⊆ M₁' : B₁ ⊆ B₁'` * `Φ | Ψ ⊢ M₂ ⊆ M₂' : B₂ ⊆ B₂'` * **Conclusion:** `Φ | Ψ ⊢ {π₁ ↦ M₁, π₁' ↦ M₂} ⊆ {π₁ ↦ M₁', π₁' ↦ M₂'} : B₁ & B₂ ⊆ B₁' & B₂'` * **Description:** Congruence for constructing a record or tuple with labeled fields (`π₁`, `π₁'`). The type constructor `&` likely denotes a product/record type. **Row 9:** 17. **&ECong** (Left) * **Premise:** `Φ | Ψ ⊢ M ⊆ M' : B₁ & B₂ ⊆ B₁' & B₂'` * **Conclusion:** `Φ | Ψ ⊢ πM ⊆ πM' : B₁ ⊆ B₁'` * **Description:** Congruence for projecting the first field (`π`) from a record. 18. **&'ECong** (Right) * **Premise:** `Φ | Ψ ⊢ M ⊆ M' : B₁ & B₂ ⊆ B₁' & B₂'` * **Conclusion:** `Φ | Ψ ⊢ π'M ⊆ π'M' : B₂ ⊆ B₂'` * **Description:** Congruence for projecting the second field (`π'`) from a record. ### Key Observations 1. **Systematic Naming:** Rule names follow a clear pattern: a type constructor symbol (`+`, `×`, `→`, `1`, `0`, `U`, `F`, `!`, `&`) followed by `I` (Introduction) or `E` (Elimination) and `Cong` (Congruence). 2. **Context Splitting:** Several rules (e.g., `+ECong`, `×ECong`, `→ICong`, `FECong`) split the context (`Φ | Ψ`), suggesting a separation between different kinds of assumptions (e.g., linear vs. affine, or session vs. value). 3. **Consistent Relation:** The `⊆` relation is applied uniformly to both terms and types in the judgments, indicating it is likely a behavioral subtyping or simulation relation that relates both the structure and behavior of programs. 4. **Effectful Computation:** The presence of `FICong`/`FECong` (for `ret`/`bind`) and `UICong`/`UECong` (for `thunk`/`force`) strongly suggests the system models computational effects, possibly monadic or involving suspended computations. 5. **Channel/Session Types:** The `!` and `?` in rule names (though only `!ICong` is fully visible) and the use of `π` for projection in `&ECong` rules hint at a connection to session-typed programming, where `!` and `?` denote output and input actions. ### Interpretation This image presents the **congruence rules for a behavioral type system**. These rules are the foundational logical axioms that define how the subtyping/simulation relation (`⊆`) is preserved under each language construct. * **What it demonstrates:** The rules collectively define what it means for one program to be a "safe substitute" for another in the presence of various programming language features (sums, products, functions, effects, records). They ensure that if two values/types are related, then the programs built from them using these constructors are also related. * **How elements relate:** Each rule is a self-contained logical implication. The premises state the conditions under which the conclusion holds. The entire set forms a **compositional definition** of the `⊆` relation. For example, to check if a `case` expression is related to another, you use the `+ECong` rule, which reduces the problem to checking the relation on the scrutinized value and both branch bodies. * **Notable patterns/anomalies:** * The `!ICong` rule is anomalous as its premise and conclusion are identical, making it an axiom of reflexivity for the empty structure `{}`. * The system appears to be **syntax-directed**, meaning the rules are organized by the syntactic form of the term in the conclusion, which is typical for type systems and proof systems. * The notation is dense and assumes familiarity with formal methods in programming language semantics. The use of `⊆` for what might traditionally be written as `<:` (subtyping) or `≤` (simulation) is a specific notational choice of this particular system. In essence, this is a technical specification sheet for the core congruence lemmas of a sophisticated type system, likely intended for researchers or implementers working on formal verification, programming language design, or session-typed concurrency.