## Type Theory Inference Rules ### Overview The image presents a collection of inference rules, likely related to type theory or programming language semantics. Each rule defines a condition under which a certain judgment (statement) can be derived. The rules cover various constructs, including sums, products, functions, thunks, and records. ### Components/Axes Each rule is structured as follows: - **Name:** A short identifier for the rule (e.g., "+ILCONG", "XICONG"). - **Premises:** Conditions that must be true for the rule to apply. These are written above a horizontal line. - **Conclusion:** The judgment that can be derived if the premises are true. This is written below the horizontal line. - **Judgments:** These typically have the form "Φ ⊢ V ⊑ V': A ⊑ A'", where: - Φ represents a typing context. - V and V' are values or expressions. - A and A' are types. - ⊑ denotes a subtyping relation. - ⊢ denotes derivability. ### Detailed Analysis or Content Details Here's a breakdown of each rule, transcribing the text and providing a brief explanation: **Row 1** * **+ILCONG** * Premise: Φ ⊢ V ⊑ V': A₁ ⊑ A₁' * Conclusion: Φ ⊢ inl V ⊑ inl V': A₁ + A₂ ⊑ A₁' + A₂' * Interpretation: If V is a subtype of V' with type A₁ a subtype of A₁', then inl V is a subtype of inl V' with type A₁ + A₂ a subtype of A₁' + A₂'. This rule handles the left injection of a sum type. * **+IRCONG** * Premise: Φ ⊢ V ⊑ V': A₂ ⊑ A₂' * Conclusion: Φ ⊢ inr V ⊑ inr V': A₁ + A₂ ⊑ A₁' + A₂' * Interpretation: If V is a subtype of V' with type A₂ a subtype of A₂', then inr V is a subtype of inr V' with type A₁ + A₂ a subtype of A₁' + A₂'. This rule handles the right injection of a sum type. **Row 2** * **+ECONG** * 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' * Interpretation: This rule handles the case expression for sum types. It states that if V is a subtype of V', and the branches E₁ and E₂ are subtypes of E₁' and E₂' respectively, then the case expression is well-typed. * **0ECONG** * Premise: Φ ⊢ V ⊑ V': 0 ⊑ 0 * Conclusion: Φ ⊢ abort V ⊑ abort V': T ⊑ T' * Interpretation: This rule deals with the `abort` expression, which likely represents a non-returning computation. **Row 3** * **1ICONG** * Conclusion: Φ ⊢ () ⊑ (): 1 ⊑ 1 * Interpretation: This rule states that the unit value () is a subtype of itself, with type 1 being a subtype of itself. * **1ECONG** * Premise: Φ ⊢ V ⊑ V': 1 ⊑ 1 * Premise: Φ ⊢ E ⊑ E': T ⊑ T' * Conclusion: Φ ⊢ split V to ().E ⊑ split V' to ().E': T ⊑ T' * Interpretation: This rule handles the `split` expression for the unit type. **Row 4** * **XICONG** * Premises: * Φ ⊢ V₁ ⊑ V₁': A₁ ⊑ A₁' * Φ ⊢ V₂ ⊑ V₂': A₂ ⊑ A₂' * Conclusion: Φ ⊢ (V₁, V₂) ⊑ (V₁', V₂'): A₁ × A₂ ⊑ A₁' × A₂' * Interpretation: If V₁ is a subtype of V₁' and V₂ is a subtype of V₂', then the pair (V₁, V₂) is a subtype of (V₁', V₂'). This rule handles the introduction of product types. * **→ICONG** * Premise: Φ, x ⊑ x': A ⊑ A' ⊢ M ⊑ M': B ⊑ B' * Conclusion: Φ ⊢ λx:A.M ⊑ λx':A'.M': A → B ⊑ A' → B' * Interpretation: This rule handles lambda abstraction. If M is a subtype of M' under the assumption that x is a subtype of x', then the lambda abstraction λx:A.M is a subtype of λx':A'.M'. **Row 5** * **XECONG** * 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' * Interpretation: This rule handles the `split` expression for product types. * **→ECONG** * Premises: * Φ ⊢ M ⊑ M': A → B ⊑ A' → B' * Φ ⊢ V ⊑ V': A ⊑ A' * Conclusion: Φ ⊢ M V ⊑ M' V': B ⊑ B' * Interpretation: This rule handles function application. If M is a subtype of M' and V is a subtype of V', then M V is a subtype of M' V'. **Row 6** * **UICONG** * Premise: Φ ⊢ M ⊑ M': B ⊑ B' * Conclusion: Φ ⊢ thunk M ⊑ thunk M': UB ⊑ UB' * Interpretation: This rule handles the introduction of thunks (delayed computations). * **UECONG** * Premise: Φ ⊢ V ⊑ V': UB ⊑ UB' * Conclusion: Φ ⊢ force V ⊑ force V': B ⊑ B' * Interpretation: This rule handles the `force` operation on thunks, evaluating the delayed computation. **Row 7** * **FICONG** * Premise: Φ ⊢ V ⊑ V': A ⊑ A' * Conclusion: Φ ⊢ ret V ⊑ ret V': FA ⊑ FA' * Interpretation: This rule handles the `ret` operation, likely related to a monadic type (F). * **FECONG** * Premises: * Φ ⊢ M ⊑ M': FA ⊑ FA' * Φ, x ⊑ x': A ⊑ A' ⊢ N ⊑ N': B ⊑ B' * Conclusion: Φ ⊢ bind x ← M; N ⊑ bind x' ← M'; N': B ⊑ B' * Interpretation: This rule handles the `bind` operation, likely related to a monadic type (F). **Row 8** * **TICONG** * Conclusion: Φ ⊢ {} ⊑ {}: T ⊑ T * Interpretation: This rule states that the empty record {} is a subtype of itself, with type T being a subtype of itself. * **&ICONG** * Premises: * Φ ⊢ M₁ ⊑ M₁': B₁ ⊑ B₁' * Φ ⊢ M₂ ⊑ M₂': B₂ ⊑ B₂' * Conclusion: Φ ⊢ {π → M₁ | π' → M₂} ⊑ {π → M₁' | π' → M₂'}: B₁ & B₂ ⊑ B₁' & B₂' * Interpretation: This rule handles record extension. **Row 9** * **&ECONG** * Premise: Φ ⊢ M ⊑ M': B₁ & B₂ ⊑ B₁' & B₂' * Conclusion: Φ ⊢ πM ⊑ πM': B₁ ⊑ B₁' * Interpretation: This rule handles record field access. * **&E'CONG** * Premise: Φ ⊢ M ⊑ M': B₁ & B₂ ⊑ B₁' & B₂' * Conclusion: Φ ⊢ π'M ⊑ π'M': B₂ ⊑ B₂' * Interpretation: This rule handles record field access. ### Key Observations * The rules define a subtyping relation (⊑) between values and types. * The rules cover common type theory constructs like sums, products, functions, and records. * The rules appear to be part of a formal system for verifying the correctness of programs. * The presence of "thunk" and "force" suggests a system that supports lazy evaluation. * The presence of "ret" and "bind" suggests a system that incorporates monadic types. ### Interpretation The inference rules define a type system that ensures type safety and allows for subtyping. The rules specify how to derive judgments about the relationships between values, expressions, and types. The system likely aims to prevent runtime errors by ensuring that programs adhere to the specified type constraints. The inclusion of features like thunks and monads suggests a sophisticated type system capable of handling advanced programming paradigms. The rules collectively define a formal system for reasoning about the types and behavior of programs.

\n ## Mathematical Formulas: Congruence Relations ### Overview The image presents a collection of mathematical formulas, seemingly related to congruence relations and logical operations. The formulas are arranged in a grid-like structure, each labeled with a prefix like "HlCong", "IrCong", etc. The notation involves symbols from logic and set theory, including quantifiers, implication, and set membership. ### Components/Axes There are no axes in the traditional sense. Instead, each formula is labeled with a unique identifier at the beginning of the line (e.g., "HlCong", "IrCong", "ECong"). The formulas themselves consist of logical expressions and set-theoretic notation. The image is organized into a grid of these formulas. ### Detailed Analysis or Content Details Here's a transcription of each formula, along with a breakdown of the symbols where possible. Note that precise interpretation requires domain expertise in mathematical logic. 1. **HlCong:** Φ + V ⊆ V': A₁ ⊆ A₂ 2. **IrCong:** Φ + V ⊆ V': A₂ ⊆ A₁ 3. **ECong:** Φ + V ⊆ V': A₁ + A₂ ⊆ A₁ + A₂ 4. **0ECong:** Φ + V ⊆ V': 0 ⊆ 0 5. **1ECong:** Φ + V ⊆ V': 1 ⊆ 1 6. **11Cong:** Φ + 0 ⊆ 0: 1 ⊆ 1 7. **XICong:** Φ + V ⊆ V': A₁ ⊆ A₂ 8. **XECong:** Φ + V ⊆ V': A₁ + A₂ ⊆ A₁ + A₂ 9. **UICong:** Φ + l ⊆ M: B ⊆ B' 10. **FECong:** Φ + V ⊆ V': A ⊆ A' 11. **FICong:** Φ + V ⊆ V': A ⊆ A' 12. **TICong:** Φ + l ⊆ {}: T ⊆ T 13. **&ECong:** Φ + V + M ⊆ M': B₁ ⊆ B₂ 14. **&IECong:** Φ + V + M ⊆ M': B₂ ⊆ B₁ 15. **in1 V ⊆ in1 V': A₁ + A₂ ⊆ A₁ + A₂** 16. **in2 V ⊆ in2 V': A₁ + A₂ ⊆ A₁ + A₂** 17. **case V{x₁ E₁ | x₂ E₂}: T** 18. **abort V ⊆ abort V': T** 19. **split V to ( ) ⊆ split V to ( ): E' ⊆ T** 20. **→Cong:** Φ, x ⊆ X': A ⊆ A' | Ψ + M ⊆ M': B ⊆ B' 21. **→ECong:** Φ + Ψ + x ⊆ x': A ⊆ A' | Ψ + M ⊆ M': A → B ⊆ A → B' 22. **UECong:** Φ + V ⊆ V': U ⊆ U' 23. **thunk M ⊆ thunk M': U ⊆ U'** 24. **force V ⊆ force V': B ⊆ B'** 25. **bind x ⊆ bind x': M ⊆ N** 26. **+ x + M ⊆ M': B₁ ⊆ B₂** 27. **+ x + M ⊆ M': B₂ ⊆ B₁** 28. **+ x + { } ⊆ {}: T** 29. **+ x + M ⊆ M': B₁ ⊆ B₂** 30. **+ x + M ⊆ M': B₂ ⊆ B₁** The symbols used include: * Φ, Ψ: Likely represent logical formulas or sets. * V, V': Variables or sets. * ⊆: Subset relation. * A₁, A₂, B₁, B₂: Sets. * E₁, E₂: Elements or conditions. * x, y: Variables. * M, M', N: Sets. * 0, 1: Possibly representing empty set and universal set, respectively. * →: Implication. * +: Set union or addition. * {}: Empty set. * T: Possibly representing a truth value or a set. * ⊆: Subset relation. ### Key Observations The formulas appear to be exploring different properties of congruence relations, potentially within a formal system or programming language context. The prefixes (e.g., "HlCong", "IrCong") likely denote different rules or theorems. The repeated use of the subset relation (⊆) suggests a focus on set-theoretic properties. The formulas involving "in", "case", "abort", "split", "thunk", "force", and "bind" hint at operations related to computation or program evaluation. ### Interpretation The image presents a formalization of congruence relations, likely within a logical or computational framework. The formulas define how these relations behave under various operations and conditions. The systematic naming convention (e.g., "HlCong", "IrCong") suggests a structured approach to defining and proving properties of congruence. The presence of terms like "thunk" and "force" indicates a possible connection to functional programming or lazy evaluation. The overall purpose seems to be to establish a set of axioms or rules governing congruence relations, which could be used for reasoning about program correctness or formal verification. The formulas are highly abstract and require specialized knowledge to fully understand their meaning and implications. The image is a collection of facts or data, and does not contain any trends or anomalies. It is a static representation of logical statements.

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

## Logical Inference Rules: Type System Congruence and Inference Rules ### Overview The image presents a formal system of logical inference rules, likely for a type system or programming language semantics. It includes rules for congruence (⊢), inference (⊨), and operational semantics (e.g., case analysis, splitting, binding). The rules are organized into labeled sections (e.g., `+IlCong`, `+ECong`, `+IrCong`), each defining relationships between terms, types, and contexts. ### Components/Axes - **Section Headers**: - `+IlCong`, `+ECong`, `+IrCong`, `1ICong`, `×ICong`, `→ICong`, `×ECong`, `→ECong`, `UICong`, `UECong`, `FICong`, `FECong`, `&ICong`, `&ECong`, `+TICong`, `+TICong`. - **Logical Constructs**: - Terms (`V`, `V'`, `A`, `A'`, `x`, `x'`, `y`, `y'`, `M`, `M'`, `N`, `N'`, `E`, `E'`, `T`, `T'`, `B`, `B'`, `B₁`, `B₂`, `B₁'`, `B₂'`, `B₁ & B₂`, `B₁' & B₂'`). - Contexts (`Φ`, `Ψ`). - Type/Term Relationships (e.g., `V ⊢ V' : A₁`, `Φ ⊢ V ⊨ V' : A₁`). - **Operational Semantics**: - Case analysis (`case V{x₁.E₁ | x₂.E₂}`). - Splitting (`split V to (x).E`). - Binding (`bind x ← M; N`). - Force (`force V : B`). - Ret (`ret V`). ### Detailed Analysis 1. **Congruence Rules**: - `+IlCong`: If `Φ ⊢ V ⊢ V' : A₁` and `Φ ⊢ inl V ⊢ inl V' : A₁ + A₂`, then `Φ ⊢ V ⊢ V' : A₁`. - `+ECong`: If `Φ ⊢ V ⊢ V' : A₁ + A₂`, `Φ, x₁ ⊢ x₁' : A₁`, `Φ, x₂ ⊢ x₂' : A₂`, `Φ, x₁.E₁ ⊢ E'₁ : T`, and `Φ, x₂.E₂ ⊢ E'₂ : T`, then `Φ ⊢ case V{x₁.E₁ | x₂.E₂} ⊢ case V{x₁'.E₁' | x₂'.E₂'} : T`. - `1ICong`: `Φ ⊢ () ⊢ () : 1`. - `×ICong`: If `Φ ⊢ V₁ ⊢ V₁' : A₁` and `Φ ⊢ V₂ ⊢ V₂' : A₂`, then `Φ ⊢ (V₁, V₂) ⊢ (V₁', V₂') : A₁ × A₂`. - `→ICong`: If `Φ, x ⊢ x' : A` and `Φ ⊢ M ⊢ M' : B`, then `Φ ⊢ λx:A.M ⊢ λx':A'.M' : A → B`. 2. **Inference Rules**: - `+IrCong`: If `Φ ⊢ V ⊢ V' : A₂`, then `Φ ⊢ inr V ⊢ inr V' : A₁ + A₂`. - `0ECong`: `Φ ⊢ V ⊢ V' : 0`. - `×ECong`: If `Φ ⊢ V ⊢ V' : A₁ × A₂`, `Φ, x ⊢ x' : A₁`, `Φ, y ⊢ y' : A₂`, and `Φ ⊢ split V to (x).E ⊢ split V' to (x').E' : T`, then `Φ ⊢ V ⊢ V' : A₁ × A₂`. - `FECong`: If `Φ ⊢ V ⊢ V' : A` and `Φ ⊢ ret V ⊢ ret V' : FA`, then `Φ ⊢ V ⊢ V' : A`. 3. **Operational Rules**: - `UICong`: If `Φ ⊢ M ⊢ M' : B`, then `Φ ⊢ think M ⊢ think M' : UB`. - `UECong`: If `Φ ⊢ V ⊢ V' : UB`, then `Φ ⊢ force V ⊢ force V' : B`. - `&ICong`: If `Φ ⊢ M₁ ⊢ M₁' : B₁` and `Φ ⊢ M₂ ⊢ M₂' : B₂`, then `Φ ⊢ {π ↦ M₁ | π' ↦ M₂} ⊢ {π ↦ M₁' | π' ↦ M₂'} : B₁ & B₂`. - `&ECong`: If `Φ ⊢ M ⊢ M' : B₁ & B₂`, then `Φ ⊢ πM ⊢ π'M' : B₁` and `Φ ⊢ πM ⊢ π'M' : B₂`. ### Key Observations - **Structural Consistency**: Rules for sums (`A₁ + A₂`), products (`A₁ × A₂`), and function types (`A → B`) are systematically defined. - **Contextual Dependence**: Most rules require contextual assumptions (`Φ`, `Ψ`) to ensure type safety. - **Operational Semantics**: Case analysis, splitting, and binding rules define how terms evaluate under specific conditions. ### Interpretation This system formalizes a type-theoretic framework, likely for a dependently typed language or proof assistant. The rules ensure that: 1. **Type Safety**: Congruence rules (`+IlCong`, `+ECong`) preserve type relationships under substitution. 2. **Operational Correctness**: Rules like `case`, `split`, and `bind` define deterministic evaluation strategies. 3. **Context Management**: Hypothetical contexts (`Φ`, `Ψ`) track assumptions, ensuring soundness in inference. The absence of numerical data or trends suggests this is a theoretical framework rather than empirical analysis. The rules collectively enforce consistency between syntactic structures and their semantic interpretations, critical for verifying program correctness or type soundness.