Explicit substitution
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science, lambda calculi are said to have explicit substitutions if they pay special attention to the formalization of the process of substitution. This is in contrast to the standard lambda calculus where substitutions are performed by beta reductions in an implicit manner which is not expressed within the calculus; the "freshness" conditions in such implicit calculi are a notorious source of errors. The concept has appeared in a large number of published papers in quite different fields, such as in abstract machines, predicate logic, and symbolic computation.
In computer science, lambda calculi are said to have explicit substitutions if they pay special attention to the formalization of the process of substitution. This is in contrast to the standard lambda calculus where substitutions are performed by beta reductions in an implicit manner which is not expressed within the calculus; the "freshness" conditions in such implicit calculi are a notorious source of errors. The concept has appeared in a large number of published papers in quite different fields, such as in abstract machines, predicate logic, and symbolic computation. A simple example of a lambda calculus with explicit substitution is "λx", which adds one new form of term to the lambda calculus, namely the form M⟨x:=N⟩, which reads "M where x will be substituted by N". (The meaning of the new term is the same as the common idiom let x:=N in M from many programming languages.) λx can be written with the following rewriting rules: (λx.M) N → M⟨x:=N⟩ x⟨x:=N⟩ → N x⟨y:=N⟩ → x (x≠y) (M 1 M 2 ) ⟨x:=N⟩ → (M 1 ⟨x:=N⟩) (M 2 ⟨x:=N⟩) (λx.M) ⟨y:=N⟩ → λx.(M⟨y:=N⟩) (x≠y and x not free in N) While making substitution explicit, this formulation still retains the complexity of the lambda calculus "variable convention", requiring arbitrary renaming of variables during reduction to ensure that the "(x≠y and x not free in N)" condition on the last rule is always satisfied before applying the rule. Therefore many calculi of explicit substitution avoid variable names altogether by using a so-called "name-free" De Bruijn index notation. (M⟨x:=N⟩)⟨y:=P⟩ = (M⟨y:=P⟩)⟨x:=(N⟨y:=P⟩)⟩ (where x≠y and x not free in P) A surprising counterexample, due to Melliès, shows that the way this rule is encoded in the original calculus of explicit substitutions is not strongly normalizing. Following this, a multitude of calculi were described trying to offer the best compromise between syntactic properties of explicit substitution calculi.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1168185414 under CC BY-SA 4.0; modifications have been made.