Castable is uninhabitable

[RossTate]

shared interface Castable<in Types> {
    doc "Cast this object to the given type."
    shared formal CastValue castTo<CastValue>()
            given CastValue satisfies Types;
}

Suppose x inhabits Castable<T> for some T. Then x.castTo<Bottom>() (valid because Bottom satisfies T) constructs a Bottom, which is impossible. Thus no such x can exist.

In particular, saying that Integer and such satisfies Castable means the type system is unsound.

[gavinking]

You can just return bottom in that case, no? i.e. throw an exception. To me something which promises to return a Bottom means that it causes an exception...

[RossTate]

Sorry, I forgot about errors. Here's my refinement:

It is impossible to implement Castable without castTo always throwing an exception or castTo doing reflection on the type parameter CastValue.

[gavinking]

Castable has only a very special technical use for numeric widening conversions of user-defined numeric types. It's not meant for any kind of general-purpose usage.

And it's not reflection, because the compiler does it at compile time.

UPDATE: sorry, this was a comment I was trying to post before I got disconnected. I agree that castTo() does reflection.

[gavinking]

It is impossible to implement Castable without castTo always throwing an exception or castTo doing reflection on the type parameter CastValue.

Agreed.

(We can do this because we'll have reified generics.)

[RossTate]

And it's not reflection, because the compiler does it at compile time.

So if I do the following the compiler will inline all the polymorphism?

Iterator<R> zipProduct<M,N,R>(variable Iterator<M> lefts, variable Iterator<N> rights)
        where M satisfies Castable<R>,
              N satisfies Castable<R>,
              R of M|N satisfies Numeric<R> {
    while ((more (left, lefts), more (right, rights)) = (lefts, rights)) {
        yield left.castTo<R>() * right.castTo<R>();
    }
}

[gavinking]

And it's not reflection, because the compiler does it at compile time. UPDATE: sorry, this was a comment I was trying to post before I got disconnected. I agree that castTo() does reflection.

Ross, I misunderstood your original point, which is why I posted the "UPDATE". There's two purposes to Castable:

1. to encode into the type of the concrete numeric class the types to which it can be widened, letting the compiler figure out if one of the types can be widened to the other type, and correctly choose the wider of the two types, and
2. to provide the castTo() method where the numeric object can actually widen itself.

The hard bit is (1). I'm not sure if you can even easily solve (1) with multimethods in a statically typed language. Well, perhaps you can, but we don't have 'em. What I was saying is that none of this is reflective, the compiler figures out statically how to solve a set of type constraints and find the wider type, or, if not possible, gives an error.

The easy bit is (2). Yes, ok, it's "reflection" in the narrow technical sense that the argument to castTo() is a type. But in fact it's actually only going to use this type as an enum value to switch on, it's not going to go using the type as a metamodel or calling any operations reflectively or anything like that. All invocations are totally static calls. So I would not really have used the word "reflection" for this. Which is why I misunderstood your comment at first. I thought you were thinking about (1).

[RossTate]

I guess the main issue is that you're suggesting these things can be done polymorphically, but if you try to be clever and actually do so you're producing code you don't realize is really inefficient because it's doing reflection (which I understand to mean whenever code examines a type). So, in reality, such polymorphism is to be discouraged.

Accepting that polymorphism is problematic in practice for this problem, you can solve issue 1, you just use overloading (not multimethods because those can't change the return type), at least for operators. Then you don't need the not-to-be-used-polymorphically polymorphic method castTo.

[gavinking]

I guess the main issue is that you're suggesting these things can be done polymorphically, but if you try to be clever and actually do so you're producing code you don't realize is really inefficient because it's doing reflection (which I understand to mean whenever code examines a type). So, in reality, such polymorphism is to be discouraged.

No, I woudn't agree with that. What I would say is that the compiler should be aggressive about optimizing away the polymorphism when it can. (And indeed, that's what our compiler does.)

Having addition be a polymorphic operation is really useful and it's a pain that it's not in Java.

Whether numeric widening needs to be polymorphic or not is an interesting question, and if the answer is "no" then I would probably at this point just say "screw it" and do like Java and many other languages and "hardcode" numeric widening for the built-in numeric types into the language spec. I wouldn't try to somehow map it to overloading which doesn't work anyway in generic code.

Accepting that polymorphism is problematic in practice for this problem, you can solve issue 1, you just use overloading (not multimethods because those can't change the return type), at least for operators. Then you don't need the not-to-be-used-polymorphically polymorphic method castTo.

I don't accept that. In generic code, castTo() would actually get called and it would work. In non-generic code, where we know we are adding an Integer to a Float, the compiler optimizes it away.

[RossTate]

I guess it comes down to feasibility. You should at least be able to get basic uses of zipProduct to work cuz that's an easy one. You'll have a much harder time when clever programmers realize they should never use something like Double as a parameter. In that case, you'll get a bunch of dynamic dispatches like the following so you won't simply be able to inline the code:

shared interface Scalable {
    void scaleBy<N>(N scale) where N satisfies Castable<Double>;
}

[gavinking]

Exactly. Today this method:

//ceylon
void scaleBy(Float scale);

results in this Java:

//java
void scaleBy(double scale); 

But this version:

//ceylon
void scaleBy<N>(N scale) given N satisfies Castable<Float>;

Results in this Java:

//java
<N extends Castable<? super Float>> void scaleBy(N scale);

Clearly the second is going to be much less efficient.

[gavinking]

Y'know, I frankly like your example as a positive example of Castable:

void scaleBy(Castable<Float> scale) {
    size*=scale.castTo(Float);
}

And now I can do:

scale(2);
scale(1.5);

Sort of nice. And all completely typesafe.

[RossTate]

Uhh, are you agreeing with me then that polymorphic uses of Castable should not be used? In which case, why are you saying that an advantage of your solution over overloading is that it's polymorphic?

P.S. When I say polymorphic, I mean generic.

[RossTate]

Oops, concurrent comments.

The point of my example is to illustrate that Castable is nice but will cause efficiency problems. How do you expect to make my example run efficiently?

[gavinking]

The point of my example is to illustrate that Castable is nice but will cause efficiency problems. How do you expect to make my example run efficiently?

I mean, it's not going to be as efficient - a boxed type, an extra method call, and then a switch, but that's already the expectation we have on the JVM. Generic code is never as efficient as code which works directly with primitive types.

[RossTate]

I think it's more expensive than you realize. It's definitely more than a switch, because you're forgetting that the type for castTo can be an intersection type, a union type, Number or Top and so on.

So say I pass an Integer to scaleBy(Float). Then all that has to be done is int to double at the bytecode level, then push that result on the stack and call the function which then just grabs that result from the stack.

Say I pass an an Integer to <T extends Castable<Float>> scaleBy(T).

1. Box the integer (an allocation)
2. Push the address of Integer's meta-data on the stack
3. Push the boxed integer on the stack
4. Call scaleby, which then does
5. Grab the boxed integer from the stack
6. Pushes the address of Float's meta-data on the stack
7. Calls castTo on the boxed integer, which then does
8. Grab Float's meta-data from the stack
9. Pushes Integer's meta-data onto the stack and then the grabbed meta-data
10. Calls isSubtypeOf, which then does a bunch of things I don't want to think about
11. Branches on the result (which fails, and so it proceeds on to casting to Float)
12. Pushes Float's meta-data onto the stack and then the grabbed meta-data
13. Calls isSubtypeOf, which again does a bunch of things I don't want to think about
14. Branches on the result (which succeeds)
15. Grabs the int from the field of the boxed integer
16. Turns that int into a double at the bytecode level
17. Boxes that result (another allocation)
18. Returns the boxed double
19. Then scaleBy unboxes the result

That is much more expensive than generic Java code would usually cost. Furthermore, because of the reflection, lots of this probably won't be optimized even after inlining.

[gavinking]

This is a nice discussion of the intricacies of Castable, but at this point we're definitely not going to implement this stuff in Ceylon 1.0 (instead we'll remove Castable, at least temporarily). So I'm closing this issue, and moving discussion to #405.