Context Navigation

source: doc/working/glen_conversions/index.html @ cdb4eaa

Last change on this file since cdb4eaa was 6eb131c, checked in by Aaron Moss <a3moss@…>, 6 years ago

Proposal documents for user-defined conversions

pull Glen's old conversions document into working docs
update user_conversions.md to reference new location

Property mode set to 100644

File size: 59.5 KB

Line
1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2	"http://www.w3.org/TR/html4/strict.dtd">
3	<html>
4	<head>
5	<title>Conversions for Cforall</title>
6	<style type='text/css'>
7	.rationale { font-size: smaller; background-color: #F0F0FF }
8	pre { margin-left: 2em; border-width: 1px; }
9	code, pre { font-family: courier; font-weight: bold; }
10	pre i {font-weight: normal; }
11	dfn {font-weight: bold; font-style: italic; }
12	</style>
13	</head>
14
15	<body>
16	<h1>Conversions for Cforall</h1>
17
18	<p><b>NOTE:</b> This proposal for constructors and user-defined conversions
19	does not represent the current state of Cforall language development, but is
20	maintained for its possible utility in building user-defined conversions. See
21	<tt>doc/proposals/user_conversions.md</tt> for a more current presentation of
22	these ideas.</p>
23
24	<p>This is the first draft of a description of a possible extension to the
25	current definition of Cforall ("Cforall-as-is") that would let programmers
26	fit new types into Cforall's system of conversions.</p>
27
28	<ol>
29	<li><a href="#notes">Design Notes</a>
30	<ol>
31	<li><a href="#goals">Goals</a></li>
32	<li><a href="#conversions">Conversions</a></li>
33	<li><a href="#constructors">Constructors</a></li>
34	<li><a href="#ambiguity">Ambiguity</a></li>
35	</ol>
36	</li>
37	<li><a href="#extension">Proposed Extension</a>
38	<ol>
39	<li><a href="#ops">New Operator Identifiers</a></li>
40	<li><a href="#casts">Cast Expressions</a></li>
41	<li><a href='#definitions'>Object Definitions</a></li>
42	<li><a href='#default'>Default Functions</a></li>
43	</ol>
44	</li>
45	<li><a href="#chaining">Conversion Composition</a></li>
46	<li><a href='#cost'>Constructors and Cost</a></li>
47	<li><a href='#heap'>Heap Allocation</a></li>
48	<li><a href='#generic'>Generic Conversions and Constructors</a></li>
49	<li><a href="#usual">C's "Usual Arithmetic Conversions"</a>
50	<ol>
51	<li><a href="#floating">Floating-Point Types</a></li>
52	<li><a href="#largeint">Large Integer Types</a></li>
53	<li><a href="#intpromo">C's "Integer Promotions"</a></li>
54	</ol>
55	</li>
56	<li><a href="#otherpromo">Other Promotions</a></li>
57	<li><a href="#demotions">Other Pre-Defined Implicit Conversions</a></li>
58	<li><a href="#explicit">Pre-Defined Explicit Conversions</a></li>
59	<li><a href="#nonconversions">Non-Conversions</a></li>
60	<li><a href="#assignment">Assignment Operators</a></li>
61	<li><a href="#overload">Overload Resolution</a></li>
62	<li><a href="#final">Final Notes</a></li>
63	</ol>
64
65	<h2 id="notes">Design Notes</h2>
66
67	<h3 id='goals'>Goals</h3>
68	<p>My design goal for this extension is to provide a framework that
69	explains the bulk of C's conversion semantics in terms of more basic
70	languages, just as Cforall explains most expression semantics in terms of
71	overloaded function calls.</p>
72
73	<p>My pragmatic goal is to allow a programmer to define a portable rational
74	number data type, fit it into the existing C type system, and use it in
75	mixed-mode arithmetic expressions, all in a convenient and esthetically
76	pleasing manner.</p>
77
78	<h3 id="conversions">Conversions</h3>
79
80	<p>A <dfn>conversion</dfn> creates a value from a value of a different
81	type. C defines a large number of conversions, especially between
82	arithmetic types. A subset of these can be performed by <dfn>implicit
83	conversions</dfn>, which occurs in certain contexts: in assignment
84	expressions, when passing arguments to function (where parameters are
85	"assigned the value of the corresponding argument"), in initialized
86	declarations (where "the same type constraints and conversions as for
87	simple assignment apply"), and in mixed mode arithmetic. All conversions
88	can be performed explicitly by cast expressions.</p>
89
90	<p>C prefers some implicit conversions, the <dfn>promotions</dfn>, to the
91	others. The promotions are ranked among themselves, creating a hierarchy
92	of types. In mixed-mode operations, the "usual arithmetic conversions"
93	promote the operands to what amounts to their least common supertype.
94	Cforall-as-is uses a slightly larger set of promotions to choose the
95	smallest possible promotion when resolving overloading.</p>
96
97	<p>An extension should allow Cforall to explain C's conversions as a set of
98	pre-defined functions, including its explicit conversions, implicit
99	conversions, and preferences among conversions. The extension must let the
100	programmer define new conversions for programmer-defined types, for
101	instance so that new arithmetic types can be used conveniently in
102	mixed-mode arithmetic.</p>
103
104	<h3 id="constructors">Constructors</h3>
105
106	<p>C++ introduced constructors to the C language family, and I will use its
107	terminology. A <dfn>constructor</dfn> is a function that initializes an
108	object. C does not have constructors; instead, it makes do with
109	initialization, which works like assignment. Cforall-as-is does not have
110	constructors, either: instead, by analogy with C's semantics, a
111	programmer-defined assignment function may be called during initialization.
112	However, there is a key difference between a function that implements
113	assignment and a constructor: constructors assume that the object is
114	uninitialized, and must set up any data structure invariants that the
115	object is supposed to obey. An assignment function assumes that the target
116	object obeys its invariants.</p>
117
118	<p>A <dfn>default constructor</dfn> has no parameters other than the object it
119	initializes. It establishes invariants, but need not do anything else. A
120	default constructor for a rational number type might set the denominator to be
121	non-zero, but leave the numerator undefined.</p>
122
123	<p>A <dfn>copy constructor</dfn> has two parameters: the object it
124	initializes, and a value of the same type. Its purpose is to copy the
125	value into the object, and so it is very similar to an assignment
126	function. In fact, it could be expressed as a call to a default constructor
127	followed by an assignment.</p>
128
129	<p>A <dfn>converting constructor</dfn> also has two parameters, but the
130	second parameter is a value of some type different from the type
131	of the object it initializes. Its purpose is to convert the value to the
132	object's type before copying it, and so it is very similar to a C
133	assignment operation that performs an implicit conversion.</p>
134
135	<p>C++ sensibly defines parameter passing as call by initialization, since
136	the parameter is uninitialized when the argument value is placed in it.
137	Extended Cforall should do the same. However, parameter passing is one of
138	the main places where implicit conversions occur. Hence in extended
139	Cforall <em>constructors define the implicit conversions</em>. Cforall
140	should also encourage programmers to maintain the similarity between
141	constructors and assignment.</p>
142
143	<h3 id="ambiguity">Ambiguity</h3>
144
145	<p>In extended Cforall, programmer-defined conversions should fit in with
146	the predefined conversions. For instance, programmer-defined promotions
147	should interact with the normal promotions so that programmer-defined types
148	can take part in mixed-mode arithmetic expressions. The first design that
149	springs to mind is to define a minimal set of conversions between
150	neighbouring types in the type hierarchy, and to have Cforall create
151	conversions between more distant types by composition of predefined and
152	programmer-defined conversions. Unfortunately, if one draws a graph of C's
153	promotions, with C's types as vertices and C's promotions as edges, the
154	result is a directed acyclic graph, not a tree. This means that an attempt
155	to build the full set of promotions by composition of a minimal set of
156	promotions will fail.</p>
157
158	<p> Consider a simple processor with 32-bit <code>int</code> and
159	<code>long</code> types. On such a machine, C's "usual arithmetic
160	conversions" dictate that mixed-mode arithmetic that combines a signed
161	integer with an unsigned integer must promote the signed integer to an
162	unsigned type. Here is a directed graph showing the some of the minimal
163	set of promotions. Each of the four promotions is necessary, because each
164	could be required by some mixed-mode expression, and none can be decomposed
165	into simpler conversions.</p>
166
167	<pre>
168	long --------> unsigned long
169	^ ^
170	\| \|
171	int ---------> unsigned int
172	</pre>
173
174	<p>Now imagine attempting to compose an <code>int</code>-to-<code>unsigned
175	long</code> conversion from the minimal set: there are two paths through
176	the graph, so the composition is ambiguous.</p>
177
178	<p>(In C, and in Cforall-as-is, no ambiguity exists: there is just one
179	<code>int</code>-to-<code>unsigned long</code> promotion, defined by the
180	language semantics. In Cforall-as-is, the preference for
181	<code>int</code>-to-<code>long</code> over
182	<code>int</code>-to-<code>unsigned long</code> is determined by a
183	"conversion cost" calculated from the graph of the full set of promotions,
184	but the calculation depends on maximal path lengths, not the exact
185	path.)</p>
186
187	<p>Unfortunately, the same problem with ambiguity creeps in any time
188	conversions might be chained together. The extension must carefully
189	control conversion composition, so that programmers can avoid ambiguous
190	conversions.</p>
191
192	<h2 id='extension'>Proposed Extension</h2>
193
194	<p>The rest of this document describes my proposal to add
195	programmer-definable conversions and constructors to Cforall.</p>
196
197	<p class='rationale'>If your browser supports CSS style sheets, the
198	proposal will appear in "normal" paragraphs, and commentary on the proposal
199	will have the same appearance as this paragraph.</p>
200
201	<h3 id='ops'>New Operator Identifiers</h3>
202
203	<p>Cforall would be given a <dfn>cast identifier</dfn>, two
204	<dfn>constructor identifiers</dfn>, and a <dfn>destructor
205	identifier</dfn>:</p>
206
207	<ul>
208	<li> <code>(?)?</code>, for cast functions.</li>
209	<li> <code>(?create)?</code>, for constructors.</li>
210	<li> <code>(?promote)?</code>, for constructors that are promotions.</li>
211	<li> <code>(?destroy)?</code>, for destructors.</li>
212	</ul>
213
214	<div class='rationale'>
215	<p>The ugly identifier <code>(?)?</code> is meant to be mnemonic for the
216	cast expression. The other identifiers are pretty weak (suggestions,
217	anyone?) but are supposed to remind the programmer of the connection
218	between conversions and constructors.</p>
219
220	<p>We could instead use a single <code>(?create)?</code> identifier for
221	constructors and add a <code>promote</code> storage class specifier, at
222	some small risk clashes of with identifiers in existing code.</p> </div>
223
224	<p>It is an error to declare two functions with different constructor
225	identifiers that have the same type in the same translation unit.</p>
226
227	<p>Functions declared with these identifiers can be polymorphic. Unlike
228	other polymorphic functions, the return type of a polymorphic cast function
229	need not be derivable from the type of its parameters</p>
230
231	<div class='rationale'>
232	<p>The return type of a call to a polymorphic cast
233	function can be deduced from the calling context.</p>
234
235	<pre>
236	forall(type T1) T1 (?)?(T2); // <i>Legal.</i>
237	forall(type T1) T1 pfun(T2); // <i>Illegal -- no way to infer </i>T1.
238	</pre>
239	</div>
240
241	<p>A <dfn>cast function</dfn> from type <code>T1</code> to type
242	<code>T2</code> is named "<code>(?)?</code>", accepts exactly one explicit
243	argument of type <i>T1</i>, and returns a value of type <i>T2</i>.</p>
244
245	<p class='rationale'>If the cast function is polymorphic, it will have
246	type parameters and assertion parameters as well, and can be said to be a
247	cast function from many different types to many different types.
248	</p>
249
250	<p>A <dfn>default constructor function</dfn> for type <i>T</i> is named
251	"<code>(?create)?</code>", accepts exactly one explicit argument of type
252	<i>T</i><code>*</code>, and returns <code>void</code>.</p>
253
254	<p>A <dfn>copy constructor function</dfn> for type <i>T</i> is named
255	<code>"(?create)?</code>", accepts exactly two explicit arguments of types
256	<i>T</i><code>*</code> and <i>T</i>, and returns <code>void</code>.</p>
257
258	<p>A <dfn>converting constructor function</dfn> for type <i>T1</i> from
259	<i>T2</i> is named "<code>(?create)?</code>" or "<code>(?promote)?</code>",
260	accepts exactly two explicit arguments of types <i>T1</i><code>*</code> and
261	<i>T2</i>, and returns <code>void</code>.</p>
262
263	<p>A <dfn>destructor function</dfn> for type <i>T</i> is named
264	"<code>(?destroy)?</code>", accepts exactly one explicit argument of type
265	<i>T</i><code>*</code>, and returns <code>void</code>.</p>
266
267	<div class='rationale'>
268
269	<p>The monomorphic function prototypes for these functions are</p>
270	<pre>
271	<i>T1</i> (?)?(<i>T2</i>);
272	void (?create)?(<i>T1</i>*);
273	void (?create)?(<i>T1</i>*, <i>T2</i>);
274	void (?promote)?(<i>T1</i>*, <i>T2</i>);
275	void (?destroy)?(<i>T1</i>*);
276	</pre>
277	</div>
278
279	<h3 id='casts'>Cast Expressions</h3>
280
281	<p>In most cases the cast expression <code>(<i>T</i>)<i>e</i></code> would
282	be treated like the function call <code>(?)?(<i>e</i>)</code>, except that
283	only cast functions to type <i>T</i> would be valid interpretations of
284	<code>(?)?</code>, and <code><i>e</i></code> would not be implicitly
285	converted to the cast function's parameter type. In particular, the usual
286	rules for resolving function overloading (see <a href='#overload'>below</a>)
287	would be used to choose the best interpretation of the expression.</p>
288
289	<div class='rationale'>
290	<p>For example, in</p>
291	<pre>
292	type Wazzit;
293	type Thingum;
294	Wazzit w;
295	(Thingum)w;
296	</pre>
297	<p>the cast function that is called must be "<code>Thingum
298	(?)?(Wazzit)</code>", or a polymorphic function that can be specialized to
299	that.</p>
300
301	<p>The ban on implicit conversions within the cast allows programmers to
302	explicitly control composition of conversions and avoid ambiguity. I also
303	hope that this will make it easier for compilers and programmers to
304	determine which conversions will be applied in which circumstances. If
305	implicit conversions could be applied to the inputs and outputs of casts,
306	when any and all of the conversion functions involved could be polymorphic
307	... the possibilities seem endless, unfortunately.</p>
308
309	</div>
310
311	<h3 id='definitions'>Object Definitions</h3>
312	<p>A definition of an object <i>x</i> would call a constructor function. Let
313	<i>T</i> be <i>x</i>'s type with type qualifiers removed, and let <i>a</i>
314	be <i>x</i>'s address (with type <code><i>T</i>*</code>).</p>
315
316	<p class='rationale'>If type qualifiers weren't ignored, <code>const</code>
317	objects couldn't be initialized, and every constructor would have to be
318	duplicated, with one version for <i>T</i>* objects and one for
319	<code>volatile</code> <i>T</i>* objects.</p>
320
321	<ul>
322	<li>A definition with an initializer that is a single expression
323	<i>e</i>, optionally enclosed in braces, would call a copy or converting
324	constructor. The call would be treated much like the function call
325	<code><i>f</i>(<i>a</i>,<i>e</i>)</code>, except that only copy and
326	converting constructors for type <i>T</i> would be valid interpretations
327	of <code><i>f</i></code>, and <i>e</i> would not be implicitly
328	converted to the type of the constructor's second parameter.</li>
329	<li>If <i>x</i> has automatic storage duration and is not initialized
330	explicitly, the definition would call a default constructor function.
331	The call would be treated much like the function call
332	<code><i>f</i>(<i>a</i>)</code>, except that only default
333	constructor functions for type <i>T</i> would be valid interpretations of
334	<code><i>f</i></code>.</li>
335	<li><p>If <i>x</i> has static storage duration and is not initialized
336	explicitly, and is defined within the scope of a type definition that
337	defines <i>T</i>, then <i>T</i>'s implementation type would determine how
338	<i>x</i> is initialized.</p>
339	<div class='rationale'>
340	<pre>
341	type Rational = struct { int numerator; unsigned denominator; };
342	Rational r; // Both members initialized to 0.
343	</pre>
344	</div>
345	</li>
346	<li><p>If <i>x</i> has static storage duration and is not initialized
347	explicitly, and the type <i>T</i> is an opaque type, the definition
348	would be treated as if <i>x</i> was initialized with the expression
349	<code>0</code>.</p>
350	<div class='rationale'>
351	<p>This is a simple extension of C's rules for static objects,
352	which initialized them all to 0. Frequently, the 0 involved
353	will have type <i>T</i>, and the definition will call a copy
354	constructor.</p>
355	<pre>
356	extern type Rational;
357	extern Rational 0;
358	static Rational r; // initialized with the Rational 0.
359	</pre>
360	<p>In other cases, the 0 will be an integer or null pointer, and the
361	definition will call a converting constructor.</p>
362
363	<p>The obvious alternative design would call <i>T</i>'s default
364	constructor. That design would be inconsistent, because some static
365	objects would go uninitialized. It would also cause subtle problems,
366	because a particular static definition could be uninitialized or
367	initialized to 0 depending on whether <i>T</i> is an <code>extern
368	type</code> or a <code>typedef</code>.</p>
369	</div>
370	</li>
371	</ul>
372
373	<p>Except when calling constructors, parameter passing invokes constructor
374	functions. Passing argument expression <i>e</i> to a parameter would be
375	equivalent to initializing the parameter with that expression. When
376	calling constructors, the value of the argument would be copied into the
377	parameter.</p>
378
379	<p>When the lifetime of <i>x</i> ends, a destructor function would be called.
380	The call would be treated much like the function call
381	<code>(?destroy)?(<i>a</i>)</code>. When a block ends, the objects that were
382	defined in the block would be destroyed in the reverse of the order in which
383	they are declared.</p>
384
385	<p>The storage class specifier <code>register</code> will have the
386	semantics that it has in C++, instead of the semantics of C: it is merely a
387	hint to the implementation that the object will be heavily used, and does
388	not prevent programs from computing the address of the object.</p>
389
390	<h3 id='default'>Default Functions</h3>
391
392	<p>In Cforall-as-is, every declaration with type-class <code>type</code>
393	implicitly declares a default assignment function, with the same scope and
394	linkage as the type. Extended Cforall would also declare a <dfn>default
395	default constructor</dfn> and a <dfn>default destructor</dfn>.</p>
396
397	<div class='rationale'>
398	<pre>
399	{
400	extern type T;
401	T t; // <i>calls external constructor for T.</i>
402	} // <i>calls external destructor for T.</i>
403	</pre>
404	<p>The destructor and some sort of constructor are necessary to instantiate
405	the type. I include the default constructor because it is the most basic.
406	Arguably the declaration should also declare a default copy constructor,
407	but I chose not to because Cforall can construct a copy constructor from
408	the default constructor and the assignment operator, as will be seen
409	<a href="#generic">below</a>.</p>
410
411	<p>If the type does not need to be instantiated, it probably should have
412	been declared by <code>dtype</code> instead of by <code>type</code>.</p>
413	</div>
414
415	<p>A type definition would implicitly define a default constructor and
416	destructor by inheriting the implementation type's default constructor and
417	destructor, just as is done for the implicitly defined default assignment
418	function.</p>
419
420	<h2 id='chaining'>Conversion Composition</h2>
421
422	<p>As mentioned above, Cforall does not apply implicit conversions to the
423	arguments and results of cast expressions or constructor calls. Neither
424	does it automatically create conversions or constructors by composing
425	programmer-defined compositions: given</p>
426
427	<pre>
428	T1 (?)?(T2);
429	T2 (?)?(T3);
430	T3 v3;
431	(T1)v3;
432	</pre>
433
434	<p>then Cforall does not automatically create</p>
435
436	<pre>
437	T1 (?)?(T3 p) { return (T1)(T2)p; }
438	</pre>
439
440	<p>Composition of conversions does show up through a third mechanism where
441	the programmer has more control: assertion lists. Consider a
442	<code>Month</code> type, that represents months as integers between 0 and
443	11. Clearly a <code>Month</code> can be promoted to <code>unsigned</code>,
444	and to any type above <code>unsigned</code> in the arithmetic type
445	hierarchy as well.</p>
446
447	<pre id='monthpromo'>
448	type Month = unsigned;
449
450	forall(type T \| void (?promote)(T*, unsigned))
451	void (?promote)?(T* target, Month source) {
452	unsigned u_temp = (unsigned)source;
453	T t_temp = u_temp; // <i>calls the assertion parameter.</i>
454	*target = t_temp;
455	}
456	</pre>
457
458	<p>The intimidating polymorphic promotion declaration says that, if
459	<code>T</code> is a type and <code>unsigned</code> can be promoted to
460	<code>T</code>, then the function can promote <code>Month</code> to
461	<code>T</code>.</p>
462
463	<pre>
464	Month m;
465	unsigned long ul = m;
466	</pre>
467
468	<p>To initialize <code>ul</code>, Cforall must bind <code>T</code> to
469	<code>unsigned long</code>, find the (pre-defined)
470	<code>unsigned</code>-to-<code>unsigned long</code> promotion, and pass it
471	to the assertion parameter of the polymorphic
472	<code>Month</code>-to-<code>T</code> function.</p>
473
474	<p>But what about converting from <code>Month</code> to
475	<code>unsigned</code> itself?</p>
476
477	<pre>
478	unsigned u = m; // <i>How?</i>
479	</pre>
480
481	<p>A monomorphic <code>Month</code>-to-<code>unsigned</code> constructor
482	would do the job, but its body would mostly duplicate the body of the
483	polymorphic function.</p>
484
485	<p>Instead, Cforall should use the polymorphic promotion and the
486	<code>unsigned</code> copy constructor. To initialize <code>u</code>,
487	Cforall should pass the <code>unsigned</code> copy constructor to the assertion
488	parameter of the polymorphic <code>Month</code> promotion, and bind
489	<code>T</code> to <code>unsigned</code>.</p>
490
491	<p>Note that the polymorphic promotion can promote <code>Month</code> to
492	the standard types, to implementation-defined extended types, and to
493	programmer-defined types that have yet to be written. This is much better
494	than writing a flock of monomorphic promotions, with function bodies that
495	would be nearly identical, to convert <code>Month</code> to each unsigned
496	type individually. The predefined constructors make heavy use of this
497	<dfn id='idiom'>constructor idiom</dfn>: instead of writing</p>
498
499	<pre>
500	void (?promote)? (T1*, T2);
501	</pre>
502
503	<p>("You can make a T2 into a T1"), write</p>
504	<pre>
505	forall(type T \| void (?promote)?(T, T1) ) void (?promote)?(T, T2);
506	</pre>
507
508	<p>("You can make a T2 into anything that can be made from a T1").</p>
509
510	<h2 id='cost'>Constructors and Cost</h2>
511
512	<p>Calls to constructors have <dfn>construction costs</dfn>, which let
513	Cforall choose the least expensive implicit conversion when given a
514	choice.</p>
515
516	<ol>
517	<li>The cost of a call to a copy constructor is 0.</li>
518	<li>The cost of a call to a monomorphic constructor is 1.</li>
519	<li>The cost of a call to a polymorphic constructor, or a specialization
520	of it, is 1 plus the sum of the construction costs of constructors
521	that are passed to it through assertion parameters.</li>
522	</ol>
523
524	<div class='rationale'>
525
526	<p>Note that, although point 3 refers to constructors that are
527	passed at run-time, the translator statically matches arguments to
528	assertion parameters, so it can determine construction costs statically.</p>
529
530	<p>Construction cost is defined for <em>every</em>
531	constructor, not just the promotions (which are the equivalent of the safe
532	conversions of Cforall-as-is). This seemed like the easiest way to handle
533	(admittedly dicey) "mixed" constructors, where the constructor and its
534	assertion parameter have different identifiers:</p>
535
536	<pre>
537	type Thingum;
538	type Wazzit;
539	forall(type T \| void (?create)?(T*, Thingum) )
540	void (?promote)?(T*, Wazzit);
541	</pre>
542	</div>
543
544	<h3>Examples:</h3>
545	<p>"<code>unsigned ui = 42U;</code>" calls a copy constructor, and so has
546	cost 0.</p>
547
548	<p>"<code>unsigned ui = m;</code>", where <code>m</code> has type
549	<code>Month</code>, calls the polymorphic <code>Month</code> promotion
550	defined <a href="#monthpromo">previously</a>. It passes the
551	<code>unsigned</code>-to-<code>unsigned</code> copy constructor to the
552	assertion parameter, and so has cost 1+0 = 1.</p>
553
554	<p>"<code>unsigned long ul = m;</code>" calls the polymorphic
555	<code>Month</code> promotion, passing the
556	<code>unsigned</code>-to-<code>unsigned long</code> constructor to the
557	assertion parameter. <code>unsigned</code>-to-<code>unsigned long</code>
558	is defined below and will turn out to have cost 1, so the total cost is 2.</p>
559
560	<p>Inside the body of the <code>Month</code> promotion, the assertion
561	parameter has a monomorphic type, and so has a construction cost of 1 where
562	it is called by the initialization of <code>t_temp</code>. The cost of the
563	<em>argument</em> passed through the assertion parameter has no relevance
564	inside the body of the promotion.</p>
565
566	<h2 id='overload'>Overload Resolution</h2>
567
568	<p>In Cforall-as-is, there is at most one language-defined implicit
569	conversion between any two types. In extended Cforall, more than one
570	conversion may be applicable, and overload resolution must be adapted to
571	account for that, by using the lowest-cost conversion.</p>
572
573	<p>The <dfn>unsafe conversion cost</dfn> of a function call expression
574	would be the total conversion cost of implicit calls of
575	<code>(?create)?()</code> constructors applied directly to arguments of the
576	function -- 0 if there are none.</p>
577
578	<p class='rationale'>This would replace a rule in Cforall-as-is, which
579	considers all unsafe conversions to be equally bad and just counts them. I
580	think the difference would be subtle and unimportant.</p>
581
582	<p>The <dfn>promotion cost</dfn> would be the total conversion costs of
583	implicit calls of <code>(?promote)?()</code> constructors applied directly
584	to arguments of the function -- 0 if there are none.</p>
585
586	<p>Overload resolution would examine each argument expression individually.
587	The best interpretations of an expression would be:</p>
588
589	<ol>
590	<li>the interpretations with the lowest unsafe conversion cost;</li>
591	<li>of these, the interpretations with the lowest promotion cost;</li>
592	<li>of these, if any can be promoted to the parameter type, then just
593	those that can be converted at minimal cost; otherwise, all remaining
594	interpretations.</li>
595	</ol>
596
597	<p>The best interpretation would be implicitly converted to the parameter
598	type, by calling the conversion function with minimal cost. If there is
599	more than one best interpretation, or if there is more than one
600	minimal-cost conversion, the argument is ambiguous.</p>
601
602	<p>A maximal set of interpretations of the function call expression that
603	have compatible result types produces a single interpretation: the
604	interpretations with the lowest unsafe conversion cost, and of these, the
605	interpretations with the lowest promotion cost. If there is more than one
606	such interpretation, the function call expression is ambiguous.</p>
607
608	<h2 id='heap'>Heap Allocation</h2>
609
610	<p>Cforall would define new heap allocation functions that would ensure
611	that constructors and destructors would be applied to objects in the
612	heap. There's lots of room for ambitious design here, but a simple
613	facility might look like this:</p>
614
615	<pre>
616	forall(type T) void delete(T const volatile restrict* ptr) {
617	if (ptr) (?destroy)?(ptr);
618	free(ptr);
619	}
620	</pre>
621
622	<div class='rationale'>
623	<p>In a call to <code>delete()</code>, the argument might be a pointer to a
624	pointer: <code>T</code> would be a pointer type, and the argument might
625	have all three type qualifiers. (If it doesn't, pointer conversions will add
626	missing qualifiers to the argument.)</p>
627	<pre>
628	// <i>Pointer to a const volatile restricted pointer to an int:</i>
629	int * const volatile restrict * pcvrpi;
630	// <i>...</i>
631	delete(cvrpi); // T<i> bound to </i>int *
632	</pre>
633	</div>
634
635	<p>A <code>new()</code> function would take the address of a pointer and an
636	initial value, and points the pointer at heap storage initialized to that
637	value.</p>
638	<pre>
639	forall(type T \| void (?create)?(T*, T))
640	void new(T* volatile restrict* ptr, T val) {
641	*ptr = malloc(sizeof(T));
642	if (ptr) (?create)?(ptr, val); // <i>explicit constructor call</i>
643	}
644
645	forall(type T \| void (?create)?(T*, T))
646	void new(T const* volatile restrict* ptr, T val),
647	new(T volatile* volatile restrict* ptr, T val),
648	new(T restrict* volatile restrict* ptr, T val),
649	new(T const volatile* volatile restrict* ptr, T val),
650	new(T const restrict* volatile restrict* ptr, T val),
651	new(T volatile restrict* volatile restrict* ptr, T val),
652	new(T const volatile restrict* volatile restrict* ptr, T val);
653	</pre>
654	<p class='rationale'>Cforall can't add type qualifiers to pointed-at
655	pointer types, so <code>new()</code> needs one variation for each set of
656	type qualifiers.</p>
657
658	<p>Another <code>new()</code> function would omit the initial value, and
659	apply the default constructor. <span class='rationale'>Obviously, there's
660	no point in allocating <code>const</code>-qualified uninitialized
661	storage.</span></p>
662	<pre>
663	forall(type T)
664	void new(T* volatile restrict * ptr) {
665	*ptr = malloc(sizeof(T));
666	if (ptr) (?create)?(ptr); // <i>Explicit default constructor call.</i>
667	}
668
669	forall(type T)
670	void new(T volatile* volatile restrict*),
671	void new(T restrict* volatile restrict*),
672	void new(T volatile restrict* volatile restrict*);
673	</pre>
674
675	<h2 id='generic'>Generic Conversions and Constructors</h2>
676
677	<p>Cforall would provide a polymorphic default constructor function and
678	destructor function, for types that do not have their own:</p>
679
680	<pre>
681	forall(type T)
682	void (?create)?(T*) { return; };
683
684	forall(type T)
685	void (?destroy)?(T*) { return; };
686	</pre>
687
688	<p class='rationale'>The generic default constructor and destructor provide
689	C semantics for uninitialized variables: "do nothing".</p>
690
691	<p>For every structure type <code>struct <i>s</i></code> Cforall would define a
692	default constructor function that applies a default constructor to each
693	member, in no particular order. Similarly, it would define a destructor that
694	applies the destructor of each member in no particular order.</p>
695
696	<p>Any promotion would be treated as a plain constructor:</p>
697	<pre>
698	forall(type T, type S \| void (?promote)(T*, S))
699	void (?create)?(T*, S) {
700	(?promote)?(T*, S); // <i>Explicit constructor call!</i>
701	}
702	</pre>
703
704	<p>A predefined cast function would allow explicit conversions anywhere
705	that implicit conversions are possible:</p>
706	<pre>
707	forall(type T, type S \| void (?create)?(T*, S))
708	T (?)?(S source) {
709	T temp = source;
710	return temp;
711	}
712	</pre>
713
714	<p>A predefined converting constructor would allow initialization anywhere
715	that assignment is defined:</p>
716	<pre>
717	forall(type T \| void (?create)?(T), type S \| T ?=?(T, S))
718	void (?create)?(T* target, S source) {
719	(?create)?(target);
720	*target = source;
721	}
722	</pre>
723
724	<p class='rationale'>This implements the typical semantic link between
725	assignment and initialization.</p>
726
727	<p>The predefined copy constructor function is</p>
728	<pre>
729	forall(type T)
730	void (?promote)?(T* target, T source) {
731	(?create)?(target);
732	*target = source;
733	}
734	</pre>
735
736	<p class='rationale'>Since Cforall defines assignment and default
737	constructors for structure types, this provides the copy constructor for
738	structure types.</p>
739
740	<p>Finally, Cforall defines the conversion to <code>void</code>, which
741	discards its argument.</p>
742	<pre>
743	forall(type T) void (?promote)(void*, T);
744	</pre>
745
746	<h2 id='usual'>C's "Usual Arithmetic Conversions"</h2>
747
748	<p>C has five groups of arithmetic types: signed integers, unsigned
749	integers, complex floating-point numbers, imaginary floating-point numbers,
750	and real floating-point numbers. (Implementations are not required to
751	provide complex and imaginary types.) Some of the "usual arithmetic
752	conversions" promote upward within a group or to a more general group: from
753	<code>int</code> to <code>long long</code>, for instance. Others
754	promote across from a type in one group to a similar type in another group:
755	for instance, from <code>int</code> to <code>unsigned int</code>.</p>
756
757	<h3 id='floating'>Floating-Point Types</h3>
758
759	<p>The floating point types would use the <a href="#idiom">constructor
760	idiom</a> for upward promotions, and monomorphic constructors for
761	promotions across from real and imaginary types to complex types with the
762	same precision.</p>
763
764	<p>I will use a macro to abbreviate the constructor idiom.
765	"<code>Promoter(T,S)</code>" promotes <code>S</code> to any type that
766	<code>T</code> can be promoted to</p>
767	<pre>
768	#define Promoter(Target, Source) \
769	forall(type T \| void (?promote)?(T, Target)) void (?promote)?(T, Source)
770
771	Promoter(long double _Complex, double _Complex); // <i>a</i>
772	Promoter(double _Complex, float _Complex); // <i>b</i>
773	Promoter(long double, double); // <i>c</i>
774	Promoter(double, float); // <i>d</i>
775	Promoter(long double _Imaginary, double _Imaginary); // <i>e</i>
776	Promoter(double _Imaginary, float _Imaginary); // <i>f</i>
777
778	void (?promote)?(long double _Complex*, long double); // <i>g</i>
779	void (?promote)?(long double _Complex*, long double _Imaginary); // <i>h</i>
780	void (?promote)?(double _Complex*, double); // <i>i</i>
781	void (?promote)?(double _Complex*, double _Imaginary); // <i>j</i>
782	void (?promote)?(float _Complex*, float); // <i>k</i>
783	void (?promote)?(float _Complex*, float _Imaginary); // <i>l</i>
784	</pre>
785
786	<div class='rationale'>
787	<p>It helps to draw a graph of the promotions. In this diagram,
788	monomorphic promotions are solid arrows from the source type to the target
789	type, and polymorphic promotions are dotted arrows from the source type to
790	a bubble that surrounds all possible target types. (Twenty years after
791	first hearing about them, I have finally found a use for directed
792	multigraphs!) To determine the promotion from one type to another, find a
793	path of zero or more dotted arrows optionally ending with a solid arrow.</p>
794	<div>
795	<img alt="Floating point promotions" src="./float_promo.png">
796	</div>
797
798	<p>A <code>long double _Complex</code> can be constructed from</p>
799	<ol>
800	<li>a <code>double _Complex</code>, via <i>a</i>, with a <code>double
801	_Complex</code> copy constructor passed as the assertion
802	parameter.</li>
803	<li>a <code>long double</code>, via constructor <i>g</i>.</li>
804	<li>a <code>double</code>, via <i>c</i> (which promotes
805	<code>double</code> to <code>long double</code> and higher), with
806	<i>g</i> passed as the assertion parameter. In other words, the path
807	from <code>double</code> to <code>long double _Complex</code> passes
808	through <code>long double</code></li>
809	<li>a <code>float _Complex</code>, via <i>b</i>. For the assertion
810	parameter, Cforall passes a <code>double
811	_Complex</code>-to-<code>long double _Complex</code> constructor that
812	it makes by specializing <i>a</i>; for the assertion parameter of the
813	specialization, it passes a <code>long double
814	_Complex</code>-to-<code>long double _Complex</code> copy
815	constructor.</li>
816	<li>a <code>float</code>, via <i>d</i>, with a specialization of <i>c</i>
817	passed as its assertion parameter, with <i>g</i> passed as the
818	specialization's assertion parameter.</li>
819	</ol>
820
821	<p>Note how "upward" and "across" promotions interact. Polymorphic
822	"upward" promotions connect widely separated types by composing
823	constructors through their assertion parameters. Monomorphic "across"
824	promotions extend composition one step across to corresponding types in
825	different groups.</p>
826
827	<p>Defining the set of predefined promotions turned out to be quite tricky.
828	For example, if "across" promotions used the constructor idiom, ambiguity
829	would result: a conversion from <code>float</code> to <code>double
830	_Complex</code> could convert upward through <code>double</code> or across
831	through <code>float _Complex</code>. The key points are:</p>
832	<ol>
833	<li>Monomorphic constructors are only used to connect neighbouring types
834	in the conversion hierarchy, because they have constructor cost 1.</li>
835	<li>Polymorphic constructors only connect directly to neighbours, because
836	their minimal cost is 1. They reach other types by composition.</li>
837	<li>The types in the assertion parameter of a polymorphic constructor
838	specify the exact path between two types by specifying the
839	next type in a sequence of composed constructors.</li>
840	<li>There can be more than one path between two types, provided that the
841	paths have different construction costs or degrees of
842	polymorphism.</li>
843	</ol>
844
845	</div>
846
847	<h3 id='largeint'>Large Integer Types</h3>
848
849	<p class='rationale'>The conversions for the integer types cannot be
850	defined by a simple list, because the set of integer types is
851	implementation-defined, the range of each type is implementation-defined,
852	and the set of promotions depend on whether a particular signed type can
853	represent all values of a particular unsigned type. As I read the C
854	standard, every signed type has a matching unsigned type, but the reverse
855	is not true. This complicates the definitions below.</p>
856
857	<ul>
858	<li>Let the <dfn>rank</dfn> of an integer type be the integer conversion
859	rank defined in C99, with the added condition that the ranks form a
860	continuous sequence of integers.</li>
861	<li>Let <dfn><i>r</i><sub>int</sub></dfn> be the rank of
862	<code>int</code>.</li>
863	<li>Let <dfn><code>signed(<i>r</i>)</code></dfn> and
864	<dfn><code>unsigned(<i>r</i>)</code></dfn>
865	be the signed integer type and unsigned integer type with rank
866	<i>r</i>.</li>
867	</ul>
868
869	<p>Integers promote upward to floating-point types. Let <i>SMax</i> be the
870	highest ranking signed integer type, and let <i>UMax</i> be the highest
871	ranking unsigned integer type. Then Cforall would define</p>
872
873	<pre>
874	Promoter(float, <i>SMax</i>);
875	Promoter(float, <i>Umax</i>);
876	</pre>
877
878	<p>Signed types promote across to unsigned types with the same rank. For
879	every <i>r</i> >= <i>r</i><sub>int</sub> such that
880	<code>signed(<i>r</i>)</code> exists, Cforall would define</p>
881
882	<pre>
883	void (?promote)?( unsigned(<i>r</i>)*, signed(<i>r</i>) );
884	</pre>
885
886	<p>Lower-ranking signed integers promote to higher-ranking signed integers.
887	For every signed integer type <i>T</i> with rank greater than
888	<i>r</i><sub>int</sub>, let <i>S</i> be the signed integer type with the
889	next lowest rank. Then Cforall would define</p>
890
891	<pre>
892	Promoter(<i>T</i>, <i>S</i>);
893	</pre>
894
895	<p>Similarly, lower-ranking unsigned integers promote to higher-ranking
896	unsigned integers. For every <i>r</i> > <i>r</i><sub>int</sub>, Cforall
897	would define</p>
898
899	<pre>
900	Promoter(unsigned(<i>r</i>), unsigned(<i>r</i>-1));
901	</pre>
902
903	<p>C's usual arithmetic conversions may promote an unsigned type to a
904	signed type, but only if the signed type can represent every value of the
905	unsigned type. For every <i>r</i> >= <i>r</i><sub>int</sub>, if there
906	are any signed types that can represent every value in
907	<code>unsigned(<i>r</i>)</code>, let <i>S</i> be the
908	lowest ranking of these types; then Cforall defines</p>
909
910	<pre>
911	Promoter(<i>S</i>, unsigned(<i>r</i>));
912	</pre>
913
914	<h3 id='intpromo'>C's "Integer Promotions"</h3>
915
916	<div class='rationale'>
917
918	<p>C's <dfn>integer promotions</dfn> apply to "small" types (those with
919	rank less than <i>r</i><sub>int</sub>): they promote to <code>int</code> if
920	<code>int</code> can hold all of their values, and to <code>unsigned
921	int</code> otherwise. At least one unsigned type, <code>_Bool</code>,
922	will promote to <code>int</code>. This breaks the pattern set by the usual
923	arithmetic conversions, where unsigned types always promote to the next
924	larger unsigned type. Consider a machine with 32-bit <code>int</code>s and
925	16-bit <code>unsigned short</code>s: if two <code>unsigned short</code>s
926	are added, they must be promoted to <code>int</code> instead of
927	<code>unsigned int</code>. Hence for this machine there must <em>not</em>
928	be a promotion from <code>unsigned short</code> to <code>unsigned
929	int</code>.</p>
930
931	<p>Since the C integer promotions always promote small signed types to
932	<code>int</code>, Cforall would extend the chain of polymorphic "upward"
933	and monomorphic "across" signed integer promotions to the small
934	signed types.</p>
935	</div>
936
937	<p>For every signed integer type <i>S</i> with rank less than
938	<i>r</i><sub>int</sub>, Cforall would define</p>
939	<pre>
940	Promoter(<i>T</i>, <i>S</i>);
941	</pre>
942	<p>where <i>T</i> is the signed integer type with the next highest
943	rank.</p>
944
945	<p>Let <i>r</i><sub>break</sub> be the rank of the highest-ranking unsigned
946	type whose values can all be represented by <code>int</code>, and let
947	<i>T</i> be the lowest-ranking signed type that can represent all of the
948	values of <code>unsigned(<i>r</i><sub>break</sub>)</code>. Cforall would
949	define</p>
950
951	<pre>
952	Promoter(T, unsigned(<i>r</i><sub>break</sub>));
953	</pre>
954
955	<p>For every
956	<i>r</i> less than <i>r</i><sub>int</sub> except
957	<i>r</i><sub>break</sub>, Cforall would define</p>
958	<pre>
959	Promoter(unsigned(<i>r+1</i>), unsigned(<i>r</i>));
960	</pre>
961
962	<p class='rationale'><i>r</i><sub>break</sub> is the point where the normal
963	pattern of unsigned promotion breaks. Unsigned types with higher rank
964	promote upward toward <code>unsigned int</code>. Unsigned types with
965	lower rank promote upward to the type at the break, which promotes upward
966	to a signed type and onward toward <code>int</code>.</p>
967
968	<p>For each <i>r</i> < <i>r</i><sub>int</sub> such that
969	<code>signed(<i>r</i>)</code> exists, Cforall would define</p>
970	<pre>
971	void (?promote)?(unsigned(<i>r</i>)*, signed(<i>r</i>));
972	</pre>
973
974	<p class='rationale'>These "across" promotions are not strictly necessary,
975	but it seems useful to extend the pattern of signed-to-unsigned monomorphic
976	conversions established by the larger integer types. Note that because of
977	these promotions, <code>unsigned(<i>r</i><sub>break</sub>)</code> does
978	promote to the next larger unsigned type, after a detour through a signed
979	type that increases the conversion cost.</p>
980
981	<p>Finally, <code>char</code> is equivalent to <code>signed char</code> or
982	<code>unsigned char</code>, on an implementation-defined basis. If
983	<code>char</code> is equivalent to <code>signed char</code>, the
984	implementation would define</p>
985
986	<pre>
987	Promoter(signed char, char);
988	</pre>
989
990	<p>Otherwise, it would define</p>
991	<pre>
992	Promoter(unsigned char, char);
993	</pre>
994
995	<h2 id="otherpromo">Other Promotions</h2>
996	<p>Promotions can add qualifiers to the pointed-to type of a
997	pointer type.</p>
998	<pre>
999	forall(dtype DT) void (?promote)?(const DT*, DT);
1000	forall(dtype DT) void (?promote)?(volatile DT*, DT);
1001	forall(dtype DT) void (?promote)?(restrict DT*, DT);
1002	forall(dtype DT) void (?promote)?(const volatile DT*, DT);
1003	forall(dtype DT) void (?promote)?(const restrict DT*, DT);
1004	forall(dtype DT) void (?promote)?(volatile restrict DT*, DT);
1005	forall(dtype DT) void (?promote)?(const volatile restrict DT*, DT);
1006
1007	forall(dtype DT) void (?promote)?(const volatile DT*, const DT);
1008	forall(dtype DT) void (?promote)?(const restrict DT*, const DT);
1009	forall(dtype DT) void (?promote)?(const volatile restrict DT*, const DT);
1010
1011	forall(dtype DT) void (?promote)?(const volatile DT*, volatile DT);
1012	forall(dtype DT) void (?promote)?(volatile restrict DT*, volatile DT);
1013	forall(dtype DT) void (?promote)?(const volatile restrict DT*, volatile DT);
1014
1015	forall(dtype DT) void (?promote)?(const restrict DT*, restrict DT);
1016	forall(dtype DT) void (?promote)?(volatile restrict DT*, restrict DT);
1017	forall(dtype DT) void (?promote)?(const volatile restrict DT**, restrict
1018	DT*);
1019
1020	forall(dtype DT) void (?promote)?(const volatile restrict DT**, const volatile DT);
1021	forall(dtype DT) void (?promote)?(const volatile restrict DT**, const restrict DT);
1022	forall(dtype DT) void (?promote)?(const volatile restrict DT**, volatile restrict DT);
1023	</pre>
1024
1025	<p class='rationale'> The type qualifier promotions are simple, but verbose
1026	because Cforall doesn't abstract over type qualifiers very well. They also
1027	give <em>every</em> type qualifier promotion a cost of 1. It is possible
1028	to define a smaller set of promotions, some using the constructor idiom,
1029	that gives greater cost to promotions that add more qualifiers, but the set
1030	is arbitrary and asymmetric: only one of the three promotions that add one
1031	qualifier to an unqualified pointer type can use the constructor idiom, or
1032	else ambiguity results.</p>
1033
1034	<p>Within the scope of a type definition <code>type <i>T1</i> =
1035	<i>T2</i>;</code>, constructors would convert between the new type and its
1036	implementation type.</p>
1037
1038	<pre>
1039	void (?promote)(<i>T2</i>*, <i>T1</i>);
1040	void (?promote)(<i>T2</i>*, <i>T1</i>);
1041	void (?create)?(<i>T1</i>*, <i>T2</i>);
1042	void (?create)?(<i>T1</i>*, <i>T2</i>);
1043	</pre>
1044
1045	<p class='rationale'>The conversion from the implementation type
1046	<code><i>T2</i></code> to the new type <code><i>T1</i></code> gives
1047	functions that implement operations on <code><i>T1</i></code> access to the
1048	type's implementation. The conversion is a promotion because most such
1049	functions work with the implementation most of the time. The reverse
1050	conversion is merely implicit, so that mixed operations won't be
1051	ambiguous.</p>
1052
1053	<h2 id="demotions">Other Pre-Defined Implicit Conversions</h2>
1054	<h3>Arithmetic Conversions</h3>
1055
1056	<p class='rationale'>C defines implicit conversions between any two
1057	arithmetic types. In Cforall terms, the conversions that are not
1058	promotions are ordinary conversions. Most of the ordinary conversions
1059	follow a pattern that looks like the <a href='#usual'>Usual Arithmetic
1060	Conversions</a> in reverse. Once again, I will use a macro to hide details
1061	of the constructor idiom.</p>
1062
1063	<pre>
1064	#define Creator(Target, Source) \
1065	forall(type T \| void (?create)?(T, Target)) void (?create)?(T, Source)
1066
1067	Creator(double _Complex, long double _Complex);
1068	Creator(float _Complex, double _Complex);
1069	Creator(double, long double);
1070	Creator(float, double);
1071	Creator(double _Imaginary, long double _Imaginary);
1072	Creator(float _Imaginary, double _Imaginary);
1073
1074	void (?create)?(long double*, long double _Complex);
1075	void (?create)?(long double _Imaginary*, long double _Complex);
1076	void (?create)?(double*, double _Complex);
1077	void (?create)?(double _Imaginary*, double _Complex);
1078	void (?create)?(float*, float _Complex);
1079	void (?create)?(float _Imaginary*, float _Complex);
1080	</pre>
1081
1082	<p class='rationale'>The C99 draft standards that I have access to state
1083	that real types and imaginary types are implicitly interconvertible. This
1084	seems like a mistake, since the result of the conversion will always be
1085	zero, but ...</p>
1086
1087	<pre>
1088	void (?create)?(long double*, long double _Imaginary);
1089	void (?create)?(long double _Imaginary*, long double);
1090	void (?create)?(double*, double _Imaginary);
1091	void (?create)?(double _Imaginary*, double);
1092	void (?create)?(float*, float _Imaginary);
1093	void (?create)?(float _Imaginary*, float);
1094	</pre>
1095
1096	<p>Let <i>SMax</i> be the highest ranking signed integer type, and let
1097	<i>UMax</i> be the highest ranking unsigned integer type. Then Cforall
1098	would define</p>
1099
1100	<pre>
1101	Creator(<i>SMax</i>, float);
1102	Creator(<i>SMax</i>, float _Complex);
1103	Creator(<i>SMax</i>, float _Imaginary);
1104	Creator(<i>UMax</i>, float);
1105	Creator(<i>UMax</i>, float _Complex);
1106	Creator(<i>UMax</i>, float _Imaginary);
1107	</pre>
1108
1109	<p>For every signed integer type <i>T</i> with rank greater than that of
1110	<code>signed char</code>, Cforall would define</p>
1111
1112	<pre>
1113	Creator(<i>S</i>, <i>T</i>);
1114	</pre>
1115	<p>where <i>S</i> is the signed integer type with the next lowest rank.</p>
1116
1117	<p>For every rank <i>r</i> greater than the rank of <code>_Bool</code>,
1118	Cforall would define</p>
1119
1120	<pre>
1121	Creator(unsigned(<i>r</i>-1), unsigned(<i>r</i>));
1122	</pre>
1123
1124	<p>For every rank <i>r</i> such that <code>signed(<i>r</i>)</code> exists,
1125	Cforall would define</p>
1126
1127	<pre>
1128	void (?create)?( signed(<i>r</i>)*, unsigned(<i>r</i>) );
1129	</pre>
1130
1131	<p><code>char</code> and <code>_Bool</code> are interconvertible.</p>
1132	<pre>
1133	void (?create)?(char*, _Bool);
1134	void (?create)?(_Bool*, char);
1135	</pre>
1136
1137	<p>If <code>char</code> is equivalent to <code>signed char</code>, the
1138	implementation would define</p>
1139
1140	<pre>
1141	Creator(char, signed char);
1142	void (?create)?(char*, unsigned char);
1143	</pre>
1144
1145	<p>Otherwise, the implementation would define</p>
1146	<pre>
1147	Creator(char, unsigned char);
1148	void (?create)?(char*, signed char);
1149	void (?create)?(_Bool*, signed char);
1150	void (?create)?(signed char*, _Bool);
1151	</pre>
1152
1153	<h3>Pointer conversions</h3>
1154
1155	<p>Pointer types are implicitly interconvertible with pointers to void,
1156	provided that the target type has all of the qualifiers of the source
1157	type.</p>
1158
1159	<pre>
1160	forall(dtype SourceType,
1161	type QVPtr \| void (?promote)?(QVPtr, void))
1162	void (?create)?(QVPtr, SourceType);
1163	</pre>
1164
1165	<p class='rationale'>This conversion uses the constructor idiom, but note
1166	that the assertion parameter is a promotion even though the conversion
1167	itself is not a promotion. My intent is that the assertion parameter will
1168	be bound to a promotion that adds <a href='#otherpromo'>type qualifiers</a>
1169	to a pointer type. A conversion from <code>int*</code> to <code>const
1170	void*</code> would bind <code>SourceType</code> to <code>int</code>,
1171	<code>QVPtr</code> to <code>const void*</code>, and the assertion parameter
1172	to a promotion from <code>void</code> to <code>const void</code> (which
1173	is a specialization of one of the polymorphic type qualifier promotions
1174	given above). Because of this composition of pointer conversions, I don't
1175	have to define conversions for every combination of type qualifiers on the
1176	target type. I do have to handle all combinations of qualifiers on the
1177	source type:</p>
1178
1179	<pre>
1180	forall(dtype SourceType,
1181	type QVPtr \| void (?promote)?(QVPtr, const void))
1182	void (?create)?(QVPtr, const SourceType);
1183	forall(dtype SourceType,
1184	type QVPtr \| void (?promote)?(QVPtr, volatile void))
1185	void (?create)?(QVPtr, volatile SourceType);
1186	forall(dtype SourceType,
1187	type QVPtr \| void (?promote)?(QVPtr, restrict void))
1188	void (?create)?(QVPtr, restrict SourceType);
1189	forall(dtype SourceType,
1190	type QVPtr \| void (?promote)?(QVPtr, const volatile void))
1191	void (?create)?(QVPtr, const volatile SourceType);
1192	forall(dtype SourceType,
1193	type QVPtr \| void (?promote)?(QVPtr, const restrict void))
1194	void (?create)?(QVPtr, const restrict SourceType);
1195	forall(dtype SourceType,
1196	type QVPtr \| void (?promote)?(QVPtr, volatile restrict void))
1197	void (?create)?(QVPtr, volatile restrict SourceType);
1198	forall(dtype SourceType,
1199	type QVPtr \| void (?promote)?(QVPtr, const volatile restrict void))
1200	void (?create)?(QVPtr, const volatile restrict SourceType);
1201
1202	forall(type QTPtr,
1203	dtype TargetType \| void (?promote)?(QTPtr, TargetType)
1204	void (?create)?(QTPtr, void);
1205	forall(type QTPtr,
1206	dtype TargetType \| void (?promote)?(QTPtr, const TargetType)
1207	void (?create)?(QTPtr, const void);
1208	forall(type QTPtr,
1209	dtype TargetType \| void (?promote)?(QTPtr, volatile TargetType)
1210	void (?create)?(QTPtr, volatile void);
1211	forall(type QTPtr,
1212	dtype TargetType \| void (?promote)?(QTPtr, restrict TargetType)
1213	void (?create)?(QTPtr, restrict void);
1214	forall(type QTPtr,
1215	dtype TargetType \| void (?promote)?(QTPtr, const volatile TargetType)
1216	void (?create)?(QTPtr, const volatile void);
1217	forall(type QTPtr,
1218	dtype TargetType \| void (?promote)?(QTPtr, const restrict TargetType)
1219	void (?create)?(QTPtr, const restrict void);
1220	forall(type QTPtr,
1221	dtype TargetType \| void (?promote)?(QTPtr, volatile restrict TargetType)
1222	void (?create)?(QTPtr, volatile restrict void);
1223	forall(type QTPtr,
1224	dtype TargetType \| void (?promote)?(QTPtr, const volatile restrict TargetType)
1225	void (?create)?(QTPtr, const volatile restrict void);
1226	</pre>
1227
1228	<h2 id="explicit">Pre-Defined Explicit Conversions</h2>
1229	<p>Function pointers are interconvertible.</p>
1230	<pre>
1231	forall(ftype FT1, ftype FT2, type T \| FT1* (?)?(T) ) FT2* (?)?(FT1*);
1232	</pre>
1233
1234	<p>Data pointers including pointers to <code>void</code> are
1235	interconvertible, regardless of type qualifiers.</p>
1236
1237	<pre>
1238	forall(dtype DT1, dtype DT2) DT2* (?)?(DT1*);
1239	forall(dtype DT1, dtype DT2) const DT2* (?)?(DT1*);
1240	forall(dtype DT1, dtype DT2) volatile DT2* (?)?(DT1*);
1241	forall(dtype DT1, dtype DT2) const volatile DT2* (?)?(DT1*);
1242
1243	forall(dtype DT1, dtype DT2) DT2* (?)?(const DT1*);
1244	forall(dtype DT1, dtype DT2) const DT2* (?)?(const DT1*);
1245	forall(dtype DT1, dtype DT2) volatile DT2* (?)?(const DT1*);
1246	forall(dtype DT1, dtype DT2) const volatile DT2* (?)?(const DT1*);
1247
1248	forall(dtype DT1, dtype DT2) DT2* (?)?(volatile DT*);
1249	forall(dtype DT1, dtype DT2) const DT2* (?)?(volatile DT*);
1250	forall(dtype DT1, dtype DT2) volatile DT2* (?)?(volatile DT*);
1251	forall(dtype DT1, dtype DT2) const volatile DT2* (?)?(volatile DT*);
1252
1253	forall(dtype DT1, dtype DT2) DT2* (?)?(const volatile DT*);
1254	forall(dtype DT1, dtype DT2) const DT2* (?)?(const volatile DT*);
1255	forall(dtype DT1, dtype DT2) volatile DT2* (?)?(const volatile DT*);
1256	forall(dtype DT1, dtype DT2) const volatile DT2* (?)?(const volatile DT*);
1257	</pre>
1258
1259	<p>Integers and pointers are interconvertible. For every integer type
1260	<i>I</i> define</p>
1261	<pre>
1262	forall(dtype DT, type T \| <i>I</i> (?)?(T) ) DT* ?(?)(T);
1263	forall(ftype FT, type T \| <i>I</i> (?)?(T) ) FT* ?(?)(T);
1264
1265	forall(dtype DT, type T \| DT* (?)?(T) ) <i>I</i> (?)?(T);
1266	forall(dtype DT, type T \| DT* (?)?(T) ) <i>I</i> (?)?(T);
1267	</pre>
1268
1269	<h2 id='nonconversions'>Non-Conversions</h2>
1270	<p>C99 has a few other "conversions" that don't fit into this proposal.
1271	Outside of some special circumstances (such as application of
1272	<code>sizeof</code>),</p>
1273	<ul>
1274	<li>array lvalues "convert" to pointers</li>
1275	<li>function designators "convert" to pointers to functions</li>
1276	<li>non-array lvalues "convert" to plain values</li>
1277	<li>bit fields undergo "integer promotion" to <code>int</code> or
1278	<code>unsigned int</code> values.</li>
1279	</ul>
1280
1281	<p>I'd like to stop calling these "conversions". Perhaps they could be
1282	handled by some verbiage in the semantics of "Primary Expressions".</p>
1283
1284	<p>Cforall-as-is provides "specialization", which reduces the number of
1285	type parameters or assertion parameters of a polymorphic object or
1286	function. Specialization looks like a conversion -- it can happen
1287	implicitly or as a result of a cast -- but would no longer be considered to
1288	be a conversion.</p>
1289
1290	<h2 id='assignment'>Assignment</h2>
1291
1292	<p>Since extended Cforall separates conversion from assignment, it can
1293	simplify Cforall-as-is's set of assignment operators. Implicit conversions
1294	can add type qualifiers to the target's type, and to the source's type in
1295	the case of pointer assignment.</p>
1296
1297	<pre>
1298	char ?=?(volatile char*, char);
1299	char ?+=?(volatile char*, char);
1300	// <i>... and similarly for the rest of the basic types and</i>
1301	// <i>compound assignment operators.</i>
1302	</pre>
1303	<pre class='rationale'>
1304	char c;
1305	c = 'a'; // <i>=> ?=?( &c, 'a' );</i>
1306	// <i>=> ?=?( (volatile char*)&c, 'a' );</i>
1307	</pre>
1308
1309	<pre>
1310	// <i>Assignment between data pointers, where the target has all of</i>
1311	// <i>the qualifiers of the source.</i>
1312	forall(dtype DT)
1313	DT* ?=?(DT* volatile restrict, DT);
1314	forall(dtype DT)
1315	const DT* ?=?(const DT* volatile restrict, const DT);
1316	forall(dtype DT)
1317	volatile DT* ?=?(volatile DT* volatile restrict, volatile DT);
1318	forall(dtype DT)
1319	const volatile DT* ?=?(const volatile DT* volatile restrict, const volatile DT);
1320
1321	// <i>Assignment to data pointers from </i>void<i>pointers.</i>
1322	forall(dtype DT) DT* ?=?(DT* volatile restrict, void)
1323	forall(dtype DT)
1324	const DT* ?=?(const DT* volatile restrict, const void);
1325	forall(dtype DT)
1326	volatile DT* ?=?(volatile DT* volatile restrict, volatile void);
1327	forall(dtype DT)
1328	const volatile DT* ?=?(const volatile DT* volatile restrict, const volatile void);
1329
1330	// <i>Assignment to </i>void<i> pointers from data pointers.</i>
1331	forall(dtype DT)
1332	void* ?=?(void* volatile restrict, DT);
1333	forall(dtype DT)
1334	const void* ?=?(const void* volatile restrict, const DT);
1335	forall(dtype DT)
1336	volatile void* ?=?(volatile void* volatile restrict, volatile DT);
1337	forall(dtype DT)
1338	const volatile void* ?=?(const volatile void* volatile restrict, const volatile DT);
1339
1340	// <i>Assignment from null pointers to other pointer types.</i>
1341	forall(dtype DT)
1342	void* ?=?(void* volatile restrict, forall(dtype DT2) const DT2);
1343	forall(dtype DT)
1344	const void* ?=?(const void* volatile restrict, forall(dtype DT2) const DT2);
1345	forall(dtype DT)
1346	volatile void* ?=?(volatile void* volatile restrict, forall(dtype DT2) const DT2);
1347	forall(dtype DT)
1348	const volatile void* ?=?(const volatile void* volatile restrict, forall(dtype DT2) const DT2);
1349
1350	// <i>Function pointer assignment</i>
1351	forall(ftype FT) FT* ?=?(FT* volatile restrict, FT);
1352	forall(ftype FT) FT* ?=?(FT* volatile restrict, forall(ftype FT2) FT2);
1353	</pre>
1354
1355	<div class='rationale'>
1356
1357	<p>The difference, relative to Cforall-as-is, is that assignment operators
1358	come in one flavor (a pointer to a volatile value as the first operand)
1359	instead of two (a pointer to volatile in one case, a plain pointer in the
1360	other) or the four that <code>restrict</code> would have led to.</p>
1361
1362	<p>However, to make this work, the type of <dfn>default assignment</dfn>
1363	functions must also change. A declaration of a type <code>T</code> would
1364	implicitly declare</p> <pre> T ?=?(T volatile restrict*, T) </pre> </div>
1365
1366	<h2 id='final'>Final Notes</h2>
1367
1368	<p>The <a href='#idiom'>constructor idiom</a> is polymorphic in the
1369	object's type: an initial value of one particular type can initialize
1370	objects of many types. The constructor that promotes a <code>Wazzit</code>
1371	into a <code>Thingum</code> is declared</p>
1372
1373	<pre>
1374	forall(type T \| void (?promote)?(T*, Thingum) )
1375	void (?promote)?(T*, Wazzit);
1376	</pre>
1377	<p>("You can make a <code>Wazzit</code> into a <code>Thingum</code> and
1378	types higher in the hierarchy.")</p>
1379
1380	<p>It would also be possible to use a constructor idiom where the object's
1381	type is fixed and the initial value's type is polymorphic:</p>
1382
1383	<pre>
1384	forall(type T \| void (?promote)?(Wazzit*, T) )
1385	void (?promote)?(Thingum*, T);
1386	</pre>
1387	<p>("You can make a <code>Thingum</code> from a <code>Wazzit</code> and
1388	types lower in the hierarchy.")</p>
1389
1390	<p>The "polymorphic value" idiom has the advantage that it is fairly
1391	obvious that the function is a constructor for type <code>Thingum</code>.
1392	In the "polymorphic object" idiom, <code>Thingum</code> is buried in the
1393	assertion parameter.</p>
1394
1395	<p>However, I chose the "polymorphic object" idiom because it matches C's
1396	semantics for signed-to-unsigned integer conversions. In the "polymorphic
1397	object" idiom, the natural way to write the polymorphic promoter from
1398	<code>int</code> to larger types is
1399	</p>
1400
1401	<pre>
1402	forall(type T \| void (?promote)?(T*, long) )
1403	void (?promote)?(T* tp, int i) {
1404	long l = i;
1405	*tp = (T)l; // <i>calls the assertion parameter.</i>
1406	}
1407	</pre>
1408
1409	<p>Now consider the case of a CPU with 16-bit <code>int</code>s, where we
1410	need to convert an <code>int</code> value <code>-1</code> to a 32-bit
1411	<code>unsigned long</code>. The assertion parameter will be bound to the
1412	monomorphic <code>long</code>-to-<code>unsigned long</code> promoter. The
1413	function body above converts the <code>int</code> -1 to a <code>long</code>
1414	-1, and then uses the assertion parameter to convert the result to the
1415	correct <code>unsigned long</code> value: 4,294,967,295.</p>
1416
1417	<p>In the "polymorphic value" idiom, the conversion would be done by
1418	calling the polymorphic promoter to <code>unsigned long</code> from smaller
1419	types:</p>
1420
1421	<pre>
1422	forall(type T \| void (?promote)?(unsigned*, T) )
1423	void (?promote)?(unsigned long* ulp, T t) {
1424	unsigned u = t; // <i>calls the assertion parameter.</i>
1425	*ulp = u;
1426	}
1427	</pre>
1428
1429	<p>This time the assertion parameter will be bound to the
1430	<code>int</code>-to-<code>unsigned</code> promoter. The function body uses
1431	the assertion parameter to convert the integer -1 to <code>unsigned</code>
1432	65,565, and then converts the result to the incorrect <code>unsigned
1433	long</code> value 65,535.</p>
1434
1435	<p>Clearly the "polymorphic value" idiom would require the implementation
1436	to do some unnatural, and probably implementation-dependent, bit mangling
1437	to get the right answer. Of course, an implementation is allowed to
1438	perform any unnatural acts it chooses. But programmers would have to
1439	conform to the prevailing constructor idiom when writing their
1440	constructors, and will want to write natural and portable code.</p>
1441
1442	<!--
1443	Multi-argument constructors and {...} notation. Default and keyword
1444	parameters?
1445
1446	mutable.
1447
1448	Automating implementation-dependent promotion, so new types can fit in
1449	easily.
1450
1451	Cast has no cost; implicit construction does.
1452
1453	Allow instantiation of dtype/incomplete type if the type has a constructor?
1454	The problem is space allocation: constructors would have to allocate space,
1455	which would interfere with their use in dynamic allocation.
1456
1457	generic function that treates promoters as creators might cause loops when
1458	chaining creators.
1459
1460	-->
1461	</body>
1462	</html>

Note: See TracBrowser for help on using the repository browser.

Download in other formats: