Modular generic programming with extensible superclasses

ABSTRACT

"Generics for the Masses" (GM) and "Scrap your Boilerplate" (SYB) are generic programming approaches based on some inenious applications of Haskell type classes. To achieve modularity, the GM and SYB approach have been extended by using some experimental language extensions such as abstraction over type classes and recursive instances. Hence, the type class encodings behind the GM and SYB approach become less practical and harder to understand.We show that none of these type class features are necessary if we use the single feature of extensible superclasses, the complement of subclass extension. We formalize type classes with extensible superclasses as the combination of a previously introduced type-passing translation scheme and a general type class framework. Our results shed some new light on the use of type classes to support generic programming.

REFERENCES

• 1: S. Abdennadher. Operational semantics and confluence of constraint propagation rules. In Proc. of CP'97, LNCS, pages 252--266. Springer-Verlag, 1997.
• 2: Bart Demoen , Maria J. García de la Banda , Warwick Harvey , Kim Marriott , Peter J. Stuckey, An Overview of HAL, Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming, p.174-188, October 11-14, 1999
• 3: T. Frühwirth. Constraint handling rules. In Constraint Programming: Basics and Trends, LNCS. Springer-Verlag, 1995.
• 4: Glasgow haskell compiler home page. http://www.haskell.org/ghc/.
• 5: Cordelia V. Hall , Kevin Hammond , Simon L. Peyton Jones , Philip L. Wadler, Type classes in Haskell, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.2, p.109-138, March 1996 [doi>10.1145/227699.227700]
• 6: Robert Harper , John C. Mitchell, On the type structure of standard ML, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.211-252, April 1993 [doi>10.1145/169701.169696]
• 7: 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]
• 8: F. Henderson et al. The Mercury language reference manual, 2001. http://www.cs.mu.oz.au/research/mercury/.
• 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: R. Hinze, A. Löh, and B. Oliveira. "Scrap your boilerplate" reloaded. In Proc. of FLOPS'06, volume 3945 of LNCS, pages 13--29. Springer-Verlag, 2006.
• 11: J. Hughes. Restricted datatypes in Haskell. In Haskell Workshop, September 1999.
• 12: Hugs home page. haskell.cs.yale.edu/hugs/.
• 13: 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]
• 14: D. Jeffery, F. Henderson, and Z. Somogyi. Type classes in Mercury. In J. Edwards, editor, Proc. Twenty-Third Australasian Computer Science Conf., volume 22 of Australian Computer Science Communications, pages 128--135. IEEE Computer Society Press, January 2000.
• 15: Jhc. http://repetae.net/john/computer/jhc/.
• 16: Mark P. Jones, A system of constructor classes: overloading and implicit higher-order polymorphism, Proceedings of the conference on Functional programming languages and computer architecture, p.52-61, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165190]
• 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 , Simon Peyton Jones, Scrap your boilerplate with class: extensible generic functions, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 19: 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
• 20: Andres Löh , Ralf Hinze, Open data types and open functions, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy [doi>10.1145/1140335.1140352]
• 21: B. Oliveira, R. Hinze, and A. Löh. Generics as a library. In Henrik Nilsson, editor, Seventh Symposium on Trends in Functional Programming, 2006.
• 22: S. Peyton Jones, editor. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003.
• 23: M.J. Plasmeijer and M.C.J.D. van Eekelen. Language report Concurrent Clean. Technical Report CSI-R9816, Computing Science Institute, University of Nijmegen, Nijmegen, The Netherlands, June 1998. ftp://ftp.cs.kun.nl/pub/Clean/Clean13/doc/refman13.ps.gz.
• 24: François Pottier , Nadji Gauthier, Polymorphic typed defunctionalization and concretization, Higher-Order and Symbolic Computation, v.19 n.1, p.125-162, March 2006 [doi>10.1007/s10990-006-8611-7]
• 25: Peter J. Stuckey , Martin Sulzmann, A theory of overloading, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1216-1269, November 2005 [doi>10.1145/1108970.1108974]
• 26: Martin Sulzmann, Extracting programs from type class proofs, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy [doi>10.1145/1140335.1140348]
• 27: Satish R. Thatté, Semantics of type classes revisited, Proceedings of the 1994 ACM conference on LISP and functional programming, p.208-219, June 27-29, 1994, Orlando, Florida, United States
• 28: 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]
• 29: M. Wang, K. Chen, and S-C Khoo. Coherent and type-directed weaving of aspect-oriented higher-order functional languages. http://www.comp.nus.edu.sg/~wangmeng, 2006. Manuscript.
• 30: G. Washburn and S. Weirich. Good advice for type-directed programming, 2006. In this volume.
• 31: Hongwei Xi , Chiyan Chen , Gang Chen, Guarded recursive datatype constructors, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.224-235, January 15-17, 2003, New Orleans, Louisiana, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Languages, Theory

Keywords:
generic programming, type classes