  Structure editors allow programmers to edit the tree structure of a program
directly. This can have cognitive benefits, particularly for novice and
end-user programmers. It also simplifies matters for tool designers, because
they do not need to contend with malformed program text. This paper defines
Hazelnut, a structure editor based on a small bidirectionally typed lambda
calculus extended with holes and a cursor. Hazelnut goes one step beyond
syntactic well-formedness: its edit actions operate over statically meaningful
incomplete terms. Naively, this would force the programmer to construct terms
in a rigid "outside-in" manner. To avoid this problem, the action semantics
automatically places terms assigned a type that is inconsistent with the
expected type inside a hole. This safely defers the type consistency check
until the term inside the hole is finished. Hazelnut is a foundational
type-theoretic account of typed structure editing, rather than an end-user tool
itself. To that end, we describe how Hazelnut's rich metatheory, which we have
mechanized in Agda, guides the definition of an extension to the calculus. We
also discuss various plausible evaluation strategies for terms with holes, and
in so doing reveal connections with gradual typing and contextual modal type
theory, the Curry-Howard interpretation of contextual modal logic. Finally, we
discuss how Hazelnut's semantics lends itself to implementation as a functional
reactive program. Our reference implementation is written using js_of_ocaml.
