Revisiting Soundness for Occurrence Typing, Semantically
Yuquan Fu, Carlo Angiuli, Sam Tobin-Hochstadt
cs.PL
Sep 14, 2026 · v1
TL;DR
A revised core calculus for Typed Racket's occurrence typing is given a semantic type soundness proof via step-indexed logical relations, formalized in Lean.
Abstract
Over the past two decades, numerous systems have brought some of the benefits of dependent typing to a wide variety of new programming languages, often by restricting which terms can appear inside types. Such techniques are known as refinement types, occurrence typing, liquid types, and path dependent types, among others. However, the restrictions adopted by these systems often break the substitution property, because they explicitly disallow the ability to substitute arbitrary terms for variables inside types. This leads to significant complexity in the design and metatheory of these systems, increasing the possibility of significant errors. We consider a specific line of work on occurrence typing, namely, the calculus underlying Typed Racket due to Tobin-Hochstadt and Felleisen 2010. We show that the fundamental challenge of substitution into types resulted in multiple flaws in the formalism and the syntactic type soundness theorem of this work. These flaws are replicated in several other papers building on this work, and also surface as a soundness bug in Typed Racket itself. We identify and repair these problems, revising the core calculus of Typed Racket and giving a semantic type soundness proof using step-indexed logical relations, formalized in Lean. We argue that this approach is simpler than it may seem, and easily scales to handle the complexity of the occurrence typing in Typed Racket.
Problem
Restricted dependent type systems such as Typed Racket's occurrence typing break the substitution property, leading to complex and error-prone metatheory. The original core calculus λTR of Typed Racket and several works building on it contain flaws in their formalism and syntactic type soundness proofs, surfacing as a soundness bug in Typed Racket itself.
Approach
A revised core calculus λ̃TR is developed, incorporating Typed Racket's occurrence typing features and equality propositions while correcting well-scopedness and well-foundedness issues. Metafunctions are reformulated as judgments, a bottom object is introduced, and positive/negative erasure operations are mutually defined. Type soundness is established via step-indexed logical relations rather than syntactic methods, with the full proof formalized in the Lean proof assistant.
Results
The semantic soundness proof yields type soundness for λ̃TR and, as a corollary, that closed boolean-typed terms diverge or evaluate to a boolean. The work identifies and repairs genuine soundness flaws, including one confirmed by the Typed Racket developers, plus additional implementation bugs.