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