1 | ## Types for 0 and 1 literals ## |
---|
2 | The literals `0` and `1` are treated specially by Cforall, due to their |
---|
3 | potential uses in operator overloading. |
---|
4 | Earlier versions of Cforall allowed `0` and `1` to be variable names, allowing |
---|
5 | multiple interpretations of them according to the existing variable |
---|
6 | overloading rules, with the following declarations in the prelude: |
---|
7 | |
---|
8 | const int 0, 1; |
---|
9 | forall ( dtype DT ) const DT * const 0; |
---|
10 | forall ( ftype FT ) FT * const 0; |
---|
11 | |
---|
12 | This did, however, create some backward-compatibility problems and potential |
---|
13 | performance issues, and works poorly for generic types. To start with, this |
---|
14 | (entirely legal C) code snippet doesn't compile in Cforall: |
---|
15 | |
---|
16 | if ( 0 ) {} |
---|
17 | |
---|
18 | It desugars to `if ( (int)(0 != 0) ) {}`, and since both `int` and |
---|
19 | `forall(dtype DT) DT*` have a != operator which returns `int` the resolver can |
---|
20 | not choose which `0` variable to take, because they're both exact matches. |
---|
21 | |
---|
22 | The general `!=` computation may also be less efficient than a check for a zero |
---|
23 | value; take the following example of a rational type: |
---|
24 | |
---|
25 | struct rational { int32_t num, int32_t den }; |
---|
26 | rational 0 = { 0, 1 }; |
---|
27 | |
---|
28 | int ?!=? (rational a, rational b) { |
---|
29 | return ((int64_t)a.num)*b.den != ((int64_t)b.num)*a.den; |
---|
30 | } |
---|
31 | |
---|
32 | int not_zero (rational a) { return a.num != 0; } |
---|
33 | |
---|
34 | To check if two rationals are equal we need to do a pair of multiplications to |
---|
35 | normalize them (the casts in the example are to prevent overflow), but to |
---|
36 | check if a rational is non-zero we just need to check its numerator, a more |
---|
37 | efficient operation. |
---|
38 | |
---|
39 | Finally, though polymorphic null-pointer variables can be meaningfully |
---|
40 | defined, most other polymorphic variables cannot be, which makes it difficult |
---|
41 | to make generic types "truthy" using the existing system: |
---|
42 | |
---|
43 | forall(otype T) struct pair { T x; T y; }; |
---|
44 | forall(otype T | { T 0; }) pair(T) 0 = { 0, 0 }; |
---|
45 | |
---|
46 | Now, it seems natural enough to want to define the zero for this pair type as |
---|
47 | a pair of the zero values of its element type (if they're defined). |
---|
48 | The declaration of `pair(T) 0` above is actually illegal though, as there is |
---|
49 | no way to represent the zero values of an infinite number of types in the |
---|
50 | single memory location available for this polymorphic variable - the |
---|
51 | polymorphic null-pointer variables defined in the prelude are legal, but that |
---|
52 | is only because all pointers are the same size and the single zero value is a |
---|
53 | legal value of all pointer types simultaneously; null pointer is, however, |
---|
54 | somewhat unique in this respect. |
---|
55 | |
---|
56 | The technical explanation for the problems with polymorphic zero is that `0` |
---|
57 | is really a rvalue, not a lvalue - an expression, not an object. |
---|
58 | Drawing from this, the solution we propose is to give `0` a new built-in type, |
---|
59 | `zero_t`, and similarly give `1` the new built-in type `one_t`. |
---|
60 | If the prelude defines `!=` over `zero_t` this solves the `if ( 0 )` problem, |
---|
61 | because now the unambiguous best interpretation of `0 != 0` is to read them |
---|
62 | both as `zero_t` (and say that this expression is false). |
---|
63 | Backwards compatibility with C can be served by defining conversions in the |
---|
64 | prelude from `zero_t` and `one_t` to `int` and the appropriate pointer |
---|
65 | types, as below: |
---|
66 | |
---|
67 | // int 0; |
---|
68 | forall(otype T | { void ?{safe}(T*, int); }) void ?{safe} (T*, zero_t); |
---|
69 | forall(otype T | { void ?{unsafe}(T*, int); }) void ?{unsafe} (T*, zero_t); |
---|
70 | |
---|
71 | // int 1; |
---|
72 | forall(otype T | { void ?{safe}(T*, int); }) void ?{safe} (T*, one_t); |
---|
73 | forall(otype T | { void ?{unsafe}(T*, int); }) void ?{unsafe} (T*, one_t); |
---|
74 | |
---|
75 | // forall(dtype DT) const DT* 0; |
---|
76 | forall(dtype DT) void ?{safe}(const DT**, zero_t); |
---|
77 | // forall(ftype FT) FT* 0; |
---|
78 | forall(ftype FT) void ?{safe}(FT**, zero_t); |
---|
79 | |
---|
80 | Further, with this change, instead of making `0` and `1` overloadable |
---|
81 | variables, we can instead allow user-defined constructors (or, more flexibly, |
---|
82 | safe conversions) from `zero_t`, as below: |
---|
83 | |
---|
84 | // rational 0 = { 0, 1 }; |
---|
85 | void ?{safe} (rational *this, zero_t) { this->num = 0; this->den = 1; } |
---|
86 | |
---|
87 | Note that we don't need to name the `zero_t` parameter to this constructor, |
---|
88 | because its only possible value is a literal zero. |
---|
89 | This one line allows `0` to be used anywhere a `rational` is required, as well |
---|
90 | as enabling the same use of rationals in boolean contexts as above (by |
---|
91 | interpreting the `0` in the desguraring to be a rational by this conversion). |
---|
92 | Furthermore, while defining a conversion function from literal zero to |
---|
93 | `rational` makes rational a "truthy" type able to be used in a boolean |
---|
94 | context, we can optionally further optimize the truth decision on rationals as |
---|
95 | follows: |
---|
96 | |
---|
97 | int ?!=? (rational a, zero_t) { return a.num != 0; } |
---|
98 | |
---|
99 | This comparison function will be chosen in preference to the more general |
---|
100 | rational comparison function for comparisons against literal zero (like in |
---|
101 | boolean contexts) because it doesn't require a conversion on the `0` argument. |
---|
102 | Functions of the form `int ?!=? (T, zero_t)` can acutally be used in general |
---|
103 | to make a type `T` truthy without making `0` a value which can convert to that |
---|
104 | type, a capability not available in the current design. |
---|
105 | |
---|
106 | This design also solves the problem of polymorphic zero for generic types, as |
---|
107 | in the following example: |
---|
108 | |
---|
109 | // ERROR: forall(otype T | { T 0; }) pair(T) 0 = { 0, 0 }; |
---|
110 | forall(otype T | { T 0; }) void ?{safe} (pair(T) *this, zero_t) { |
---|
111 | this->x = 0; this->y = 0; |
---|
112 | } |
---|
113 | |
---|
114 | The polymorphic variable declaration didn't work, but this constructor is |
---|
115 | perfectly legal and has the desired semantics. |
---|
116 | |
---|
117 | We can assert that `T` can be used in a boolean context as follows: |
---|
118 | |
---|
119 | `forall(otype T | { int ?!=?(T, zero_t); })` |
---|
120 | |
---|
121 | Since the C standard (6.5.16.1.1) specifically states that pointers can be |
---|
122 | assigned into `_Bool` variables (and implies that other artithmetic types can |
---|
123 | be assigned into `_Bool` variables), it seems natural to say that assignment |
---|
124 | into a `_Bool` variable effectively constitutes a boolean context. |
---|
125 | To allow this interpretation, I propose including the following function (or |
---|
126 | its effective equivalent) in the prelude: |
---|
127 | |
---|
128 | forall(otype T | { int ?!=?(T, zero_t); }) |
---|
129 | void ?{safe}( _Bool *this, T that ) { *this = that != 0; } |
---|
130 | |
---|
131 | Note that this conversion is not transitive; that is, for `t` a variable of |
---|
132 | some "truthy" type `T`, `(_Bool)t;` would use this conversion (in the absence |
---|
133 | of a lower-cost one), `(int)t;` would not use this conversion (and in fact |
---|
134 | would not be legal in the absence of another valid way to convert a `T` to an |
---|
135 | `int`), but `(int)(_Bool)t;` could legally use this conversion. |
---|
136 | |
---|
137 | Similarly giving literal `1` the special type `one_t` allows for more |
---|
138 | concise and consistent specification of the increment and decrement operators, |
---|
139 | using the following de-sugaring: |
---|
140 | |
---|
141 | ++i => i += 1 |
---|
142 | i++ => (tmp = i, i += 1, tmp) |
---|
143 | --i => i -= 1 |
---|
144 | i-- => (tmp = i, i -= 1, tmp) |
---|
145 | |
---|
146 | In the examples above, `tmp` is a fresh temporary with its type inferred from |
---|
147 | the return type of `i += 1`. |
---|
148 | Under this proposal, defining a conversion from `one_t` to `T` and a |
---|
149 | `lvalue T ?+=? (T*, T)` provides both the pre- and post-increment operators |
---|
150 | for free in a consistent fashion (similarly for -= and the decrement |
---|
151 | operators). |
---|
152 | If a meaningful `1` cannot be defined for a type, both increment operators can |
---|
153 | still be defined with the signature `lvalue T ?+=? (T*, one_t)`. |
---|
154 | Similarly, if scalar addition can be performed on a type more efficiently than |
---|
155 | by repeated increment, `lvalue T ?+=? (T*, int)` will not only define the |
---|
156 | addition operator, it will simultaneously define consistent implementations of |
---|
157 | both increment operators (this can also be accomplished by defining a |
---|
158 | conversion from `int` to `T` and an addition operator `lvalue T ?+=?(T*, T)`). |
---|
159 | |
---|
160 | To allow functions of the form `lvalue T ?+=? (T*, int)` to satisfy "has an |
---|
161 | increment operator" assertions of the form `lvalue T ?+=? (T*, one_t)`, |
---|
162 | we also define a non-transitive unsafe conversion from `_Bool` (allowable |
---|
163 | values `0` and `1`) to `one_t` (and `zero_t`) as follows: |
---|
164 | |
---|
165 | void ?{unsafe} (one_t*, _Bool) {} |
---|
166 | |
---|
167 | As a note, the desugaring of post-increment above is possibly even more |
---|
168 | efficient than that of C++ - in C++, the copy to the temporary may be hidden |
---|
169 | in a separately-compiled module where it can't be elided in cases where it is |
---|
170 | not used, whereas this approach for Cforall always gives the compiler the |
---|
171 | opportunity to optimize out the temporary when it is not needed. |
---|
172 | Furthermore, one could imagine a post-increment operator that returned some |
---|
173 | type `T2` that was implicitly convertable to `T` but less work than a full |
---|
174 | copy of `T` to create (this seems like an absurdly niche case) - since the |
---|
175 | type of `tmp` is inferred from the return type of `i += 1`, you could set up |
---|
176 | functions with the following signatures to enable an equivalent pattern in |
---|
177 | Cforall: |
---|
178 | |
---|
179 | lvalue T2 ?+=? (T*, one_t); // increment operator returns T2 |
---|
180 | void ?{} (T2*, T); // initialize T2 from T for use in `tmp = i` |
---|
181 | void ?{safe} (T*, T2); // allow T2 to be used as a T when needed to |
---|
182 | // preserve expected semantics of T x = y++; |
---|