2008 · 121 citations · 18 references
ComputingComputer ScienceProgramming LanguagesSyntaxTheory Of ComputationData TypesFunctional ProgrammingFunctional SyntaxObject-oriented ProgrammingRecursion TheoryType SystemsAbstract Syntax ModelingAbstract TypesAbstraction MechanismsSubstitutions
Higher-order abstract syntax (HOAS) is a simple, powerful technique for implementing object languages, since it directly supports common and tricky routines dealing with variables, such as capture-avoiding substitution and renaming. This is achieved by representing binders in the object-language via binders in the meta-language. However, enriching functional programming languages with direct support for HOAS has been a major challenge, because recursion over HOAS encodings requires one to traverse lambda-abstractions and necessitates programming with open objects.
18
A new approach to abstract syntax involving binders
Murdoch J. Gabbay, Andrew M. Pitts · 2003 · 279 citations
Computing, Computer Science, Algebra +15
M. Abadi, Pierre-Louis Curien, Jean-Jacques Lévy · 1990 · 213 citations · Full text
Mark R. Shinwell, Andrew M. Pitts, Murdoch J. Gabbay · 2003 · 174 citations