Generic Programming and Library Development

Quarter 4, 2008

Template assignment

To get started, you should get the unknown X from Jyrki. This is a routine available in the C++ standard library (under header <algorithm> or <numeric>) that will also be part of the CPH STL. The exact specification of X can be found from the C++ standard [1].

This assignment is to be solved individually. However, we encourage you to discuss with your fellow students. Each student will work with different X, but the difficulties you encounter are similar, so you should be able to support each others.

When we started the CPH STL project (in 2000), our focus was on time and space efficiency of the STL components. During the years we have also put focus on safety, reliability, and usability of the components. In this assignment your task is to produce several useful extensions of routine X that deal with the latter aspects. The assignment consists of five problems (see below). To pass the assignment, you have to try to solve at least four of the five problems.

You should document your work by writing a short report (2-4 pages) using the LaTeX style DIKU-article. Include the code developed in the appendix of the report; consider using the listings package as in CPH STL report 2007-4 (see directory CPHSTL/Report/Associative-containers). Necessary instructions for using the style are available at the CPH STL home page under menu item Tools. You should commit the outcome of your work (including all files that are not auto-generated) to the CPH STL CVS repository by Friday, 2 May 2008 at 9.15. Add a new directory named after X under CPHSTL/Release/Algorithm/; the convention is that directory names start with capital letters. If you have many files, place the report in a separate subdirectory (with name Report) and all programs in another directory (with name Code). Your report directory should include a makefile that generates the report (you should be able to reuse, without any modifications, the makefile coming with the example how to use the LaTeX style (see CPHSTL/Report/Example).

To access the CVS repository, you need an account on the cphstl.dk computer. If the e-mail address you gave to us is of the form login-name@diku.dk, where login-name is meaningful, you should already have an account on that computer (with the same login name and password as on our other computers). However, if you cannot access the computer with ssh, visit Jyrki's office so he will open an account for you. If you have not used CVS earlier, consult the information available at http://www.cphstl.dk/tools.html.

Problems

1) Usability extension:

Normally, the generic algorithms of the C++ standard library operate on sequences specified by a pair of iterators. These iterators determine a half-open range of valid iterators. For iterators p and q the range can be denoted as [p, q). Provide an overloaded version (or versions) of X so that X can be called with a container or with a range. For example, for the routine find we would like to support the following type of usage (this is file example.c++ in directory CPHSTL/Release/Algorithm/Find):

#include "assert.h++" // defines dynamic_assert
#include "find.c++" // defines cphstl::find
#include "list.h++" // defines cphstl::list
#include "range.h++" // defines cphstl::range

int main() {
  int a[] = {1, 2, 3, 4};
  unsigned int const n = sizeof(a) / sizeof(a[0]);

  // normal usage

  int* p = cphstl::find(a, a + n, int());
  dynamic_assert(p == a + n);

  // range usage

  cphstl::range<int[n]> r(a);
  int const* q = cphstl::find(r, int());
  dynamic_assert(q == r.end());

  // container usage

  typedef cphstl::list<int> L;
  L list(a, a + n);
  L::const_iterator s = cphstl::find(list, int());
  dynamic_assert(s == list.end());
}

The included files can be found from the CPH STL CVS repository in directories CPHSTL/Release/Assert (assert.h++), CPHSTL/Release/Algorithm (find.h++), CPHSTL/Release/List (list.h++), and CPHSTL/Release/Common (range.h++).

2) Concept analysis:

Analyse the exact requirements on types for the parameters of routine X. A partial solution to this problem is provided in [2]. For the routine find, which has two overloaded versions, the type requirements posed for the parameters are given below. This information was deduced by studying the source code carefully.

template <typename P, typename V>
P 
find (P, P, V const&);

// Requirements:
// V has operator==
// P has operator*; unary
// Return type of operator* must be convertible to V
// P has operator==
// P has operator++
// P has operator=

template <typename C, typename V>
typename C::const_iterator 
find(C const&, V const&);

// Requirements:
// C has type member const_iterator
// C has function member begin
// C has function member end
// plus those for find(C::const_iterator, C::const_iterator, V const&);

3) Contract extension:

The C++ standard library relies on a cooperative design meaning that clients are responsible for using the library facilities in a correct way. For example, it is the user's responsibility to make sure that the pop_back member function of vector is not called if the vector is empty. (Especially, pop_back is not allowed to throw an exception.) In contrast, a defensive design holds the server responsible for carrying out correct operations and enforcing correct usage of itself under all circumstances. The experience shows that defensive systems are easier to test, maintain, and reuse. Also, they are more supportive for novice users.

Extend routine X with defensive contracts checking that all preconditions (and postconditions) are met for incoming (and outgoing) data. To check all compile-time requirements use static_assert, and to check all run-time requirements use dynamic_assert available at the CPH STL (see directory CPHSTL/Release/Assert). Some of the tools needed for implementing compile-time checks are not yet available at the library; the purpose is to build this part of the library collectively during the assignment period (to files CPHSTL/Release/Common/type.h++ and CPHSTL/Release/Common/type.c++).

4) Language extension:

According to modern C++0x terminology, a concept is a set of requirements on types bundled together under a single name. Concepts are already supported by an experimental C++ compiler conceptgcc (see [3]). Extend routine X so that the concept checks are performed in the syntax supported by conceptgcc. To actually compile and execute your programs, you have to download the compiler to your own computer, or use one of bach or kand computers at DIKU.

kand-1> conceptgcc -v
Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: ...
Thread model: posix
gcc version 4.3.0 20070330 (experimental) (Indiana University ConceptGCC alpha 6)

5) Testing:

You can use the version of X available at the CPH STL as a starting point for your work. Consult directory CPHSTL/Program/Algorithm. If it is not available, you have to develop it yourself; or if the current version does not compile, you have to correct the compilation errors first. Thereafter, develop the extensions 1-4 mentioned above, and test the correctness of all developed code. The examples described in [2] may be helpful when writing the testing code.

References

[1]

American National Standards Institute: International standard: Programming languages---C++, 2nd edition, ISO/IEC (2003) [pdf]

[2]

Matthew H. Austern: Generic programming and the STL---Using and extending the C++ standard template library (1999) [This book is in the PE-lab's library.]

[3]

The Trustees of Indiana University: Generic programming in ConceptC++ (2006-2008) [html]

Appendix: The module structure of the CPH STL CVS repository

CPHSTL
  Download---all released components
  Paper---all scientific articles
  Presentation---all slides
  Program---much of the code written during the years
  Release---the code planned to be released soon
  Report---all CPH STL reports
  Review---all design and code reviews
  Script---some useful scripts
  Tool---tools written as part of the project
  WWW---all web pages