Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Modern development practises encourage extensive testing of code while it is still under development, using unit tests to check individual code units in isolation. Such tests are typically case-based, checking a likely error scenario or an error that has previously been identified and fixed. Coming up with good test cases is challenging, and focusing on individual tests can distract from creating tests that cover the full functionality.

Axioms, known from program specification, allow for an alternative way of generating test cases, where the intended functionality is described as rules or equations that can be checked automatically. Axioms are proposed as part of the concept feature of the upcoming C++0x standard.

In this paper, we describe how tests may be generated automatically from axioms in C++ concepts, and supplied with appropriate test data to form effective automated unit tests.

REFERENCES

• 1: S. Antoy, Systematic design of algebraic specifications, Proceedings of the 5th international workshop on Software specification and design, p.278-280, April 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/75199.75241]
• 2: Sergio Antoy , Dick Hamlet, Automatically Checking an Implementation against Its Formal Specification, IEEE Transactions on Software Engineering, v.26 n.1, p.55-69, January 2000 [doi>10.1109/32.825766]
• 3: Anya Helene Bagge , Valentin David , Magne Haveraaen, Axiom-based testing for C++, Companion to the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA [doi>10.1145/1449814.1449829]
• 4: Anya Helene Bagge , Magne Haveraaen, Axiom-Based Transformations: Optimisation and Testing, Electronic Notes in Theoretical Computer Science (ENTCS), v.238 n.5, p.17-33, October, 2009 [doi>10.1016/j.entcs.2009.09.038]
• 5: A. H. Bagge and M. Haveraaen. Interfacing concepts: Why declaration style shouldn't matter. In T. Ekman and J. J. Vinju, editors, Proceedings of the Ninth Workshop on Language Descriptions, Tools and Applications (LDTA '09), Electronic Notes in Theoretical Computer Science. Elsevier, York, UK, March 2009.
• 6: K. Beck. Extreme programming: A humanistic discipline of software development. In Proceedings of the 1st International Conference on Fundamental Approaches to Software Engineering (FASE'98), pages 1--6. Springer Berlin / Heidelberg, 1998.
• 7: Beck, Test Driven Development: By Example, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 8: K. Beck and E. Gamma. JUnit -- Java Unit testing. http://www.junit.org and http://junit.sourceforge.net/ per 2007-03-15.
• 9: P. Becker. Working draft, standard for programming language C++. Technical Report N2857=09-0047, JTC1/SC22/WG21 -- The C++ Standards Committee, March 23rd, 2009.
• 10: Alexandre Borghi , Valentin David , Akim Demaille, C-Transformers: a framework to write C program transformations, Crossroads, v.12 n.3, p.3-3, Spring 2006 [doi>10.1145/1144366.1144369]
• 11: Martin Bravenboer , Karl Trygve Kalleberg , Rob Vermaas , Eelco Visser, Stratego/XT 0.16: components for transformation systems, Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 09-10, 2006, Charleston, South Carolina [doi>10.1145/1111542.1111558]
• 12: Huo Yan Chen , T. H. Tse , F. T. Chan , T. Y. Chen, In black and white: an integrated approach to class-level testing of object-oriented programs, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.250-295, July 1998 [doi>10.1145/287000.287004]
• 13: Huo Yan Chen , T. H. Tse , T. Y. Chen, TACCLE: a methodology for object-oriented software testing at the class and cluster levels, ACM Transactions on Software Engineering and Methodology (TOSEM), v.10 n.1, p.56-109, Jan. 2001 [doi>10.1145/366378.366380]
• 14: Koen Claessen , John Hughes, QuickCheck: a lightweight tool for random testing of Haskell programs, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.268-279, September 2000 [doi>10.1145/351240.351266]
• 15: Roong-Ko Doong, An approach to testing object-oriented programs, Polytechnic University, Brooklyn, NY, 1993
• 16: Roong-Ko Doong , Phyllis G. Frankl, Case studies on testing object-oriented programs, Proceedings of the symposium on Testing, analysis, and verification, p.165-177, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120822]
• 17: Roong-Ko Doong , Phyllis G. Frankl, The ASTOOT approach to testing object-oriented programs, ACM Transactions on Software Engineering and Methodology (TOSEM), v.3 n.2, p.101-130, April 1994 [doi>10.1145/192218.192221]
• 18: John Gannon , Paul McMullin , Richard Hamlet, Data Abstraction, Implementation, Specification, and Testing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.3, p.211-223, July 1981 [doi>10.1145/357139.357140]
• 19: Marie-Claude Gaudel, Testing Can Be Formal, Too, Proceedings of the 6th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, p.82-96, May 22-26, 1995
• 20: M.-C. Gaudel and P. L. Gall. Testing data types implementations from algebraic specifications. In Formal Methods and Testing, volume 4949 of Lecture Notes in Computer Science, pages 209--239. Springer, 2008.
• 21: J. Goguen, J. Thatcher, and E. Wagner. An initial algebra approach to the specification, correctness and implementation of abstract data types. In R. Yeh, editor, Current Trends in Programming Methodology, volume 4, pages 80--149. Prentice Hall, 1978.
• 22: P. Gottschling. Fundamental algebraic concepts in concept-enabled C++. Technical Report TR639, Department of Computer Science, Indiana University, 2006.
• 23: 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 [doi>10.1145/1167473.1167499]
• 24: D. Gregor and A. Lumsdaine. Core concepts for the C++0x standard library (revision 2). Technical Report N2621=08-0131, JTC1/SC22/WG21 -- The C++ Standards Committee, May 19th, 2008.
• 25: Walter J. Gutjahr, Partition Testing vs. Random Testing: The Influence of Uncertainty, IEEE Transactions on Software Engineering, v.25 n.5, p.661-674, September 1999 [doi>10.1109/32.815325]
• 26: J. Guttag, Notes on Type Abstraction (Version 2), IEEE Transactions on Software Engineering, v.6 n.1, p.13-23, January 1980 [doi>10.1109/TSE.1980.230209]
• 27: J. V. Guttag and J. J. Horning. The algebraic specification of abstract data types. Acta Inf., 10:27--52, 1978.
• 28: John V. Guttag , Ellis Horowitz , David R. Musser, Abstract data types and software validation, Communications of the ACM, v.21 n.12, p.1048-1064, Dec. 1978 [doi>10.1145/359657.359666]
• 29: Dick Hamlet , Ross Taylor, Partition Testing Does Not Inspire Confidence (Program Testing), IEEE Transactions on Software Engineering, v.16 n.12, p.1402-1411, December 1990 [doi>10.1109/32.62448]
• 30: R. Hamlet. Random testing. In J. Marciniak, editor, Encyclopedia of Software Engineering, pages 970--978. Wiley, 1994.
• 31: M. Haveraaen and E. Brkic. Structured testing in Sophus. In E. Coward, editor, Norsk informatikkonferanse NIK'2005, pages 43--54. Tapir akademisk forlag, Trondheim, Norway, 2005. URL http://www.nik.no/2005/.
• 32: M. Haveraaen, H. A. Friis, and H. Munthe-Kaas. Computable scalar fields: a basis for PDE software. Journal of Logic and Algebraic Programming, 65(1):36--49, September-October 2005.
• 33: Magne Haveraaen , Karl Trygve Kalleberg, JAxT and JDI: the simplicity of junit applied to axioms and data invariants, Companion to the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA [doi>10.1145/1449814.1449834]
• 34: Merlin Hughes , David Stotts, Daistish: systematic algebraic testing for OO programs in the presence of side-effects, Proceedings of the 1996 ACM SIGSOFT international symposium on Software testing and analysis, p.53-61, January 08-10, 1996, San Diego, California, United States [doi>10.1145/229000.226301]
• 35: K. T. Kalleberg. Abstractions for Language-Independent Program Transformations, chapter 11. University of Bergen, Norway, Postboks 7800, 5020 Bergen, Norway, June 2007. ISBN 978-82-308-0441-4.
• 36: Barbara Liskov , Stephen Zilles, Specification techniques for data abstractions, Proceedings of the international conference on Reliable software, p.72-87, April 21-23, 1975, Los Angeles, California [doi>10.1145/800027.808426]
• 37: Barbara Liskov , Stephen Zilles, Specification techniques for data abstractions, Proceedings of the international conference on Reliable software, p.72-87, April 21-23, 1975, Los Angeles, California [doi>10.1145/800027.808426]
• 38: M. Masood, E. Birkenes, K. T. Kalleberg, M. Haveraaen, and A. H. Bagge. Axiom-based testing of Java collections with JAxT. Technical Report 388, Department of Informatics, University of Bergen, P.O.Box 7803, N-5020 Bergen, Norway, August 2009. URL http://www.ii.uib.no/publikasjoner/texrap/.
• 39: I. S. W. B. Prasetya, T. E. J. Vos, and A. Baars. Trace-based reflexive testing of OO programs. Technical Report UU-CS-2007-037, Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands, 2007. URL http://www.cs.uu.nl/research/techreps/repo/CS-2007/2007-037.pdf.
• 40: David Saff, Theory-infected: or how i learned to stop worrying and love universal quantification, Companion to the 22nd ACM SIGPLAN conference on Object-oriented programming systems and applications companion, October 21-25, 2007, Montreal, Quebec, Canada [doi>10.1145/1297846.1297919]
• 41: Koushik Sen, Effective random testing of concurrent programs, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321679]
• 42: Jeremy G. Siek , Andrew Lumsdaine, The Matrix Template Library: A Unifying Framework for Numerical Linear Algebra, Workshop ion on Object-Oriented Technology, p.466-467, July 20-24, 1998
• 43: P. Sommerlad. C++ Unit Testing Easier, 2009. URL http://r2.ifs.hsr.ch/cute.
• 44: P. David Stotts , Mark Lindsey , Angus Antley, An Informal Formal Method for Systematic JUnit Test Case Generation, Proceedings of the Second XP Universe and First Agile Universe Conference on Extreme Programming and Agile Methods - XP/Agile Universe 2002, p.131-143, August 04-07, 2002
• 45: Xiaolong Tang , Jaakko Järvi, Concept-based optimization, Proceedings of the 2007 Symposium on Library-Centric Software Design, p.97-108, October 21-21, 2007, Montreal, Canada [doi>10.1145/1512762.1512772]
• 46: The Transformers Group, LRDE, EPITA. Transformers, 2008. URL http://www.lrde.epita.fr/cgi-bin/twiki/view/Transformers/Transformers.
• 47: Bo Yu , Liang Kong , Yufeng Zhang , Hong Zhu, Testing Java Components based on Algebraic Specifications, Proceedings of the 2008 International Conference on Software Testing, Verification, and Validation, p.190-199, April 09-11, 2008 [doi>10.1109/ICST.2008.39]
• 48: Hong Zhu, A Note on Test Oracles and Semantics of Algebraic Specifications, Proceedings of the Third International Conference on Quality Software, p.91, November 06-07, 2003

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

General Terms:
Design, Languages, Reliability

Keywords:
C++, C++0x, algebraic specification, axiom-based testing, axioms, concepts, generative programming, mouldable programming, program transformation, test generation, unit testing