Covariant out parameters with subtype=subset
in [OOP]
|
Prev: CGVCVIP 2010: 1st call extension – until 24 May 2010
Next: CFP International Conference WWW/Internet 2010: submissions until 28 May 2010
From: David Barrett-Lennard on 6 May 2010 04:55 This is in response to the following exchange in a thread about 2 months ago: On Mar 3, 5:58 pm, "Dmitry A. Kazakov" <mail...(a)dmitry-kazakov.de> wrote: > On Tue, 2 Mar 2010 16:34:40 -0800 (PST), Nilone wrote: > > >> So considering the notorious real vs. complex > >> example, yes, real can be viewed as a subset of complex, but that does not > >> make it a subtype of in the Liskov sense. sqrt(-1) proves that. > > > There's no problem is the data model I'm advocating. If you have > > sqrt :: complex -> complex, and real <: complex, then sqrt :: real -> > > complex is implied. Similarly, sin :: real -> real implies sin :: int > > -> real but also sin :: real -> complex. > > No, it does not work. Enforcing contravariant results is not a solution. If > you did that, you would break other operations like +, -. Those need to be > covariant in the results. I agree, but interestingly it can be made to work in C++ by using implicit conversions whenever a subtype=subset relationship exists between two data types. Let data type = set of values + operators on those values subtype of data type = subset of values + superset of operators The subtype "inherits" all operators from its supertype, with contravariant out parameters. However, it turns out that C++ treats free functions that require implicit conversions on their in parameters as losers for the purpose of overload resolution, making it easy for the subtype to provide an "override". This allows an out parameter to be made covariant if that is sensible. It also allows for a subtype to provide a more efficient implementation. We have: real <: complex (implicit conversion) complex + complex --> complex real + real --> real So even though real + real ---> complex appears to be available by implicit conversion from real value to complex value, the specialisation of binary + for reals is the "winner" according to the overload resolution rules in C++. BTW I would say that inheriting contravariant results is very useful. Just be prepared to avoid overloading operators with distinct meanings. E.g. integers inherit rational valued multiplicative inverses from the supertype rationals if we distinguish between exact division on rationals and integer division which discards the remainder. No one would question that these are *different* operators. E.g. 5/2 = 2.5 whereas 5 div 2 = 2. As another example, polynomials on the reals inherit complex valued roots. The restriction to real valued roots is a different function and it would be reasonable to give it a different name. Doing so avoids confusion and mistakes. I suggest it helps rather than hinders the writing of generic algorithms. A tricky example is whether to overload '+' for modulo arithmetic operators. Let Zn stand for the type for {0,...,n-1} and supporting modulo n arithmetic. Then Zn <: Zm whenever n <= m as long as we are prepared for Zn to inherit the Zm operators with contravariant out parameters. In this case making the out parameters covariant is not permitted. We can deal with this issue in two ways. One way is to recognise that modulo + can be regarded as a ternary operator. E.g. moduloplus(x,y,n) = x + y (mod n). Another way is to overload + and understand the pitfalls of doing so. For example, Zn may hide + operator inherited from Zm and replace it with something else. It is worth being careful here. E.g. many bugs occur in C/C++ because of this sort of confusion. E.g. unsigned int x = 10; assert(x-20 < 0); // oops. modulo arithmetic! The deeper issue here is that we typically write programs using integer types with a finite representation and pretend/assume/know that integer arithmetic never overflows in that application. So really I think a language should allow one to express idealised algorithms which only explicitly use modulo arithmetic operators in those comparatively rare circumstances where they are logically necessary. That would allow the + symbol to be reserved for the normal addition operator on the integers (the very same one inherited from the supertype lineage of rational, real and complex). See the recent thread "Implicit conversions for value subtyping" on comp.lang.c++.moderated for further discussion. E.g. I talk about how modern C++ compilers manage to generate optimal code in certain cases. There is also some discussion about limitations of C++ for doing this.
From: Dmitry A. Kazakov on 7 May 2010 08:14
On Thu, 6 May 2010 01:55:04 -0700 (PDT), David Barrett-Lennard wrote: > On Mar 3, 5:58 pm, "Dmitry A. Kazakov" <mail...(a)dmitry-kazakov.de> > wrote: >> On Tue, 2 Mar 2010 16:34:40 -0800 (PST), Nilone wrote: >> >>>> So considering the notorious real vs. complex >>>> example, yes, real can be viewed as a subset of complex, but that does not >>>> make it a subtype of in the Liskov sense. sqrt(-1) proves that. >> >>> There's no problem is the data model I'm advocating. If you have >>> sqrt :: complex -> complex, and real <: complex, then sqrt :: real -> >>> complex is implied. Similarly, sin :: real -> real implies sin :: int >>> -> real but also sin :: real -> complex. >> >> No, it does not work. Enforcing contravariant results is not a solution. If >> you did that, you would break other operations like +, -. Those need to be >> covariant in the results. > > I agree, but interestingly it can be made to work in C++ by using > implicit conversions whenever a subtype=subset relationship exists > between two data types. Yes, C++ is pretty close to have interface implementation from concrete types. > Let > > data type = set of values + operators on those values > subtype of data type = subset of values + superset of operators Constrained subtype would be a better word. > BTW I would say that inheriting contravariant results is very useful. If inherited then not contravariant. The preference rules C++ uses for conversions are equivalent to overriding. In some sense it is in fact covariant, though poorly implemented. > Just be prepared to avoid overloading operators with distinct > meanings. E.g. integers inherit rational valued multiplicative > inverses from the supertype rationals if we distinguish between exact > division on rationals and integer division which discards the > remainder. No one would question that these are *different* > operators. E.g. 5/2 = 2.5 whereas 5 div 2 = 2. As another example, > polynomials on the reals inherit complex valued roots. There are other cases of specialization where an operation gets lost completely (e.g. Positive vs. Integer loses inverse), or partially Natural vs. Integer loses inverse everywhere except in 0, etc. There is no common rule. > Then Zn <: Zm whenever n <= m as long as we are > prepared for Zn to inherit the Zm operators with contravariant out > parameters. Why should anybody wanted this? Yes C had a design flaw allowing unsigned short to be implicitly converted to unsigned. But that is C's problem of not being strongly typed. > E.g. > > unsigned int x = 10; > assert(x-20 < 0); // oops. modulo arithmetic! Ring just does not have transitive "<", the above should be illegal. > The deeper issue here is that we typically write programs using > integer types with a finite representation and pretend/assume/know > that integer arithmetic never overflows in that application. No, that maybe is typical for a language like C++, which does not have user-defined integer types, but not universally. > So > really I think a language should allow one to express idealised > algorithms which only explicitly use modulo arithmetic operators in > those comparatively rare circumstances where they are logically > necessary. These are not rare. The typical use of a modular integer is to index a ring buffer. Modular integers (commutative ring) are as good as Z or any other mathematical structure. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |