Embedding Abstraction Functions into Dependent Type Theory

This work recasts a classic software verification idea—abstraction functions—as part of the programming language itself, embedding them into dependent type theory so they appear in types. The authors introduce a phase distinction and a gluing construction that make an abstraction function a type-level object, plus two modalities that separate a type into concrete and abstract aspects. A noninterference result is reported that captures the modularity guarantees of this design, and the approach is extended to reason about cost so client-facing cost behavior can be related to cost-aware specifications. A monadic sealing effect is used to allow implementations to be bounded by their specifications even when private details affect observable costs, supporting modular development that hides irrelevant private details while specifying both behavior and cost.

What the study examined

This work looks at how a long-standing verification technique can be integrated directly into a modern type system. The focal idea is that abstraction functions—mappings that connect detailed implementations to their public specifications—can be encoded inside the type language rather than treated as separate artifacts.

Dependent type theory is a system where types can depend on values, enabling rich specifications to live alongside program code.

Key findings

First, the authors show that a phase distinction can be used to separate what is concrete from what is abstract. This distinction leads to a gluing construction that represents an abstraction function as a type-level entity. Two modalities then allow a single type to be viewed in two ways: one that exposes concrete implementation details and one that exposes only the abstract specification.

• Modularity guarantee: A noninterference theorem about the phase distinction characterizes how private implementation details stay separate from client-facing specifications, providing a formal notion of modularity.
• Cost reasoning: The same framework extends to reasoning about cost. The approach allows client costs to be analyzed relative to specifications that are aware of cost, so observable resource usage can be related formally to what the specification promises.
• Monadic sealing: A sealing effect, presented in monadic form, supports modularity for cost. This permits implementations to be upper-bounded by their specifications even when private details influence observable cost.

Why it matters

By bringing abstraction mechanisms into the type system, this approach changes how libraries and their clients can be verified together. It makes the connection between concrete code and abstract specifications a matter of types, which helps keep private details hidden while still enabling precise proofs.

Supporting cost as well as functional behavior means specifications can cover both what programs do and how much they cost to run, while preserving modular reasoning. The result is a theory that aims to let developers and verifiers build programs and proofs in a way that cleanly separates client-facing obligations from private implementation details.