Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.

REFERENCES

• 1: Richard S. Bird. Using circular programs to eliminate multiple traversals of data. Acta Inf., 21:239--250, 1984.
• 2: John Tang Boyland, Remote attribute grammars, Journal of the ACM (JACM), v.52 n.4, p.627-687, July 2005 [doi>10.1145/1082036.1082042]
• 3: Manuel M. T. Chakravarty , Gabriele Keller , Simon Peyton Jones, Associated type synonyms, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia [doi>10.1145/1086365.1086397]
• 4: Oege de Moor, Kevin Backhouse, and S. Doaitse Swierstra. First-class attribute grammars. Informatica (Slovenia), 24(3), 2000a.
• 5: Oege de Moor , Simon L. Peyton Jones , Eric Van Wyk, Aspect-Oriented Compilers, Proceedings of the First International Symposium on Generative and Component-Based Software Engineering, p.121-133, September 28-30, 1999
• 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 , S. Doaitse Swierstra, The architecture of the Utrecht Haskell compiler, Proceedings of the 2nd ACM SIGPLAN symposium on Haskell, September 03-03, 2009, Edinburgh, Scotland [doi>10.1145/1596638.1596650]
• 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: Mark P. Jones, Type Classes with Functional Dependencies, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.230-244, April 02, 2000
• 15: Uwe Kastens. Ordered Attribute Grammars. Acta Informatica, 13: 229--256, 1980.
• 16: Oleg Kiselyov , Ralf Lämmel , Keean Schupke, Strongly typed heterogeneous collections, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA [doi>10.1145/1017472.1017488]
• 17: Conor McBride, Faking it Simulating dependent types in Haskell, Journal of Functional Programming, v.12 n.5, p.375-392, July 2002 [doi>10.1017/S0956796802004355]
• 18: Ulf Norell. Dependently typed programming in Agda. In 6th International School on Advanced Functional Programming, 2008.
• 19: Nicolas Oury , Wouter Swierstra, The power of Pi, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, September 20-28, 2008, Victoria, BC, Canada [doi>10.1145/1411204.1411213]
• 20: Simon Peyton Jones, Mark Jones, and Erik Meijer. Type classes: an exploration of the design space. In Haskell Workshop, June 1997.
• 21: Thomas W. Reps , Carla Marceau , Tim Teitelbaum, Remote attribute updating for language-based editors, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-13, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512645]
• 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 , Joost Visser, Strong types for relational databases, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA [doi>10.1145/1159842.1159846]
• 24: S. doaitse Swierstra , Olaf Chitil, Linear, bounded, functional pretty-printing, Journal of Functional Programming, v.19 n.1, p.1-16, January 2009 [doi>10.1017/S0956796808006990]
• 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.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Design, Languages, Performance, Standardization

Keywords:
HList, Haskell, attribute grammars, class system, lazy evaluation, type-level programming