<\/p>\n
We all know that C++ templates can receive types as “parameters”. In the same spirit we could can “return values”s, so that we can form a function. The basic paradigm is the following:<\/p>\n
template<class T>\r\nstruct Computed {\r\n using type = T;\r\n}<\/pre>\nIn this way we constructed a type level function named Computed<\/code>, with one parameter\u00a0 and result the parameter itself. We use the function as Computed<float>::type<\/code>, the result being float<\/code>\u00a0itself.<\/p>\n<\/p>\n
Why an extra struct<\/code>wrapper instead of directly defining the “function”? That’s because partialization on using<\/code>\u00a0is not allowed. Such codes are invalid:<\/p>\ntemplate <class T>\r\nusing computed<T> = T;\r\n\r\ntemplate<>\r\nusing computed<int> = double;<\/pre>\n\nAs of why this isn’t supported by C++, I’m not sure.<\/div>\n<\/div>\nPartialization<\/h4>\n\nWhat is partialization? You can take it as “pattern matching” in Haskell.<\/div>\n<\/div>\ntemplate<class T>\r\nstruct Computed {\r\n using type = T;\r\n}\r\n\r\ntemplate<>\r\nstruct Computed<int> {\r\n using type = double;\r\n}<\/pre>\n\nThus, Computed<bool>::type<\/code> would become bool<\/code>, while Computed<int>::type<\/code> would (specially) be double<\/code>. Certainly, there are a set of rules for the matching process. E.g. the most “specific” case gets matched first. This is somewhat from Haskell, where the first-defined case comes first. The equivalent code in Haskell is:<\/div>\n<\/div>\ndata Type = Bool | Double | Int\r\n\r\ncomputed :: Type -> Type\r\ncomputed Int = Double\r\ncomputed t = t<\/pre>\n\nWith this correspondence in mind, if you are familiar with the implementation of Peano numbers in Haskell, then you are ready to do it in C++. If you aren’t, don’t worry. We are going to explore the Peano numbers next.<\/div>\n<\/div>\nPeano numbers<\/h3>\n\nWhat are the Peano numbers? They are natural numbers defined with “induction”. More precisely, it would be a system of axioms that behaves like the “natural” numbers in naive intuition, a.k.a. a possible axiomatization of the natural numbers. There are only two symbols in this system, a Zero<\/code> for 0<\/code>, and a Succ<\/code> for the successive. Thus 1<\/code> would be Succ<Zero><\/code>, 2<\/code> would be Succ<Succ<Zero>><\/code>, and so on. This is but the heuristic demonstration of “induction”.<\/div>\nWe can represent the two symbols in C++ as follows:<\/div>\n<\/div>\nstruct Peano {};\r\nstruct Zero: Peano {};\r\ntemplate<class T>\r\nstruct Succ: Peano {};<\/pre>\n\nThen what is “addition”? Starting from an example. We are need to define a template (type level function) with two parameters:<\/div>\n<\/div>\ntemplate<class T1, class T2>\r\nstruct Add {\r\n using type = ???;\r\n}<\/pre>\n\nsatisfying the laws in intuition, such as 2+1=3<\/code>, or Add<Succ<Succ<Zero>>, Succ<Zero>>::type = Succ<Succ<Succ<Zero>>><\/code>. Certainly the latter expression is not valid C++, since there is no equality operator for types. Instead, we should use the std::is_same<T1, T2><\/code> function, which is predefined in <type_traits><\/code>. Or you can implement it yourself, again using partialization. This is a possible implementation:<\/div>\n<\/div>\ntemplate<class T, class U>\r\nstruct is_same {\r\n static constexpr bool value = false;\r\n};\r\n \r\ntemplate<class T>\r\nstruct is_same<T, T> {\r\n static constexpr bool value = true;\r\n};<\/pre>\n\nThen how do we actually implement the addition? We can certainly implement a partialization for each specific case. An example is:<\/div>\n<\/div>\ntemplate<>\r\nstruct Add<Succ<Succ<Zero>>, Succ<Zero>> {\r\n using type = Succ<Succ<Succ<Zero>>>;\r\n}<\/pre>\n\nSuch exhaustion could actually work, since most C++ compilers only allow a finite level of nested templates (255 for clang by default). But such a “solution” is too silly to accept. Indeed, addition can be covered with only 2 rules: 0 + b = b, (Succ a) + b = Succ (a + b)<\/code>. In C++ they are:<\/div>\n<\/div>\ntemplate<class T1, class T2>\r\nstruct Add;\r\n\r\ntemplate<class T>\r\nstruct Add<Zero, T> {\r\n using type = T;\r\n};\r\n\r\ntemplate<class T1, class T2>\r\nstruct Add<Succ<T1>, T2> {\r\n using type = Succ<typename Add<T1, T2>::type>\r\n};<\/pre>\n\nNotice that typename<\/code> — the compiler doesn’t know whether the ::type<\/code> is a member type or a member variable, so we need this keyword as a hint.<\/div>\nHereby we’ve finished the definition of addition. We can do some test to verify if std::is_same<Add<Succ<Succ<Zero>>, Succ<Zero>>::type, Succ<Succ<Succ<Zero>>>>::value == true<\/code> or so. Such nesting of Succ<\/code> is somewhat hard to read, so you can simply write a template to generate Peano types from integers:<\/div>\n<\/div>\ntemplate<int v>\r\nstruct peano {\r\n using type = Succ<typename peano<v - 1>::type>;\r\n};\r\n\r\ntemplate<>\r\nstruct peano<0> {\r\n using type = Zero;\r\n};<\/pre>\nThen you can simplify it to Add<peano<2>::type, peano<1>::type>::type<\/code> and peano<3>::type<\/code>. The other opeartions like subtraction, multiplication and division can be similarly implemented, which are left as exercises.<\/p>\nExercises:<\/h3>\n\nFinish the exercises for arithmetic, comparison and parity at Peano numbers | Codewars<\/a>\u00a0 and pass the tests.<\/div>\n<\/div>\nAfterwords<\/h3>\n
We can further “prove” the assertions in our intuition, such addition is commutative, multiplication is distributive over addition, and so on. We may talk about this later.<\/p>\n
<\/div>\n<\/p>","protected":false},"excerpt":{"rendered":"
Fundamentals Function on Types We all know that C++ templates can receive types as “parameters”. In the same spirit we could can “return values”s, so that we can form a function. The basic paradigm is the following: template<class T> struct Computed { using type = T; } In this way we constructed a type level … Continue reading “Implement Compile Time Peano Numbers – A Primer in C++ Template Metaprogramming”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":370,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16],"tags":[26,28,27,29],"_links":{"self":[{"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/posts\/362"}],"collection":[{"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/comments?post=362"}],"version-history":[{"count":8,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/posts\/362\/revisions"}],"predecessor-version":[{"id":426,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/posts\/362\/revisions\/426"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/media\/370"}],"wp:attachment":[{"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/media?parent=362"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/categories?post=362"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/colliot.org\/en\/wp-json\/wp\/v2\/tags?post=362"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}