FM for Higher-Order Abstract Syntax

Murdoch J. Gabbay

Abstract

It has historically been a problem to give inductive definitions of syntax-with-binding up to alpha-equivalence. Two examples of methodologies which do give such definitions are "de Bruijn indeces" and "weak Higher-Order Abstract Syntax". Datatypes of terms of the untyped lambda-calculus using the two approaches are
  • Lam_dB = Nat + Lam_dB * Lam_dB + Lam_dB
  • Lam_WH = Atm + Lam_WH * Lam_WH + Atm -> Lam_WH

    respectively, where here Nat is the set (object) of natural numbers and Atm is some set (object) of urelemente or *atoms*.

    FM techniques propose the following:

  • Lam_FM = Atm + Lam_FM * Lam_FM + [Atm] Lam_FM,

    where here [Atm]X is the *FM abstraction type*, which has properties of both a product Atm*X and a function space Atm -> X. This type does not exist in ordinary set theory (category of sets Sets), but in the closely related theory of FM sets (Schan, the Schanuel topos). It turns out that Schan admits a simple axiomatisation as a category of sets with an action by permutations (bijections) of Atm and a finiteness condition, which I shall give. We can now ask what happens if we `tweak' these axioms to consider categories of sets with other kinds of actions. I consider sets with renamings (not necessarily injective functions on Atm) and a finiteness condition. I obtain a category similar to Schan, but which supports a natural interpretation of weak HOAS.