Context Navigation

index.html@ e018546

Visit:

ADT ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum

Last change on this file since e018546 was 6eb131c, checked in by Aaron Moss <a3moss@…>, 7 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

Rev	Line
[6eb131c]	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.

Context Navigation

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

Download in other formats: