{"id":5180,"date":"2017-02-12T20:25:46","date_gmt":"2017-02-12T20:25:46","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/c-is-still-lazy\/"},"modified":"2023-06-26T12:23:18","modified_gmt":"2023-06-26T12:23:18","slug":"c-is-still-lazy","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/c-is-still-lazy\/","title":{"rendered":"C++ is Lazy: CRTP"},"content":{"rendered":"

In my previous post, Recursion, List Manipulation, and Lazy Evaluation<\/a>, 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.<\/p>\n

<\/p>\n

 <\/p>\n

CRTP<\/h2>\n

But what does CRTP mean? The acronym CRTP stands for the C++ idiom C<\/strong>uriously R<\/strong>ecurring T<\/strong>emplate P<\/strong>attern and means a technique in C++ in which a class Derived<\/span> derives from a class template Base. <\/span>The key is that Base<\/span> has Derived<\/span> as a template argument.<\/span><\/code><\/code><\/p>\n

<\/p>\n

\n
template<\/span><class<\/span> T<\/span>>\r\nclass<\/span> Base<\/span>{\r\n...\r\n};\r\n\r\nclass<\/span> Derived<\/span> : public<\/span> Base<Derived>{\r\n...\r\n};\r\n<\/pre>\n<\/div>\n
 <\/p>\n
If that is not mind-blowing and how does lazy evaluation kick in? At first lazy evaluation.<\/p>\n<\/p>\n
As lazy as possible<\/h3>\n
The key observation for understanding the CRTP idiom is that the instantiation of a method of a class template happens only when needed. Proof?<\/p>\n
 <\/p>\n
<\/p>\n
\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20<\/pre>\n<\/td>\n
\n
\/\/ lazy.cpp<\/span>\r\n\r\n#include <iostream><\/span>\r\n\r\ntemplate<\/span><class<\/span> T<\/span>> \r\nstruct<\/span> Lazy{\r\n    void<\/span> func() { std::cout << \"func\"<\/span> << std::endl;}\r\n    void<\/span> func2(); \/\/ not defined<\/span>\r\n};\r\n\r\nint<\/span> main(){\r\n  \r\n  std::cout << std::endl;\r\n    \r\n  Lazy<int<\/span>> lazy;\r\n  lazy.func();\r\n  \r\n  std::cout << std::endl;\r\n    \r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
Although the method func2<\/span> (line 8) of the class,  Lazy<\/span> is only declared but not defined; the compiler accepts the program. Because I don’t call func2,<\/span> I need no definition.<\/span><\/p>\n
\"lazy\"<\/p>\n
That is precisely the property that the CRTP uses because the definition of a method of class templates is only needed if called. The method’s declaration is sufficient for the instantiation of the base class. Therefore, you can implement static polymorphism.<\/p>\n
Static Polymorphism<\/h3>\n
Static polymorphism is quite similar to dynamic polymorphism. But contrary to dynamic polymorphism with virtual methods, the dispatch of the method calls will occur at compile time. Now, we are at the center of the CRTP idiom.<\/p>\n
<\/p>\n
\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50<\/pre>\n<\/td>\n
\n
\/\/ crtp.cpp<\/span>\r\n\r\n#include <iostream><\/span>\r\n\r\ntemplate<\/span> <typename<\/span> Derived>\r\nstruct<\/span> Base{\r\n  void<\/span> interface(){\r\n    static_cast<\/span><Derived*>(this<\/span>)->implementation();\r\n  }\r\n  void<\/span> implementation(){\r\n    std::cout << \"Implementation Base\"<\/span> << std::endl;\r\n  }\r\n};\r\n\r\nstruct<\/span> Derived1: Base<Derived1>{\r\n  void<\/span> implementation(){\r\n    std::cout << \"Implementation Derived1\"<\/span> << std::endl;\r\n  }\r\n};\r\n\r\nstruct<\/span> Derived2: Base<Derived2>{\r\n  void<\/span> implementation(){\r\n    std::cout << \"Implementation Derived2\"<\/span> << std::endl;\r\n  }\r\n};\r\n\r\nstruct<\/span> Derived3: Base<Derived3>{};\r\n\r\ntemplate<\/span> <typename<\/span> T>\r\nvoid<\/span> execute(T& base){\r\n    base.interface();\r\n}\r\n\r\n\r\nint<\/span> main(){\r\n  \r\n  std::cout << std::endl;\r\n  \r\n  Derived1 d1;\r\n  execute(d1);\r\n    \r\n  Derived2 d2;\r\n  execute(d2);\r\n  \r\n  Derived3 d3;\r\n  execute(d3);\r\n  \r\n  std::cout << std::endl;\r\n  \r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
I use static polymorphism in the function template execution (lines 29 – 32). I invoke on each argument base<\/span> the method base.interface.<\/span> The method Base::interface<\/span> in lines 7 – 9 is the critical point of the CRTP idiom. The methods dispatch to the implementation of the derived class<\/em>: static_cast<Derived*>(this)->implementation()<\/span>.  That is possible because the method will be instantiated when called. At this point in time, the derived classes Derived1,<\/span> Derived2<\/span>, a<\/span>nd Derived3<\/span> <\/span>are fully defined. Therefore, the method Base::interface<\/span> <\/span>can use the details of its derived classes. Fascinating is the method Base::implementation<\/span> (lines 10 – 12). This method plays the role of a default implementation for the static polymorphism for the class  Derived3<\/span> (line 27).<\/p>\n
Here is the output of the program.<\/p>\n
\"crtp\"<\/p>\n
 <\/p>\n
Admittedly, the only purpose of the example was to present the mechanic behind the static polymorphism. A convincing example is still missing. Here we are.<\/p>\n
Mixins with CRTP<\/h2>\n
Mixins<\/a> are a popular concept in mixing classes in new code. Therefore, it’s an often-used technique in Python to change the behavior of a class by using multiple inheritances. Contrary to C++, it is legal in Python to have more than one method definition in a class hierarchy. Python uses that method that is first in the Method Resolution Order <\/a>(MRO).<\/p>\n
You can implement mixins in C++ by using CRTP. A prominent example is the class std::enable_shared_from_this.<\/span> Using this class, you can create objects that return a  std::shared_ptr<\/span> to themselves. You have to derive your class MySharedClass<\/span> public<\/span> from std::enable_shared_from_this<\/span>. Now, your class MySharedClass<\/span> has a method shared_from_this<\/span> for creating std::shared_ptr<\/span> to its objects. You can read the details about std::enable_shared_from_this<\/span> in my post Specialities of std::shared_ptr.<\/a><\/p>\n
An additional typical use-case for mixins is a class that you want to extend with the capability that their instances support the comparison of equality and inequality.<\/p>\n
 <\/p>\n
<\/p>\n
\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50\r\n51\r\n52\r\n53\r\n54\r\n55\r\n56<\/pre>\n<\/td>\n
\n
\/\/ crtpEquality.cpp<\/span>\r\n\r\n#include <iostream><\/span>\r\n#include <string><\/span>\r\n\r\ntemplate<\/span><class<\/span> Derived<\/span>>\r\nclass<\/span> Equality<\/span>{};\r\n\r\ntemplate<\/span> <class<\/span> Derived<\/span>>\r\nbool<\/span> operator<\/span> == (Equality<Derived> const<\/span>& op1, Equality<Derived> const<\/span> & op2){\r\n  Derived const<\/span>& d1 = static_cast<\/span><Derived const<\/span>&>(op1);     \r\n  Derived const<\/span>& d2 = static_cast<\/span><Derived const<\/span>&>(op2); \r\n  return<\/span> !(d1 < d2) && !(d2 < d1);\r\n}\r\n\r\ntemplate<\/span> <class<\/span> Derived<\/span>>\r\nbool<\/span> operator<\/span> != (Equality<Derived> const<\/span>& op1, Equality<Derived> const<\/span> & op2){\r\n  Derived const<\/span>& d1 = static_cast<\/span><Derived const<\/span>&>(op1);     \r\n  Derived const<\/span>& d2 = static_cast<\/span><Derived const<\/span>&>(op2); \r\n  return<\/span> !(op1 == op2);\r\n}\r\n\r\nstruct<\/span> Apple:public<\/span> Equality<Apple>{\r\n  Apple(int<\/span> s): size{s}{};\r\n  int<\/span> size;\r\n};\r\n\r\nbool<\/span> operator<\/span> < (Apple const<\/span>& a1, Apple const<\/span>& a2){\r\n  return<\/span> a1.size < a2.size;\r\n}\r\n\r\nstruct<\/span> Man:public<\/span> Equality<Man>{\r\n  Man(std::string n): name{n}{}\r\n  std::string name;\r\n};\r\n\r\nbool<\/span> operator<\/span> < (Man const<\/span>& m1, Man const<\/span>& m2){\r\n  return<\/span> m1.name < m2.name;\r\n}\r\n\r\n\r\nint<\/span> main(){\r\n  \r\n  std::cout << std::boolalpha << std::endl;\r\n  \r\n  Apple apple1{5};\r\n  Apple apple2{10}; \r\n  std::cout << \"apple1 == apple2: \"<\/span> << (apple1 == apple2) << std::endl;\r\n    \r\n  Man man1{\"grimm\"<\/span>};\r\n  Man man2{\"jaud\"<\/span>};\r\n  std::cout << \"man1 != man2: \"<\/span> << (man1 != man2) << std::endl;\r\n  \r\n  std::cout << std::endl;\r\n    \r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
I have implemented for the classes Apple<\/span> and Man<\/span> the smaller operator (lines 28 and 37). For further reasoning, I will only use the class Man<\/span> for simplicity.  The class Man<\/span> is publicly derived (lines 32 – 35) from Equality<Man><\/span>. I have implemented for classes of the kind Equality<Derived><\/span> the equality (lines 9 – 14) and the inequality operator (lines 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<\/span> (line 13). The equality operator and inequality operator convert its operands: Derived const&: Derived const& d1 = static_cast<Derived const&>(op1).<\/span><\/p>\n
Now, I can compare Apple<\/span> and Man<\/span> for equality and inequality.<\/p>\n
 <\/p>\n
 \"crtpEquality\"<\/p>\n
 What’s next?<\/h2>\n
 <\/p>\n
In addition to CRTP, expression templates are also based on lazy evaluation. Expression templates are “structures representing a computation at compile time, which are evaluated only as needed<\/strong> to produce efficient code for the entire computation” (https:\/\/en.wikipedia.org\/wiki\/Expression_templates<\/a>). As needed, that is the point of lazy evaluation; therefore, expression templates are the topic of my next post<\/a>.<\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p><\/p>\n","protected":false},"excerpt":{"rendered":"
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.<\/p>\n","protected":false},"author":21,"featured_media":5164,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[365],"tags":[426,412],"class_list":["post-5180","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-functional","tag-crtp","tag-python"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5180","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5180"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5180\/revisions"}],"predecessor-version":[{"id":6888,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5180\/revisions\/6888"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5164"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5180"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5180"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}