ComputingComputer ScienceMathematicsAlgebraFormal MethodsProgramming LanguagesAlgebraic ProofFunctional ProgrammingProof AssistantsRecursion TheoryTheorem ProvingUniqueness TheoryAlgebraic Data TypesCoinductionEquational LogicEquational ReasoningInfinite SequencesProof GenerationProof StrategiesRecursive Proofs
In this paper, we show how to manipulate syntax with binding using a mixed representation of names for free variables (with respect to the task in hand) and de Bruijn indices [5] for bound variables. By doing so, we retain the advantages of both representations: naming supports easy, arithmetic-free manipulation of terms; de Bruijn indices eliminate the need for α-conversion. Further, we have ensured that not only the user but also the implementation need never deal with de Bruijn indices, except within key basic operations.Moreover, we give a hierarchical representation for names which naturally reflects the structure of the operations we implement. Name choice is safe and straightforward. Our technology combines easily with an approach to syntax manipulation inspired by Huet's 'zippers'[10].Without the ideas in this paper, we would have struggled to implement EPIGRAM [19]. Our example-constructing inductive elimination operators for datatype families-is but one of many where it proves invaluable.
10
Conor McBride, James McKinna · Journal of Functional Programming · 2004 · 327 citations · Full text
Gérard Huet · Journal of Functional Programming · 1997 · 310 citations
Computation and reasoning: a type theory for computer science
Choice Reviews Online · 1995 · 243 citations
Computing, Computer Science, Logic +16
Unification under a mixed prefix
Dale Miller · Journal of Symbolic Computation · 1992 · 165 citations
Language Studies, Computer Science, Computational Linguistics +2