## Formal Type System Specification: Recursive Types with Roll/Unroll ### Overview The image presents a formal specification of a type system featuring recursive types, distinguished between value types and computation types. It includes syntactic definitions, typing inference rules, and axioms for recursive type equivalence. The content is purely mathematical/logical notation with no natural language prose beyond labels. ### Components/Axes The document is structured into several distinct sections: 1. **Syntactic Categories (Top Section):** Defines the grammar for the type system. * **Value Types (A):** `A + ::= μX.A | X` and `- ::= ?` * **Computation Types (B):** `B + ::= νY.B | Y` and `- ::= ¡` * **Values (V):** `V + ::= roll_{μX.A} V` and `- ::= ⟨A ↩ A⟩V` * **Terms (M):** `M + ::= roll_{νY.B} M | unroll M` and `- ::= ⟨B ↩ B⟩M` * **Both (E):** `E + ::= unroll V to roll x.E` 2. **Inference Rules (Middle Section):** A set of 10 horizontal inference rules, each with premises above a line and a conclusion below. They are labeled: `μI`, `μE`, `νI`, `νE`, `μICONG`, `μECONG`, `νICONG`, `νECONG`. 3. **Recursive Type Axioms (Bottom Section):** A table defining equivalence relations (`β` and `η`) for the two recursive type constructors (`μ` and `ν`). ### Detailed Analysis #### 1. Syntactic Definitions * **Value Types (A):** Represent types of values. Can be a recursive type `μX.A` (mu-type) or a type variable `X`. The `-` production `?` likely represents an unknown or error type. * **Computation Types (B):** Represent types of computations. Can be a co-recursive type `νY.B` (nu-type) or a type variable `Y`. The `-` production `¡` (inverted exclamation mark) likely represents a computation effect or divergence. * **Values (V):** The `roll` constructor packages a value into a recursive type `μX.A`. The `-` production `⟨A ↩ A⟩V` is unclear from the image alone; the symbol `↩` may denote a coercion or injection. * **Terms (M):** The `roll` constructor packages a term into a co-recursive type `νY.B`. The `unroll` destructor unfolds a recursive type. The `-` production `⟨B ↩ B⟩M` mirrors the value production. * **Both (E):** The `unroll V to roll x.E` construct appears to be a specific term for rolling a recursive value within a specific scope `x`. #### 2. Inference Rules (Transcribed) The rules use a typing judgment `Γ | Δ ⊢ ... : ...` where `Γ` likely types values and `Δ` types computations. * **μI (Mu Introduction):** * Premise: `Γ ⊢ V : A[μX.A/X]` * Conclusion: `Γ ⊢ roll_{μX.A} V : μX.A` * *Logic Check:* This rule allows constructing a value of recursive type `μX.A` by rolling a value `V` that has the type `A` with the recursive type substituted in for the bound variable `X`. * **μE (Mu Elimination):** * Premise: `Γ, x: A[μX.A/X] | Δ ⊢ E : T` * Conclusion: `Γ | Δ ⊢ unroll V to roll x.E : T` * *Logic Check:* This rule eliminates a recursive value `V` of type `μX.A`. It provides the unrolled value (with type `A[μX.A/X]`) to the term `E` under the binder `x`. * **νI (Nu Introduction):** * Premise: `Γ | Δ ⊢ M : B[νY.B/Y]` * Conclusion: `Γ | Δ ⊢ roll_{νY.B} M : νY.B` * *Logic Check:* Analogous to `μI`, but for co-recursive computation types `νY.B`. * **νE (Nu Elimination):** * Premise: `Γ | Δ ⊢ M : νY.B` * Conclusion: `Γ | Δ ⊢ unroll M : B[νY.B/Y]` * *Logic Check:* Unrolls a computation of type `νY.B` to expose its underlying structure `B` with the recursive type substituted in. * **μICONG (Mu Introduction Congruence):** * Premise: `Γ ⊢ V ⊑ V' : A[μX.A/X]` * Conclusion: `Γ ⊢ roll V ⊑ roll V' : μX.A` * *Logic Check:* If two values are subtyped (`⊑`) before rolling, their rolled versions are also subtyped. * **μECONG (Mu Elimination Congruence):** * Premises: `Γ ⊢ V ⊑ V' : μX.A` and `Γ, x: A[μX.A/X] | Δ ⊢ E ⊑ E' : T` * Conclusion: `Γ | Δ ⊢ unroll V to roll x.E ⊑ unroll V' to roll x.E' : T` * *Logic Check:* Congruence rule for the elimination form, requiring subtyping on both the recursive value and the body term. * **νICONG (Nu Introduction Congruence):** * Premise: `Γ | Δ ⊢ M ⊑ M' : B[νY.B/Y]` * Conclusion: `Γ | Δ ⊢ roll M ⊑ roll M' : νY.B` * *Logic Check:* Analogous to `μICONG` for co-recursive types. * **νECONG (Nu Elimination Congruence):** * Premise: `Γ | Δ ⊢ M ⊑ M' : νY.B` * Conclusion: `Γ | Δ ⊢ unroll M ⊑ unroll M' : B[νY.B/Y]` * *Logic Check:* Congruence rule for unrolling, preserving subtyping. #### 3. Recursive Type Axioms Table | Type | β (Beta Reduction) | η (Eta Expansion) | | :--- | :--- | :--- | | **μ** | `unroll roll V to roll x.E ⊑ E[V/x]` | `E ⊑ unroll x to roll y.E[roll y/x]` <br> where `x : μX.A ⊢ E : T` | | **ν** | `unroll roll M ⊑ M` | `• : νY.B ⊢ • ⊑ roll unroll • : νY.B` | * **β Axioms:** Define computational equivalences. For `μ`, rolling then unrolling a value `V` is equivalent to substituting `V` into the body `E`. For `ν`, rolling then unrolling a computation `M` is equivalent to `M` itself. * **η Axioms:** Define observational equivalences. For `μ`, a term `E` is equivalent to unrolling a dummy recursive value and then rolling it back within the body. For `ν`, the axiom uses a placeholder `•` to state that a computation of type `νY.B` is equivalent to rolling its unrolled form. ### Key Observations 1. **Dual Structure:** The system exhibits a clear duality between value types (`μ`, positive/inductive) and computation types (`ν`, negative/coinductive), mirrored in their introduction (`roll`) and elimination (`unroll`) rules. 2. **Subtyping Focus:** The presence of the `⊑` symbol and the `CONG` rules indicates this is a system with subtyping, not just type equality. The rules carefully define how subtyping propagates through recursive type constructors. 3. **Scoped Elimination:** The `μE` rule uses a specific `unroll V to roll x.E` construct, suggesting elimination of recursive values is a scoped operation that binds the unrolled value. 4. **Axiom Presentation:** The `β` and `η` axioms are presented as subtyping relations (`⊑`), not strict equality, which is consistent with a system where observational equivalence may be coarser than syntactic equality. ### Interpretation This image defines the core formal machinery for a programming language type system with **recursive types**. Such systems are fundamental for defining recursive data structures (like lists or trees) and recursive functions. * **What it demonstrates:** It provides a rigorous, syntactic definition of how recursive types are formed (`μ`, `ν`), how values and computations of these types are constructed (`roll`) and deconstructed (`unroll`), and how subtyping works across these operations. The axioms establish the essential computational and observational properties that make recursive types useful and coherent. * **Relationships:** The inference rules show the direct relationship between the syntactic forms (Values, Terms) and the type judgments. The `CONG` rules bridge the subtyping relation with the type constructors. The axioms ground the formal system in intuitive equivalences (unrolling what you just rolled should get you back where you started). * **Notable Aspects:** The use of distinct syntactic categories for values (`V`) and computations (`M`) suggests a **call-by-value** or **value restriction** discipline, common in languages like ML or Scala to ensure type safety with mutable state. The `ν` type constructor is less common than `μ` and is often associated with **lazy** or **coinductive** types, capable of representing infinite structures. The presence of both suggests a sophisticated type system capable of handling both strict and lazy evaluation or both inductive and coinductive data.