Regular types in C++

50 %
50 %
Information about Regular types in C++

Published on January 30, 2016

Author: ilio-catallo

Source: slideshare.net

1. Regular types Ilio Catallo - Politecnico di Milano ilio.catallo@polimi.it

2. Outline • Fundamental opera/ons • Regular types • Semi-regular & totally ordered types • Making vector_int regular • Bibliography

3. Fundamental opera.ons

4. Commonali(es among types What is in common between chars and doubles1 ? char c1 = 'a', c2 = 'b'; double d1 = 1.3, d2 = 2.7; 1 For the remainder of this presenta1on, we will limit ourselves to non-singular double values, i.e., we will exclude NaN from the set of possible values

5. Commonali(es among types For a start, both chars and doubles and can be swapped std::swap(c1, c2); std::swap(d1, d2);

6. Why is that so?

7. swap implementa*on for doubles Let us look at the implementa0on of swap as if it was wri4en just for doubles void swap(double& x, double& y) { double tmp = x; x = y; y = tmp; }

8. Requirements on doubles Which requirements on doubles are needed for swap to work? void swap(double& x, double& y) { double tmp = x; x = y; y = tmp; }

9. Requirements on doubles First, it should be possible to copy construct a double void swap(double& x, double& y) { double tmp = x; // tmp is copy constructed from x x = y; y = tmp; }

10. Requirements on doubles Second, it should be possible to assign a double void swap(double& x, double& y) { double tmp = x; x = y; // x is assigned y y = tmp; // y is assigned tmp }

11. Requirements on doubles Given that double values are in fact both assignable and copy construc1ble, we can run swap on them std::swap(d1, d2);

12. swap implementa*on for chars Let us now turn our a,en-on to a version of swap tailored for chars void swap(char& x, char& y) { char tmp = x; x = y; y = tmp; }

13. Requirements on chars As before, we no,ce that char values need to be assignable and copy construc1ble void swap(char& x, char& y) { char tmp = x; x = y; y = tmp; }

14. Requirements on chars As before, since char values are in fact assignable and copy construc1ble, it is possible to swap them std::swap(c1, c2);

15. Swapping built-in types It is immediate to see that our finding generalizes to all built-in types std::swap(b1, b2); // b1 and b2 are bools std::swap(f1, f2); // f1 and f2 are floats std::swap(i1, i2); // i1 and i2 are ints

16. Common opera*ons We conclude that assignment and copy construc0on are opera/ons common to all built-in types

17. Common opera*ons That is, for any built-in type T the following is always possible: T a; a = b; // assignment T c = d; // copy construction

18. Common opera*ons In light of this, we can write a uniform implementa.on of swap for all built-in types void swap(T& x, T& y) { // T is a built-in type T tmp = x; x = y; y = tmp; }

19. Do built-in types share any addi3onal opera3ons?

20. Fundamental opera.ons As a ma&er of fact, we observe that there is a core set of opera4ons which are defined for all built-in types

21. Fundamental opera.ons We call such opera-ons the fundamental opera.ons ┌────────────────────────┬──────────┐ │ Default construction │ T a; │ ├────────────────────────┼──────────┤ │ Copy construction │ T a = b; │ ├────────────────────────┼──────────┤ │ Destruction │ ~T(a); │ ├────────────────────────┼──────────┤ │ Assignment │ a = b; │ ├────────────────────────┼──────────┤ │ Equality │ a == b; │ ├────────────────────────┼──────────┤ │ Inequality │ a != b; │ ├────────────────────────┼──────────┤ │ Ordering │ a < b; │ └────────────────────────┴──────────┘

22. Regular types

23. Operators for UDTs The C++ programming language allows the use of built-in type operator syntax for user-defined types (UDTs)

24. Example: the point2 UDT struct point { point(double x, double y): x(x), y(y) {} double x; double y; }; 2 Remember that there is no difference between a struct and a class, up to default members' visibility. Conven=onally, we use structs when our UDTs do not need a private sec=on

25. Example: the point UDT Intui&vely, it makes sense to define operator == as equality: bool operator==(point const& p1, point const& p2) { return p1.x == p2.x && p1.y == p2.y; }

26. Overload seman-cs However, C++ does not dictate any seman&c rules on operator overloading

27. Overload seman-cs That is, developers are free to define == as: bool operator==(point const& p1, point const& p2) { return p1.x * p2.x > p1.y * p2.y; }

28. Seman&cs mismatch This could lead to a mismatch between the expected and the actual seman4cs of an operator

29. Seman&cs mismatch This could lead to a mismatch between the expected and the actual seman4cs of an operator ( °□°

30. Seman&cs mismatch "I admire the commi.ee dedica/on to programming freedom, but I claim that such freedom is an illusion. Finding the laws that govern so=ware components gives us freedom to write complex programs the same way that finding the laws of physics allows us to construct complex mechanical and electrical systems." (A. Stepanov)

31. Built-in types as a theore1cal founda1on The opera)ons common to all built-in types are among the most well-understood and pervasively used

32. Built-in types as a theore1cal founda1on This is because, over the years, the development of built-in types has led to consistent defini9ons that match • the programmer intui-on, and • the underlying mathema-cal understanding

33. Idea: deriving the seman.cs of user-defined types from that of built-in types

34. Preserving opera-on seman-cs The idea is that when a code fragment has a certain meaning for built-in types, it should preserve the same meaning for UDTs

35. Regular types To this end, we introduce the concept of a regular type as a type behaving like the built-in types

36. Regular types We call such types regular, since their use guarantees regularity of behavior and – therefore – interoperability

37. std::vector is regular For instance, std::vector<T> is regular whenever T is regular

38. std::vector is regular As with built-in types, std::vector<T> is thus copy construc+ble and assignable for each regular type T std::vector<int> w = v; // copy construction std::vector<int> u; u = w; // assignment

39. std::vector is swappable Hence, we can swap3 two vectors of any regular type T: std::vector<int> v = {7, 3, 5}; std::vector<int> w = {10, 11, 4}; std::swap(v, w); 3 In reality, for the sake of performance, the Standard Library provides a specialized version std::swap for the specific case of std::vector. Although less performing, the general purpose version would however equally work

40. How can we assure our UDTs to be regular?

41. What does it mean to be regular? Ul#mately, we need to inves#gate how several of the built-in operators should behave when applied to user-defined types

42. What does it mean to be regular? This amounts to understanding how to apply the fundamental opera5ons to UDTs ┌────────────────────────┬──────────┐ │ Default construction │ T a; │ ├────────────────────────┼──────────┤ │ Copy construction │ T a = b; │ ├────────────────────────┼──────────┤ │ Destruction │ ~T(a); │ ├────────────────────────┼──────────┤ │ Assignment │ a = b; │ ├────────────────────────┼──────────┤ │ Equality │ a == b; │ ├────────────────────────┼──────────┤ │ Inequality │ a != b; │ ├────────────────────────┼──────────┤ │ Ordering │ a < b; │ └────────────────────────┴──────────┘

43. What does it mean to be regular? First, we no,ce that the fundamental opera,ons can be divided into three groups ┌────────────────────────┬──────────┐ │ │ T a; │ │ ├──────────┤ │ │ T a = b; │ │ Copying and assignment ├──────────┤ │ │ ~T(a); │ │ ├──────────┤ │ │ a = b; │ ├────────────────────────┼──────────┤ │ │ a == b; │ │ Equality ├──────────┤ │ │ a != b; │ ├────────────────────────┼──────────┤ │ Ordering │ a < b; │ └────────────────────────┴──────────┘

44. What does it mean to be regular? Let us now inves,gate in greater detail the proper%es of each such group ┌────────────────────────┬──────────┐ │ │ T a; │ │ ├──────────┤ │ │ T a = b; │ │ Copying and assignment ├──────────┤ │ │ ~T(a); │ │ ├──────────┤ │ │ a = b; │ ├────────────────────────┼──────────┤ │ │ a == b; │ │ Equality ├──────────┤ │ │ a != b; │ ├────────────────────────┼──────────┤ │ Ordering │ a < b; │ └────────────────────────┴──────────┘

45. Copying and assignment

46. Copy and assignment are interchangeable We know that built-in types allow wri4ng interchangeably: T a; a = b; // assignment T a = b; // copy construction

47. Copy and assignment are interchangeable The ra'onale behind this is that it allows natural code such as: T a; if (something) a = b; else a = c;

48. Default construc.on Observe that we need default construc.on to make assignment and copy construc7on interchangeable T a = b; T a; a = b; T a;

49. Default construc.on Note that we require a default constructed regular type to be assignable and destruc.ble

50. Par$al construc$on That is, we require default ini2aliza2on only to par$ally form an object

51. Preserving equality The next step is to note that for all built-in types copy construc5on and assignment are equality-preserving opera5ons T a = b; // copy construction a == b; // true!

52. Preserving equality The next step is to note that for all built-in types copy construc5on and assignment are equality-preserving opera5ons T a; a = b; // assignment a == b; // true!

53. Preserving equality • Copy construc-ng means to make a copy that is equal to the original • Assignment copies the right-hand side object to the le;-hand side object, leaving their values equal

54. Dependency on equality Since we need the ability to test for equality, we have that copy construc7on and assignment depend on equality

55. A refined defini)on of regularity In other words, regular types possess the equality operator and equality-preserving copy construc4on and assignment

56. Defining equality Although equality is conceptually central, we do not yet have a sa.sfactory defini.on of equality of two objects of a regular type

57. Equality

58. Equality for built-in types On built-in types, the equality rela3on is normally defined as bitwise equality

59. Equality for UDTs Star%ng from this, we can devise a natural defini,on of equality for user-defined types

60. Equality for UDTs Namely, we can define equality of user-defined types from the equality of its parts

61. Equality for UDTs However, in order to build the equality operator from the equality operator of its parts, we must iden%fy its parts

62. Example: the point type struct point { point(double x, double y): x(x), y(y) {} double x; double y; };

63. Example: operator== for points bool operator==(point const& p1, point const& p2) { return p1.x == p2.x && p1.y == p2.y; }

64. Remote parts Complex objects are o&en constructed out of mul0ple simpler objects, connected by pointers

65. Remote parts In such cases, we say that the given complex object has remote parts

66. Example: the person type struct mail_address {...}; class person { public: person(...) {...} private: std::string name; std::string surname; mail_address* address; };

67. 1st a&empt: operator== for persons friend bool operator==(person const& p1, person const& p2) { return p1.name == p2.name && p1.surname == p2.surname; }

68. 2nd a&empt: operator== for persons friend bool operator==(person const& p1, person const& p2) { return p1.name == p2.name && p1.surname == p2.surname && p1.address == p2.address; }

69. 3rd a&empt: operator== for persons friend bool operator==(person const& p1, person const& p2) { return p1.name == p2.name && p1.surname == p2.surname && *p1.address == *p2.address; }

70. Comparing remote parts For objects with remote parts, the equality operator must compare the corresponding remote parts, rather than the pointers to them

71. Comparing remote parts We do not want objects with equal remote parts to compare unequal just because the remote parts were in different memory loca3ons

72. Defini&on of equality We can therefore devise the following defini4on of equality: Two objects are equal if their corresponding parts are equal (applied recursively), including remote parts (but not comparing their addresses), excluding inessen>al components, and excluding components which iden>fy related objects

73. Equality comes with inequality It is not enough to define equality, we also need to define inequality to match it

74. Unequal vs. not equal We need to do so in order to preserve the ability to write interchangeably: a != b; // unequal !(a == b); // not equal

75. Unequal vs. not equal That is, the statements "two things are unequal to each other" and "two 6ngs are not equal to each other" should be equivalent a != b; // unequal !(a == b); // not equal

76. Inequality operator Fortunately, this is very simple: // T is some user-defined type bool operator!=(T const& x, T const& y) { return !(x == y); }

77. Equality and inequality C++ does not enforce that equality and inequality should be defined together, so remember to define inequality every 7me equality is defined

78. Ordering

79. The importance of ordering We need to have ordering if we want to find things quickly, as ordering enables sor$ng, and therefore binary search

80. Ordering For defining ordering on a user-defined type we need to set in place the four rela%onal operators <, >, <=, >=

81. Rela%onal operators However, we need to implement only one rela(onal operator, which can then be used to derive the defini8on on the remaining three

82. Less-than operator We choose < as the primary operator, since when we refer to ordering we usually mean ascending ordering

83. Less-than operator seman.cs Intui&vely, since we are overloading the less-than operator <, the ordering criterion we implement must behave like <

84. How to make our overload behave the way that < behaves?

85. Strictness First, let us no-ce this natural property of < when used as an arithme-c operator: 5 ≮ 5 12 ≮ 12 etc.

86. Strictness Hence, also our ordering rela0on of choice must be strict, that is: a ≮ a for all a in T

87. Is this defini+on strict? // T is some user-defined type bool operator<(T const& x, T const& y) { return true; }

88. Is this defini+on strict? // T is some user-defined type bool operator<(T const& x, T const& y) { return true; // according to this 5 < 5, // which violates strictness }

89. Transi'vity Second, it is immediate to see that the less-than operator is transi've: 4 < 7 and 7 < 12 implies 4 < 12

90. Transi'vity Hence, also our ordering rela0on of choice must be transi've // T is some user-defined type bool operator<(T const& x, T const& y) { // maintain transitivity }

91. Trichotomy law Finally, the less-than operator < obeys the trichotomy law: For every pair of elements, exactly one of the following holds: a < b, b < a or a == b

92. Trichotomy law Note that the trichotomy law requires the defini5on of < to be consistent with the defini5on of == so that: !(a < b) && !(b < a) is equivalent to a == b

93. Equality is central Hence, as with assignment and copy, also ordering depends on equality !(a < b) && !(b < a) is equivalent to a == b

94. Is this a well-formed overload? bool operator<(point const& p1, point const& p2) { return p1.x < p2.x; }

95. Is this a well-formed overload? It respects strictness bool operator<(point const& p1, point const& p2) { return p1.x < p2.x; // (5, 2) ≮ (5, 2) }

96. Is this a well-formed overload? It respects transi,vity bool operator<(point const& p1, point const& p2) { return p1.x < p2.x; // (5,2) < (6, 3) < (10, 5) }

97. Is this a well-formed overload? But it does not obey to the trichotomy law bool operator<(point const& p1, point const& p2) { return p1.x < p2.x; // (5, 3) ≮ (5, 8) and // (5, 8) ≮ (5, 3) but... // (5, 8) ≠ (5, 3) }

98. Is this a well-formed overload? bool operator<(point const& p1, point const& p2) { if (p1.x < p2.x) return true; if (p1.x > p2.x) return false; return p1.y < p2.y; }

99. Is this a well-formed overload? We are imposing a lexicographic ordering over points bool operator<(point const& p1, point const& p2) { if (p1.x < p2.x) return true; if (p1.x > p2.x) return false; return p1.y < p2.y; }

100. Is this a well-formed overload? Lexicographic ordering respects strictness, transi2vity and the trichotomy law bool operator<(point const& p1, point const& p2) { if (p1.x < p2.x) return true; if (p1.x > p2.x) return false; return p1.y < p2.y; }

101. Strict total ordering We refer to an ordering rela.on that is strict, transi.ve and that obeys the trichotomy law as a strict total ordering

102. Remaining operators As with equality, we must define manually the remaining rela5onal operators >, >=, <=

103. Greater-than operators // T is some user-defined type bool operator>(T const& x, T const& y) { return y < x; }

104. Greater-or-equal-than operator // T is some user-defined type bool operator>=(T const& x, T const& y) { return !(x < y); }

105. Less-or-equal-than operator // T is some user-defined type bool operator<=(T const& x, T const& y) { return !(y < x); }

106. Semi-regular & totally ordered types

107. Regularity Some%mes, although a type looks like a regular type, we cannot formally guarantee its regularity

108. complex seems regular For instance, the complex type we previously wrote feels like a regular type complex a; // default construction complex b = a; // copy construction complex c; c = b; // assignment a == b; // equality a != c; // inequality

109. complex numbers cannot be ordered However, we cannot impose a natural order on complex numbers4 complex a(5, 2); complex b(8, 0); a < b; // not defined 4 See, e.g., h)p://math.stackexchange.com/a/488015/79684

110. complex is non-regular As such, complex is formally a non-regular type complex a(5, 2); complex b(8, 0); a < b; // not defined

111. complex is non-regular However, this might be too restric1ve. For this reason, we opt for a more fine-grained classifica.on

112. A relaxed no+on of regularity We relax our defini.on of regular types and consider regular also types for which it is not possible to devise a natural order complex a(5, 2); complex b(8, 0); a < b; // not defined

113. Totally ordered types We instead refer to regular types for which a natural order is possible as totally ordered types

114. Semi-regular types Similarly, we refer to type that supports equality-preserving copy and assignment without being equality comparable as semi-regular

115. Semi-regular types Intui&vely, this means that a semi-regular type is copyable

116. Type classifica,on ┌────────────────────────┬──────────┐ │ │ T a; │ │ ├──────────┤ │ │ T a = b; │ │ Semi-regular ├──────────┤ │ │ ~T(a); │ │ ├──────────┤ │ │ a = b; │ ├────────────────────────┼──────────┤ │ │ a == b; │ │ Regular ├──────────┤ │ │ a != b; │ ├────────────────────────┼──────────┤ │ Totally ordered │ a < b; │ └────────────────────────┴──────────┘

117. Making vector_int regular

118. vector_int class vector_int { public: vector_int(): sz(0), elem(nullptr) {} vector_int(std::size_t sz): sz(sz), elem(new int[sz]) {...} vector_int(vector_int const& v): sz(v.sz), elem(new int[v.sz]) {...} ~vector_int() {...} std::size_t size() const {...} int operator[](std::size_t i) const {...} int& operator[](std::size_t i) {...} vector_int& operator=(vector_int const& v) {...} private: std::size_t sz; int* elem; };

119. Making vector_int regular In order to make vector_int regular we need to define (in)equality and the four rela-on operators

120. Equality class vector_int { public: ... bool operator==(vector_int const& v) const { if (sz != v.sz) return false; for (std::size_t i = 0; i < sz; ++i) if (elem[i] != v.elem[i]) return false; return true; } };

121. Less-than operator class vector_int { public: ... bool operator<(vector_int const& v) const { std::size_t min_size = std::min(sz, v.sz); std::size_t i = 0; while (i < min_size && elem[i] == v.elem[i]) ++i; if (i < min_size) return elem[i] < v.elem[i]; else return sz < v.sz; } };

122. Bibliography

123. Bibliography • J.C. Dehnert, A. Stepanov, Fundamentals of generic programming • A. Stepanov, Notes on programming • A. Stepanov, P. McJones, Elements of programming

124. Bibliography • A. Stepanov, D. Rose, From Mathema6cs to Generic Programming • A. Stepanov, Efficient Programming with Components (Lecture 1 and Lecture 2)

Add a comment

Related pages

c++ - What is a "Regular Type" in the context of move ...

Alex Stepanov defined Regular Types as types satisfying certain properties ... What is a “Regular Type” in the context of ... T b = a; T c = std::move ...
Read more

Regular language - Wikipedia, the free encyclopedia

To locate the regular languages in the Chomsky hierarchy, one notices that every regular language is context-free. The converse is not true: for example ...
Read more

Using Regular Expressions in C# .NET - CodeProject

Objective-C and Swift; Database; Hardware & Devices > ... Using Regular Expressions in C# .NET. Anupam Banerji, 16 Jul 2010 CPOL 3.40 (17 votes ...
Read more

Regular Expressions Usage in C# - C# Corner - Developers ...

The source code shows how to use Regular Expressions in C#. ... C, C++, MFC HoloLens ... Filter An Array of Different Data Types by Array Filter Method.
Read more

Regular Expressions (RegEx) - Wiki Home

The use of Regular Expressions to search and manipulate ... (C) The type returned ... The method tries to match the regular expression in C with the ...
Read more

regex - Regular Expression to match C data type - Stack ...

I have strings like int int[] char[] int[][] char** int* etc I want a regular expression to match this. The best I have been able to come up with is [a ...
Read more

Regular Expression Short-Answer question type - MoodleDocs

Regular Expression Short-Answer question type; ... will not be interpreted as a regular expression but "as is" and c) has a Grade value of 100%.
Read more

- C++ Reference - cplusplus.com - The C++ ...

This must be an object of a basic_regex type ... Basic types: basic_regex Regular expression ... C library: (assert.h)
Read more

File types In Linux/Unix explained in detail. - The Linux ...

File types In Linux/Unix explained in detail. ... (c) Named pipe file or ... Regular file type Explained in Linux.
Read more