article

Essential language support for generic programming

Authors:

Jeremy G. Siek,

Andrew LumsdaineAuthors Info & Claims

ACM SIGPLAN Notices, Volume 40, Issue 6

Pages 73 - 84

https://doi.org/10.1145/1064978.1065021

Published: 12 June 2005 Publication History

Abstract

Concepts are an essential language feature for generic programming in the large. Concepts allow for succinct expression of constraints on type parameters of generic algorithms, enable systematic organization of problem domain abstractions, and make generic algorithms easier to use. In this paper we present the design of a type system and semantics for concepts that is suitable for non-type-inferencing languages. Our design shares much in common with the type classes of Haskell, though our primary influence is from best practices in the C++ community, where concepts are used to document type requirements for templates in generic libraries. Concepts include a novel combination of associated types and same-type constraints that do not appear in type classes, but that are similar to nested types and type sharing in ML.

References

[1]

Ada 95 Reference Manual, 1997.]]

[2]

J.-D. Boissonnat, F. Cazals, F. Da, O. Devillers, S. Pion, F. Rebufat, M. Teillaud, and M. Yvinec. Programming with CGAL: the example of triangulations. In Proceedings of the fifteenth annual symposium on Computational geometry, pages 421--422. ACM Press, 1999.]]

Digital Library

[3]

Boost. Boost C++ Libraries. http://www.boost.org/.]]

[4]

G. Bracha, N. Cohen, C. Kemper, S. Marx, et al. JSR 14: Add Generic Types to the Java Programming Language, April 2001. http://www.jcp.org/en/jsr/detail?id=014.]]

[5]

K. B. Bruce, A. Schuett, and R. van Gent. PolyTOIL: A type-safe polymorphic object-oriented language. In W. Olthoff, editor, Proceedings of ECOOP '95, number 952 in Lecture Notes in Computer Science, pages 27--51. Springer-Verlag, 1995.]]

Digital Library

[6]

P. Canning, W. Cook, W. Hill, W. Olthoff, and J. C. Mitchell. F-bounded polymorphism for object-oriented programming. In Proceedings of the fourth international conference on functional programming languages and computer architecture, 1989.]]

Digital Library

[7]

L. Cardelli and P. Wegner. On understanding types, data abstraction, and polymorphism. ACM Computing Surveys, 17(4):471--522, 1985.]]

Digital Library

[8]

M. Chakravarty, G. Keller, S. P. Jones, and S. Marlow. Associated types with class. In Proceedings of the 32nd ACM-SIGACT Symposium on Principles of Programming Languages, POPL 2005, Long Beach, California, pages 1--13. ACM, Jan. 2005.]]

Digital Library

[9]

K. Chen, P. Hudak, and M. Odersky. Parametric type classes. In LISP and Functional Programming, pages 170--181, 1992.]]

Digital Library

[10]

G. J. Ditchfield. Contextual polymorphism, 1994.]]

[11]

G. J. Ditchfield. Cforall reference manual and rationale, 1997.]]

[12]

E. Ernst. gbeta -- a Language with Virtual Attributes, Block Structure, and Propagating, Dynamic Inheritance. PhD thesis, Department of Computer Science, University of Aarhus, AArhus, Denmark, 1999.]]

[13]

E. Ernst. Family polymorphism. In ECOOP, volume 2072 of Lecture Notes in Computer Science, pages 303--326. Springer, June 2001.]]

Digital Library

[14]

R. Garcia, J. Järvi, A. Lumsdaine, J. Siek, and J. Willcock. A comparative study of language support for generic programming. In Proceedings of the 18th ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, pages 115--134. ACM Press, Oct. 2003.]]

Digital Library

[15]

J.-Y. Girard. Interprétation Fonctionnelle et Élimination des Coupures de l'Arithmetique d'Ordre Superieur. Thèse de doctorat d'état, Université Paris VII, Paris, France, 1972.]]

[16]

J. A. Goguen, T. Winker, J. Meseguer, K. Futatsugi, and J.-P. Jouannaud. Introducing OBJ. In Applications of Algebraic Specification using OBJ. Cambridge University Press, 1992.]]

[17]

C. V. Hall, K. Hammond, S. L. P. Jones, and P. L. Wadler. Type classes in Haskell. ACM Trans. Program. Lang. Syst., 18(2):109--138, 1996.]]

Digital Library

[18]

International Standardization Organization (ISO). ANSI/ISO Standard 14882, Programming Language C++. 1 rue de Varembé, Case postale 56, CH-1211 Genève 20, Switzerland, 1998.]]

[19]

J. Järvi, A. Lumsdaine, J. Siek, and J. Willcock. An analysis of constrained polymorphism for generic programming. In K. Davis and J. Striegnitz, editors, Multiparadigm Programming in Object-Oriented Languages Workshop (MPOOL) at OOPSLA, Anaheim, CA, Oct. 2003.]]

[20]

J. Järvi, J. Willcock, and A. Lumsdaine. Algorithm specialization and concept constrained genericity. In Concepts: a Linguistic Foundation of Generic Programming. Adobe Systems, Apr. 2004.]]

[21]

M. P. Jones. Type classes with functional dependencies. In European Symposium on Programming, number 1782 in LNCS, pages 230--244. Springer-Verlag, March 2000.]]

Digital Library

[22]

W. Kahl and J. Scheffczyk. Named instances for Haskell type classes. In R. Hinze, editor, Proc. Haskell Workshop 2001, volume 59 of ENTCS, 2001. See also: http://ist.unibw-muenchen.de/Haskell/NamedInstances/.]]

[23]

D. Kapur and D. Musser. Tecton: a framework for specifying and verifying generic system components. Technical Report RPI--92--20, Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York 12180, July 1992.]]

[24]

D. Kapur, D. R. Musser, and X. Nie. An overview of the tecton proof system. Theoretical Computer Science, 133:307--339, Oct. 1994.]]

Digital Library

[25]

D. Kapur, D. R. Musser, and A. Stepanov. Operators and algebraic structures. In Proc. of the Conference on Functional Programming Languages and Computer Architecture, Portsmouth, New Hampshire. ACM, 1981.]]

Digital Library

[26]

D. Katiyar, D. Luckham, and J. Mitchell. A type system for prototyping languages. In Conference Record of POPL '94: 21st ACM SIGPLAN--SIGACT Symposium of Principles of Programming Languages, Portland, Oregon, pages 138--150, 1994.]]

Digital Library

[27]

A. Kennedy and D. Syme. Design and implementation of generics for the .NET Common Language Runtime. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 1--12, Snowbird, Utah, June 2001.]]

Digital Library

[28]

A. Kershenbaum, D. Musser, and A. Stepanov. Higher order imperative programming. Technical Report 88-10, Rensselaer Polytechnic Institute, 1988.]]

[29]

U. Köthe. Handbook on Computer Vision and Applications, volume 3, chapter Reusable Software in Computer Vision. Acadamic Press, 1999.]]

[30]

D. Le Botlan and D. Rémy. MLF: Raising ML to the power of System-F. In Proceedings of the International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden, pages 27--38. ACM Press, aug 2003.]]

Digital Library

[31]

X. Leroy, D. Doligez, J. Garrigue, D. Remy, and J. Vouillon. The Object Caml Documentation and User's Manual, September 2003.]]

[32]

B. Liskov, R. Atkinson, T. Bloom, E. Moss, C. Schaffert, B. Scheifler, and A. Snyder. CLU reference manual. Technical Report LCS-TR-225, Cambridge, MA, USA, October 1979.]]

Digital Library

[33]

B. Liskov and J. Guttag. Abstraction and specification in program development. MIT Press, Cambridge, MA, USA, 1986.]]

Digital Library

[34]

D. MacQueen. An implementation of Standard ML modules. In Proceedings of the 1988 ACM Conference on LISP and Functional Programming, Snowbird, UT, pages 212--223, New York, NY, 1988. ACM.]]

Digital Library

[35]

B. Meyer. Eiffel: the Language. Prentice Hall, New York, NY, first edition, 1992.]]

Digital Library

[36]

Microsoft Corporation. Generics in C, September 2002. Part of the Gyro distribution of generics for .NET available at http://research.microsoft.com/projects/clrgen/.]]

[37]

R. Milner, M. Tofte, and R. Harper. The Definition of Standard ML. MIT Press, 1990.]]

Digital Library

[38]

J. C. Mitchell. Polymorphic type inference and containment. Information and Computation, 76(2-3):211--249, 1988.]]

Digital Library

[39]

D. R. Musser and A. Stepanov. Generic programming. In ISSAC: Proceedings of the ACM SIGSAM International Symposium on Symbolic and Algebraic Computation, 1988.]]

Digital Library

[40]

D. R. Musser and A. A. Stepanov. A library of generic algorithms in Ada. In Using Ada (1987 International Ada Conference), pages 216--225, New York, NY, Dec. 1987. ACM SIGAda.]]

Digital Library

[41]

G. Nelson and D. C. Oppen. Fast decision procedures based on congruence closure. J. ACM, 27(2):356--364, 1980.]]

Digital Library

[42]

T. Nipkow. Structured Proofs in Isar/HOL. In H. Geuvers and F. Wiedijk, editors, Types for Proofs and Programs (TYPES 2002), volume 2646, pages 259--278, 2003.]]

Digital Library

[43]

T. Nipkow, L. C. Paulson, and M.Wenzel. Isabelle/HOL --- A Proof Assistant for Higher-Order Logic, volume 2283 of LNCS. Springer, 2002.]]

Digital Library

[44]

M. Odersky and al. An overview of the scala programming language. Technical Report IC/2004/64, EPFL Lausanne, Switzerland, 2004.]]

[45]

M. Odersky, V. Cremet, C. Röckl, and M. Zenger. A nominal theory of objects with dependent types. In Proc. ECOOP'03, Springer LNCS, 2003.]]

[46]

M. Odersky and K. Läufer. Putting type annotations to work. In Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 54--67. ACM Press, 1996.]]

Digital Library

[47]

B. C. Pierce. Intersection types and bounded polymorphism. Mathematical Structures in Computer Science, 11, 1996.]]

Digital Library

[48]

B. C. Pierce. Types and Programming Languages. MIT Press, 2002.]]

Digital Library

[49]

W. R. Pitt, M. A. Williams, M. Steven, B. Sweeney, A. J. Bleasby, and D. S. Moss. The bioinformatics template library: generic components for biocomputing. Bioinformatics, 17(8):729--737, 2001.]]

[50]

E. Poll and S. Thompson. The Type System of Aldor. Technical Report 11-99, Computing Laboratory, University of Kent at Canterbury, Kent CT2 7NF, UK, July 1999.]]

[51]

D. Rémy and J. Vouillon. Objective ML: An effective object-oriented extension to ML. Theory And Practice of Object Systems, 4(1):27--50, 1998. A preliminary version appeared in the proceedings of the 24th ACM Conference on Principles of Programming Languages, 1997.]]

Digital Library

[52]

J. C. Reynolds. Towards a theory of type structure. In B. Robinet, editor, Programming Symposium, volume 19 of Lecture Notes in Computer Science, pages 408--425, Berlin, 1974. Springer-Verlag.]]

Digital Library

[53]

J. Siek, L.-Q. Lee, and A. Lumsdaine. The generic graph component library. In Proceedings of the 1999 ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 399--414. ACM Press, 1999.]]

Digital Library

[54]

J. Siek, L.-Q. Lee, and A. Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, 2002.]]

Digital Library

[55]

J. Siek and A. Lumsdaine. Essential language support for generic programming: Formalization part 1. Technical Report 605, Indiana University, December 2004.]]

[56]

J. G. Siek and A. Lumsdaine. Advances in Software Tools for Scientific Computing, chapter A Modern Framework for Portable High Performance Numerical Linear Algebra. Springer, 2000.]]

[57]

Silicon Graphics, Inc. SGI Implementation of the Standard Template Library, 2004. http://www.sgi.com/tech/stl/.]]

[58]

A. Stepanov. gclib. http://www.stepanovpapers.com, 1987.]]

[59]

A. A. Stepanov and M. Lee. The Standard Template Library. Technical Report X3J16/94-0095, WG21/N0482, ISO Programming Language C++ Project, May 1994.]]

[60]

B. Stroustrup. Parameterized types for C++. In USENIX C++ Conference, October 1988.]]

[61]

J. Tiuryn and P. Urzyczyn. The subtyping problem for second-order types is undecidable. Information and Computation, 179(1):1--18, 2002.]]

Digital Library

[62]

M. Troyer, S. Todo, S. Trebst, and A. F. and. ALPS: Algorithms and Libraries for Physics Simulations. http://alps.comp-phys.org/.]]

[63]

P. Wadler and S. Blott. How to make ad-hoc polymorphism less ad-hoc. In ACM Symposium on Principles of Programming Languages, pages 60--76. ACM, Jan. 1989.]]

Digital Library

[64]

J. Walter and M. Koch. uBLAS. Boost. http://www.boost.org/libs/numeric/ublas/doc/index.htm.]]

[65]

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.]]

Cited By

Oliveira BSchrijvers TChoi WLee WYi K(2012)The implicit calculusACM SIGPLAN Notices10.1145/2345156.225407047:6(35-44)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2345156.2254070
Gibbons J(2007)Datatype-Generic ProgrammingDatatype-Generic Programming10.1007/978-3-540-76786-2_1(1-71)Online publication date: 2007
https://doi.org/10.1007/978-3-540-76786-2_1
Chakravarty MKeller GJones S(2005)Associated type synonymsACM SIGPLAN Notices10.1145/1090189.108639740:9(241-253)Online publication date: 12-Sep-2005
https://dl.acm.org/doi/10.1145/1090189.1086397
Show More Cited By

Index Terms

Essential language support for generic programming
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Abstract data types
        Constraints
        Polymorphism
      2. Language types
        Multiparadigm languages
    2. Software libraries and repositories

Recommendations

Essential language support for generic programming
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

Concepts are an essential language feature for generic programming in the large. Concepts allow for succinct expression of constraints on type parameters of generic algorithms, enable systematic organization of problem domain abstractions, and make ...
A comparative study of language support for generic programming
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications

Many modern programming languages support basic generic programming, sufficient to implement type-safe polymorphic containers. Some languages have moved beyond this basic support to a broader, more powerful interpretation of generic programming, and ...
A comparative study of language support for generic programming
Special Issue: Proceedings of the OOPSLA '03 conference

Many modern programming languages support basic generic programming, sufficient to implement type-safe polymorphic containers. Some languages have moved beyond this basic support to a broader, more powerful interpretation of generic programming, and ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 40, Issue 6

Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

June 2005

325 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1064978

Issue’s Table of Contents

PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation
June 2005
338 pages
ISBN:1595930566
DOI:10.1145/1065010
General Chair:
Vivek Sarkar
IBM Research
,
Program Chair:
Mary Hall
USC/ISI

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2005

Published in SIGPLAN Volume 40, Issue 6

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
1,229
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Oliveira BSchrijvers TChoi WLee WYi K(2012)The implicit calculusACM SIGPLAN Notices10.1145/2345156.225407047:6(35-44)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2345156.2254070
Gibbons J(2007)Datatype-Generic ProgrammingDatatype-Generic Programming10.1007/978-3-540-76786-2_1(1-71)Online publication date: 2007
https://doi.org/10.1007/978-3-540-76786-2_1
Chakravarty MKeller GJones S(2005)Associated type synonymsACM SIGPLAN Notices10.1145/1090189.108639740:9(241-253)Online publication date: 12-Sep-2005
https://dl.acm.org/doi/10.1145/1090189.1086397
Chakravarty MKeller GJones SDanvy OPierce B(2005)Associated type synonymsProceedings of the tenth ACM SIGPLAN international conference on Functional programming10.1145/1086365.1086397(241-253)Online publication date: 28-Sep-2005
https://dl.acm.org/doi/10.1145/1086365.1086397
Racordon DChung BEdwards JTaeumel M(2024)Use Site Checking Considered HarmfulProceedings of the 2024 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3689492.3689814(275-287)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3689492.3689814
Racordon DLaemmel RPereira JMosses P(2024)Type Checking with Rewriting RulesProceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3687997.3695640(171-183)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3687997.3695640
Racordon DFlesselle EBovel MErtl MKirsch C(2024)Existential Containers in ScalaProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685056(55-64)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685056
Yallop JWhite L(2019)Lambda: the ultimate sublanguage (experience report)Proceedings of the ACM on Programming Languages10.1145/33427133:ICFP(1-17)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3342713
Karafotias GTeranishi AKorres GEyssel FCopti SEid M(2017)Intensifying Emotional Reactions via Tactile Gestures in Immersive FilmsACM Transactions on Multimedia Computing, Communications, and Applications10.1145/309284013:3(1-17)Online publication date: 28-Jun-2017
https://dl.acm.org/doi/10.1145/3092840
Lin SLin YChen CHung Y(2017)Recognizing Human Actions with Outlier Frames by Observation Filtering and CompletionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/308925013:3(1-23)Online publication date: 28-Jun-2017
https://dl.acm.org/doi/10.1145/3089250
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents