Can I read Abstract Syntax: Substitution and Binders: Invited Address on EtoBox?

Abstract Syntax: Substitution and Binders: Invited Address by John Power is a Computer Science article available to read on EtoBox.

What is Abstract Syntax: Substitution and Binders: Invited Address about?

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 pseudomonad on Cat and consider (S1) op : 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 T coc -= [(-) op , Set] for free cocompletions, one can define a canonical substitution monoidal structure on the category [(S1) op , 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 P b(Inj op , Set) studied by Gabbay and Pitts in their quite different analysis of binders, which

Who reads Abstract Syntax: Substitution and Binders: Invited Address?

Author

John Power

Publisher

Elsevier Science; Elsevier ; Elsevier BV; Amsterdam: Elsevier BV (ISSN 1571-0661)

Published

2007

Language

EN

Field

Computer Science (Physical Sciences)