Meta-issue: using a generic function type as a type argument or as a bound is an error

[leafpetersen]

It is a static error to use a generic function as a type argument, or as a bound to a generic.

• Issue for specification
• Issue for analyzer implementation

Example:

typedef F = T Function<T>(T x);
typedef G<T> = T Function(T x);

class A<T extends F> {} // error
class B<T extends G<int>> {} // ok
void f<T extends F>() {} // errror
void g<T extends G<int>> {} // ok

void main() {
  var a1 = <F>[]; // error
  var a2 = <G>[]; // ok, G<dynamic>
  var a3 = <G<int>>[]; // ok
  var a4 = g<F>(); // error
  var a5 = g<G>(); // ok G<dynamic>
}

[eernstg]

I'm not sure where this constraint comes from, is it simply a matter of avoiding to support a potentially complex corner of the language?

What I wrote in the informal specification of generic function type aliases already in the introduction was that this feature is intended to allow actual type arguments and bounds (among other things) to be generic function types. After all, we could already express the type-level functions (like G) with the existing typedef construct, so the generic function types (like F) are the new thing that this feature gives us (apart from a more readable syntax).

In 'Static Analysis' it says that type parameter bounds cannot be of kind * -> * (like G), they must be of kind * (i.e., they must be types), but it does not say that it can't be a generic function type (like F).

It's worth noting that there is no abstraction over several aspects of generic function types. In particular, when the statically known type of a first-class function is a generic function type then that function will be generic at run-time, and it will take exactly as many type arguments as we know about statically, with exactly the same bounds. Similarly, with a non-generic static function type (other than Function), the run-time value will be a non-generic function. To me, it seems like the situation is pretty well-defined so I don't see why we'd outlaw cases like "generic function type as bound" or ".. as actual type argument".

I also noted that the example code above suggests that a lone G in a type position would be treated as a request for instantiate-to-bound. That makes sense, but I did not anticipate it and I'd need to adjust the informal spec to say so. However, I do tend to think that an implicit instantiate-to-bound on G could be confusing for developers, especially those who don't really understand the difference between F and G, so I'd tend to prefer that <G>[] is an error rather than being the same thing as <G<dynamic>>[].

[leafpetersen]

My original generic method proposal was for prenex, predicative polymorphism. We relaxed that to be just predicative, but my intention was that we would stay in the predicative fragment. Since we have agreed to make type bounds behave invariantly (that is, <T extends B>(S0) -> R0 is a subtype of <T extends A>(S0) -> R0 requires that A == B rather than just A <: B) it is possible that we could expand ourselves to the impredicative fragment and still be decidable, but I don't know that this is the case. It is certainly the case that if we used the A <: B rule, we would be undecidable[1]. Even if expanding to the impredicative form doesn't push us into the undecidable fragment, it may restrict our options later on (though we may already be fairly close to the edge of decidability[2]).

So I'm fairly strongly in favor of at least starting in the predicative fragment, and only expanding to the impredicative fragment when and if we have convinced ourselves of that it's decidable and worth any opportunity cost that we would pay.

[1] http://www2.tcs.ifi.lmu.de/lehre/SS07/Typen/pierce93bounded.pdf
[2] http://repository.upenn.edu/cgi/viewcontent.cgi?article=1714&context=cis_papers

[eernstg]

OK, that makes sense. This actually means that generic function types can be used in the following situations, and only in those situation (where G is a generic function type):

• as a type annotation on an local, instance, static, or global variable (e.g., G x;).
• as a function return or parameter type (G foo(G x) => x;), which is non-prenex.
• in a type test (e is G).
• in a type cast (e as G).
• in an on-catch clause (... on G catch ...).
• as a parameter or return type in a function type (G Function(G)), which is also non-prenex.

If a list of generic functions is needed then we can embed it into the nominal type universe using a wrapper class:

typedef G = T Function<T>(T);
class G1 { final G x; C(this.x); }
List<G1> xs; // OK.

[leafpetersen]

Obsolete.