Hobbits for Haskell: a library for higher-order encodings in functional programming languages

Adequate encodings are a powerful programming tool, which eliminate whole classes of program bugs: they ensure that a program cannot generate ill-formed data, because such data is not part of the representation; and they also ensure that a program is well-defined, meaning that it cannot have different behaviors on different representations of the same piece of data. Unfortunately, it has proven difficult to define adequate encodings of programming languages themselves. Such encodings would be very useful in language processing tools such as interpreters, compilers, model-checking tools, etc., as these systems are often difficult to get correct. The key problem in representing programming languages is in encoding binding constructs; previous approaches have serious limitations in either the operations they allow or the correcness guarantees they make. In this paper, we introduce a new library for Haskell that allows the user to define and use higher-order encodings, a powerful technique for representing bindings. Our library allows straightforward recursion on bindings using pattern-matching, which is not possible in previous approaches. We then demonstrate our library on a medium-sized example, lambda-lifting, showing how our library can be used to make strong correctness guarantees at compile time.