Language Requirements for Large-Scale Generic Libraries

  • Jeremy Siek
  • Andrew Lumsdaine
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3676)


The past decade of experience has demonstrated that the generic programming methodology is highly effective for the design, implementation, and use of large-scale software libraries. The fundamental principle of generic programming is the realization of interfaces for entire sets of components, based on their essential syntactic and semantic requirements, rather than for any particular components. Many programming languages have features for describing interfaces between software components, but none completely support the approach used in generic programming. We have recently developed \(\mathcal{G}\), a language designed to provide first-class language support for generic programming and large-scale libraries. In this paper, we present an overview of \(\mathcal{G}\) and analyze the interdependence between language features and library design in light of a complete implementation of the Standard Template Library using \(\mathcal{G}\). In addition, we discuss important issues related to modularity and encapsulation in large-scale libraries and how language support for validation of components in isolation can prevent many common problems in component integration.


Generic Algorithm Generic Programming Language Feature Type Pass Type Requirement 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Kapur, D., Musser, D.R., Stepanov, A.: Operators and algebraic structures. In: Proc. of the Conference on Functional Programming Languages and Computer Architecture. ACM Press, Portsmouth (1981)Google Scholar
  2. 2.
    Musser, D.R., Stepanov, A.A.: Generic programming. In: Gianni, P. (ed.) ISSAC 1988. LNCS, vol. 358, pp. 13–25. Springer, Heidelberg (1989)Google Scholar
  3. 3.
    Musser, D.R., Stepanov, A.A.: A library of generic algorithms in Ada. In: Using Ada (1987 International Ada Conference), pp. 216–225. ACM SIGAda, New York (1987)Google Scholar
  4. 4.
    Kershenbaum, A., Musser, D., Stepanov, A.: Higher order imperative programming. Technical Report 88-10, Rensselaer Polytechnic Institute (1988)Google Scholar
  5. 5.
    Stroustrup, B.: Parameterized types for C++. In: USENIX C++ Conference (1988)Google Scholar
  6. 6.
    Stepanov, A.A., Lee, M.: The Standard Template Library. Technical Report X3J16/94-0095, WG21/N0482, ISO Programming Language C++ Project (1994)Google Scholar
  7. 7.
    Austern, M.H.: Generic Programming and the STL. Professional computing series. Addison-Wesley, Reading (1999)Google Scholar
  8. 8.
    Köthe, U.: Reusable Software in Computer Vision. In: Handbook on Computer Vision and Applications, vol. 3. Academic Press, London (1999)Google Scholar
  9. 9.
    Siek, J., Lee, L.Q., Lumsdaine, A.: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, Reading (2002)Google Scholar
  10. 10.
    Boissonnat, J.D., Cazals, F., Da, F., Devillers, O., Pion, S., Rebufat, F., Teillaud, M., Yvinec, M.: Programming with CGAL: the example of triangulations. In: Proceedings of the fifteenth annual symposium on Computational geometry, pp. 421–422. ACM Press, New York (1999)CrossRefGoogle Scholar
  11. 11.
    Pitt, W.R., Williams, M.A., Steven, M., Sweeney, B., Bleasby, A.J., Moss, D.S.: The bioinformatics template library: generic components for biocomputing. Bioinformatics 17, 729–737 (2001)CrossRefGoogle Scholar
  12. 12.
    Troyer, M., Todo, S., Trebst, S., Alet, F.: ALPS: Algorithms and Libraries for Physics Simulations,
  13. 13.
    Garcia, R., Jarvi, J., Lumsdaine, A., Siek, J., Willcock, J.: A comparative study of language support for generic programming. In: OOPSLA 2003: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, pp. 115–134. ACM Press, New York (2003)CrossRefGoogle Scholar
  14. 14.
    Siek, J., Lumsdaine, A.: Essential language support for generic programming. In: PLDI 2005: Proceedings of the ACM SIGPLAN 2005 conference on Programming language design and implementation, pp. 73–84. ACM Press, New York (2005)CrossRefGoogle Scholar
  15. 15.
    Girard, J.Y.: Interprétation Fonctionnelle et Élimination des Coupures de l’Arithmétique d’Ordre Supérieur. Thèse de doctorat d’état, Université Paris VII, Paris, France (1972)Google Scholar
  16. 16.
    Reynolds, J.C.: Towards a theory of type structure. In: Robinet, B. (ed.) Programming Symposium. LNCS, vol. 19, pp. 408–425. Springer, Heidelberg (1974)Google Scholar
  17. 17.
    Boost (Boost C++ Libraries),
  18. 18.
    International Organization for Standardization: ISO/ IEC 14882:1998: Programming languages — C++. International Organization for Standardization, Geneva, Switzerland (1998)Google Scholar
  19. 19.
    Liskov, B., Snyder, A., Atkinson, R., Schaffert, C.: Abstraction mechanisms in CLU. Communications of the ACM 20, 564–576 (1977)zbMATHCrossRefGoogle Scholar
  20. 20.
    Milner, R.: A theory of type polymorphism in programming. Journal of Computer and System Sciences 17, 348–375 (1978)zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    Bourbaki, N.: Elements of Mathematics. Theory of Sets. Springer, Heidelberg (1968)zbMATHGoogle Scholar
  22. 22.
    Wadler, P., Blott, S.: How to make ad-hoc polymorphism less ad-hoc. In: ACM Symposium on Principles of Programming Languages, pp. 60–76. ACM, New York (1989)Google Scholar
  23. 23.
    Chakravarty, M.M.T., Keller, G., Peyton Jones, S., Marlow, S.: Associated types with class. In: POPL 2005: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp. 1–13. ACM Press, New York (2005)CrossRefGoogle Scholar
  24. 24.
    Chakravarty, M.M.T., Keller, G., Jones, S.P.: Associated type synonyms. In: Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP 2005). ACM Press, New York (2005)Google Scholar
  25. 25.
    Canning, P., Cook, W., Hill, W., Olthoff, W., Mitchell, J.C.: F-bounded polymorphism for object-oriented programming. In: Proceedings of the fourth international conference on functional programming languages and computer architecture (1989)Google Scholar
  26. 26.
    Odersky, M., et al.: An overview of the scala programming language. Technical Report IC/2004/64, EPFL Lausanne, Switzerland (2004)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Jeremy Siek
    • 1
  • Andrew Lumsdaine
    • 1
  1. 1.Open Systems LaboratoryIndiana University 

Personalised recommendations