A lightweight approach to datatype-generic rewriting

ABSTRACT

Previous implementations of generic rewriting libraries have a number of limitations: they require the user to either adapt the datatype on which rewriting is applied, or the rewriting rules are specified as functions, which makes it hard or impossible to document, test, and analyse them. We describe a library that demonstrates how to overcome these limitations by defining rules in terms of datatypes, and show how to use a type-indexed datatype to automatically extend a datatype for syntax trees with a case for metavariables. We then show how rewrite rules can be implemented without any knowledge of how the datatype is extended with metavariables. We use Haskell, extended with associated type synonyms, to implement both type-indexed datatypes and generic functions. We analyse the performance of our library and compare it with other approaches to generic rewriting.

REFERENCES

• 1: Artem Alimarine and Sjaak Smetsers. Improved fusion for optimizing generics. In Manuel V. Hermenegildo and Daniel Cabeza, editors, Practical Aspects of Declarative Languages, 7th International Symposium, PADL 2005, Long Beach, CA, USA, January 10-11, 2005, Proceedings, volume 3350 of Lecture Notes in Computer Science, pages 203--218. Springer-Verlag, 2005.
• 2: Peter Borovanský, Claude Kirchner, Hélèene Kirchner, and Christophe Ringeissen. Rewriting with strategies in ELAN: A functional semantics. International Journal of Foundations of Computer Science, 12(1): 69--95, 2001.
• 3: Björn Bringert , Aarne Ranta, A pattern for almost compositional functions, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 4: Neil C. C. Brown and Adam T. Sampson. Matching and modifying with generics. In Peter Achten, Pieter Koopman, and Marco T. Morazán, editors, Draft Proceedings of the Ninth Symposium on Trends in Functional Programming (TFP), May 26-28 2008, Center Parcs 'Het Heijderbos', The Netherlands, pages 304--318, 2008. The draft proceedings of the symposium have been published as a technical report (ICIS-R08007) at Radboud University Nijmegen.
• 5: 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
• 6: Manuel M. T. Chakravarty, Gabriele Keller, Roman Leshchinskiy, and Simon Peyton Jones. Generic programming with type families, 2008. Work in progress.
• 7: Koen Claessen , John Hughes, QuickCheck: a lightweight tool for random testing of Haskell programs, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.268-279, September 2000
• 8: Duncan Coutts , Roman Leshchinskiy , Don Stewart, Stream fusion: from lists to streams to nothing at all, Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, October 01-03, 2007, Freiburg, Germany
• 9: Arie Van Deursen , Jan Heering , Paul Klint, Language Prototyping: An Algebraic Specification Approach: Vol. V, World Scientific Publishing Co., Inc., River Edge, NJ, 1996
• 10: Bastiaan Heeren , Johan Jeuring , Arthur Leeuwen , Alex Gerdes, Specifying Strategies for Exercises, Proceedings of the 9th AISC international conference, the 15th Calculemas symposium, and the 7th international MKM conference on Intelligent Computer Mathematics, July 28-August 01, 2008, Birmingham, UK [doi>10.1007/978-3-540-85110-3_36]
• 11: Ralf Hinze , Johan Jeuring , Andres Löh, Type-indexed data types, Science of Computer Programming, v.51 n.1-2, p.117-151, May 2004 [doi>10.1016/j.scico.2003.07.001]
• 12: Stefan Holdermans, Johan Jeuring, Andres Löh, and Alexey Rodriguez. Generic views on data types. In Tarmo Uustalu, editor, Mathemathics of Program Construction, 8th International Conference, MPC 2006, Kuressaare, Estonia, July 3-5, 2006, Proceedings, volume 4014 of Lecture Notes in Computer Science, pages 209--234. Springer-Verlag, 2006.
• 13: Gérard Huet, The Zipper, Journal of Functional Programming, v.7 n.5, p.549-554, September 1997 [doi>10.1017/S0956796897002864]
• 14: Patrik Jansson and Johan Jeuring. A framework for polytypic programming on terms, with an application to rewriting. In Johan Jeuring, editor, Proceedings Workshop on Generic Programming (WGP2000), July 6, 2000, Ponte de Lima, Portugal, pages 33--45, 2000. The proceedings of the workshop have been published as a technical report (UU-CS-2000-19) at Utrecht University.
• 15: Patrik Jansson , Johan Jeuring, PolyP—a polytypic programming language extension, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.470-482, January 15-17, 1997, Paris, France [doi>10.1145/263699.263763]
• 16: Patrik Jansson , Johan Jeuring, Polytypic unification, Journal of Functional Programming, v.8 n.5, p.527-536, September 1998 [doi>10.1017/S095679689800313X]
• 17: Ralf Lämmel , Simon Peyton Jones, Scrap your boilerplate: a practical design pattern for generic programming, Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, January 18-18, 2003, New Orleans, Louisiana, USA
• 18: Ralf Lämmel , Joost Visser, Typed Combinators for Generic Traversal, Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages, p.137-154, January 19-20, 2002
• 19: Neil Mitchell , Colin Runciman, Uniform boilerplate and list processing, Proceedings of the ACM SIGPLAN workshop on Haskell workshop, September 30-30, 2007, Freiburg, Germany [doi>10.1145/1291201.1291208]
• 20: Thomas van Noort. Generic views for generic types. Master's thesis, Utrecht University, 2008.
• 21: Ulf Norell and Patrik Jansson. Polytypic programming in Haskell. In Philip W. Trinder, Greg Michaelson, and Ricardo Pena, editors, Implementation of Programming Languages, 15th International Workshop, IFL 2003, Edinburgh, UK, September 8-11, 2003, Revised Papers, volume 3145 of Lecture Notes in Computer Science, pages 168--184. Springer-Verlag, 2004.
• 22: Bruno C. d. S. Oliveira , Jeremy Gibbons, TypeCase: a design pattern for type-indexed functions, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.98-109, September 30-30, 2005, Tallinn, Estonia [doi>10.1145/1088348.1088358]
• 23: Alexey Rodriguez, Stefan Holdermans, Andres Löh, and Johan Jeuring. Generic programming with fixed points for mutually recursive datatypes. Technical Report UU-CS-2008-019, Utrecht University, 2008.
• 24: Tim Sheard, Generic unification via two-level types and parameterized modules, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 25: Tim Sheard , Simon Peyton Jones, Template meta-programming for Haskell, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.1-16, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581691]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Reusable libraries
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

General Terms:
Design, Languages

Keywords:
datatype-generic programming, term rewriting