Generic sort

[John Rose]

On Sep 13, 2014, at 9:26 AM, Paul Govereau <paul.govereau at oracle.com> wrote:

> Hello,
> 
> I have been trying to write a fully generic SortedArrayList<any T>, but I don't see a good way to implement sort. The difficulty has to do with comparison. I am assuming that, like objects but unlike the primitive types, value types will not have an implicit ordering. So, objects and values must support an interface for comparison.

This is contemplated in the VT proposal; see occurrences of Comparable.

The bridge from a VT to an interface is about the same as from a class to the same interface.  In both cases, if you have a concrete type, you invoke methods on the concrete type, not the interface.

The missing bit is to supply a canonical VT-style box for each primitive.

> For the primitives, the bytecode needed for comparison is not easily synthesized (e.g. do you choose fcmpl or fcmpg?).

I would say (as Joe suggests) look to the current wrapper types for guidance.

> It seems that we need something like this:
> 
> class SortedArrayList<any T> {
>  T[] array;
>  ...
> 
>  <where ref T extends Comparable<T>>
>  int cmp(T x, T y) {
>     try return x.compareTo(y);
>     catch (NullPointerException e) {
>       return -1; // similar to fcmpl
>     }
>  }
> 
>  <where val T extends Comparable<T>>
>  int cmp(T x, T y) {
>    return x.comapreTo(y);  // no null pointers.
>  }

When I see this, my first thought is why do we need 'where' clauses for this use case?  Is the possibility of a RuntimeException enough to break parametric polymorphism?  I don't see why.

If null handling is necessary (beyond NPEs which can be swept under the rug), push that down into a 'where' clause:

<where T extends Object>
static boolean isNull(T x) { return x == null; }
<where else>
static boolean isNull(T x) { return false; }

...better yet, since null processing is wired into the VM, allow "x == null" in polymorphic code (given 'any x'), and define it to mean false when T is a non-reference.  This is logically true.  It also meets the spirit of the polymorphic template:  "x could be a reference, in some instances, so it makes sense to ask if it is null, at least sometimes".

> 
>  <where T=int|char|byte|boolean>
>  int cmp(T x, T y) { return x < y; }  // if_icmplt
>  <where T=long>
>  int cmp(T x, T y) { return x < y; }  // lcmp; iflt
>  <where T=float>
>  int cmp(T x, T y) { return x < y; }  // fcmpl; iflt
>  <where T=double>
>  int cmp(T x, T y) { return x < y; }  // dcmpl; iflt

This stuff should all be mediated by wrappers.  Put another way, it doesn't belong in SortedArray, but in some global definitions which connect primitive types to Comparable.

>  ...
> }
> 
> Note, in this case SortedArrayList<Object> is not inhabited. Do we think that the programmer must give an implementation for Object that raises exceptions, or do we think the type system will disallow instantiation with Object?

It should be:
  class SortedArrayList<any T extends Comparable<T>> {

Then the question does not arise.

> Here is another example along the same lines.
> 
> class Group<any T> {
>  ...
>  <where ref T extends Numeric<T>>
>  T add(T x, T y) { return x.add(y); } // invoke*
> 
>  <where val T extends Numeric<T>>
>  T add(T x, T y) { return x.add(y); } // vinvoke*
> 
>  <where prim T>
>  T add(T x, T y) { return x+y; }  // iadd/ladd/fadd/dadd
> }
> 
> Group<BigInteger> OK reference type
> Group<Complex>    OK value type
> Group<int>        OK primitive
> Group<Object>     ?? not OK

Should be Group<any T extends Numeric>.

To me, this is an argument for primitive boxes to implement Number (which they happen to even today) and for Number to implement a value-compatible interface Numeric.

(BTW, character and boolean don't exactly add, nor are they Numbers.  "prim" is not the right type selector or type bound here.)

— John