Type Safety via Hoare Logic with Separation and Pure Types
Wenhua Li, Darius Foo, Quang Trung Ta, Wei-Ngan Chin
cs.PL
Jul 28, 2026 · v1
TL;DR
Meta-theory of the TypeHL type-safety framework is mechanised in Lean 4, yielding a self-certifying reflective type-checker.
Abstract
Type safety has traditionally rested on carefully crafted type systems, under the motto "well-typed programs cannot go wrong". Modern demands push type systems past this basic guarantee: toward memory safety (e.g., Rust), stronger data-structure invariants (e.g., GADTs), and broader typability (e.g., MLstruct). The motto absorbs each such property by enlarging the set of states deemed "wrong", but collapses them into one binary verdict: heap ownership, flow-sensitive changes to a variable's type, and the gap between a recoverable and a fatal error are relational, stateful facts about intermediate states that one verdict cannot tell apart. Worse, each demand typically brings its own extension, making it hard to say what each guarantees or how they combine. Floyd-Hoare logic supplies a unified foundation. We present a framework for type-safety verification built from four ingredients: (i) case specifications for path-sensitive typing; (ii) separation types, inspired by separation logic, for flow-sensitive type mutation and must-aliasing; (iii) a disciplined distinction between Err (runtime error values our types track) and Abrt (compile-time errors), yielding the refined motto well-typed programs must never abort; and (iv) type predicates for data-structure invariants. Since all four are ordinary types in one Boolean algebra rather than separate extensions, the framework subsumes both GADTs and liquid types within one type logic, spanning weak specifications that tolerate Err to strong ones that eliminate it. Subtyping reduces to one decidable emptiness test, so a single lightweight procedure serves the whole framework with no SMT oracle in its trusted base. We formalise the Hoare rules and prove soundness in a machine-checked Lean mechanisation; by proof reflection it yields a self-certifying type-checker, evaluated on a benchmark suite.
Problem
Modern type systems fold many properties (memory safety, data-structure invariants, broader typability) into a single binary 'go wrong' verdict, obscuring stateful, relational facts about intermediate states. Each demand arrives as a separate extension, making guarantees hard to relate or compose.
Approach
A framework recasts type safety as Floyd-Hoare logic with four ingredients: case specifications for path-sensitivity, separation types for flow-sensitive mutation and must-aliasing, an Err/Abrt error hierarchy, and type predicates for data-structure invariants. All are ordinary types in one Boolean algebra, with subtyping reduced to a single decidable emptiness test, avoiding an SMT oracle in the trusted base. The Hoare rules and soundness are mechanised in Lean 4 across three layers (pure, separation, higher-order), with no dependence on Mathlib and no sorry/admit.
Results
The framework subsumes GADTs and liquid types within one type logic. The Lean development comprises roughly 78,400 lines, with symbolic certificates (including red-black insert) axiom-clean, and produces an executable self-certifying type-checker evaluated on a benchmark suite.
| Feature | TypeHL | OCaml | Rust | Liquid Haskell |
|---|
| GADTs | yes | yes | no | yes |
| Type Predicates | yes | no | no | yes |
| Separation types | yes | no | partial | no |
| Flow-sensitive types | yes | no | yes | no |
| Err/Exc/Abrt as types | yes | no | no | no |
Feature comparison: full/partial/no support across type-system features