C++ is Lazy: CRTP

Contents[Show]

In my previous post Recursion, List Manipulation and Lazy Evaluation I wrote about the characteristics of functional programming:  The story about lazy evaluation in C++ is short. Sorry to say but I have forgotten templates. The two advanced techniques CRTP and expression templates are based on lazy evaluation.

 

CRTP

But what does CRTP mean? The acronym CRTP stands for the C++ idiom Curiously Recurring Template Pattern and means a technique in C++ in which a class Derived derives from a class template Base. The key is that Base has Derived as template argument.

template<class T>
class Base{
...
};

class Derived : public Base<Derived>{
...
};

 

If that is not mind blowing and how does lazy evaluation kicks in? At first to lazy evaluation.

As lazy as possible

The key observation for the understanding for the CRTP idiom is that the instantiation of a method of a class template happens only when needed. Proof?

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// lazy.cpp

#include <iostream>

template<class T> 
struct Lazy{
    void func() { std::cout << "func" << std::endl;}
    void func2(); // not defined
};

int main(){
  
  std::cout << std::endl;
    
  Lazy<int> lazy;
  lazy.func();
  
  std::cout << std::endl;
    
}

 

Although the method func2 (line 8) of the class,  Lazy is only declared but not defined, the compiler accepts the program. Because I don't call func2, I need no definition.

lazy

That is exactly the property that the CRTP uses because the definition of a method of class templates is only needed if called. The declaration of the method is totally sufficient for the instantiation of the base class. Therefore, you can implement static polymorphism.

Static Polymorphism

Static polymorphism is quite similar to dynamic polymorphism. But in contrary to dynamic polymorphism with virtual methods, the dispatch of the method calls will take place a compile time. Now, we are at the center of the CRTP idiom.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// crtp.cpp

#include <iostream>

template <typename Derived>
struct Base{
  void interface(){
    static_cast<Derived*>(this)->implementation();
  }
  void implementation(){
    std::cout << "Implementation Base" << std::endl;
  }
};

struct Derived1: Base<Derived1>{
  void implementation(){
    std::cout << "Implementation Derived1" << std::endl;
  }
};

struct Derived2: Base<Derived2>{
  void implementation(){
    std::cout << "Implementation Derived2" << std::endl;
  }
};

struct Derived3: Base<Derived3>{};

template <typename T>
void execute(T& base){
    base.interface();
}


int main(){
  
  std::cout << std::endl;
  
  Derived1 d1;
  execute(d1);
    
  Derived2 d2;
  execute(d2);
  
  Derived3 d3;
  execute(d3);
  
  std::cout << std::endl;
  
}

 

I use in the function template execute (line 29 - 32) static polymorphism. I invoke on each argument base the method base.interface. The method Base::interface in line 7 - 9 is the key point of the CRTP idiom. The methods dispatches to the implementation of the derived class: static_cast<Derived*>(this)->implementation().  That is possible because the method will be instantiated when called. At this point in time the derived classes Derived1, Derived2 and Derived3 are fully defined. Therefore, the method Base::interface can use the details of its derived classes. Especially interesting is the method Base::implementation (line 10 - 12). This method plays the role of a default implementation for the static polymorphism for the class  Derived3 (line 27).

Here is the output of the program.

crtp

 

Admittedly, the only purpose of the example was it to present you the mechanic behind the static polymorphism. A convincing example is still missing. Here we are.

Mixins with CRTP

Mixins are a popular concept in the design of classes to mix in new code. Therefore, it's a often used technique in Python to change the behaviour of a class by using multiple inheritances. In contrary to C++ it is legal in Python to have more than one definition of a method in a class hierarchy. Python uses simply that method that is first in the Method Resolution Order (MRO).

You can implement mixins in C++ by using CRTP. A prominent example is the class std::enable_shared_from_this. By using this class you can create objects that return a  std::shared_ptr to themselves. You have to derive your class MySharedClass public from std::enable_shared_from_this. Now, your class MySharedClass has a method shared_from_this for creating std::shared_ptr to its objects. You can read the details about std::enable_shared_from_this in my post Specialities of std::shared_ptr.

An additional typical use-case for mixins is a class that you want to extend with the capability that their instances support the comparison for equality and inequality.

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// crtpEquality.cpp

#include <iostream>
#include <string>

template<class Derived>
class Equality{};

template <class Derived>
bool operator == (Equality<Derived> const& op1, Equality<Derived> const & op2){
  Derived const& d1 = static_cast<Derived const&>(op1);     
  Derived const& d2 = static_cast<Derived const&>(op2); 
  return !(d1 < d2) && !(d2 < d1);
}

template <class Derived>
bool operator != (Equality<Derived> const& op1, Equality<Derived> const & op2){
  Derived const& d1 = static_cast<Derived const&>(op1);     
  Derived const& d2 = static_cast<Derived const&>(op2); 
  return !(op1 == op2);
}

struct Apple:public Equality<Apple>{
  Apple(int s): size{s}{};
  int size;
};

bool operator < (Apple const& a1, Apple const& a2){
  return a1.size < a2.size;
}

struct Man:public Equality<Man>{
  Man(std::string n): name{n}{}
  std::string name;
};

bool operator < (Man const& m1, Man const& m2){
  return m1.name < m2.name;
}


int main(){
  
  std::cout << std::boolalpha << std::endl;
  
  Apple apple1{5};
  Apple apple2{10}; 
  std::cout << "apple1 == apple2: " << (apple1 == apple2) << std::endl;
    
  Man man1{"grimm"};
  Man man2{"jaud"};
  std::cout << "man1 != man2: " << (man1 != man2) << std::endl;
  
  std::cout << std::endl;
    
}

 

I have implemented for the classes Apple and Man the smaller operator (line 28 and 37). For my further reasoning, I will only use the class Man for simplicity reasons.  The class Man is public derived (line 32 - 35) from the class Equality<Man>. I have implemented for classes of the kind Equality<Derived> the equality (line 9 - 14) and the inequality operator (line 16 - 21). The inequality operator uses the equality operator (line 20). The equality operator uses the fact that the smaller operator is implemented for Derived (line 13). The equality operator and inequality operator convert its operands: Derived const&: Derived const& d1 = static_cast<Derived const&>(op1).

Now, I can compare Apple and Man for equality and inequality.

 

 crtpEquality

 What's next?

 

In addition to CRTP, expression templates are also based on the idea of lazy evaluation. Expression templates are "structures representing a computation at compile time, which structures are evaluated only as needed to produce efficient code for the entire computation" (https://en.wikipedia.org/wiki/Expression_templates). As needed, that is the point of lazy evaluation and therefore expression templates are the topic of my next post.

 

 

 

 

 

 

 

 

 

 

 

title page smalltitle page small Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Get your e-book. Support my blog.

 

Tags: templates

Comments   

0 #1 Lonna 2017-03-29 02:14
I like the helpful information you provide in your articles.
I will bookmark your blog and check again here frequently.
I am quite sure I will learn a lot of new stuff right here!
Good luck for the next!
Quote
0 #2 Kassie 2017-04-10 04:24
This post is invaluable. When can I find out more?
Quote

Add comment


My Newest E-Book

Latest comments

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 557

All 255862

Currently are 245 guests and no members online