Revisiting Soundness for Occurrence Typing, Semantically

1 Introduction

• Because types may refer to variables from outer scopes, they are context-sensitive, and restricting type contents makes substitution and preservation fail.These restrictions also prevent arbitrary terms or values from being substituted into types.Source: §1 · p. 2
• The ICFP 2010 approach used big-step semantics and closures, but still encountered ill-scoped types and problems caused by context-sensitive types.The paper argues that the approach lacked a semantic interpretation of types.Source: §1 · pp. 2–3
• Related papers that built on the ICFP 2010 work inherited similar errors, including incorrect proofs, statements, and definitions.The authors also report related issues in other systems beyond direct descendants.Source: §1 · p. 3
• The authors revise Typed Racket’s core calculus, clarify its scoping invariants, and prove semantic type soundness with step-indexed logical relations, formalized in Lean.Their revision also addresses a non-well-founded definition and an implementation unsoundness.Source: §1 · p. 3
• The authors conclude that semantic soundness techniques and closer attention to variable scoping can address these metatheoretic complexities straightforwardly.They note that logical relations can be simple when runtime behavior is not complex.Source: §1 · p. 3

2.1 A Brief Introduction to Typed Racket

• A predicate’s result type can record propositions about its argument, which the if rule adds to branch contexts to refine types.In the example, the true and false propositions let the program use number-specific or string-specific operations on the tested value.Source: §2.1 · pp. 4–5

2.2 The ICFP 2010 Metatheory and its Problems

• The ICFP 2010 approach cannot use ordinary substitution into types, and its closure typing and semantic account still produce ill-scoped types.Substituting a value can also create ill-typed intermediate terms and ill-formed propositions; the paper describes an example that leads to a runtime error.Source: §2.2 · pp. 5–6
• The authors also identify incorrect object substitution and metafunction definitions in the original work, including a contravariance error in function-type domains.The object-substitution flaw also appears in the Typed Racket implementation and can allow a program that immediately errors at runtime.Source: §2.2 · p. 6

2.3 Downstream Consequences of these Errors

• Related Typed Racket extensions and adaptations inherit flaws, while the authors identify similar scoping and semantic problems in an abstract-machine approach.They characterize the underlying difficulties as recurring across work on restricted dependent types.Source: §2.3 · p. 7

2 Why Occurrence Typing Needs More From Type Soundness

• Restricted dependent types create obligations around variable scoping and binding, while preventing arbitrary expressions from being substituted into types.These restrictions break substitution and preservation, undermining metatheoretic arguments used for simpler systems.Source: §2.3 · p. 7

3.1 Syntax and Overview

• Function types pair an input type with a four-part result describing the returned type, truth-dependent propositions, and any variable equal to the result.The syntax also includes union and base types, propositions about variables, and contexts containing bindings and hypotheses.Source: §3.1 · p. 8

3.2 Well-Formedness and Scoping

• The calculus separates introducing a variable under a binder from learning a typing proposition about an existing variable, then requires variables in types and propositions to be in scope.This addresses the difficulty of using repeated variable names for both declared types and occurrence-typing information without treating later entries as shadowing earlier ones.Source: §3.2 · p. 9

3.3 The Proof and Subtyping Systems

• Restrict and remove are mutually defined judgments with provability and subtyping, avoiding definitions that depend indirectly on their own non-derivability.Restrict and remove overapproximate type intersection and difference, and S-Expl makes every type a subtype of every other in inconsistent contexts; the systems are sound but not intended to be complete.Source: §3.3 · pp. 11–13

3.4 The Typing Judgment

• The typing judgment records a term’s type, propositions for true and false outcomes, and an object tracking whether its value equals an in-scope variable.T-If passes the condition’s propositions to the corresponding branches, while object substitution lets applications use a known variable in type results when arbitrary terms cannot appear in propositions.Source: §3.4 · pp. 13–15
• Positive erasure can be unsound for variables in function domains, so the calculus adds negative erasure and flips erasure polarity in contravariant positions.The stated soundness conditions require negative erasure to produce a subtype of the original type and the original type to be a subtype of positive erasure.Source: §3.4 · p. 16

3.5 Operational Semantics

• Because substituting a value into annotated expressions can leave free variables in types or create ill-formed types, operational semantics instead runs on expressions with type annotations erased.The small-step semantics is deterministic, call-by-value, and defined using evaluation contexts.Source: §3.5 · p. 16

4.1 Defining the Logical Relations

• The logical relations interpret free variables through value environments and use step indices to account for non-termination; negative propositions must hold at every positive index up to the current one for downward closure.The relations cover expressions, values, propositions, and contexts; equality propositions capture exact variable aliasing.Source: §4.1 · pp. 18–19

4.2 Proving Semantic Type Soundness

• Erasure subtyping and object-substitution compatibility support the fundamental theorem’s application and let cases, which yields the semantic soundness theorem.The erasure lemma is used where the type system performs object substitution.Source: §4.2 · pp. 21–22
• The proof also establishes head expansion, head reduction, and downward closure of step indices as standard properties of the mutually defined logical relations.These properties are used throughout later proofs.Source: §4.2 · p. 21
• Well-typed closed terms either diverge or evaluate to values satisfying their type result; boolean terms therefore diverge or evaluate to #t or #f.The main theorem is Theorem 4.7, with boolean soundness as Corollary 4.8.Source: §4.2 · p. 22

4.3 Lean Formalization

• The calculus and soundness development are fully formalized in Lean, including the type system, operational semantics, definitions, and theorems.The formalization is approximately 3,600 lines and uses de Bruijn binding indexed by context extensions.Source: §4.3 · pp. 22–23

5 Related Work

• The published metatheory of the Typed Racket calculus and systems modeled on it contains ill-defined formalisms and failures of type soundness, which this work clarifies and resolves.The cited family spans work from 2010 to 2021.Source: §5 · p. 23
• Flanagan’s refinement-type judgments have a circularity involving consistent substitutions in negative position; Knowles and Flanagan use a denotational interpretation, while Chugh et al. use a stratified hierarchy at added metatheoretic complexity.Liquid Types and much subsequent work rely on Rondon et al.’s work, which has an identical circularity.Source: §5 · p. 23
• Rules that use the full operational semantics in static subtyping are formally well-defined but not implementable; Liquid Haskell instead uses a syntactic proof system with a semantic correctness criterion.The syntactic proof system is often dispatched to an external solver.Source: §5 · p. 23
• Flow and TypeScript avoid some dependency challenges by restricting function result references to parameters, whereas Typed Racket propositions can refer to any in-scope variables; Castagna et al. use extra rules for ill-typed immediate steps.Flow and TypeScript also incorporate mechanisms inspired by Typed Racket’s latent propositions.Source: §5 · p. 24

6 Conclusion

• The revision incorporates the main features of λTR and the equality-proposition extension introduced by Kent et al. [17].It also includes minor improvements to T-Let and T-If, and clarifies Kent et al.’s [17] L-TRanspoRt rule.Source: §6 · pp. 24–25
• The revised calculus distinguishes context entries that bind new variables from entries that add typing information about existing variables, ensuring well-scopedness throughout the type system.It also reformulates restrict and remove as judgments to correct a well-foundedness issue, and adds S-Expl and SO-Expl rules to align the formalism with Typed Racket’s behavior.Source: §6 · p. 24
• The revision introduces a bottom object and mutually defined positive and negative erasure operations to handle contravariance in function subtyping, correcting an oversight responsible for confirmed unsoundness in Typed Racket.The implementation developers confirmed the unsoundness.Source: §6 · p. 24
• The work also found unrelated Typed Racket implementation bugs, including errors parsing complex type expressions.Source: §6 · p. 25
• The revised calculus replaces the flawed syntactic soundness proof with semantic type soundness using step-indexed logical relations, proven on paper and formalized in Lean.The Lean proof uses de Bruijn variables, enabled by clarifying context binding structure.Source: §6 · p. 25
• The authors argue that step-indexed semantic methods are significantly simpler than syntactic type soundness for systems combining occurrence typing, dependency, and scoping requirements.Source: §6 · p. 25
• The authors believe the calculus and metatheory could be extended to Typed Racket features such as refinement types [17], structures, and methods [15].Source: §6 · p. 25
• The authors also believe their approach could simplify, and in some cases correct, the metatheory of similar systems.Source: §6 · p. 25

A Appendix for “Revisiting Soundness for Occurrence Typing, Semantically”

• The appendix includes the full definition of the λ̃TR formalism.Source: A Appendix for “Revisiting Soundness… · p. 28
• The appendix includes some figures omitted from the main paper.Source: A Appendix for “Revisiting Soundness… · p. 28
• The semantic type soundness theorems and proofs are located in Section A.5.Source: A Appendix for “Revisiting Soundness… · p. 28

A.1 Syntax

• Figure 13 is titled “Syntax.”Source: Figure 13 · p. 28
• Figure 14 is titled “Runtime Syntax.”Source: Figure 14 · p. 28
• Figure 15 is titled “Projection from syntax to runtime syntax.”Source: Figure 15

A.2 Type system

• Figure 19 presents rules for restrict and remove, and Figure 20 presents subtyping rules.Source: Figure 19 · p. 31, Figure 20 · p. 32
• Figures 21–22 present typing rules and types of base values and primitive operations.Source: Figure 21 · p. 33, Figure 22 · p. 33
• Figure 23 is titled “Object Substitution/Erasure.”Source: Figure 23 · p. 34

• The section includes a figure on primitive operation interpretation.Source: Figure 24
• The section includes a figure on reduction rules.Source: Figure 25 · p. 35

• A figure presents interpretations of type results.Source: Figure 26
• A figure presents interpretation of types.Source: Figure 27
• A figure presents interpretation of propositions.Source: Figure 28
• A figure presents interpretation of contexts.Source: Figure 29 · p. 37

Lemmas A.1–A.2

• One-step reduction is deterministic, and two reductions of an expression to values must have equal step counts and equal resulting values.Source: §A.5 · p. 38

Lemma A.3 (Well-formedness Weakening)

• Well-formedness of types, propositions, results, and objects is preserved when extending a well-formed context whose domain contains the original context’s domain.Source: §A.5 · p. 38

Lemma A.4 (Subtyping for Erasure)

• If Γ ⊢ ψ, then Γ ⊢ ψ[x//⊤]; if Γ ⊢ₒ obj, then Γ ⊢ₒ[x//⊥] <∶ o and Γ ⊢ₒ <∶ o[x//⊤].Source: §A.5 · p. 40

Lemma A.7 (Renaming for Closing Substitution)

• For closing substitutions, the displayed renaming lemma states that if distinct variables x and y map to the same value v, then y maps to v.Source: §A.5 · p. 46

Lemma A.8 (Head Expansion)

• The displayed head-expansion conclusion gives either an n-step reduct or a value reached in fewer than n steps that satisfies the value relation.Source: §A.5 · p. 46

A.5 Proof

• Lemma A.10 establishes monotonicity of logical relations for indices m ≤ n.The proof handles all clauses simultaneously by induction on n.Source: §A.5 · pp. 46–47
• Theorem A.11 establishes correctness of subtyping and proof-system judgments under an interpreted context.Its proof uses simultaneous rule induction over the mutually defined judgments.Source: §A.5 · pp. 48, 51
• Erasure preserves logical relations: under an interpreted context, erasing x to top preserves interpretations of types and propositions.The proof applies the correctness theorem to the substituted type and proposition judgments.Source: §A.5 · p. 56
• Object substitution preserves a result interpretation when the object is top or denotes an alias of the substituted variable’s value.The proof reduces the substituted result interpretation to three obligations and handles object cases using the stated alias condition.Source: §A.5 · pp. 56–57
• If a context is semantically well-formed and Γ ⊢ e : R, then e satisfies the expression interpretation of R.This is the fundamental theorem of logical relations.Source: §A.5 · p. 57
• Syntactically well-typed closed terms are semantically well-typed at every index.This follows as Corollary A.15.Source: §A.5 · p. 64
• Well-typed closed terms either diverge or evaluate to a value that satisfies their type at every index.The proof rules out getting stuck using head reduction and determinacy, then establishes the value interpretation by head reduction and determinacy.Source: §A.5 · p. 64
• Well-typed boolean terms either diverge or evaluate to #t or #f.The proof derives this from semantic type soundness and the interpretation of booleans.Source: §A.5 · p. 64