skip to main content
10.1145/2426890.2426910acmconferencesArticle/Chapter ViewAbstractPublication PagespepmConference Proceedingsconference-collections
research-article

Fixing idioms: a recursion primitive for applicative DSLs

Published:21 January 2013Publication History

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.

References

  1. A. I. Baars, A. Löh, and S. D. Swierstra. Parsing permutation phrases. J. Funct. Program., 14(6):635--646, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. A. I. Baars and S. D. Swierstra. Type-safe, self inspecting code. In Haskell, pages 69--79, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. A. I. Baars, S. D. Swierstra, and M. Viera. Typed transformations of typed abstract syntax: The left corner transform. In LDTA, pages 18--33, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. K. Brink, S. Holdermans, and A. Löh. Dependently typed grammars. In MPC, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. J. Carette, O. Kiselyov, and C.-c. Shan. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. J. Funct. Program., 19(05):509--543, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. A. Chlipala. Parametric higher-order abstract syntax for mechanized semantics. In ICFP, pages 143--156, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. N. A. Danielsson. Total parser combinators. In ICFP, pages 285--296, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. N. A. Danielsson, J. Hughes, P. Jansson, and J. Gibbons. Fast and loose reasoning is morally correct. In POPL, pages 206--217, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. N. A. Danielsson and U. Norell. Structurally recursive descent parsing. Draft, 2008.Google ScholarGoogle Scholar
  10. D. Devriese and F. Piessens. Explicitly recursive grammar combinators - Implemention of some grammar algorithms. Technical Report CW594, KULeuven CS, 2010.Google ScholarGoogle Scholar
  11. D. Devriese and F. Piessens. Explicitly recursive grammar combinators. In PADL, pages 84--98. Springer, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. D. Devriese and F. Piessens. Finally tagless observable recursion for an abstract grammar model. Journal of Functional Programming, 22(06):757--796, 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. C. Elliott and P. Hudak. Functional reactive animation. In ICFP, pages 263--273, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. L. Erkök and J. Launchbury. Recursive Monadic Bindings. In ICFP, pages 174--185, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. L. Erkök and J. Launchbury. A recursive do for Haskell. In Haskell, pages 29--37, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. R. Frost, R. Hafiz, and P. Callaghan. Parser combinators for ambiguous left-recursive grammars. In PADL, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. J. Hughes. Generalising monads to arrows. Sci. Comput. Program., 37(1--3):67--111, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. N. R. Krishnaswami and N. Benton. A semantic model for graphical user interfaces. In ICFP, pages 45--57, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. S. Lindley, P. Wadler, and J. Yallop. Idioms are oblivious, arrows are meticulous, monads are promiscuous. In MSFP, pages 97--117, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. P. Ljunglöf. Pure functional parsing - an advanced tutorial. Master's thesis, Chalmers, 2002.Google ScholarGoogle Scholar
  22. C. McBride. Faking it: Simulating dependent types in Haskell. J. Funct. Program., 12(4--5):375--392, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. C. McBride and R. Paterson. Applicative programming with effects. J. Funct. Program., 18:1--13, January 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. M. Might, D. Darais, and D. Spiewak. Parsing with derivatives: a functional pearl. In ICFP, pages 189--195, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. B. C. Oliveira and W. R. Cook. Functional programming with structured graphs. In ICFP, pages 77--88, 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. B. C. Oliveira and A. Löh. Abstract syntax graphs for domain specific languages. In PEPM, 2013. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. R. Paterson. A new notation for arrows. In ICFP, pages 229--240, 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. J. Peterson, P. Hudak, and C. Elliott. Lambda in Motion: Controlling Robots with Haskell. In PADL, pages 91--105, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. S. Peyton Jones, D. Vytiniotis, S. Weirich, and G. Washburn. Simple unification-based type inference for GADTs. In ICFP, pages 50--61, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. M. Sulzmann, M. M. T. Chakravarty, S. P. Jones, and K. Donnelly. System F with type equality coercions. In TLDI, pages 53--66, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. S. D. Swierstra and L. Duponcheel. Deterministic, error-correcting combinator parsing. In AFP, pages 184--207, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. J. Voigtl\"ander. Free theorems involving type constructor classes: functional pearl. In ICFP, pages 173--184, 2009.Google ScholarGoogle Scholar
  33. D. Vytiniotis, S. Peyton Jones, T. Schrijvers, and M. Sulzmann. OutsideIn (X) Modular type inference with local assumptions. J. Funct. Program., 1(1):1--80, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. P. Wadler. Theorems for free! In FPLCA, pages 347--359, 1989. Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. G. Washburn and S. Weirich. Boxes go bananas: Encoding higher-order abstract syntax with parametric polymorphism. In ICFP, pages 249--262, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  36. G. Winskel. The formal semantics of programming languages: an introduction. MIT Press, 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Fixing idioms: a recursion primitive for applicative DSLs

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      PEPM '13: Proceedings of the ACM SIGPLAN 2013 workshop on Partial evaluation and program manipulation
      January 2013
      162 pages
      ISBN:9781450318426
      DOI:10.1145/2426890

      Copyright © 2013 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 21 January 2013

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      PEPM '13 Paper Acceptance Rate13of29submissions,45%Overall Acceptance Rate66of120submissions,55%

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader