skip to main content
10.1145/1596550.1596586acmconferencesArticle/Chapter ViewAbstractPublication PagesicfpConference Proceedingsconference-collections
research-article

Attribute grammars fly first-class: how to do aspect oriented programming in Haskell

Published: 31 August 2009 Publication History

Abstract

Attribute Grammars (AGs), a general-purpose formalism for describing recursive computations over data types, avoid the trade-off which arises when building software incrementally: should it be easy to add new data types and data type alternatives or to add new operations on existing data types? However, AGs are usually implemented as a pre-processor, leaving e.g. type checking to later processing phases and making interactive development, proper error reporting and debugging difficult. Embedding AG into Haskell as a combinator library solves these problems.
Previous attempts at embedding AGs as a domain-specific language were based on extensible records and thus exploiting Haskell's type system to check the well formedness of the AG, but fell short in compactness and the possibility to abstract over oft occurring AG patterns. Other attempts used a very generic mapping for which the AG well-formedness could not be statically checked.
We present a typed embedding of AG in Haskell satisfying all these requirements. The key lies in using HList-like typed heterogeneous collections (extensible polymorphic records) and expressing AG well-formedness conditions as type-level predicates (i.e., type-class constraints). By further type-level programming we can also express common programming patterns, corresponding to the typical use cases of monads such as Reader, Writer and State. The paper presents a realistic example of type-class-based type-level programming in Haskell.

Supplementary Material

JPG File (attributegrammarsflyfirst-classhowtodoaspectoriented.jpg)
MP4 File (attributegrammarsflyfirst-classhowtodoaspectoriented.mp4)

References

[1]
Richard S. Bird. Using circular programs to eliminate multiple traversals of data. Acta Inf., 21:239--250, 1984.
[2]
John Boyland. Remote attribute grammars. Journal of the ACM (JACM, 52(4), Jul 2005. URL http://portal.acm.org/citation.cfm?id=1082036.1082042.
[3]
Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. Associated type synonyms. In ICFP '05: Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, pages 241--253, New York, NY, USA, 2005. ACM.
[4]
Oege de Moor, Kevin Backhouse, and S. Doaitse Swierstra. First-class attribute grammars. Informatica (Slovenia), 24(3), 2000a.
[5]
Oege de Moor, L. Peyton Jones, Simon, and Van Wyk, Eric. Aspect-oriented compilers. In GCSE '99: Proceedings of the First International Symposium on Generative and Component-Based Software Engineering, pages 121--133, London, UK, 2000b. Springer-Verlag. ISBN 3-540-41172-0.
[6]
Atze Dijkstra and S. Doaitse Swierstra. Typing Haskell with an Attribute Grammar. In Advanced Functional Programming Summerschool, number 3622 in LNCS. Springer-Verlag, 2004.
[7]
Atze Dijkstra, Jeroen Fokker, and S. Doaitse Swierstra. The structure of the essential haskell compiler, or coping with compiler complexity. In Implementation of Functional Languages, 2007.
[8]
Atze Dijkstra, Jeroen Fokker, and S. Doaitse Swierstra. The architecture of the Utrecht Haskell compiler. In Haskell Symposium, New York, NY, USA, September 2009. ACM.
[9]
Jeroen Fokker and S. Doaitse Swierstra. Abstract interpretation of functional programs using an attribute grammar system. In Adrian Johnstone and Jurgen Vinju, editors, Language Descriptions, Tools and Applications, 2008.
[10]
Benedict R. Gaster and Mark P. Jones. A polymorphic type system for extensible records and variants. NOTTCS-TR 96-3, Nottingham, 1996.
[11]
Thomas Hallgren. Fun with functional dependencies or (draft) types as values in static computations in haskell. In Proc. of the Joint CS/CE Winter Meeting, 2001.
[12]
Ralf Hinze. Fun with phantom types. In Jeremy Gibbons and Oege de Moor, editors, The Fun of Programming, pages 245--262. Palgrave Macmillan, 2003.
[13]
Mark P. Jones. Typing Haskell in Haskell. In Haskell Workshop, 1999. URL http://www.cse.ogi.edu/ mpj/thih/thih-sep1-1999/.
[14]
P. Jones, Mark. Type classes with functional dependencies. In ESOP '00: Proceedings of the 9th European Symposium on Programming Languages and Systems, pages 230--244, London, UK, 2000. Springer-Verlag.
[15]
Uwe Kastens. Ordered Attribute Grammars. Acta Informatica, 13: 229--256, 1980.
[16]
Oleg Kiselyov, Ralf Lammel, and Keean Schupke. Strongly typed heterogeneous collections. In Haskell '04: Proceedings of the ACM SIGPLAN workshop on Haskell, pages 96--107. ACM Press, 2004.
[17]
Conor McBride. Faking it simulating dependent types in haskell. J. Funct. Program., 12(5):375--392, 2002.
[18]
Ulf Norell. Dependently typed programming in Agda. In 6th International School on Advanced Functional Programming, 2008.
[19]
Nicolas Oury and Wouter Swierstra. The power of Pi. In ICFP '08: Proceedings of the Thirteenth ACM SIGPLAN International Conference on Functional Programming, 2008.
[20]
Simon Peyton Jones, Mark Jones, and Erik Meijer. Type classes: an exploration of the design space. In Haskell Workshop, June 1997.
[21]
W. Reps, Thomas, Carla Marceau, and Tim Teitelbaum. Remote attribute updating for language-based editors. In POPL '86: Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pages 1--13, New York, NY, USA, 1986. ACM.
[22]
J.C. Reynolds. User defined types and procedural data as complementary approaches to data abstraction. In S.A. Schuman, editor, New Directions in Algorithmic Languages. INRIA, 1975.
[23]
Alexandra Silva and Joost Visser. Strong types for relational databases. In Haskell '06: Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, pages 25--36, New York, NY, USA, 2006. ACM. ISBN 1-59593-489-8.
[24]
S. Doaitse Swierstra and Olaf Chitil. Linear, bounded, functional pretty-printing. Journal of Functional Programming, 19(01):1--16, 2009.
[25]
S. Doaitse Swierstra, Pablo R. Azero Alcocer, and Joao A. Saraiva. Designing and implementing combinator languages. In S. D. Swierstra, Pedro Henriques, and Jose Oliveira, editors, Advanced Functional Programming, Third International School, AFP'98, volume 1608 of LNCS, pages 150--206. Springer-Verlag, 1999.
[26]
S.D. Swierstra. Linear, online, functional pretty printing (extended and corrected version). Technical Report UU-CS-2004-025a, Inst. of Information and Comp. Science, Utrecht Univ., 2004.
[27]
Phil Wadler. The Expression Problem. E-mail available online., 1998.

Cited By

View all
  • (2019)Attribute grammars fly first-class... safer!Proceedings of the 31st Symposium on Implementation and Application of Functional Languages10.1145/3412932.3412942(1-12)Online publication date: 25-Sep-2019
  • (2018)A Staged Embedding of Attribute Grammars in HaskellProceedings of the 30th Symposium on Implementation and Application of Functional Languages10.1145/3310232.3310235(95-106)Online publication date: 5-Sep-2018
  • (2018)Memoized zipper-based attribute grammars and their higher order extensionScience of Computer Programming10.1016/j.scico.2018.10.006Online publication date: Nov-2018
  • Show More Cited By

Index Terms

  1. Attribute grammars fly first-class: how to do aspect oriented programming in Haskell

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ICFP '09: Proceedings of the 14th ACM SIGPLAN international conference on Functional programming
      August 2009
      364 pages
      ISBN:9781605583327
      DOI:10.1145/1596550
      • cover image ACM SIGPLAN Notices
        ACM SIGPLAN Notices  Volume 44, Issue 9
        ICFP '09
        September 2009
        343 pages
        ISSN:0362-1340
        EISSN:1558-1160
        DOI:10.1145/1631687
        Issue’s Table of Contents
      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]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 31 August 2009

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. HList
      2. Haskell
      3. attribute grammars
      4. class system
      5. lazy evaluation
      6. type-level programming

      Qualifiers

      • Research-article

      Conference

      ICFP '09
      Sponsor:
      ICFP '09: ACM SIGPLAN International Conference on Functional Programming
      August 31 - September 2, 2009
      Edinburgh, Scotland

      Acceptance Rates

      Overall Acceptance Rate 333 of 1,064 submissions, 31%

      Upcoming Conference

      ICFP '25
      ACM SIGPLAN International Conference on Functional Programming
      October 12 - 18, 2025
      Singapore , Singapore

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)7
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 27 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2019)Attribute grammars fly first-class... safer!Proceedings of the 31st Symposium on Implementation and Application of Functional Languages10.1145/3412932.3412942(1-12)Online publication date: 25-Sep-2019
      • (2018)A Staged Embedding of Attribute Grammars in HaskellProceedings of the 30th Symposium on Implementation and Application of Functional Languages10.1145/3310232.3310235(95-106)Online publication date: 5-Sep-2018
      • (2018)Memoized zipper-based attribute grammars and their higher order extensionScience of Computer Programming10.1016/j.scico.2018.10.006Online publication date: Nov-2018
      • (2016)Embedding attribute grammars and their extensions using functional zippersScience of Computer Programming10.1016/j.scico.2016.03.005132:P1(2-28)Online publication date: 15-Dec-2016
      • (2016)Memoized Zipper-Based Attribute GrammarsProgramming Languages10.1007/978-3-319-45279-1_4(46-61)Online publication date: 17-Sep-2016
      • (2015)Attribute grammars in ErlangProceedings of the 14th ACM SIGPLAN Workshop on Erlang10.1145/2804295.2804296(1-12)Online publication date: 30-Aug-2015
      • (2015)JavaRAG: a Java library for reference attribute grammarsProceedings of the 14th International Conference on Modularity10.1145/2724525.2724572(55-67)Online publication date: 16-Mar-2015
      • (2015)Generalising Tree Traversals to DAGsProceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation10.1145/2678015.2682539(27-38)Online publication date: 13-Jan-2015
      • (2015)Zipper-Based Modular and Deforested ComputationsCentral European Functional Programming School10.1007/978-3-319-15940-9_10(407-427)Online publication date: 21-Mar-2015
      • (2014)From object algebras to attribute grammarsACM SIGPLAN Notices10.1145/2714064.266023749:10(377-395)Online publication date: 15-Oct-2014
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media