nLab explicit substitution

Explicit substitutions

Context

Type theory

natural deduction metalanguage, practical foundations

  1. type formation rule
  2. term introduction rule
  3. term elimination rule
  4. computation rule

type theory (dependent, intensional, observational type theory, homotopy type theory)

syntax object language

computational trinitarianism =
propositions as types +programs as proofs +relation type theory/category theory

logicset theory (internal logic of)category theorytype theory
propositionsetobjecttype
predicatefamily of setsdisplay morphismdependent type
proofelementgeneralized elementterm/program
cut rulecomposition of classifying morphisms / pullback of display mapssubstitution
introduction rule for implicationcounit for hom-tensor adjunctionlambda
elimination rule for implicationunit for hom-tensor adjunctionapplication
cut elimination for implicationone of the zigzag identities for hom-tensor adjunctionbeta reduction
identity elimination for implicationthe other zigzag identity for hom-tensor adjunctioneta conversion
truesingletonterminal object/(-2)-truncated objecth-level 0-type/unit type
falseempty setinitial objectempty type
proposition, truth valuesubsingletonsubterminal object/(-1)-truncated objecth-proposition, mere proposition
logical conjunctioncartesian productproductproduct type
disjunctiondisjoint union (support of)coproduct ((-1)-truncation of)sum type (bracket type of)
implicationfunction set (into subsingleton)internal hom (into subterminal object)function type (into h-proposition)
negationfunction set into empty setinternal hom into initial objectfunction type into empty type
universal quantificationindexed cartesian product (of family of subsingletons)dependent product (of family of subterminal objects)dependent product type (of family of h-propositions)
existential quantificationindexed disjoint union (support of)dependent sum ((-1)-truncation of)dependent sum type (bracket type of)
logical equivalencebijection setobject of isomorphismsequivalence type
support setsupport object/(-1)-truncationpropositional truncation/bracket type
n-image of morphism into terminal object/n-truncationn-truncation modality
equalitydiagonal function/diagonal subset/diagonal relationpath space objectidentity type/path type
completely presented setsetdiscrete object/0-truncated objecth-level 2-type/set/h-set
setset with equivalence relationinternal 0-groupoidBishop set/setoid with its pseudo-equivalence relation an actual equivalence relation
equivalence class/quotient setquotientquotient type
inductioncolimitinductive type, W-type, M-type
higher inductionhigher colimithigher inductive type
-0-truncated higher colimitquotient inductive type
coinductionlimitcoinductive type
presettype without identity types
set of truth valuessubobject classifiertype of propositions
domain of discourseuniverseobject classifiertype universe
modalityclosure operator, (idempotent) monadmodal type theory, monad (in computer science)
linear logic(symmetric, closed) monoidal categorylinear type theory/quantum computation
proof netstring diagramquantum circuit
(absence of) contraction rule(absence of) diagonalno-cloning theorem
synthetic mathematicsdomain specific embedded programming language

homotopy levels

semantics

Explicit substitutions

Idea

Ordinary substitution is a meta-level notion, i.e. an operation on syntax. By contrast, explicit substitutions incorporate a notion of substitution as part of a syntax. The original calculus of explicit substitutions was introduced by Abadi, Cardelli, Curien & Lévy 1991.

Definition/Example

A paradigmatic (and in some sense universal) example is given by adding explicit substitutions to simply typed lambda calculus. For this we add a new term constructor

MxNM\langle x\coloneqq N\rangle

denoting internally “the substitution of NN for xx in MM”. That this is a term constructor means, for instance, that xxyx\langle x\coloneqq y\rangle is a term distinct from yy; whereas for the ordinary notion of substitution as an operation, x[xy]x[x\coloneqq y] would be a notation for the result of the operation of substituting the term yy for the variable xx in the term xx, which is precisely the term yy.

The relation between xxyx\langle x\coloneqq y\rangle and yy is recovered by modifying the reduction relation. We modify the usual beta-reduction rule (λx.M)(N)M[xN](\lambda x.M)(N) \to M[x\coloneqq N] to use an explict substitution instead:

(λx.M)(N)MxN(\lambda x.M)(N) \to M\langle x\coloneqq N\rangle

and then give reduction rules that mimic the inductive definition of the usual operation of substitution on terms:

xxN N yxN y(xy) (M 1M 2)xN (M 1xN)(M 2xN) (λy.M)xN λy.(MxN)(xyandynot free inN)\begin{aligned} x\langle x\coloneqq N\rangle &\to N\\ y \langle x\coloneqq N\rangle &\to y \quad (x\neq y)\\ (M_1 M_2)\langle x\coloneqq N\rangle &\to (M_1 \langle x\coloneqq N\rangle)(M_2 \langle x\coloneqq N\rangle) \\ (\lambda y.M)\langle x\coloneqq N\rangle &\to \lambda y. (M\langle x\coloneqq N\rangle) \quad (x\neq y \;\text{and}\; y \;\text{not free in}\; N) \end{aligned}

(We are being somewhat cavalier about variables; one can also define and implement explicit substitutions using de Bruijn indices.)

Combining substitutions and strong normalization

Note that there is no rule for reducing a term of the form (MxN)yP(M \langle x\coloneqq N\rangle) \langle y\coloneqq P\rangle. Instead we have to first reduce MxNM \langle x\coloneqq N\rangle until its “head” is no longer an explicit substitution, and then we can apply reduction rules for the “outer” substitution yP\langle y\coloneqq P\rangle. We might be tempted to assert a rule such as

(MxN)yP(MyP)xNyP (M \langle x\coloneqq N\rangle) \langle y\coloneqq P\rangle \to (M\langle y\coloneqq P\rangle) \langle x\coloneqq N\langle y\coloneqq P\rangle \rangle

but such a rule is undesirable because it destroys the strong normalization property of the reduction system: although every term still can be reduced to a normal form, there are also infinite reduction sequences that simply interchange pairs of substitutions forever.

One might hope that this could be avoided by introducing “explicit simultaneous substitutions” with a reduction rule

(MxN)yPMxN,yP. (M \langle x\coloneqq N\rangle) \langle y\coloneqq P\rangle \to M \langle x\coloneqq N, y\coloneqq P\rangle.

Apparently for a long time it was hoped that this would work, but Mellies showed that it doesn’t: explicit simultaneous substitutions with a rule of this sort also yield infinite reduction sequences. Note that Mellies worked with a de Bruijn version, so his rules look somewhat different; a version of the counterexample using named variables can be found in Bloo-Rose, along with a proof that without any way to “combine substitutions” strong normalization is preserved.

Categorical Models of Explicit Substitutions

The original calculus of explicit substitutions of Abadi et al (usually called λσ\lambda\sigma) considered as a type theory, can be given sound and complete categorical models, in terms of indexed categories.

This explicit substitutions construction is parametric in the kind of logic that the terms stand for. The Calculus of Constructions (Ritter), Intuitionistic Propositional Logic and Intuitionistic Linear Logic (Ghani2000) and propositional Constructive Necessity (Ghani1998) can be given formalizations and implementations in terms of explicit substitutions calculi. These constructions help to show the correctness of the implementation of the associated type theories.

The linear substitution calculus

In 2010 a new version of a linear substitution calculus was introduced by Delia Kesner and Beniamino Accattoli, which according to Damiano Mazza is based on two fundamental ideas:

Explicit substitutions in the λ\lambda-calculus come from linear logic: if you write down a term calculus for the {,!}\{\multimap,!\} fragment of ILL, however you do it, you’re going to see let binders pop up, and these behave very much like explicit substitutions, in the sense that normalization needs commuting conversions. Now, if you take Girard’s (call-by-name) embedding of the λ\lambda-calculus in ILL, you see that β\beta-reduction decomposes exactly along the lines of what an ES calculus would do, with the explicit substitutions corresponding to the let binders for exponentials. While I think that this had been noticed immediately after the introduction of linear logic, Delia and Beniamino took it a step further and designed an ES calculus (the structural λ\lambda-calculus, a precursor to the LSC) by mimicking the behavior of ILL terms which are in the image of Girard’s embedding. The upshot is that, since Girard’s embedding preserves SN, so does the structural λ\lambda-calculus: linear logic is the “right” way of implementing explicit substitutions.

Explicit substitutions should behave like boxes in proof nets: the let binders mentioned above correspond to what are known as “exponential boxes” in proof nets. Cut-elimination in proof nets has the amazing property (from the rewriting viewpoint) that it does not need commuting conversions. In terms of explicit substitutions, this means that ESs should not need to “move” through a term in order to be applied, one should be able to apply them just where they are created. Rewriting should happen “remotely” or, as they say, “at a distance”. Beniamino and Delia noticed that there’s a consistent way of generalizing redexes in a term calculus with ESs (no need for proof nets!) so that they are transparent to the presence of ESs. Combine this with the above idea (that ESs should behave like in linear logic, i.e., be “linear”, substituting one occurrence at a time) and you obtain the LSC.

The LSC, just as the previous versions of explicit substitutions calculi, has found applications in

abstract machines: Beniamino Accattoli, Pablo Barenbaum, and Damiano Mazza showed how the LSC may be related in a very sharp way to a host of abstract machines, for any reduction strategy you can think of (call by name, call by value, call by need). Each strategy in the LSC “distills” an abstract machine, in the sense that the rewriting rules of the LSC are in bijection with the actual computational transitions of the machines, while the “administrative” transitions (needed by the machine to navigate through the term in search for the next redex) sort of “evaporate” and become structural equivalences in the LSC (they relate syntactically different terms which are behaviorally equal). In particular, the LSC gives a slick formulation of (weak) call-by-need.

In fact the formalization of abstract machines is given as the original motivation of Abadi et al.

The LSC also has applications in:

complexity: for decades, people had been wondering whether β\beta-reduction is a reasonable cost model for computational complexity. Most were convinced that the answer was “no”, because β\beta-reduction may make an arbitrary number of duplications in just one step. Suprisingly, Beniamino Accattoli and Ugo Dal Lago showed that the answer is in fact “yes”, and their proof uses the LSC in a crucial way, in particular its capability of succinctly expressing computation thanks to sharing.

References

  • Martín Abadi, Luca Cardelli, Pierre-Louis Curien, and Jean-Jacques Lévy. Explicit Substitutions. J. Funct. Program., 1(4):375–416, 1991. doi:10.1017/S0956796800000186. link

  • Paul-André Melliès, Typed λ\lambda-calculi with explicit substitution may not terminate. In M. Dezani (ed.), Int. Conf. on Typed Lambda Calculus and Applications, Lecture Notes in Computer Science, 1995.

  • Roel Bloo and Kristoffer H. Rose, Preservation of Strong Normalisation in Named Lambda Calculi with Explicit Substitution and Garbage Collection. In CSN-95: Computer Science in the Netherlands 1995, citeseer

  • Eike Ritter, Categorical abstract machines for higher-order typed lambda calculi, Theoretical Computer Science, vol 136, p.125–162, 1994. link

  • Neil Ghani, Valeria de Paiva and Eike Ritter, Linear Explicit Substitutions, Journal of the IGPL, Vol, 8(1), pp.7-31, 2000. link

  • Neil Ghani, Valeria de Paiva and Eike Ritter, Explicit substitutions for constructive necessity, In Larsen, Kim G. and Skyum, Sven and Winskel, Glynn (eds.), Automata, Languages and Programming, 1998. [citeseer]{https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=712ec1a9241700486bb9aba5aba83f51398ec246)

The linear substitution calculus is discussed in:

  • Beniamino Accattoli, An abstract factorization theorem for explicit substitutions, link

  • Beniamino Accattoli, Eduardo Bonelli, Delia Kesner, Carlos Lombardi, A nonstandard standardization theorem, link

  • Beniamino Accattoli, Pablo Barenbaum, Damiano Mazza, Distilling Abstract Machines, arxiv

  • Beniamino Accattoli and Ugo Dal Lago, (Leftmost-outermost) beta reduction is invariant, indeed, lmcs

Explicit substitution in dependent type theory:

Last revised on May 23, 2024 at 16:21:15. See the history of this page for a list of all contributions to it.