From: David Barrett-Lennard on
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
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