Uninstantiated generic types as generic type arguments

[HertzDevil]

Normally, all generic type arguments of a generic cannot themselves be uninstantiated generics:

Comparable(Array)            # Error: can't use Array(T) as generic type argument yet, use a more specific type
[1].is_a?(Comparable(Array)) # Error: can't use Array(T) as generic type argument yet, use a more specific type

But such generics can be formed nonetheless:

class Foo(T); end
module Moo(T); end

alias F = Foo(Foo) # okay
alias M = Moo(Moo) # okay

class Bar < F      # okay
  include Moo(Moo) # okay
end

{% Bar.ancestors %} # => [Moo(Moo(T)), Foo(Foo(T)), Reference, Object]

Bar.new.is_a?(F) # => true
Bar.new.is_a?(M) # => true

Formal type parameters can be leaked in this way too:

class Foo(T)
  @x : T?
end

module Moo(T)
  @y : T?
end

typeof(Bar.new.@x) # => (Foo(T) | Nil)
typeof(Bar.new.@y) # => (Moo(T) | Nil)

So far we have been using types like Comparable(Array) in the standard library without any significant issues. What should we do about these types?

[beta-ziliani]

Perhaps obvious, but it's important to mention that Bar.new.@x makes the program crush.

cast from Crystal::GenericModuleType to Crystal::SubclassObservable failed, at /build/crystal/src/crystal-1.4.1/src/compiler/crystal/semantic/call.cr:1229:5:1229 (TypeCastError)

[asterite]

I don't think we should let un instantiated generic types as instance variables. It's allowed for include to use T as a generic type restriction (Comparable is a good example of that).

Regarding ancestors... I guess uninstantiated generic types make sense In a hierarchy.

[beta-ziliani]

Sorry, I don't follow what you're saying.

I don't think we should let un instantiated generic types as instance variables.

IIUC this is just focusing on the leakage of T in @x : T?, but to me the problem is that T is leaked on its own (like in the list of ancestors).

Regarding ancestors... I guess uninstantiated generic types make sense In a hierarchy.

Uninstantiated, yes, but I don't think a free variable make sense. To me, the intention should be clear: does Bar intends to instantiate T within, or the intention is to forward it (as in class Bar(T) < Foo(Foo(T)))?

But perhaps I'm missing a use case. You mention Comparable, what do you mean?
Sorry for the question-bombing!

[HertzDevil]

By writing include Comparable(Array), the Ts in Comparable#<=>(other : T) and #<(other : T) etc. are substituted with just Array. This allows the comparison methods to act on any two Arrays, even with different generic type arguments. If we write include Comparable(Array(T)) or Comparable(self), then only same-type comparisons would work:

module Foo(T)
  def foo(other : T)
    T
  end
end

class Bar1(T1)
  include Foo(Bar1)
end

class Bar2(T2)
  include Foo(Bar2(T2))
end

class Bar3(T3)
  include Foo(self)
end

Bar1(Int32).new.foo(Bar1(Int32).new) # => Bar1(T1)
Bar1(Int32).new.foo(Bar1(Char).new)  # => Bar1(T1)
Bar2(Int32).new.foo(Bar2(Int32).new) # => Bar2(Int32)
Bar2(Int32).new.foo(Bar2(Char).new)  # Error: no overload matches
Bar3(Int32).new.foo(Bar3(Int32).new) # => Bar3(Int32)
Bar3(Int32).new.foo(Bar3(Char).new)  # Error: no overload matches

{{ Array(Int32).ancestors }} includes Comparable(Array(T)), but here the T is the result of printing an uninstantiated generic type; no Crystal::TypeParameter called T is leaked here. That type would simply be referred to as Comparable(Array) like now if it were permitted everywhere.

Note that the following is also technically possible:

# `F` must be an uninstantiated generic; in C++ this might look like
# `template <template <typename...> typename F> struct Generic { };`
module Comparable::Generic(F)
  abstract def <=>(other : F(*T)) forall T

  def <(other : F(*T)) forall T; ...; end
end

class Array(T)
  include Comparable::Generic(Array)

  # the compiler pretends that `Array` subsumes `Array(*T) forall T`
  # during abstract def checking, because `T` is undefined
  # while this is indeed true, things get tricky if we use
  # `Array(U) forall U` instead
  def <=>(other : Array); ...; end
end

This approach would formalize the use of uninstantiated generics as higher-kinded type variables.

[straight-shoota]

The argument type for Array#<=> is not really an unrestricted Array type. It's actually something like Array(Comparable(T)).
That's technically not entirely accurate, because the comparison is the other way around and it would be more like Array(Comparable(U)) for all U such that T < Comparable(U).
That's just too complex to express.

I believe we could probably reverse the call direction of the comparison in Array<=> so that we can make the argument an actual Array(Comparable(T)).

Implementing this triggers a compiler bug and sends it into an endless loop (https://github.com/straight-shoota/crystal/tree/test/array-comparable). 🤷‍♂️

[asterite]

The argument type for Array#<=> is not really an unrestricted Array type

It is! Take a look at this:

class Foo
  getter x

  def initialize(@x : Int32)
  end

  def <=>(other : Foo)
    x <=> other.x
  end
end

ary = [Foo.new(3), Foo.new(2), Foo.new(1)]
p ary.sort

It just works ©️

That's just too complex to express

This is something that I really like about Crystal: no need to delve into super complex type restrictions.

If we do restrict it to Array(Comparable(T)) then it's a breaking change. But don't feel it's the right thing to do. In my mind Comparable just defines < and others for you based on a single <=> method, but it doesn't signal that a type is comparable. Similar to how a type can respond to to_json or from_json without necessarily including JSON::Serializable. Whether that's something desireable or not is a different topic, but it's how things work (more like a duck-type way, which is what I really like about Ruby.)

[straight-shoota]

@asterite I don't get your code example. We're talking about Array#<=>, not #sort (which is eventually T#<=>).

I sympathize with the ability to avoid complexity.
But there is a good motivation to adding such type restrictions: Better errors.
Right now, if you do something like [1] <=> ['c'] you get an error message that complains about undefined Int32#<=>(String). That's not very helpful. It might be good enough to figure out what's wrong.
But it would be more user friendly if Array#<=> wouldn't even compile when the item types are not comparable.

[asterite]

Ah, you are right. Here's a better example:

class Foo
  getter x

  def initialize(@x : Int32)
  end

  def <=>(other : Foo)
    x <=> other.x
  end
end

ary1 = [Foo.new(3), Foo.new(2), Foo.new(1)]
ary2 = [Foo.new(1), Foo.new(2), Foo.new(1)]
p ary1 <=> ary2

Right now, if you do something like [1] <=> ['c'] you get an error message that complains about undefined Int32#<=>(String)

That makes total sense if you look at the entire error trace... which is hidden by default 🤦

[asterite]

Right now, if you do something like [1] <=> ['c'] you get an error message that complains about undefined Int32#<=>(String)

A better answer that doesn't use the facepalm emoji (sorry about that): we could check if each element responds to <=> with the target type. If not, we can give a nice error message. But I don't think enforcing this at the type level is the best solution.

[HertzDevil]

Traits / concepts (a more glorified version of #2549) are another way to specify the correct overload signatures without depending on Comparable:

class Array(T)
  def <=>(other : Array(U)) : Int32? forall U requires typeof(self[0] <=> other[0]) <= Int32?
    # ...
  end

  # also okay
  def <=>(other : Array) : Int32? requires typeof(self[0] <=> other[0]) <= Int32?
    # ...
  end
end

But this alone doesn't make the original issue go away, because we still need to include Comparable to generate #== / #< / #> / #<= / #>= from #<=>, and those methods' restrictions refer to the T in Comparable. On the oher hand, one could say that none of the non-abstract methods in Comparable need a T at all.