Scrap your boilerplate with class: extensible generic functions

ABSTRACT

The 'Scrap your boilerplate' approach to generic programming allows the programmer to write generic functions that can traverse arbitrary data structures, and yet have type-specific cases. However, the original approach required all the type-specific cases to be supplied at once, when the recursive knot of generic function definition is tied. Hence, generic functions were closed. In contrast, Haskell's type classes support open, or extensible, functions that can be extended with new type-specific cases as new data types are defined. In this paper, we extend the 'Scrap your boilerplate' approach to support this open style. On the way, we demonstrate the desirability of abstraction over type classes, and the usefulness of recursive dictionarie.

REFERENCES

• 1: Michael Brandt , Fritz Henglein, Coinductive Axiomatization of Recursive Type Equality and Subtyping, Proceedings of the Third International Conference on Typed Lambda Calculi and Applications, p.63-81, April 02-04, 1997
• 2: Arthur I. Baars , S. Doaitse Swierstra, Typing dynamic typing, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.157-166, October 04-06, 2002, Pittsburgh, PA, USA
• 3: L Cardelli. Amber. In G Cousineau, PL Curien, and B Robinet, editors, Combinators and functional programming languages. LNCS 242, Springer Verlag, 1986.
• 4: 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
• 5: James Cheney , Ralf Hinze, A lightweight implementation of generics and dynamics, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.90-104, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581698]
• 6: Koen Claessen , John Hughes, Testing monadic code with QuickCheck, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.65-77, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581696]
• 7: Dave Clarke , Andres Löh, Generic Haskell, Specifically, Proceedings of the IFIP TC2/WG2.1 Working Conference on Generic Programming, p.21-47, July 11-12, 2002
• 8: Simon D. Foster. "HAIFA: The Haskell Application Interoperation Framework Architecture"; web site, 2004--2005. http://www.repton-world.org.uk/mediawiki/index.php/HAIFA_Wiki.
• 9: Ralf Hinze, Generics for the masses, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 10: Robert Harper , Greg Morrisett, Compiling polymorphism using intensional type analysis, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199475]
• 11: Ralf Hinze and Simon Peyton Jones. Derivable type classes. In Graham Hutton, editor, Proceedings of the 2000 Haskell Workshop, Montreal, number NOTTCS-TR-00-1 in Technical Reports, September 2000.
• 12: RJM Hughes. Restricted data types in haskell. In Erik Meijer, editor, Proceedings of the 1999 Haskell Workshop, number UU-CS-1999-28 in Technical Reports, 1999. ftp://ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-1999/1999-28.pdf.
• 13: Andres Löh , Dave Clarke , Johan Jeuring, Dependency-style generic haskell, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.141-152, August 25-29, 2003, Uppsala, Sweden
• 14: Jeffrey R. Lewis , John Launchbury , Erik Meijer , Mark B. Shields, Implicit parameters: dynamic scoping with static types, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.108-118, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325708]
• 15: 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
• 16: Ralf Lämmel , Simon Peyton Jones, Scrap more boilerplate: reflection, zips, and generalised casts, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 17: K Zhuo Ming Lu and M Sulzmann. An implementation of subtyping among regular expression types. In Proc Asian Programming Languages Symposium (APLAS'04), volume 3302 of Lecture Notes in Computer Science, pages 57--73. Springer Verlag, 2004.
• 18: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
• 19: 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]
• 20: Konstantinos F. Sagonas, Terrance Swift, and David Scott Warren. An abstract machine for efficiently computing queries to well-founded models. J. Log. Program., 45(1--3):1--41, 2000.
• 21: Dimitrios Vytiniotis , Geoffrey Washburn , Stephanie Weirich, An open and shut typecase, Proceedings of the 2005 ACM SIGPLAN international workshop on Types in languages design and implementation, p.13-24, January 10-10, 2005, Long Beach, California, USA [doi>10.1145/1040294.1040296]
• 22: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
• 23: Stephanie Weirich, Type-safe cast: (functional pearl), Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.58-67, September 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.m Miscellaneous

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

General Terms:
Design, Languages

Keywords:
extensibility, generic programming, recursive dictionaries, type classes, typecase