Constrain type vars / free variables to specific types

[ozra]

It would be good be able to constrain generic variables, just like common variables - exact same concept: (I'm skipping the meat of the classes just to show the concept.)

[ed: 2016-09-12, modified the example slightly]

class Foo(T)
end

class Fur(T < Float32 | Float64) < Foo(T)
end

class Bar(T1 < Float32 | Float64, T2 < Foo(_)) < Foo(T1)
end

class Baz(T1 < Float32 | Float64, T2 < Foo(_)) < Foo(T1)
end

Adding type intersections in addition to type unions could prove usable for constraints too:

class Foo(T < (SomeTrait & OtherTrait) | MoreCompleteTrait | SuperType)
end

ed: Below has its own issue now instead: #3298

Preferably, it should also be possible to "overload" the generic class matching to most specific type var constraint, thereby making specializations possible:

class Foo(T)
end

class Fur(T < Float32 | Float64) < Foo(T)
end

# Two Bar classes with different specializations depending 
# on most specific generic constraint match
class Bar(T1 < Foo(_), T2 < Foo(_)) < Foo(T1)
end

class Bar(T1 < Float32 | Float64, T2 < Foo(_)) < Foo(T1)
end

[asterite]

I think code that involves generics is already pretty complex to want to make the type system more complex. But I think @waj likes these ideas so I'll leave this open as an enhancement. Personally, I feel code should be simpler, and generics should only be used for containers.

[bcardiff]

So there are two concepts in the proposal: 1) type restrictions in the generic args 2) class/code specialization.

If we think 1) alone, a usage I can think of is just to allow better errors to the user when using an invalid argument due to some interface assumtions ( Foo(T) where T includes MixinBar ). Based on how de compiler works, there is no information to take advantage of. There is no partial compilation of Foo(T). It is compiled on each concrete type: Foo(Int32), etc. So, if the type used for T does not includes the expected MixinBar, today the code won't compile when a method of the mixin is used. With 1) it might fail when instantiation Foo(T) on a wrong T.

Other usage of 1) is to express some dependency like Foo(T) where T includes Enumerable(S). And use S somewhere in the code. This is neat, attractive, yet I don't have a real use case today :-). But I love formality around the type system.

Regarding 2) It might be enough at the beginning to allow class/code specialization at least on concrete types. class Foo(Int32) ... end. If there is a specialization for many types, it might be addressed by macro expansion. I think the specialization feature is important, but I think this, allowing it only in concrete types, might be a way to see if it useful without going all the way down extending a lot the language.

[ozra]

Exactly. As you mention 1) is a great help to catch errors earlier and give more specific helpful error messages.

When it comes to 2)

It is compiled on each concrete type: Foo(Int32)

Each specific instantiation is compiled from class description, it simply will be based on the description matching the types better. So it "solves it self" as soon as the "overloading on typevar restrictions" matching is in place, so there's no special case for specialization requiring it to be limited to concrete types. And most of the logic for matching should be the same as for regular overloading, so a lot of the logic would already be available for revamping. Or am I missing something?

[stugol]

+1 for these features

[mrkaspa]

+1 this also should work for modules, and abstract classes with abstract methods

[ozra]

As mentioned in OP, I've edited it slightly, added #3298 issue for 2) to keep tracking separate.

[RX14]

There's a workaround used in Atomic(T) here. A nicer syntax would probably be useful though.

[ozra]

@RX14 thanks for linking the macro example. Macros solve most things (Crystal rocks), and still, as you say: nicer syntax would be nice :-)

Also, for numbers as parametrization: (Z < Number#, T < SomeType) or something. To indicate that it is an instance of the type (maybe I've foolishly missed a reverse of T.class?). The other way around would be kinda ridiculous ((Z < Number, T < SomeType.class)), given type parametrizations are most common.

If I recall correctly (I don't code C#), C# defines constraints suffixed to typedef head. Perhaps that's a style that would suit Crystal: class Foo(T, U, Z) < SuupaFoo(T) where T < AbstractFoo, U > T, Z < Number#

Wonder if both constraints and specializations could be solved smoothly by a AST rewrite stage, making macro nodes from such statements, and then expand those as usual. In order to re-use and keep as much code as generic as possible in the compiler (mash all implementations of specialized defs into one def with macro conditionals to select actually used code, etc).

[bjeanes]

Cross-posting and elaborating on my comment from #3298:

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

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

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

class Hash(K, V = Array(K))
  include TSort(K)
end

dag = {1=>[2, 3], 2=>[3], 3=>[] of Int32}
non_dag = {:x=>42, :y=>99}

dag.tsort     #=> [3, 2, 1]
non_dag.tsort #!! wouldn't compile

[sol-vin]

+1 would love to restrict generics based on type, for example, allowing only an inherited type.

class ClassA
end

class ClassB < ClassA
end

class Example(T : ClassA) #would only allow those of type class A
end

[hanyuone]

Would a syntax like where T < CustomType be good? For example:

alias Foo = Int32 | String
alias Bar = Float64 | Char

class FooArray(T) where T < Foo
end

class FooBarHash(K, V) where K < Foo, V < Bar
end

This fits in with languages like Java and also conforms to the current forall syntax, although I'm not sure if this verbosity is worth it for readability. The main concern is how often this will be used, but I think just inserting the restrictions next to the argument is less readable and almost as verbose.

I'm not sure if this is the right place or time to post this right now, but it's an idea to throw out in the open.

[straight-shoota]

It could just be forall, don't need to add another keyword. Inline notation is also fine, though.

[hanyuone]

@straight-shoota So basically:

class FooArray(T) < Array(T) forall T < Foo

Shouldn't be too hard to parse, then.

[RX14]

@straight-shoota but forall on methods and the usage of forall here are entirely different semantics, so why use the same syntax.

Also, having the (T) and the forall is just weird, i'd rather just use class Foo(T : Class, K : Class) which fits the current syntax.

[bew]

Also, having the (T) and the forall is just weird, i'd rather just use class Foo(T : Class, K : Class) which fits the current syntax.

Also it would allow to do class Foo(T : Bar = Baz) to add a type restriction with a default without adding too much new syntax

[malte-v]

I wrote a lightweight (~100 LOC) implementation for this using the macro interpreter (see proposal: https://github.com/crystal-lang/crystal/issues/3298#issuecomment-500363243). It can handle (abstract) classes/structs and modules. Some examples:

class Foo(T) where T < Number
end

Foo(Int32).new # OK
Foo(String).new # Error: type var String doesn't satisfy restriction 'T < Number' of generic class Foo

struct MyTuple(*T) where T.size > 1
end

MyTuple(Bool, String, Int32).new # OK
MyTuple(Float64) # Error: type var Float64 doesn't satisfy restriction 'T.size > 1' of generic struct

struct NumberTuple(*T) where T.type_vars.all? &.< Number
end

NumberTuple(Int32, Float64).new # OK
NumberTuple(Int32, Float64, String).new # Error: type vars Int32, Float64, String don't satisfy restriction 'T.type_vars.all?(&.<(Number))' of generic struct NumberTuple

module Bar(T) where T < Int::Signed
end

class Foo(T)
  include Bar(T)
end

Foo(Int16).new # OK
Foo(UInt64).new # Error: type var UInt64 doesn't satisfy restriction 'T < Int::Signed' of generic module Bar

Changes: https://github.com/malte-v/crystal/commit/47351403c0ff32d9cda9481b73954eb437ac60c0

Do you think this could be a viable solution?

[HertzDevil]

A while ago I was thinking that if constrained generic parameters use:

# `<=` for subtypes, `<` for proper subtypes
# ditto for supertypes
class Foo(T) forall T <= Int
end

then the unconstrained generics, which we already have now, would be written as:

class Proc(*T, R) forall T, R
end

Full specializations (#3298) would eventually not require any special syntax, as a lack of forall should indicate that the generic arguments are not formal parameters:

struct Slice(T) forall T
end

# okay, `UInt8` is not an unbound parameter
# requires `Slice` and `UInt8` to be defined prior to this point
# this is _not_ equivalent to `Slice(T) forall T <= UInt8`,
# because `Slice(NoReturn)#hexstring` is undefined here
# can perhaps be written as `Slice(T) forall T == UInt8` too
# (implies syntactic equality, not just type equivalence?)
struct Slice(UInt8)
  def hexstring; end
end

struct StaticArray(T, N)
end

# partial specialization
struct StaticArray(UInt8, N) forall N
end

# not allowed; `Int32` is not an unbound parameter
# no prior definitions of `Bar` exist to provide a name
# for the corresponding formal parameter
class Bar(Int32)
end

# not allowed; `String` is not an unbound parameter
# no prior definitions of `Foo` allow `T = String`, as `T <= Int`
class Foo(String)
end

The full macro language for the constraint is probably overkill, we should start with the subtyping operators first.

The equivalent issue for free variables in defs is #11908 (it proposes only <= but generic type instantiations can't "overload" so we have a bit more freedom here).