Loading...
Please wait, while we are loading the content...
Hobbits for Haskell: a library for higher-order encodings in functional programming languages
| Content Provider | ACM Digital Library |
|---|---|
| Author | Frisby, Nicolas Brauner, Paul Westbrook, Edwin |
| Abstract | 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. |
| Starting Page | 35 |
| Ending Page | 46 |
| Page Count | 12 |
| File Format | PDF MP4 |
| ISBN | 9781450308601 |
| DOI | 10.1145/2034675.2034681 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2011-09-22 |
| Publisher Place | New York |
| Access Restriction | Subscribed |
| Subject Keyword | Haskell Higher-order encodings Name-binding |
| Content Type | Audio Text |
| Resource Type | Article |
