## Formal Inference Rules Diagram: Dynamic Type System ### Overview The image displays a set of formal inference rules, likely from a programming language type system or formal logic system. The rules are presented in a standard mathematical notation with premises above a horizontal line and a conclusion below. The primary language of the notation is mathematical symbols; there is no natural language prose beyond the rule labels. ### Components/Axes The diagram is structured as a collection of six distinct inference rules, each with a label and a formal statement. 1. **Top Central Rule (Unnamed):** * **Position:** Centered at the top of the image. * **Content:** `Φ ⊢ V ⊆ V' : A ⊆ A' and Φ ⊢ M ⊆ M' : B ⊆ B'` * **Description:** This appears to be a composite statement or axiom, asserting two separate subset relations (`⊆`) under a context `Φ`. It relates terms `V` and `V'` of type `A` and `A'`, and terms `M` and `M'` of type `B` and `B'`. 2. **Rule: TmDynRefl** * **Position:** Top-left quadrant. * **Premises (Above Line):** `Γ ⊆ Γ' | Δ ⊆ Δ' ⊢ E ⊆ E' : T ⊆ T'` * **Conclusion (Below Line):** `Γ ⊆ Γ' | Δ ⊆ Δ' ⊢ E ⊆ E' : T ⊆ T'` * **Description:** This is a reflexivity rule. The conclusion is identical to the premise, stating that the relation is reflexive for the judgment `E ⊆ E' : T ⊆ T'` under contexts `Γ ⊆ Γ'` and `Δ ⊆ Δ'`. 3. **Rule: TmDynVar** * **Position:** Top-right quadrant. * **Premises (Above Line):** `Φ, x ⊆ x' : A ⊆ A', Φ' ⊢ x ⊆ x' : A ⊆ A'` * **Conclusion (Below Line):** `Φ, x ⊆ x' : A ⊆ A', Φ' ⊢ x ⊆ x' : A ⊆ A'` * **Description:** This rule deals with variable binding. It states that if a context `Φ` is extended with a variable relation `x ⊆ x' : A ⊆ A'` to form `Φ, x ⊆ x' : A ⊆ A', Φ'`, then the variable relation itself holds in that extended context. 4. **Rule: TmDynTrans** * **Position:** Middle-left. * **Premises (Above Line):** Two lines. * Line 1: `Γ ⊆ Γ' | Δ ⊆ Δ' ⊢ E ⊆ E' : T ⊆ T'` * Line 2: `Γ' ⊆ Γ'' | Δ' ⊆ Δ'' ⊢ E' ⊆ E'' : T' ⊆ T''` * **Conclusion (Below Line):** `Γ ⊆ Γ'' | Δ ⊆ Δ'' ⊢ E ⊆ E'' : T ⊆ T''` * **Description:** This is a transitivity rule. It states that if `E` is related to `E'` and `E'` is related to `E''`, then `E` is related to `E''`, with the contexts (`Γ`, `Δ`) and types (`T`) also combining transitively. 5. **Rule: TmDynValSubst** * **Position:** Middle-right. * **Premises (Above Line):** Two lines. * Line 1: `Φ ⊢ V ⊆ V' : A ⊆ A'` * Line 2: `Φ, x ⊆ x' : A ⊆ A', Φ' ⊢ E ⊆ E' : T ⊆ T'` * **Conclusion (Below Line):** `Φ ⊢ Ψ E[V/x] ⊆ E'[V'/x'] : T ⊆ T'` * **Description:** This is a value substitution rule. It allows substituting a value `V` (related to `V'`) for a variable `x` (related to `x'`) in a term `E` (related to `E'`), yielding a new related term `E[V/x]` (related to `E'[V'/x']`). The context `Φ` is preserved, while the extended context `Φ, x ⊆ x' : A ⊆ A', Φ'` is discharged. 6. **Rule: TmDynHole** * **Position:** Bottom-left. * **Premises (Above Line):** `Φ | • ⊆ • : B ⊆ B'` * **Conclusion (Below Line):** `Φ | • ⊆ • : B ⊆ B'` * **Description:** This rule concerns a "hole" (denoted by `•`). It states that the relation for a hole under context `Φ` and a second context (denoted by `|`) is reflexive. 7. **Rule: TmDynStkSubst** * **Position:** Bottom-right. * **Premises (Above Line):** Two lines. * Line 1: `Φ ⊢ M₁ ⊆ M₁' : B₁ ⊆ B₁'` * Line 2: `Φ | • ⊆ • : B₁ ⊆ B₁' ⊢ M₂ ⊆ M₂' : B₂ ⊆ B₂'` * **Conclusion (Below Line):** `Φ ⊢ Ψ M₂[M₁/•] ⊆ M₂'[M₁'/•] : B₂ ⊆ B₂'` * **Description:** This is a stack or hole substitution rule. It substitutes a term `M₁` (related to `M₁'`) for a hole `•` in a term `M₂` (related to `M₂'`), resulting in `M₂[M₁/•]` (related to `M₂'[M₁'/•]`). The type changes from `B₁` to `B₂`. ### Detailed Analysis * **Notation:** The rules use a consistent notation: * `Φ`, `Γ`, `Δ`, `Ψ`: Contexts or environments. * `⊆`: A subset or subtyping/relation symbol. * `:` : A separator, often between a term and its type. * `⊢`: The turnstile symbol, indicating "entails" or "proves". * `|`: A separator between different context components in some rules (TmDynRefl, TmDynTrans, TmDynHole, TmDynStkSubst). * `•`: Represents a "hole" or placeholder. * `[V/x]`: Standard notation for substitution of `V` for `x`. * **Structure:** Each rule follows the pattern: **Name** (e.g., `TmDynTrans`), followed by a horizontal line with premises above and the conclusion below. * **Relationships:** The rules form a coherent system. `TmDynRefl` and `TmDynTrans` establish the relation as a preorder. `TmDynVar` handles variable cases. `TmDynValSubst` and `TmDynStkSubst` are congruence or substitution rules, allowing the relation to be preserved under substitution of related values/terms into related contexts/holes. ### Key Observations 1. **Systematic Naming:** All rule names begin with the prefix `TmDyn`, suggesting they belong to a "Term Dynamic" subsystem or theory. 2. **Dual Contexts:** Several rules (TmDynRefl, TmDynTrans, TmDynHole, TmDynStkSubst) employ a two-part context separated by `|` (e.g., `Γ ⊆ Γ' | Δ ⊆ Δ'` or `Φ | • ⊆ •`). This may indicate separate tracking of different kinds of information (e.g., term-level vs. stack-level, or two different typing environments). 3. **Substitution Patterns:** Two distinct substitution rules are present: one for values into term variables (`TmDynValSubst`) and one for terms into holes (`TmDynStkSubst`). 4. **Hole Abstraction:** The use of `•` as a first-class syntactic entity that can be substituted into is a notable feature, common in systems modeling computation with contexts or continuations. ### Interpretation This diagram formally defines a **dynamic relation** (likely a behavioral type, bisimulation, or a form of contextual equivalence) between terms in a programming language or calculus. The "Dyn" in the rule names strongly points to "dynamic" semantics. * **What it defines:** The rules specify when two terms (`E` and `E'`, or `M` and `M'`) are considered related (`⊆`) under given contexts and with respect to their types. This relation is: * **Reflexive and Transitive** (from `TmDynRefl` and `TmDynTrans`), making it a preorder. * **Compatible with Variable Binding** (`TmDynVar`). * **Compatible with Substitution** (`TmDynValSubst`, `TmDynStkSubst`), meaning if two terms are related, substituting them into related contexts yields related results. This is the hallmark of a **logical relation** or a **bisimulation**. * **Why it matters:** Such formal systems are used to prove properties like type safety, contextual equivalence, or correct compilation for languages with dynamic features (e.g., gradual typing, dynamic linking, or security-typed languages). The rules provide the inductive definition needed for such proofs. * **Underlying Model:** The presence of a "hole" (`•`) and stack substitution (`TmDynStkSubst`) suggests the underlying calculus might be a **contextual calculus** or one where terms are placed into evaluation contexts (stacks). The relation may be defining when two terms behave the other same when placed in any compatible context. * **Peircean Analysis (Reading between the lines):** The notation `Φ ⊢ ...` versus `Γ | Δ ⊢ ...` hints at a separation of concerns within the system. `Φ` might represent a global or value-level context, while `Γ | Δ` could represent a split between term and continuation/stack contexts. The system is carefully designed to ensure that the dynamic relation is preserved under all the standard syntactic constructs (variables, substitution), which is essential for proving robust behavioral properties.