Name
Abstract | ||
|---|---|---|
In a lazy functional language, the standard encoding of recursion in DSLs uses the host language's recursion, so that DSL algorithms automatically use the host language's least fixpoints, even though many domains require algorithms to produce different fixpoints. In particular, this is the case for DSLs implemented as Applicative functors (structures with a notion of pure computations and function application). We propose a recursion primitive afix that models a recursive binder in a finally tagless HOAS encoding, but with a novel rank-2 type that allows us to specify and exploit the effects-values separation that characterizes Applicative DSLs. Unlike related approaches for Monads and Arrows, we model effectful recursion, not value recursion. Using generic programming techniques, we define an arity-generic version of the operator to model mutually recursive definitions. We recover intuitive user syntax with a form of shallow syntactic sugar: an alet construct that syntactically resembles the let construct, which we have implemented in the GHC Haskell compiler. We describe a proposed axiom for the afix operator. We demonstrate usefulness with examples from Applicative parser combinators and functional reactive programming. We show how higher-order recursive operators like many can be encoded without special library support, unlike previous approaches, and we demonstrate an implementation of the left recursion removal transform. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2426890.2426910 | PEPM |
Keywords | Field | DocType |
applicative functors,lazy functional language,applicative parser combinators,value recursion,recursion primitive afix,higher-order recursive operator,applicative dsls,left recursion removal,effectful recursion,host language | Programming language,Functional programming,Computer science,Theoretical computer science,Syntactic sugar,Mutual recursion,Haskell,Parser combinator,Left recursion,Monad (functional programming),Recursion | Conference |
Citations | PageRank | References |
3 | 0.42 | 28 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dominique Devriese | 1 | 347 | 26.79 |
| Ilya Sergey | 2 | 162 | 16.06 |
| Dave Clarke | 3 | 416 | 26.19 |
| Frank Piessens | 4 | 2455 | 162.28 |