Unbound swMATH ID: 22613 Software Authors: Weirich, Stephanie; Yorgey, Brent A.; Sheard, Tim Description: Binders unbound. mplementors of compilers, program refactorers, theorem provers, proof checkers, and other systems that manipulate syntax know that dealing with name binding is difficult to do well. Operations such as α-equivalence and capture-avoiding substitution seem simple, yet subtle bugs often go undetected. Furthermore, their implementations are tedious, requiring “boilerplate” code that must be updated whenever the object language definition changes. Many researchers have therefore sought to specify binding syntax declaratively, so that tools can correctly handle the details behind the scenes. This idea has been the inspiration for many new systems (such as Beluga, Delphin, FreshML, FreshOCaml, Cαml, FreshLib, and Ott) but there is still room for improvement in expressivity, simplicity and convenience. In this paper, we present a new domain-specific language, Unbound, for specifying binding structure. Our language is particularly expressive – it supports multiple atom types, pattern binders, type annotations, recursive binders, and nested binding (necessary for telescopes, a feature found in dependently-typed languages). However, our specification language is also simple, consisting of just five basic combinators. We provide a formal semantics for this language derived from a locally nameless representation and prove that it satisfies a number of desirable properties. We also present an implementation of our binding specification language as a GHC Haskell library implementing an embedded domain specific language (EDSL). By using Haskell type constructors to represent binding combinators, we implement the EDSL succinctly using datatype-generic programming. Our implementation supports a number of features necessary for practical programming, including flexibility in the treatment of user-defined types, best-effort name preservation (for error messages), and integration with Haskell’s monad transformer library. Homepage: https://dl.acm.org/citation.cfm?doid=2034773.2034818 Keywords: generic programming; Haskell; name binding; patterns Related Software: Isabelle/HOL; Psi-calculi; Nominal Isabelle; LNgen; Beluga; GitHub; MiniAgda; Paco; Gmeta; PoplMark; Quipper; Agda; CakeML; Isabelle; HYBRID; Logitext; Incredible Proof Machine; Coq; FreshOCaml; HNT Cited in: 4 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Binders unbound. Zbl 1323.68177Weirich, Stephanie; Yorgey, Brent A.; Sheard, Tim 2011 all top 5 Cited by 13 Authors 1 Abel, Andreas M. 1 Allais, Guillaume 1 Breitner, Joachim 1 Hameer, Aliya 1 Kaliszyk, Cezary 1 Momigliano, Alberto 1 Pientka, Brigitte 1 Schäfer, Steven 1 Sheard, Tim 1 Stark, Kathrin 1 Urban, Christian 1 Weirich, Stephanie 1 Yorgey, Brent A. Cited in 2 Serials 1 Journal of Functional Programming 1 Logical Methods in Computer Science Cited in 2 Fields 4 Computer science (68-XX) 1 Mathematical logic and foundations (03-XX) Citations by Year