substitutiontype

Substitutiontype is a term used in formal type systems to describe the mechanism by which type variables are replaced with concrete types in order to instantiate polymorphic expressions. In languages with parametric polymorphism, types may be expressed with variables such as α or β. A substitution type, or simply a substitution, is a finite mapping from type variables to types. The notation T[σ] denotes the type T after applying the substitution σ. The most common form is a mapping {α → τ, β → κ}.

Applying a substitution means replacing every occurrence of a type variable with its bound type, typically in a capture-avoiding way to prevent unintended binding of free variables. Substitutions compose: if σ maps α to τ and τ maps β to υ, then applying σ followed by τ yields α mapping to υ. The identity substitution leaves every type unchanged.

Substitutions underpin type inference and unification algorithms, as they allow the instantiation of generic definitions and resolution of type constraints. For example, instantiating the polymorphic identity function ∀α. α → α with α := Int yields the concrete type Int → Int. Variants include capture-avoiding substitutions to prevent variable capture, and kind-aware substitutions for languages with higher-kinded types.

Potential pitfalls include the occurs check, which prevents infinite types, and the need to rename bound variables to preserve alpha-equivalence during substitution. In practice, the substitution mechanism is a core component of type checkers, compilers, and proof systems that support polymorphism.