Beyond templates: a study of clones in the STL and some general implications

ABSTRACT

Templates (or generics) help us write compact, generic code, which aids both reuse and maintenance. The STL is a powerful example of how templates help achieve these goals. Still, our study of the STL revealed substantial, and in our opinion, counter-productive repetitions (so-called clones) across groups of similar class or function templates. Clones occurred, as variations across these similar program structures were irregular and could not be unified by suitable template parameters in a natural way. We encountered similar problems in other class libraries as well as in application programs, written in a range of programming languages. In the paper, we present quantitative and qualitative results from our study. We argue that the difficulties we encountered affect programs in general. We present a solution that can treat such template-unfriendly cases of redundancies at the meta-level, complementing and extending the power of language features, such as templates, in areas of generic programming.

REFERENCES

• 1: B. S. Baker, On finding duplication and near-duplication in large software systems, Proceedings of the Second Working Conference on Reverse Engineering, p.86, July 14-16, 1995
• 2: Magdalena Balazinska , Ettore Merlo , Michel Dagenais , Bruno Lague , Kostas Kontogiannis, Partial Redesign of Java Software Systems Based on Clone Analysis, Proceedings of the Sixth Working Conference on Reverse Engineering, p.326, October 06-08, 1999
• 3: Magdalena Balazinska , Ettore Merlo , Michel Dagenais , Bruno Lagüe , Kostas Kontogiannis, Advanced Clone-Analysis to Support Object-Oriented System Refactoring, Proceedings of the Seventh Working Conference on Reverse Engineering (WCRE'00), p.98, November 23-25, 2000
• 4: Paul G. Bassett, Framing software reuse: lessons from the real world, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 5: Don Batory , Vivek Singhal , Marty Sirkin , Jeff Thomas, Scalable software libraries, Proceedings of the 1st ACM SIGSOFT symposium on Foundations of software engineering, p.191-199, December 08-10, 1993, Los Angeles, California, United States
• 6: Ira D. Baxter , Andrew Yahin , Leonardo Moura , Marcelo Sant'Anna , Lorraine Bier, Clone Detection Using Abstract Syntax Trees, Proceedings of the International Conference on Software Maintenance, p.368, March 16-19, 1998
• 7: Biggerstaff, T. "The library scaling problem and the limits of concrete component reuse," 3rd Int'l. Conf. on Software Reuse, ICSR'94, 1994, pp. 102--109.
• 8: Bracha G. et al. "JSR 14: Add Generic Types to the Java™ Programming Language," Java Community Process, http://www.jcp.org/en/jsr/detail?id=14
• 9: Frederick P. Brooks, Jr., The mythical man-month (anniversary ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 10: T. John Brown , Ivor Spence , Peter Kilpatrick , Danny Crookes, Adaptable Components for Software Product Line Engineering, Proceedings of the Second International Conference on Software Product Lines, p.154-175, August 19-22, 2002
• 11: Case Studies on XVCL Website, http://fxvcl.sourceforge.net/CaseStudy.htm
• 12: James R. Cordy, Comprehending Reality " Practical Barriers to Industrial Adoption of Software Maintenance Automation, Proceedings of the 11th IEEE International Workshop on Program Comprehension, p.196, May 10-11, 2003
• 13: Krzysztof Czarnecki , Ulrich W. Eisenecker, Generative programming: methods, tools, and applications, ACM Press/Addison-Wesley Publishing Co., New York, NY, 2000
• 14: Stéphane Ducasse , Matthias Rieger , Serge Demeyer, A Language Independent Approach for Detecting Duplicated Code, Proceedings of the IEEE International Conference on Software Maintenance, p.109, August 30-September 03, 1999
• 15: Michael D. Ernst , Greg J. Badros , David Notkin, An Empirical Analysis of C Preprocessor Use, IEEE Transactions on Software Engineering, v.28 n.12, p.1146-1170, December 2002 [doi>10.1109/TSE.2002.1158288]
• 16: Refactoring: improving the design of existing code, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 17: Ronald Garcia , Jaakko Jarvi , Andrew Lumsdaine , Jeremy G. Siek , Jeremiah Willcock, A comparative study of language support for generic programming, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 18: Home page of SGI STL, http://www.sgi.com/tech/stl/
• 19: Stan Jarzabek , Li Shubiao, Eliminating redundancies with a "composition with adaptation" meta-programming technique, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 20: J. Howard Johnson, Substring Matching for Clone Detection and Change Tracking, Proceedings of the International Conference on Software Maintenance, p.120-126, September 01, 1994
• 21: Toshihiro Kamiya , Shinji Kusumoto , Katsuro Inoue, CCFinder: a multilinguistic token-based code clone detection system for large scale source code, IEEE Transactions on Software Engineering, v.28 n.7, p.654-670, July 2002 [doi>10.1109/TSE.2002.1019480]
• 22: Anssi Karhinen , Alexander Ran , Tapio Tallgren, Configuring designs for reuse, Proceedings of the 19th international conference on Software engineering, p.701-710, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253839]
• 23: Andrew Kennedy , Don Syme, Design and implementation of generics for the .NET Common language runtime, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.1-12, June 2001, Snowbird, Utah, United States
• 24: David R. Musser , Gilmer J. Derge , Atul Saini, STL tutorial and reference guide, second edition: C++ programming with the standard template library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 25: William F. Opdyke, Refactoring object-oriented frameworks, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 26: David Lorge Parnas, Software aging, Proceedings of the 16th international conference on Software engineering, p.279-287, May 16-21, 1994, Sorrento, Italy
• 27: Thompson, S., "Higher Order + Polymorphic = Reusable", unpublished manuscript available from the Computing Laboratory, University of Kent. http://www.cs.ukc.ac.uk/pubs/1997
• 28: "XML-based Variant Configuration Language," XVCL Website, http://fxvcl.sourceforge.net
• 29: Hongyu Zhang , Stan Jarzabek, An XVCL Approach to Handling Variants: A KWIC Product Line Example, Proceedings of the Tenth Asia-Pacific Software Engineering Conference Software Engineering Conference, p.116, December 10-12, 2003
• 30: Zhang, H. and Jarzabek, S., "An XVCL-based Approach to Software Product Line Development", Proc. 15th International Conference on Software Engineering and Knowledge Engineering (SEKE'03), San Francisco, USA, 1-3 July, 2003.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Domain engineering; Reusable libraries
      D.2.2 Design Tools and Techniques

General Terms:
Design, Experimentation, Languages

Keywords:
clones, meta-programming, software maintenance