source: doc/proposals/ @ 41634098

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

Added white paper on user-defined conversions based on resolver design doc

  • Property mode set to 100644
File size: 11.3 KB
1## User-defined Conversions ##
2C's implicit "usual arithmetic conversions" define a structure among the
3built-in types consisting of _unsafe_ narrowing conversions and a hierarchy of
4_safe_ widening conversions.
5There is also a set of _explicit_ conversions that are only allowed through a
6cast expression.
7Based on Glen's notes on conversions [1], I propose that safe and unsafe
8conversions be expressed as constructor variants, though I make explicit
9(cast) conversions a constructor variant as well rather than a dedicated
11Throughout this article, I will use the following operator names for
12constructors and conversion functions from `From` to `To`:
14        void ?{} ( To*, To );            // copy constructor
15        void ?{} ( To*, From );          // explicit constructor
16        void ?{explicit} ( To*, From );  // explicit cast conversion
17        void ?{safe} ( To*, From );      // implicit safe conversion
18        void ?{unsafe} ( To*, From );    // implicit unsafe conversion
22Glen's design made no distinction between constructors and unsafe implicit
23conversions; this is elegant, but interacts poorly with tuples.
24Essentially, without making this distinction, a constructor like the following
25would add an interpretation of any two `int`s as a `Coord`, needlessly
26multiplying the space of possible interpretations of all functions:
28        void ?{}( Coord *this, int x, int y );
30That said, it would certainly be possible to make a multiple-argument implicit
31conversion, as below, though the argument above suggests this option should be
32used infrequently:
34        void ?{unsafe}( Coord *this, int x, int y );
36An alternate possibility would be to only count two-arg constructors
37`void ?{} ( To*, From )` as unsafe conversions; under this semantics, safe and
38explicit conversions should also have a compiler-enforced restriction to
39ensure that they are two-arg functions (this restriction may be valuable
42Regardless of syntax, there should be a type assertion that expresses `From` 
43is convertable to `To`.
44If user-defined conversions are not added to the language,
45`void ?{} ( To*, From )` may be a suitable representation, relying on
46conversions on the argument types to account for transitivity.
47On the other hand, `To*` should perhaps match its target type exactly, so
48another assertion syntax specific to conversions may be required, e.g.
49`From -> To`.
51### Constructor Idiom ###
52Basing our notion of conversions off otherwise normal Cforall functions means
53that we can use the full range of Cforall features for conversions, including
55Glen [1] defines a _constructor idiom_ that can be used to create chains of
56safe conversions without duplicating code; given a type `Safe` which members
57of another type `From` can be directly converted to, the constructor idiom
58allows us to write a conversion for any type `To` which `Safe` converts to:
60        forall(otype To | { void ?{safe}( To*, Safe ) })
61        void ?{safe}( To *this, From that ) {
62                Safe tmp = /* some expression involving that */;
63                *this = tmp; // uses assertion parameter
64        }
66This idiom can also be used with only minor variations for a parallel set of
67unsafe conversions.
69What selective non-use of the constructor idiom gives us is the ability to
70define a conversion that may only be the *last* conversion in a chain of such.
71Constructing a conversion graph able to unambiguously represent the full
72hierarchy of implicit conversions in C is provably impossible using only
73single-step conversions with no additional information (see Appendix A), but
74this mechanism is sufficiently powerful (see [1], though the design there has
75some minor bugs; the general idea is to use the constructor idiom to define
76two chains of conversions, one among the signed integral types, another among
77the unsigned, and to use monomorphic conversions to allow conversions between
78signed and unsigned integer types).
80### Appendix A: Partial and Total Orders ###
81The `<=` relation on integers is a commonly known _total order_, and
82intuitions based on how it works generally apply well to other total orders.
83Formally, a total order is some binary relation `<=` over a set `S` such that
84for any two members `a` and `b` of `S`, `a <= b` or `b <= a` (if both, `a` and
85`b` must be equal, the _antisymmetry_ property); total orders also have a
86_transitivity_ property, that if `a <= b` and `b <= c`, then `a <= c`.
87If `a` and `b` are distinct elements and `a <= b`, we may write `a < b`.
89A _partial order_ is a generalization of this concept where the `<=` relation
90is not required to be defined over all pairs of elements in `S` (though there
91is a _reflexivity_ requirement that for all `a` in `S`, `a <= a`); in other
92words, it is possible for two elements `a` and `b` of `S` to be
93_incomparable_, unable to be ordered with respect to one another (any `a` and
94`b` for which either `a <= b` or `b <= a` are called _comparable_).
95Antisymmetry and transitivity are also required for a partial order, so all
96total orders are also partial orders by definition.
97One fairly natural partial order is the "subset of" relation over sets from
98the same universe; `{ }` is a subset of both `{ 1 }` and `{ 2 }`, which are
99both subsets of `{ 1, 2 }`, but neither `{ 1 }` nor `{ 2 }` is a subset of the
100other - they are incomparable under this relation.
102We can compose two (or more) partial orders to produce a new partial order on
103tuples drawn from both (or all the) sets.
104For example, given `a` and `c` from set `S` and `b` and `d` from set `R`,
105where both `S` and `R` both have partial orders defined on them, we can define
106a ordering relation between `(a, b)` and `(c, d)`.
107One common order is the _lexicographical order_, where `(a, b) <= (c, d)` iff
108`a < c` or both `a = c` and `b <= d`; this can be thought of as ordering by
109the first set and "breaking ties" by the second set.
110Another common order is the _product order_, which can be roughly thought of
111as "all the components are ordered the same way"; formally `(a, b) <= (c, d)` 
112iff `a <= c` and `b <= d`.
113One difference between the lexicographical order and the product order is that
114in the lexicographical order if both `a` and `c` and `b` and `d` are
115comparable then `(a, b)` and `(c, d)` will be comparable, while in the product
116order you can have `a <= c` and `d <= b` (both comparable) which will make
117`(a, b)` and `(c, d)` incomparable.
118The product order, on the other hand, has the benefit of not prioritizing one
119order over the other.
121Any partial order has a natural representation as a directed acyclic graph
123Each element `a` of the set becomes a node of the DAG, with an arc pointing to
124its _covering_ elements, any element `b` such that `a < b` but where there is
125no `c` such that `a < c` and `c < b`.
126Intuitively, the covering elements are the "next ones larger", where you can't
127fit another element between the two.
128Under this construction, `a < b` is equivalent to "there is a path from `a` to
129`b` in the DAG", and the lack of cycles in the directed graph is ensured by
130the antisymmetry property of the partial order.
132Partial orders can be generalized to _preorders_ by removing the antisymmetry
134In a preorder the relation is generally called `<~`, and it is possible for
135two distict elements `a` and `b` to have `a <~ b` and `b <~ a` - in this case
136we write `a ~ b`; `a <~ b` and not `a ~ b` is written `a < b`.
137Preorders may also be represented as directed graphs, but in this case the
138graph may contain cycles.
140### Appendix B: Building a Conversion Graph from Un-annotated Single Steps ###
141The short answer is that it's impossible.
143The longer answer is that it has to do with what's essentially a diamond
144inheritance problem.
145In C, `int` converts to `unsigned int` and also `long` "safely"; both convert
146to `unsigned long` safely, and it's possible to chain the conversions to
147convert `int` to `unsigned long`.
148There are two constraints here; one is that the `int` to `unsigned long` 
149conversion needs to cost more than the other two (because the types aren't as
150"close" in a very intuitive fashion), and the other is that the system needs a
151way to choose which path to take to get to the destination type.
152Now, a fairly natural solution for this would be to just say "C knows how to
153convert from `int` to `unsigned long`, so we just put in a direct conversion
154and make the compiler smart enough to figure out the costs" - this is the
155approach taken by the existing compipler, but given that in a user-defined
156conversion proposal the users can build an arbitrary graph of conversions,
157this case still needs to be handled.
159We can define a preorder over the types by saying that `a <~ b` if there
160exists a chain of conversions from `a` to `b` (see Appendix A for description
161of preorders and related constructs).
162This preorder corresponds roughly to a more usual type-theoretic concept of
163subtyping ("if I can convert `a` to `b`, `a` is a more specific type than
164`b`"); however, since this graph is arbitrary, it may contain cycles, so if
165there is also a path to convert `b` to `a` they are in some sense equivalently
168Now, to compare the cost of two conversion chains `(s, x1, x2, ... xn)` and
169`(s, y1, y2, ... ym)`, we have both the length of the chains (`n` versus `m`)
170and this conversion preorder over the destination types `xn` and `ym`.
171We could define a preorder by taking chain length and breaking ties by the
172conversion preorder, but this would lead to unexpected behaviour when closing
173diamonds with an arm length of longer than 1.
174Consider a set of types `A`, `B1`, `B2`, `C` with the arcs `A->B1`, `B1->B2`,
175`B2->C`, and `A->C`.
176If we are comparing conversions from `A` to both `B2` and `C`, we expect the
177conversion to `B2` to be chosen because it's the more specific type under the
178conversion preorder, but since its chain length is longer than the conversion
179to `C`, it loses and `C` is chosen.
180However, taking the conversion preorder and breaking ties or ambiguities by
181chain length also doesn't work, because of cases like the following example
182where the transitivity property is broken and we can't find a global maximum:
184        `X->Y1->Y2`, `X->Z1->Z2->Z3->W`, `X->W`
186In this set of arcs, if we're comparing conversions from `X` to each of `Y2`,
187`Z3` and `W`, converting to `Y2` is cheaper than converting to `Z3`, because
188there are no conversions between `Y2` and `Z3`, and `Y2` has the shorter chain
190Also, comparing conversions from `X` to `Z3` and to `W`, we find that the
191conversion to `Z3` is cheaper, because `Z3 < W` by the conversion preorder,
192and so is considered to be the nearer type.
193By transitivity, then, the conversion from `X` to `Y2` should be cheaper than
194the conversion from `X` to `W`, but in this case the `X` and `W` are
195incomparable by the conversion preorder, so the tie is broken by the shorter
196path from `X` to `W` in favour of `W`, contradicting the transitivity property
197for this proposed order.
199Without transitivity, we would need to compare all pairs of conversions, which
200would be expensive, and possibly not yield a minimal-cost conversion even if
201all pairs were comparable.
202In short, this ordering is infeasible, and by extension I believe any ordering
203composed solely of single-step conversions between types with no further
204user-supplied information will be insufficiently powerful to express the
205built-in conversions between C's types.
Note: See TracBrowser for help on using the repository browser.