Abstract Syntax: Substitution and Binders

John Power

Research output: Contribution to journalArticlepeer-review

7 Citations (SciVal)
168 Downloads (Pure)


We summarise Fiore et al's paper on variable substitution and binding, then axiomatise it. Generalising their use of the category F of finite sets to model untyped cartesian contexts, we let S be an arbitrary pseudo-monad on Cat and consider op(S1): this generality includes linear contexts, affine contexts, and contexts for the Logic of Bunched Implications. Given a pseudo-distributive law of S over the (partial) pseudo-monad Tcoc−=[op(−),Set] for free cocompletions, one can define a canonical substitution monoidal structure on the category [op(S1),Set], generalising Fiore et al's substitution monoidal structure for cartesian contexts: this provides a natural substitution structure for the above examples. We give a concrete description of this substitution monoidal structure in full generality. We then give an axiomatic definition of a binding signature, then state and prove an initial algebra semantics theorem for binding signatures in full generality, once again extending the definitions and theorem of Fiore et al. A delicate extension of the research includes the category Pb(Injop,Set) studied by Gabbay and Pitts in their quite different analysis of binders, which we compare and contrast with that of Fiore et al.
Original languageEnglish
Pages (from-to)3-16
Number of pages14
JournalElectronic Notes in Theoretical Computer Science
Publication statusPublished - 2 Apr 2007


Dive into the research topics of 'Abstract Syntax: Substitution and Binders'. Together they form a unique fingerprint.

Cite this