Generic Specializations

[ozra]

I realized, even though its been mentioned many times in comments on other issues, and it was touched upon in #934, that I couldn't find an issue specifically targeting specializations. Here goes:

Shitload of Effort

I do realize the generics are not completely stable yet, and this would be a further amount of blood, sweat and tears.

It would be very nice to be able to do specializations

I'll try to leave generic parametrization constraints out of this issue, so #934 can stand for that, however for clarity an "exact match only" "constraint" syntax could be used here (T = SomeT).

I use typeparam names according to #3294.

module CommonFooThings(TheT)
  def common_thing(x : TheT) p "Do stuff" end
end

class Foo(MyT)
  include CommonFooThings(MyT)
  def initialize(@value : MyT)
  end

  def do_stuff() p "Do something when not matched by more specific impl" end
end

class Foo(MyT = Bool)
  def do_stuff() p "Do something with bool-specific" end
end

class Foo(MyT = Symbol)
  def do_stuff() p "Do something with symbol-specific" end
end

Foo.new(true).do_stuff  # => "Do something with bool-specific"

Use Cases

Use-case is of course for performance reasons in containers and low-level readers, writers etc. For instance Set(T) now uses Hash(T) behind the scenes, but Set(Symbol), Set(Int32), Set(Char), etc. could use much more efficient implementations, without the user having to care much about it, same goes for other containers, etc. Win win.

[bcardiff]

I am 👍 on type specialization. The two questions or aspect to address IMO are:

• Override only or extend also:
  • Do we want to allow a type specialization to change the interface by adding new operations? 👍
  • Or only to override for more efficient implementations?
• Generic vs punctual specialization: Which level of expressiveness we want on while specializing
  • Only concrete? Set(Int32)
  • Support modules? Set(IO) we will need to resolve Set(IO) vs Set(MemoryIO) 👍
  • Nested/free vars? Set(Slice(T)) , Hash(T, Foo(T)). This is kind of reaching the same expressiveness as methods with type vars.

[ozra]

This is kind of reaching the same expressiveness as methods with type vars. / @bcardiff

Yeah! Using the "most specific match" resolution and constraints just as for method parameter restrictions (shouldn't they be called "constraints" also?). As mentioned in #934 - preferably allowing both unions and even intersections (also for method param restriction then). Preferably the same logic should be refactored and re-used if possible for consistency in the compiler.

Override only or extend also:

I see no reason for artificially limiting extension. If Type(ElementT) is used somewhere and Type(Bool) specific method is used, compiler will complain just as now.

[bjeanes]

I'm not 100% sure if my use-case fits into this issue or should be it's own, but...

I was hoping to do something like this (using the pseudo-syntax in this thread):

class Hash(K, V = Array(K))
  # ...
end

This is a little bit more advanced that proposed above, I believe, as it places restrictions on the relationships between generics.

The use-case in my case is for topological sorting of certain enumerable types. For instance, if we wanted to sort entries in a Hash by treating it as a DAG, it'd be incoherent for anything other than a map of K=>[K].

[ozra]

@bjeanes - see #934 as mentioned above :-)

[bjeanes]

@ozra do you want me to repost the above use case on that issue then?

[ozra]

@bjeanes - that's probably good, to make it easier for new-comers and old-timers alike to track it?

[vladfaust]

I'm sure that this particular issue can be solved with access to T on class level in macros. I often missing this feature writing more-on-less complex code.

[asterite]

This issue is just a fancier syntax for things we can already do:

https://play.crystal-lang.org/#/r/6hs2

I think this issue can be closed. Having specializations is confusing:

1. It's hard to easily find out where a method is defined
2. How do you show this in API docs?

[straight-shoota]

I wouldn't necessarily rule this out completely. We need to revisit the generics system anyway, and should keep such ideas in mind.

[bcardiff]

Having something like the proposed syntax enables us to specialize the implementation in a different part of the code base. That's a bonus for me.

[bew]

@bcardiff it looks close to https://github.com/crystal-lang/crystal/issues/934#issuecomment-471279849 even though the semantic is different..

For this issue I'd suggest class Foo(T == Bar) so when T is exactly Bar (not a restriction), add these methods.

I think we need to keep the 2 issue' solutions compatible

[Blacksmoke16]

class Foo(MyT = Symbol)
  def do_stuff() p "Do something with symbol-specific" end
end

This syntax made me think that the type of MyT would be Symbol if a generic wasn't passed, i.e.

class Foo(MyT = Bool)
  def type
    MyT
  end
end

Foo.new.type # => Bool
Foo(String).new.type # => String

Following the standard restriction would be better imo if possible. i.e class Foo(MyT : Bool)

EDIT: Having default generic types would be 💯

[vladfaust]

@Blacksmoke16,

Having default generic types

That makes no sense for me. How would you imagine an Enumerable with default generic type? :thinking:

[Blacksmoke16]

Mmm I'd have to think about what I wanted it for, but IIRC it was for that specify shard I was working on. Where, if you had defaults, could do like extend Specify which would be equivalent to extend Specify(Specify::Spec) or something like that. Where the generic on it is basically a whitelist of types that are allowed for the includer. Without one would mean allow all.

[straight-shoota]

@Blacksmoke16 MyT : Symbol doesn't make sense. MyT isn't of type Symbol. It is Symbol. Hence the equals sign. It's not ideal, agreed. Maybe there is a better choice.

[Blacksmoke16]

@straight-shoota Isn't that what .class would be for? MyT : Symbol.class? But yea...good call.

[bew]

@vladfaust default generic types can be very useful, for example we could have Hash taking the Hasher you want to use:

class Hash(K, V, HasherT = Crystal::Hasher)
end

So that is most cases when you create a Hash, the hasher will be the default one from crystal Crystal::Hasher but in the cases where you need a custom hasher you can do: h = Hash(Foo, Bar, CustomHasher).new.

[bew]

But keep in mind that this issue is not about generic default & restrictions (which is covered by #934) but about generic specialization.

If you don't see the difference, ask on the chat or the forum.

[ozra]

As @bcardiff mentions, being able to add specializations as monkey patches is a great plus, and almost likely scenario (implementing a library with SomeSuperFastThing and wanting to specialize Set specifically for that, etc.)

As @Blacksmoke16 & @bew mentions, defaults feels lika a given; basically: anything that can be done for run-time arguments in a method call should translate and be mirrored in appropriate syntax for generic parametrizations, including named and positional params and all — that would be the cleanest approach afaic.

[malte-v]

What about something like this?

class Foo(T) where T == Bool || T < Int
end

The condition after the where is evaluated by the macro interpreter and if it evaluates to true, the specialization is applied. This could also be used for restrictions if you never declare the class without a where part. This approach would allow for arbitrarily complex checks. Imagine a container type that can be optimized if the element count is a power of two:

class MyContainer(T, N) where ((N != 0) && ((N & (~N + 1)) == N))
  def optimized_method
    ...
  end
end

The macro interpreter has no trouble evaluating something like that. I think this is the easiest to implement and most versatile solution. And in the API docs, we could add a section named something like "generic specializations" and put the where parts with their methods there.

Edit: I admit the example above was bad. You could just add a check to the method body, of course. Where this would be more useful is when you want to extend a type. A better example would be:

class Matrix(T, N, M)
  # operations that make sense for any matrix
end

class Matrix(T, N, M) where N == M
  # some operations only make sense for square matrices
  def determinant
    # ...
  end

  def inverse
    # ...
  end
end

[ozra]

The "as generic as runtime code, but with compile time values (here counting types as values)" really is the most powerful, and consistent. Compare constexpr in C++17, it's just f**n amazing to work with. Using = for defaults, and == for equality is then a given of course. And </> does work well in symbolizing type relation. When we start thinking about details like structural vs nominal relation, it gets trickier — but since Crystal has a pretty hard and rough simplification of SumType / TaggedUnion widening, that's not really a subject for this type system. I still wish Unions were kept intactly exact — but that's another issue, the sole reason was performance problems.