A comparison of c++ concepts and haskell type classes

ABSTRACT

Earlier studies have introduced a list of high-level evaluation criteria to assess how well a language supports generic programming. Since each language that meets all criteria is considered generic, those criteria are not fine-grained enough to differentiate between languages for generic programming. We refine these criteria into a taxonomy that captures differences between type classes in Haskell and concepts in C++, and discuss which differences are incidental and which ones are due to other language features. The taxonomy allows for an improved understanding of language support for generic programming, and the comparison is useful for the ongoing discussions among language designers and users of both languages.

REFERENCES

• 1: Matthew H. Austern, Generic programming and the STL: using and extending the C++ Standard Template Library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 2: W. Brown, C. Jefferson, A. Meredith, and J. Widman. Named requirements for C++ concepts. Technical Report N2581=08-0091, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, Mar. 2008.
• 3: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• 4: Manuel M. T. Chakravarty , Gabriele Keller , Simon Peyton Jones, Associated type synonyms, ACM SIGPLAN Notices, v.40 n.9, September 2005
• 5: Manuel M. T. Chakravarty , Gabriele Keller , Simon Peyton Jones , Simon Marlow, Associated types with class, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-13, January 12-14, 2005, Long Beach, California, USA
• 6: Gabriel Dos Reis , Bjarne Stroustrup, Specifying C++ concepts, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-308, January 11-13, 2006, Charleston, South Carolina, USA
• 7: Ronald Garcia , Jaakko Jarvi , Andrew Lumsdaine , Jeremy Siek , Jeremiah Willcock, An extended comparative study of language support for generic programming, Journal of Functional Programming, v.17 n.2, p.145-205, March 2007 [doi>10.1017/S0956796806006198]
• 8: J. Gibbons. Datatype-generic programming. In Spring School on Datatype-Generic Programming, volume 4719 of LNCS, pages 1--71. Springer, 2007.
• 9: P. Gottschling. Fundamental algebraic concepts in concept-enabled C++. Technical Report 638, Indiana University, 2006.
• 10: P. Gottschling. Concept implication and requirement propagation. Technical Report N2646=08-0156, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, May 2008.
• 11: D. Gregor. ConceptGCC - a prototype compiler for C++ concepts. http://www.generic-programming.org/software/ConceptGCC/, Jan. 2008.
• 12: D. Gregor. Type-soundness and optimization in the concepts proposal. Technical Report N2576=08-0086, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, Mar. 2008.
• 13: D. Gregor and J. Siek. Implementing concepts. Technical Report N1848=05-0108, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, Aug. 2005.
• 14: Douglas Gregor , Jaakko Järvi , Jeremy Siek , Bjarne Stroustrup , Gabriel Dos Reis , Andrew Lumsdaine, Concepts: linguistic support for generic programming in C++, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 15: D. Gregor, B. Stroustrup, J. Widman, and J. Siek. Proposed wording for concepts (revision 5). Technical Report N2617=08-0127, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, May 2008.
• 16: R. Hinze and S. Peyton Jones. Derivable type classes. In G. Hutton, editor, Proc. 2000 ACM SIGPLAN Haskell Workshop, volume 41.1 of Electronic Notes in Theoretical Computer Science. Elsevier Science, 2001.
• 17: 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]
• 18: M. Jazayeri, R. Loos, and D. Musser, editors. Generic Programming: International Seminar, Dagstuhl Castle, Germany, 1998, Selected Papers, volume 1766 of LNCS, 2000. Springer.
• 19: 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]
• 20: 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
• 21: Mark P. Jones, Dictionary-free overloading by partial evaluation, Lisp and Symbolic Computation, v.8 n.3, p.229-248, Sept. 1995 [doi>10.1007/BF01019005]
• 22: W. Kahl and J. Scheffczyk. Named instances for Haskell type classes. In R. Hinze, editor, Proc. 2001 ACM SIGPLAN Haskell Workshop, pages 77--99. Elsevier Science, 2001.
• 23: O. Kiselyov and S. Peyton Jones. Choosing a type-class instance based on the context, Apr. 2008. URL http://haskell.org/haskellwiki/GHC/AdvancedOverlap.
• 24: O. Kiselyov and C.-C. Shan. Lightweight static resources, for safe embedded and systems programming. In Draft Proceedings of Trends in Functional Programming. Seton Hall University, 2007.
• 25: J. Meacham. Class alias proposal for Haskell, 2006. URL http://repetae.net/recent/out/classalias.html.
• 26: N. Mitchell. Deriving generic functions by example. Technical report, Dept. of Computer Science, University of York, UK, 2007. Tech. Report YCS-2007-421.
• 27: Gustav Munkby , Andreas Priesnitz , Sibylle Schupp , Marcin Zalewski, Scrap++: scrap your boilerplate in C++, Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159861.1159871]
• 28: S. Peyton Jones. Haskell 98 Language and Libraries: the Revised Report. Cambridge University Press, 2003.
• 29: S. Peyton Jones, M. Jones, and E. Meijer. Type classes: an exploration of the design space. In Haskell Workshop, 1997.
• 30: R. Rivera, B. Dawes, and D. Abrahams. The boost C++ libraries. http://www.boost.org/, 2008.
• 31: Alexey Rodriguez , Johan Jeuring , Patrik Jansson , Alex Gerdes , Oleg Kiselyov , Bruno C. d. S. Oliveira, Comparing libraries for generic programming in haskell, Proceedings of the first ACM SIGPLAN symposium on Haskell, September 25-25, 2008, Victoria, BC, Canada
• 32: Tom Schrijvers , Simon Peyton Jones , Manuel Chakravarty , Martin Sulzmann, Type checking with open type functions, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, September 20-28, 2008, Victoria, BC, Canada
• 33: T. Sheard. Generic programming in Ωmega. In Datatype-Generic Programming, volume 4719 of LNCS, pages 258--284. Springer, 2007.
• 34: Tim Sheard , Simon Peyton Jones, Template meta-programming for Haskell, ACM SIGPLAN Notices, v.37 n.12, December 2002 [doi>10.1145/636517.636528]
• 35: Jeremy G. Siek , Andrew Lumsdaine, Essential language support for generic programming, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 36: A. A. Stepanov and M. Lee. The standard template library. Technical Report HPL-95-11(R.1), Hewlett Packard Laboratories, Palo Alto, CA, USA, Nov. 1995.
• 37: Martin Sulzmann , Meng Wang, Modular generic programming with extensible superclasses, Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159861.1159869]
• 38: Martin Sulzmann , Manuel M. T. Chakravarty , Simon Peyton Jones , Kevin Donnelly, System F with type equality coercions, Proceedings of the 2007 ACM SIGPLAN international workshop on Types in languages design and implementation, January 16-16, 2007, Nice, Nice, France [doi>10.1145/1190315.1190324]
• 39: Martin Sulzmann , Gregory J. Duck , Simon Peyton-Jones , Peter J. Stuckey, Understanding functional dependencies via constraint handling rules, Journal of Functional Programming, v.17 n.1, p.83-129, January 2007 [doi>10.1017/S0956796806006137]
• 40: David Vandevoorde , Nicolai M. Josuttis, C++ Templates, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 41: 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]
• 42: J. Willcock, J. Järvi, A. Lumsdaine, and D. Musser. A formalization of concepts for generic programming. In Concepts: a Linguistic Foundation of Generic Programming at Adobe Tech Summit. Adobe Systems, Apr. 2004.
• 43: M. Zalewski, A. P. Priesnitz, C. Ionescu, N. Botta, and S. Schupp. Multi-language library development: From Haskell type classes to C++ concepts. In MPOOL 2007, 2007.

INDEX TERMS

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

General Terms:
Design, Languages

Keywords:
c++, concepts, generic programming, haskell, specification-driven development, type classes