# Resolving inductive definitions with binders in higher-order typed
functional programming (abstract)

This paper studies inductive definitions involving binders, in which
aliasing between free and bound names is permitted. Such aliasing
occurs in informal specifications of operational semantics, but is
excluded by the common representation of binding as meta-level
lambda-abstraction. Drawing upon ideas from functional logic
programming, we represent such definitions with aliasing as
recursively defined functions in a higher-order typed functional
programming language that extends core ML with types for
name-binding, a type of "semi-decidable propositions" and
existential quantification for types with decidable equality. We
show that the representation is sound and complete with respect to
the language's operational semantics, which combines the use of
evaluation contexts with constraint programming. We also give a new
and simple proof that the associated constraint problem is
NP-complete.

Last modified: Sun Sep 11 18:04:52 MDT 2011