License : Creative Commons Attribution 4.0 International (CC BY-NC-SA 4.0)
Copyright : Frédéric Pennerath, CentraleSupelec
Last modified : April 19, 2024 10:22
Link to the source : generic-programming.md

Generic programming: the basic facts

What is generic programming?

• Generic Programming (hereafter abbreviated GP) is the art of designing and implementing efficiently generic libraries based on templates.
• The goal of Generic Programming is to design generic algorithms and data structures so that their application scope is the widest possible without sacrificing performance.
• The Standard Template Library (or STL) is the perfect prototypical example that illustrates generic programming.
• Generic Programming and Object Oriented Programming (hereafter abbreviated OOP) are often presented as competitors. These two paradigms are actually complementary as they address different problems.

What are the main advantages of Generic Programming over OOP?

Solutions based on templates are generally more:

• General: a generic algorithm requires less constraints than its counterpart (object oriented libraries require inheritance, etc).
• Robust: templates produce strongly-typed code, bringing strong guarantees about code consistency when OOP does not.
• Elegant: templates can be instantiated very easily, with a natural and concise syntax.
• Performant: in many cases, OOP introduce additional operations that slow down runtime compared to the equivalent PG solution.

What are the limitations of GP?

One could ask why GP and OOP are complementary if GP has only advantages over OOP. This is because the genericity of GP is limited to compilation time whereas OOP can bring polymorphism at runtime, thanks to virtual functions.

Why is it important to understand principles of generic programming?

• To better leverage features provided by the standard library and Boost.
• To debug more easily codes instantiating templates.
• To better design and develop his own template libraries.

But wait, C++ is not the only language to have generic data structures?

In weakly typed interpreted languages like Python, you can even store values of any types in the same list (which is indeed a dynamic array or vector):

L = [ 1, 3.1415 ]
L.append('blah blah')

Even in strongly typed compiled languages like Java, you can write:

import java.util.Vector;

Vector v = new Vector();
v.add(1);     // Actually rewritten as v.add(new Integer(1));
v.add(true);  // Actually rewritten as v.add(new Boolean(true));

You can even have strong typing thanks to generics that mimic syntactically C++ templates:

import java.util.Vector;

Vector v = new Vector<Integer>();
v.add(1);     // Actually rewritten as v.add(new Integer(1));
v.add(true);  // Fail at compilation

Yes, ok but despite appearances, this is not generic programming, this is object oriented programming.

• Because there is no equivalent to C++ templates, most high-level languages (Python, Java, etc), only one implementation of Vector is possible.
• The choice is to design an array of pointer “void *” that can point to any object.
• Either objects are strongly typed (e.g Java generics) or weakly typed (dynamic type checking is then required).

The real picture for Python, Java and most high-level languages look like the following object diagram:

In comparison, templates in C++ produce much more efficient implementations:

The example of computing the Greatest Common Divisor (GCD)

Let’s consider an example to illustrate the previous statements about the difference between GP and OOP. Consider Euclid’s algorithm that computes the greatest common divisor (GCD) of two integers.

Let’s recall its principle by manually running it to compute gcd(54,174):

 174 = 54 x 3 + 12    ->   gcd(174,54) = gcd(54,12)
  54 = 12 x 4 +  6    ->   gcd(54,12)  = gcd(12,6)
  12 =  6 x 2 +  0    ->   gcd(12,6)   = gcd(6,0) = 6

int gcd(int a, int b) {
  while(b != 0) {
    int r = a - b *(a/b);  // Compute the remainder of a divided by b
    a = b; // gcd(a,b) is equal to gcd(b,r) !
    b = r;
  }
  return a; // When b = 0, gcd(a,b) is equal to a
}

While given for integers, this algorithm can be generalized to any commutative ring like the ones of polynomials, Gaussian integers, etc.

How can we rewrite the gcd function so that Euclid’s algorithm can be applied to any type of ring.

Two solutions exist:

• The first one is based on OOP, using inheritance and polymorphism (virtual methods)
• The second is based on GP, thanks to templates.

The solution based on Object-Oriented Programming

How could we write a generic Euclid algorithm in Python or Java, based on OOP?

Step 1: defining the classes hierarchy

The main idea is to use inheritance and virtual methods.

One introduces an abstract class RingElt and we leverage runtime polymorphism using virtual methods.

Step 2: we replace int with RingElt and we introduce identity()

class RingElt {
public:
  static RingElt gcd(RingElt a, RingElt b) {
    while(b != RingElt::identity()) {
      RingElt r = a - b * (a/b);
      a = b;
      b = r;
    }
    return a; 
  }
  
  static virtual const RingElt& identity() const = 0;
  ...
};

class Integer : public RingElt {
  int i_;
  static const Integer identity_;

public:
  Integer(int i) : i_(i) {}
  static const RingElt& identity() const override { return identity_; }
  ...
};

const Integer Integer::identity_ = Integer(0);

Issues

• Primitive types (like int, etc) require to be encapsulated in a class (eg Integer instead of int) and thus an additional memory indirection.
• Method identity() cannot be static and virtual at the same time.

Virtual methods, a reminder

• Virtual methods can only be called on objects (no static)
• Virtual methods rely on a hidden attribute pointing to the virtual table.

Step 3: removing virtual static members

class RingElt {
  static RingElt gcd(RingElt a, RingElt b) {
    while(b != b.identity()) {
      RingElt r = a - b * (a/b);
      a = b;
      b = r;
    }
    return a; 
  }
  virtual const RingElt& identity() const = 0;
  ...
};
class Integer : public RingElt {
  ...
  const RingElt& identity() const override { return identity_; }
  ...
};

Issues

• The creation of local variable of type RingElt is impossible and nonsense!
• Neither are the assignment of variables of type RingElt!

Step 4: cloning objects

Assignment of the underlying concrete objects (i.e. Integer or Polynomial) can be achieved using object cloning:

static RingElt* gcd(const RingElt& ra, const RingElt& rb) {
  RingElt *a = ra.clone(), *b = rb.clone();
  while(*b != b->identity()) {
    RingElt* r = a->clone();
    *r -= *b * (*a / *b);
    a = b;
    b = r;
  }
  return a; 
}

class RingElt {
public:
  static RingElt* gcd(const RingElt&, const RingElt&);
  virtual const RingElt& identity() const = 0;
  virtual RingElt* clone() const = 0;
};

class Integer : public RingElt {
  int i_; ...
public:
  Integer(int i) : i_(i) {}
  ...
  virtual RingElt* clone() {
    return new Integer(i_);
  }
  ...
};

Issues

• Arguments are now passed by reference (i.e. by address), not by value.
• Cloning returns a pointer of a clone object dynamically allocated on the heap (new)
• Problem, it’s slow: requires dynamic allocation, virtual call, etc
• Problem, it’s dangerous: zombies, i.e. unreachable clones, induce memory leaks.

Step 5: fixing memory leaks

static RingElt* gcd(const RingElt& ra, const RingElt& rb) {
  RingElt *a = ra.clone(), *b = rb.clone();
  while(*b != b->identity()) {
    RingElt* r = a->clone();
    *r -= *b * (*a / *b);
    delete a;
    a = b;
    b = r;
  }
  delete b;
  return a; // This "a" is not released to memory!
}

int main() {
  Integer a(12), b(10);
  
  Integer* p = std::static_cast<Integer*>(RingElt::gcd(a,b));
  
  std::cout << "gcd(a,b) =" << p->i_ << std::endl;
  
  delete p; // Should not forget to desallocate result
}

Issues

• The returned pointer must be cast to concrete type (e.g. Integer*). This is inelegant and dangerous as it breaks strong typing.
• The gcd returned by the function is a clone whose deallocation from memory is delegated to the user of the library.
• The user might forget to call delete. This issue can be avoid by returning a shared pointer std::shared_ptr<RingElt>.

Step 6: using smart pointers

We delegate memory desallocation to shared pointers:

static std::shared_ptr<RingElt> gcd(const RingElt& ra, const RingElt& rb) {
  std::shared_ptr<RingElt> a = ra.clone(), b = rb.clone();
  while(*b != b->identity()) {
    std::shared_ptr<RingElt> r = a->clone();
    *r -= *b * (*a / *b);
    a = b;
    b = r;
  }
  return a; 
}

class RingElt {
public:  
  static std::shared_ptr<RingElt> gcd(const RingElt&, const RingElt&);
  virtual const RingElt& identity() const = 0;
  virtual std::shared_ptr<RingElt> clone() const = 0;
};

class Integer : public RingElt {
  int i_; ...
public:
  Integer(int i) : i_(i) {}
  ...
  virtual std::shared_ptr<RingElt> clone() const override {
    return std::make_shared<Integer>(i_);
  }
  ...
};

int main() {
  Integer a(12), b(10);
  
  std::shared_ptr<Integer> p = std::static_pointer_cast<Integer>(RingElt::gcd(a,b)); // Still a cast
  
  std::cout << "gcd(a,b) =" << p->i_ << std::endl;
  
  // No more delete here
}

Issues

• The returned pointer must still be cast to concrete type (i.e. when using std::static_pointer_cast<Integer>). This can crash at runtime (i.e. segmentation faults) if the pointer does not point to an instance of Integer.
• Operators !=,*,-,/ must be implementend in the child classes, with virtual operators.

Step 7: virtual operators

static std::shared_ptr<RingElt> gcd(const RingElt& ra, const RingElt& rb) {
  std::shared_ptr<RingElt> a = ra.clone(), b = ra.clone();
  while(*b !=(b->identity())) {
    std::shared_ptr<RingElt> r = a->clone();
    *r -= *b * (*a / *b);
    a = b;
    b = r;
  }
  return a;
} 

class RingElt {
public:
  static std::shared_ptr<RingElt> gcd(const RingElt&, const RingElt&);
  virtual const RingElt& identity() const = 0;
  virtual std::shared_ptr<RingElt> clone() const = 0;
  virtual bool operator!=(const RingElt&) const = 0;
  virtual RingElt& operator-=(const RingElt&) = 0;
  virtual RingElt& operator*(const RingElt&) const = 0;
  virtual RingElt& operator/(const RingElt&) const = 0;
};

Issues

• Resolution of virtual methods/operators can substantially slow down critical operations (e.g. sum of two integers)
• Some virtual methods/operators can introduce memory leakage:

RingElt& Integer::operator*(const RingElt& other) {
  Integer* product = new Integer(i_ * static_cast<const Integer&>(other).i_);
  return *product;
}

• The only solution is to use shared pointers std::shared_ptr but
  • the syntax becomes ugly due to dereferecing points.
  • many temporary objects are dyinamically allocated before being destroyed, introducing useless and important delays.

std::shared_ptr<RingElt> Integer::operator*(const RingElt& other) {
  return std::shared_ptr<RingElt>(new Integer(i_ * static_cast<const Integer&>(other).i_));
}

static std::shared_ptr<RingElt> gcd(const RingElt& ra, const RingElt& rb) {
  std::shared_ptr<RingElt> a = ra.clone(), b = ra.clone();
  while(*b != (b->identity())) {
    std::shared_ptr<RingElt> r = a->clone();
    *r -= *(*b  * (*(*a / *b))); // Yucky!!!
    a = b;
    b = r;
  }
  return a;
} 

Step 8: prefer assignment operators +=, -=, *=, etc

To avoid these extra memory allocations, assignement operators can be used to store results on existing objects. But then the code loses in clarity:

static std::shared_ptr<RingElt> gcd(const RingElt& ra, const RingElt& rb) {
  std::shared_ptr<RingElt> a = ra.clone(), b = ra.clone();
  while(*b != b->identity()) {
    std::shared_ptr<RingElt> r = a->clone();
    *a /= *b;
    *a *= *b;
    *r -= *a;
    a = b;
    b = r;
  }
  return a;
} 

class RingElt {
public:
  static std::shared_ptr<RingElt> gcd(const RingElt&, const RingElt&);
  virtual const RingElt& identity() const = 0;
  virtual std::shared_ptr<RingElt> clone() const = 0;
  virtual bool operator!=(const RingElt&) const = 0;
  virtual RingElt& operator-=(const RingElt&) = 0;
  virtual RingElt& operator*=(const RingElt&) = 0;
  virtual RingElt& operator/=(const RingElt&) = 0;
};

Step 9: implement classes Integer and Polynomial

class Integer : public RingElt {
  int i_; ...
public:
  ...
  bool operator!=(const RingElt& elt) const {
    const Integer& i = std::static_cast<Integer&>(elt); // Dangerous!!
    return i_ != i.i_;
  }
  
  RingElt& operator*=(const RingElt& elt) {
    const Integer& i = std::static_cast<const Integer&>(elt); // Dangerous!!
    i_ *= i.i_;
    return *this;
  }
  ...
};

Issues

• Static casts cannot be avoided.
• This introduces the risk of crash at runtime.

Preliminary conclusions :

We have shown that OOP:

• Is not robust as
  • it no longer guarantees the absence of crashes at runtime due to typing errors (static cast).
  • it can induce memory leaks that are hard to detect (if not using smart pointers).
  • delegate life management of dynamically allocated objects to the library users.
• Leads to cumbersome writing :
  • Requires the user to use inheritance
  • Impossible to use external virtual operators
  • Impossible to instantiate the algorithm on simple types (int)
  • No copy construction but cloning
  • No static
• Leads to slowdowns at runtime:
  • Resolution of virtual methods
  • Use of dynamic memory allocation (cloning)
  • Necessary encapsulation of basic types
  • Limited compiler optimization (calls to virtual functions prevent inlining)

What about Generic Programming?

The solution based on Generic Programming

Let’s see how we can do the same using templates…

Step 1: transforming the initial algorithm into a function template

template<typename Ring>
Ring gcd(Ring a, Ring b) {
  while(b != Ring()) {
    Ring r = a - b * (a/b);
    a = b;
    b = r;
  }
  return a;
}

void main(int argc, char** argv) {
  std::cout << "gcd(a,b) = " << gcd(12,10) << std::endl;  // Identical to gcd<int>(12,10)
}

Notes

• Super simple: just replace int by Ring.
• No need for identity() method: relies on the trick default numerical constructors (e.g. int()) returns 0.
• Minimalist writing: no more problems of copying objects, of overloading operator, etc.
• Type inference makes writing even lighter: user uses gcd() in main() as an ordinary function without even noticing it is a template.
• Limitation: creating objects by copy are not adapted to large types (e.g. polynomials)

Step 2: code optimization

It is not because a code runs as expected that work is over…

template<typename Ring>
Ring gcd(Ring a, Ring b) {
  Ring e{}, r; 
  Ring *pa = &a, *pb = &b, *pr = &r;
  while(*pb != e) {
    *pr = *pa - *pb * (*pa / *pb);
    Ring* old_pa = pa;
    pa = pb; // Assignment of pointers instead of objects
    pb = pr;
    pr = old_pa;
  }
  return *pa;
}

Notes

• Permutation of pointers save two object copies Ring(const Ring&).
• Advantage: more efficient for large objects, like Polynomial.
• Disadvantage: slower for primitive types directly stored in registers, like int.
• Assignment operators +=, -=, etc can be more efficient.

Step 2 bis: code optimisation from C++11

template<typename Ring>
Ring gcd(Ring a, Ring b) {
  Ring e{}, r;
  while(b != e) {
    r = a - b * (a/b); // Ring(&&) is called here
    a = std::move(b); // and here
    b = std::move(r);
  }
  return a;
}

Notes

• Move constructor Ring(&&) saves an object copy in memory
• std::move forces to call Ring(&&)
• The best of both worlds: efficient for int and for Polynomial
• However this only works if the move constructor has been implemented for Polynomial:

template<typename Scalar> class Polynomial : private std::vector<Scalar> {
public:  
  // Copy constructor
  Polynomial(const Polynomial& other):
    std::vector<Scalar>(other) {}
    
  // Move constructor
  Polynomial(Polynomial&& other) :
    std::vector<Scalar>(std::move(other)) {}
  ...
};

Or even better:

template<typename Scalar> class Polynomial : private std::vector<Scalar> {
public:

  template<typename P>
  Polynomial(P&& other) :
    std::vector<Scalar>(std::forward(other)) {}
  ...
};

Conclusions

Generic Programming conciliates:

• Performance:
  • No need for dynamic allocation of memory
  • No need of virtual methods
  • No useless memory indirection due to encapsulation of primitive types within classes
  • Uniform compiler optimization (code inlining becomes possible since there are no virtual methods)
• Robustness:
  • 100% strongly typed code (no static cast) \(\rightarrow\) strong robustness guarantees at runtime
  • No memory leaks
• Conciseness:
  • Copy by balue possible (no pointers and cloning)
  • Operators can be used (including external operators)
  • Static members possible
  • No need for inheritance

Design of a generic library based on concepts

The goal of a generic library based on templates is to be as generic as possible (i.e. usable in many contexts) without sacrificing performance. However genericity of some code has its own limits. How to specify to the user these limits, i.e. the requirements a generic algorithm or data structure expects from the types provided by the user in order to work correctly?

Let’s consider our example to determine to what extent function template gcd is generic.

Question: what are the concrete types T that can be passed to the argument Ring?

There are two distinct levels of requirements that types T must satisfy:

1. Syntactic requirements: the code has to compile

template<typename Ring>
Ring gcd(Ring a, Ring b) {
  Ring e{}, r;
  while(b != e) {
    r = a - b * (a/b);
    a = std::move(b);
    b = std::move(r);
  }
  return a;
}

Therefore, the following expressions must compile:

2. Semantic requirements: the code must correctly run and terminate.

• Euclid’s algorithm expects \((Ring,+,*)\) to be a commutative ring.
• Ring() must return the identity element of \((Ring,+)\).
• Division / verifies if \(y | x\) then, \((x / y) * y = x\).
• There exists a said Euclidean function int f(Ring&) such that for \(x \neq 0\), \(f(x) \geq 0\) and \(f(x - (x/y)*y) < f(x)\).

Definitions

• In theoretical computer science, the set of syntactic and semantic requirements define an Abstract Data Type* (or ADT), e.g. boolean, list, etc.
• In the STL language:
  • An abstract data type is called a concept.
  • A type T satisfies a concept C if all syntactic requirements of C are satisfied by T.
  • A type T models a concept C if all syntactic and semantic requirements of C are satisfied by T. In that case, T is called a model for concept C.
• Specifying the requirements of a concept is useful to describe the application scope of a generic algorithm.
• Be careful:
  • A concept is not an abstract class, there is no relation with class inheritance.
  • Verifying that a type fulfills semantic requirements, requires to derive complex proofs that go beyond abilities of automated theorem proving systems.
• C++20 has introduced a syntax to specify the syntactic requirements of concepts. This brings two improvements:
  • This materializes the syntactic constraints (principle of “docs as code”).
  • This allows the compiler to detect earlier syntactic inconsistencies between types and concepts and to produce comprehensible error messages.

Here is an example that illustrates how to use concept to specify the requirements of algorithm gcd:

// Header file containing predefined concepts
#include <concepts>

// Definition of concept Ring
template<typename T> concept Ring =
  std::default_initializable<T> &&  // Reuse here predefined elementary concepts
  std::copy_constructible<T> &&
  std::move_constructible<T> &&
  std::destructible<T> &&
  std::equality_comparable<T> &&
  requires(T a, T b) {                 // Definitions of specific constraints
    { a + b } -> std::convertible_to<T>; // Addition must be defined between two instances of T
    { a - b } -> std::convertible_to<T>; // and return a value implicitely convertible to a value of type T
    { a * b } -> std::convertible_to<T>;
    { a / b } -> std::convertible_to<T>;
  };

// Usage of concept Ring : T must satisfy constraints of concept Ring
template<Ring T>
T gcd(T a, T b) {
  T e{}, r;
  while(b != e) {
    r = a - b * (a/b);
    a = std::move(b);
    b = std::move(r);
  }
  return a;
}

Tips to design a generic library

• A generic library is all the better designed as its algorithms / data structures are based on the same limited number of concepts.
• The simpler the concepts, the more generic the library.
• Sometimes requirements of an algorithm A can include all requirements of algorithm B \(\rightarrow\) need to organize concepts in an hierarchy:
  • Concept A is a subconcept of concept B if every requirement of B is also a requirement of A.
  • Corollary: a model of A is also a model of B.
• Note: the subconcept relation is completely independent of the relation of inheritance.

Exercise

Propose a generic algorithm that computes the weighted barycenter of a set of elements. These elements will be passed to the algorithm using a range of points [begin, end[. The same for weights. One will test the algorithm using provided file test-barycenter.cpp. This programm will check the validity and the generic character of yoru algorithm on elements of type double but also on the class templates Vector and Matrix that you have developped (and that you will complete if necessary). Formalize the requirements of your algorithm by introducing a concept.