Dependent and Substructural Types

Dependent types let types depend on values, enabling precise specifications, while substructural types such as linear and affine types control how resources are used.

Definition

Dependent types are types that depend on values, permitting precise properties to be stated and checked at the type level; substructural type systems restrict how variables (resources) may be duplicated or discarded, with linear types requiring each to be used exactly once.

Scope

This topic covers advanced typing disciplines that move beyond conventional systems: dependent types, in which types may mention program values, allowing types to express full specifications and serve as proofs; and substructural types (linear, affine, ownership), which restrict the structural rules of contraction and weakening to track resource usage, aliasing, and lifetimes. It connects to the Curry-Howard correspondence and to proof assistants.

Core questions

• How can types depend on values to express full program specifications?
• What is the correspondence between dependent types and constructive proofs?
• How do linear and affine types model resources, ownership, and memory safety?
• What are the trade-offs in decidability and usability of these rich systems?

Key theories

Intuitionistic (dependent) type theory

Martin-Löf's type theory unifies programming and constructive logic so that types are propositions and programs are proofs, providing the foundation for dependently typed languages and proof assistants.

Linear logic and linear types

Girard's linear logic refines classical and intuitionistic logic by controlling the structural rules, and Wadler showed how linear types built on it can safely manage in-place update and resource usage.

Statics for substructural systems

Harper develops the metatheory of substructural and other advanced type systems within a uniform statics-and-dynamics framework, clarifying their soundness and resource interpretation.

Clinical relevance

Dependent types power proof assistants and verified software, where programs come with machine-checked correctness guarantees. Substructural and ownership types underpin memory- and concurrency-safe systems languages, allowing safe manual resource management without a garbage collector.

History

Martin-Löf's intuitionistic type theory (1970s-1980s) established dependent types and the propositions-as-types view, leading to proof assistants such as Coq, Agda, and Lean. Girard's 1987 linear logic introduced resource-sensitive reasoning; Wadler's linear types brought it into language design, and ownership and borrow-checking disciplines later made substructural ideas mainstream in systems programming.

Debates

Expressiveness versus usability and decidability

Dependently typed and substructural systems can express very strong guarantees, but they raise the burden on programmers and can make type checking undecidable or onerous, driving debate over how much power is worth the cost.

Key figures

• Per Martin-Löf
• Jean-Yves Girard
• Philip Wadler
• Robert Harper

Seminal works

• martinlof1984
• girard1987
• wadler1990
• harper2016

Frequently asked questions

What is a dependent type?

A dependent type is a type whose definition depends on a value, such as the type of vectors of a specific length, which lets the type system enforce rich invariants that ordinary types cannot express.

What do linear types guarantee?

Linear types require that each value is used exactly once, which lets a compiler safely permit in-place update, manage resources, and prevent aliasing-related errors without runtime garbage collection.