The Artima Developer Community
Sponsored Link

The C++ Source
Contract Programming 101
The Nuclear Reactor and the Deep Space Probe, Part I
by Matthew Wilson
January 1, 2006

<<  Page 4 of 4

Advertisement

Unfortunately, there tends to be ambiguities in the use of exceptions in some languages/libraries, which can lead to confusion over what falls within the purview of contract programming. In Java, exceptions will be thrown upon array overflow errors. This exception is part of the specification of Java. So, the following code is legitimate Java:

try
{
  int[] array = new int[10];
  int   i;

  for(i = 0; ; ++i)
  {}
}
catch(ArrayIndexOutOfBoundsException e)
{}					
Thus we see the overflow exception being used as part of the normal control flow logic. Some Java programmers use this practice, meaning that array overflows in Java are not useable for contract programming purposes, because that would violate the Principle of Removability.

The same situation exists with regards to the at() member of C++�s std::basic_string, and appears to cause quite a degree of misunderstanding, generally in confusion between whether operator []() and at() are equivalent. Let�s have a look at at()�s signature:

const_reference at(size_type index) const;
reference       at(size_type index);
The C++ standard [18] states the following:
Requires: index <= size()
Throws: out_of_range, if index >= size()
Returns: operator [](index)

From a contract programming perspective, this is a little misleading, since the Requires part inclines one to think that the contract stipulates that index <= size(). This is not so. Indeed the precondition for at() is empty, i.e. the sum of all possible values for index [19]:

at()�s Precondition: (empty)
The postcondition is where the interest resides, since it states:
at()�s Postcondition: returns reference to the index�th element if index < size(), otherwise throws out_of_range.
In other words, if index is within range it returns a reference to the corresponding element, otherwise it throws an exception. All that�s none too surprising. Now consider how this differs from the operator []() method(s):
     const_reference operator [](size_type index) const;
     reference       operator [](size_type index);
The standard [18] states:
Returns: If index < size() returns data()[index]. Otherwise, if index == size(), the const version returns charT(). Otherwise, the behaviour is undefined.
This is a thoroughly different kettle of fish. If we request a valid index we get back a reference to the corresponding element, just as with at(). (Note that the const version defines the valid range to be [0, size() + 1), whereas in the non- const case it is [0, size()). Go figure! [20]) However, if we do not get the index right, the behaviour is undefined.
Termin(ologic)al interlude

Here's a simple rule for anyone that's confused about what the language dictates: The C++ standard [18] does not address the issue of contract enforcement at all, although it does do an acceptable job of the description of the contracted behaviour (ambiguous language such as basic_string�s at()�s "Requires" notwithstanding).

Therefore, you cannot talk of any part of the standard library as enforcing a contract, since it only ever refers to undefined behaviour. Some implementations, e.g. Metrowerks', use assertions, and therefore may be said to enforce contracts, but the standard merely leaves such things up to the implementor. If you�re writing STL extension libraries—e.g. Boost [ 21], STLSoft [22]—you can interpret each "undefined behaviour" as a potential place for contract enforcement.


There are clear differences between the contract for at() and operator [](). The contract for the mutable (non-const) version of operator []() is as follows:
operator []()�s Precondition: index < size() operator []()�s Postcondition: returns reference to the index�th element.
Other than confused users and an over-baked standard string class [23], what are the ramifications of these differences? Simply, it means that different element access paradigms are supported. The normal manipulation of arrays in C and C++, via knowing the range, is supported by operator []():
int main()
{
  std::string   s(�Something or other");
  for(std::string::size_type i = 0; i < s.size(); ++i)
  {
    std::cout << i << ": " << s[i] << std::endl;
  }
  return 0;
}
And the catch-out-of-bounds method, as shown in the Java example earlier, is supported by at():
 int main()
 {
  std::string   s(�Something or other");
  try
  {
    for(std::string::size_type i = 0; ; ++i)
    {
      std::cout << i << ": " << s.at(i) << std::endl;
    }
  }
  catch(std::out_of_range &)
  {} // Do nothing
  return 0;
}
It is important to realise that these both represent entirely valid programs, in which the client code respects the contracts of the respective std::basic_string methods used. To reiterate, specifying an out-of-bounds index for at() is not a contract violation, whereas it most certainly is for operator [](). This delineation between exception-throwing and undefined behaviour (i.e. contract violations) exists equally outside the standard. Consider the STL mapping for the Open-RJ library [24]. The record classes provides an operator [](char_type const *fieldName), which throws a std::out_of_range if fieldName does not corresponding to an existing field for that record within the database. Now it's certainly not the case that asking for a field (by name) that does not exist is invalid code. It affords a simple and elegant style in client code:
openrj::stl::file_database db("pets.orj", openrj::ELIDE_BLANK_RECORDS);

try
{
  for(openrj::stl::database::iterator b =  db.begin(); . . .  ) // enumerating db's records
  {
    openrj::stl::record  r(*b);

    std::cout << "Pet: name: " << r["Name"]
              << "; species: " << r["Species"]
              << "; weight: "  << r["Weight"]
              << std::endl;
  }
  catch(std::out_of_range &)
  {
    std::cout << "One of the records did not have the Name, Species and Weight fields" 
              << std::endl;
  }
The record class also provides an operator [](size_type index) method, for which an out of bounds index represents a contract violation. Thus, the following code is a badly formed program:
    . . .
    openrj::cpp::Record  record(*b);
    for(size_t i = 0; ; ++i)
    {
      std::cout << record[i].name << ": " << record[i].value << std::endl;
    }
    . . .
Whereas the former is perfectly valid code, and is a reasonable tool for checking the validity of Pets databases—using Record::operator []()�s thrown exception in the case that a record does not contain a field of the given name—the latter is ill-formed, and is going to cause you grief (i.e. a crash).

And if you�re still sceptical whether exceptions may be part of a function�s contract, consider the case of the operator new() function. If throwing an instance of bad_alloc (or something derived from bad_alloc) were not within its contract, it would mean that memory exhaustion—a runtime condition largely outside the control of the program designer—would be a contract violation, that is to say an unequivocal statement of design contradiction! Now that�d make writing good software something of a challenge ...

In Part 2 ...

I will dive deeper into the ramifications of failure, and present The Principle of Irrecoverability along with some case studies that help address objections that have been raised to it. I will finish by examining The Fallacy of the Recoverable Precondition Violation, which will lead nicely into Part 3.

Acknowledgements

Thanks to Bjorn Karlsson, Christopher Diggins, Chuck Allison, John Torjo, Thorsten Ottosen and Walter Bright for a lengthy and bracing discussion of this and other contract programming issues throughout October 2004. There were tears, fears, jeers and a few leers—sadly no beers—but I think we�re all the better for it. A special thought of sympathy for Walter, whose views most closely approximate those of my own—what a crazy cookie!—and several of whose gnomic observations have been incorporated into the text in several places

Thanks also to the members of the D newsgroup (news://news.digitalmars.com/d) for a similarly stimulating discussion in April 2005, particularly Ben Hinkle, Derek Parnell, George Wrede, and Regan Heath. You made me work very hard to fill in the gaps in the Principle of Irrecoverability that had previously only been held together by instinct and crossed fingers. Special thanks to Sean Kelly for stimulating the thought process that led to The Fallacy of the Recoverable Precondition Violation (part 2).

Thanks also to the following reviewers: Andrew Hunt, Bjorn Karlsson, Christopher Diggins, Kevlin Henney, Nevin Liber, Sean Kelly, Thorsten Ottosen, Walter Bright. Special thanks to Chris, whose dryness and rigour in review has proven such a valuable compliment to my intuition and verbosity, and to Kevlin, whose eloquent criticism would gently give pause to the most doubtless evangelist. And I�d also like to thank my editor Chuck Allison, for actions above and beyond the call of duty in helping me prepare this leviathan meal into digestible servings.

Despite all help received, any errors, bad jokes and poor judgements are my own.

Thank you for reading,
Matthew Wilson

References

  1. Object-Oriented Software Construction, Bertrand Meyer, Prentice Hall, 1997
  2. The Eiffel Programming Language (http://www.eiffel.com)
  3. Proposal to add Contract Programming to C++, Lawrence Crowl and Thorsten Ottosen, WG21/N1773 and J16/05-0033, 4 March 2005 ( http://www.open- std.org/JTC1/SC22/WG21/docs/papers/2005/n1773.html)
  4. Email correspondence with Kevlin Henney, June 2005
  5. Design by Contract; A Conversation with Bertrand Meyer, Part II, Bill Venners, Artima, 8 December 2003 ( http://www.artima.com/intv/contracts.html)
  6. Email correspondence with Christopher Diggins, May 2005
  7. Imperfect C++, Matthew Wilson, Addison-Wesley, 2004 (http://imperfectcplusplus.com/)
  8. Sorted, Kevlin Henney, Application Development Advisor, July-August 2003.
  9. Digital Mars C/C++ compiler Contract Programming support ( www.digitalmars.com/ctg/contract.html).
  10. The Pragmatic Programmer, Dave Hunt and Andy Thomas, Addison-Wesley, 2000
  11. Email conversation with Christopher Diggins, October 2004
  12. D is a new systems programming language, created by Walter Bright (of Digital Mars; http://www.digitalmars.com/), which merges many of the best features of C, C++ and other advanced languages, including support for contract progamming.
  13. The Practice of Programming, Kernighan and Pike, Addison-Wesley, 1999
  14. The Art of UNIX Programming, Eric Raymond, Addison-Wesley, 2003
  15. Jumping from the top of the parachutes, Matthew Wilson, Weblog 18 April 2005 ( http://www.artima.com/weblogs/viewpost.jsp?thread=104862)
  16. Programming With POSIX Threads, David R. Butenhof, Addison-Wesley, 1997
  17. Advanced Windows, Jeffrey Richter, Microsoft Press, 1997
  18. The C++ Standard, ISO/IEC 14882:98
  19. Thorsten Ottosen suggested, in an email conversation in May 2005, an alternative representation for a precondition that allows all possible values as true, rather than the empty condition. This would nicely balance the theoretical condition false for a function that had no satisfiable precondition. We�ve all come across a couple of those in our travels � ;)
  20. Obviously the reason is that returning a non-mutable (const) reference to the null-terminator is harmless, whereas returning a mutable (non-const) reference is anything but. Whether this inconsistency is worth the modest increase in non-mutable flexibility is a debate outside the scope of this article.
  21. Boost is an open-source organisation whose focus is the development of libraries that integrate with the C++ Standard Library, and is located at http://boost.org/. It has thousands of members, including many of the top names in the C++ software community.
  22. STLSoft is an open-source organisation whose focus is the development of robust, lightweight, simple-to- use, cross-platform STL-compatible software, and is located at http://stlsoft.org/. It has fewer members than Boost.
  23. Stringing Things Along, Kevlin Henney, Application Development Advisor, Volume 6 Number 6, July/August 2002.
  24. Open-RJ is an open-source, platform-independent structured file reader library for the Record JAR format. It�s available from http://openrj.org/.
The Nuclear Reactor and the Deep Space Probe, Part 1
Matthew Wilson
©2004-2006.

About the Author

Matthew is a development consultant for Synesis Software, and creator of the STLSoft libraries. He is author of Imperfect C++ (Addison-Wesley, 2004), and is currently working on volume 1 of his modicum opus, Extended STL, to be published in 2006. Matthew can be contacted via http://imperfectcplusplus.com/.

<<  Page 4 of 4


Sponsored Links



Google
  Web Artima.com   
Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us