Added informal generic method syntax and generic function type specs.

docs/language/informal/generic-function-type-alias.md

+# Feature: Generic Function Type Alias
+
+**Status**: Implemented.
+
+**This document** is an informal specification of a feature supporting the
+definition of function type aliases using a more expressive syntax than the
+one available today, such that it also covers generic function types. The
+feature also introduces syntax for specifying function types directly, such
+that they can be used in type annotations etc. without going via a
+`typedef`.
+
+In this document, a **generic function type** denotes the type of a function
+whose declaration includes a list of formal type parameters. It could also
+have been called a *generic-function type*, because it is "the type of a
+generic function". Note that this differs from "a type parameterized name
+*F* whose instances *F<T>* denote function types", which might perhaps be
+called a *generic function-type*. In this document the latter is designated
+as a **parameterized typedef**. Examples clarifying this distinction are
+given below.
+
+**This feature** introduces a new syntactic form of typedef declaration
+which includes an identifier and a type, connecting the two with an equals
+sign, `=`. The effect of such a declaration is that the name is declared to
+be an alias for the type. Type parameterization may occur in the declared
+type (declaring a generic function type) as well as on the declared name
+(declaring a parameterized typedef). This feature also introduces syntax for
+specifying function types directly, using a syntax which is similar to the
+header of a function declaration.
+
+The **motivation** for adding this feature is that it allows developers to
+specify generic function types at all, and to specify function types
+everywhere a type is expected. That includes type annotations, return types,
+actual type arguments, and formal type parameter bounds. Currently there is
+no way to specify a function type directly in these situations. Even in the
+case where a function type *can* be specified (such as a type annotation for
+a formal parameter) it may be useful for readability to declare a name as an
+alias of a complex type, and use that name instead of the type.
+
+## Examples
+
+Using the new syntax, a function type alias may be declared as follows:
+
+```dart
+typedef F = List<T> Function<T>(T);
+```
+
+This declares `F` to be the type of a function that accepts one type
+parameter `T` and one value parameter of type `T` whose name is
+unspecified, and returns a result of type `List<T>`. It is possible to use
+the new syntax to declare function types that we can already declare using
+the existing typedef declaration. For instance, `G` and `H` both declare
+the same type:
+
+```dart
+typedef G = List<int> Function(int); // New form.
+typedef List<int> H(int i); // Old form.
+```
+
+Note that the name of the parameter is required in the old form, but the
+type may be omitted. In contrast, the type is required in the new form, but
+the name may be omitted.
+
+The reason for having two ways to express the same thing is that the new
+form seamlessly covers non-generic functions as well as generic ones, and
+developers might prefer to use the new form everywhere, for improved
+readability.
+
+There is a difference between declaring a generic function type and
+declaring a typedef which takes a type argument. The former is a
+declaration of a single type which describes a certain class of runtime
+entities: Functions that are capable of accepting some type arguments as
+well as some value arguments, both at runtime. The latter is a compile-time 
+mapping from types to types: It accepts a type argument at compile time and

[Lasse Reichstein Nielsen, 2017/07/12 12:08:07]

It's not entirely compile-time. Some types are only known at runtime, so the
actual mapping has to happen there:

typedef F<T> = Function(T);
class C<T> { 
  test(Function f) => f is F<T>;
}

Here the parameterization of `F<T>` can only happen after an instance of C has
been created, so it's necessarily at runtime.

[eernst, 2017/07/12 13:21:12]

Wouldn't it be a reasonable semantics for that `C` to expand the typedef and
then rely on the dynamic semantics of the expansion? In that case the typedef
doesn't have a dynamic semantics per se.

[Lasse Reichstein Nielsen, 2017/07/13 06:57:17]

That's also a reasonable interpretation, but then it's not a mapping from types
to types, but from type-expressions to type-expressions (it's a syntax-level
macro, not a type-level function). The type parameter "T" is not a *type* at
compile-time, only at runtime, but it is a type-expression.

[eernst, 2017/07/13 12:35:20]

First, the reason why I emphasized `type-level function` from the very
beginning, and switched to `compile-time mapping from types to types` later, is
that I think this gives the reader the clearest possible distinction between
those two concepts.

A parameterized typedef is a compile-time only concept, there is no need to
leave any traces of their existence at run time. A generic function needs to
exist at run time, and it needs to have properties that reflect its ability to
accept both type and value arguments.

Don't you think that compile/run-time distinction is helpful?

On 2017/07/13 06:57:17, Lasse Reichstein Nielsen wrote:
That's actually a very tempting stance! (Types only exist at run-time, just like
everything else, except syntax). But it wouldn't be hard at all to find (very
serious) people who would insist that types _only_ exist at compile time, and if
there is something similar to types at run time it would be "type tags",
indicating that any given object has a type which is represented by that tag.

I've got enough of that bug to disagree, we do not only have (1) run-time
semantics, and (2) syntax. In particular, the language specification requires
many different kinds of type-level computations to take place during static
analysis.

For instance, we may have a `class D<T> { List<T> get foo; }` in a program, and
`myD.foo` could have type `List<List<String>>`, but the program does not have to
contain `List<List<String>>` as syntax anywhere. So that's a type, and it's not
syntax, and it's actually produced by a compile-time computation.

Another example is that the body of `D` can use `T`, which is also a type
because it derives from `type` and it conforms to the relevant static checks.
It's a first class type because different instances of `D` may have different
values for `T`, but that doesn't prevent static analysis checking usages of `T`.
For the compile-time computations on types, `T` is a type just as much as `int`
is a type, and it doesn't matter whether or not any particular type during these
computations existed as syntax at any point in time.

[Lasse Reichstein Nielsen, 2017/07/14 09:22:46]

The usual Java story is that types only exist at compile-time and it's "class"
at runtime (hence `Foo.class`, of type `Class<Foo>` being the runtime reflection
of the `Foo` type). They also say "variables have types, objects have classes".
That's probably 
On the other hand, they do erasure, so a lot of things does not exist at runtime
:)

I think my opinion is that types exist both at compile-time and at runtime. At
runtime they may be represented by "type tags", but that just means that
compile-time types and runtime types are distinct, not that they are not both
"types". We can do full type reasoning, subtype-checks, at runtime (through
generics: bool isSubtype<A,B>=><A>[] is List<B>;)

I think the distinction between compile-time and runtime is good, so my primary
concern is that the mapping appears to be either syntactic or happen at runtime
— because it works on type variables which are not types at compile-time. If we
see type variables as types (that is "? extends T" is a type in the static type
system), then I guess the explanation works.

And again, this is explanatory, so maybe it can get away with not being
absolutely correct as long as it provides a good way to think about things.

So, LGTM.

+returns a type, which may be used, say, as a type annotation. We use the
+phrase *parameterized typedef* to refer to the latter. Dart has had support
+for parameterized typedefs for a while, and the new syntax supports
+parameterized typedefs as well. Here is an example of a parameterized
+typedef, and a usage thereof:
+
+```dart
+typedef I<T> = List<T> Function(T); // New form.
+typedef List<T> J<T>(T t); // Old form.
+I<int> myFunction(J<int> f) => f;
+```
+
+In this example,
+we have declared two equivalent parameterized typedefs `I` and `J`,
+and we have used an instantiation of each of them in the type annotations
+on `myFunction`. Note that the type of `myFunction` does not include *any*
+generic types, it is just a function that accepts an argument and returns a
+result, both of which have a non-generic function type that we have
+obtained by instantiating a parameterized typedef. The argument type might
+as well have been declared using the traditional function signature syntax,
+and the return type (and the argument type, by the way) might as well have
+been declared using a regular, non-parameterized typedef:
+
+```dart
+typedef List<int> K(int i); // Old form, non-generic.
+K myFunction2(List<int> f(int i)) => f; // Same as myFunction.
+```
+
+The new syntax allows for using the two kinds of type parameters together:
+
+```dart
+typedef L<T> = List<T> Function<S>(S, {T Function(int, S) factory});
+```
+
+This declares `L` to be a parameterized typedef; when instantiating `L`
+with an actual type argument as in `L<String>`, it becomes the type of a
+generic function that accepts a type argument `S` and two value arguments:
+one required positional argument of type `S`, and one named optional
+argument with name `factory` and type `String Function(int, S)`; finally,
+it returns a value of type `List<String>`.
+
+## Syntax
+
+The new form of `typedef` declaration uses the following syntax (there are
+no deletions from the grammar; addition of a new rule or a new alternative
+in a rule is marked with NEW and modified rules are marked CHANGED):
+
+```
+typeAlias:
+  metadata 'typedef' typeAliasBody |
+  metadata 'typedef' identifier typeParameters? '=' functionType ';' // NEW
+functionType: // NEW
+  returnType? 'Function' typeParameters? parameterTypeList
+parameterTypeList: // NEW
+  '(' ')' |
+  '(' normalParameterTypes ','? ')' |
+  '(' normalParameterTypes ',' optionalParameterTypes ')' |
+  '(' optionalParameterTypes ')'
+normalParameterTypes: // NEW
+  normalParameterType (',' normalParameterType)*
+normalParameterType: // NEW
+  type | typedIdentifier
+optionalParameterTypes: // NEW
+  optionalPositionalParameterTypes | namedParameterTypes
+optionalPositionalParameterTypes: // NEW
+  '[' normalParameterTypes ','? ']'
+namedParameterTypes: // NEW
+  '{' typedIdentifier (',' typedIdentifier)* ','? '}'
+typedIdentifier: // NEW
+  type identifier
+type: // CHANGED
+  typeWithoutFunction |
+  functionType
+typeWithoutFunction: // NEW
+  typeName typeArguments?
+typeWithoutFunctionList: // NEW
+  typeWithoutFunction (',' typeWithoutFunction)*
+mixins: // CHANGED
+  'with' typeWithoutFunctionList
+interfaces: // CHANGED
+  'implements' typeWithoutFunctionList
+superclass: // CHANGED
+  'extends' typeWithoutFunction
+mixinApplication: // CHANGED
+  typeWithoutFunction mixins interfaces?
+newExpression: // CHANGED
+  'new' typeWithoutFunction ('.' identifier)? arguments
+constObjectExpression: // CHANGED
+  'const' typeWithoutFunction ('.' identifier)? arguments
+redirectingFactoryConstructorSignature: // CHANGED
+  'const'? 'factory' identifier ('.' identifier)?
+  formalParameterList '=' typeWithoutFunction ('.' identifier)?
+```
+
+The syntax relies on treating `Function` as a fixed element in a function
+type, similar to a keyword or a symbol (many languages use symbols like
+`->` to mark function types).
+
+*The rationale for using this form is that it makes a function type very
+similar to the header in a declaration of a function with that type: Just
+replace `Function` by the name of the function, and add missing parameter
+names and default values.*
+
+*The syntax differs from the existing function type syntax
+(`functionSignature`) in that the existing syntax allows the type of a
+parameter to be omitted, but the new syntax allows parameter names to be
+omitted. The rationale for this change is that a function type where a
+parameter has a specified name and no type is very likely to be a
+mistake. For instance, `int Function(int)` should not be the type of a
+function that accepts an argument named "int" of type `dynamic`, it should
+specify `int` as the parameter type and allow the name to be
+unspecified. It is still possible to opt in and specify the parameter name,
+which may be useful as documentation, e.g., if several arguments have the
+same type.*
+
+The modification of the rule for the nonterminal `type` may cause parsing
+ambiguities. The following disambiguation rule applies:
+If the parser is at a location L where the tokens starting
+at L may be a `type` or some other construct (e.g., in the body of a
+method, when parsing something that may be a statement and may also be a
+declaration), the parser can commit to parsing a `type` if it

[Lasse Reichstein Nielsen, 2017/07/12 12:08:07]

can commit -> must commit

It can't not commit, or we'll have nondeterministic parsing :)

[eernst, 2017/07/12 13:21:12]

Done.

+is looking at the identifier `Function` followed by `<` or `(`, or it
+is looking at a `type` followed by the identifier `Function` followed by `<`
+or `(`.
+
+*Note that this disambiguation rule does require parsers to have unlimited
+lookahead. However, if a parsing strategy is used where the token
+stream already contains references from each opening bracket (such as `<`
+or `(`) to the corresponding closing bracket then the decision can be
+taken in a fixed number of steps: If the current token is `Function` then
+check the immediate successor (`<` or `(` means yes, we are looking at
+a `type`, everything else means no) and we're done; if the first token is
+an `identifier` other than `Function` then we can check whether it is a
+`qualified` by looking at no more than the two next tokens, and we may then
+check whether the next token again is `<`; if it is not then we look for
+`Function` and the token after that, and if it is `<` then look for the
+corresponding `>` (we have now skipped a generic class type), and then
+the successor to that token again must be `Function`, and we finally check
+its successor (looking for `<` or `(` again). This skips over the
+presumed type arguments to a generic class type without checking that they
+are actually type arguments, but we conjecture that there are no
+syntactically correct alternatives (for example, we conjecture that there
+is no syntactically correct statement, not a declaration, starting with
+`SomeIdentifier<...> Function(...` where the angle brackets are balanced).*
+
+*Note that this disambiguation rule will prevent parsing some otherwise
+correct programs. For instance, the declaration of an asynchronous function
+named `Function` with an omitted return type (meaning `dynamic`) and an
+argument named `int` of type `dynamic` using `Function(int) async {}` will
+be a parse error, because the parser will commit to parsing a type after
+having seen "`Function(`" as a lookahead. However, we do not expect that it
+will be a serious problem for developers to be unable to write such
+programs.*
+
+## Scoping
+
+Consider a typedef declaration as introduced by this feature, i.e., a
+construct on the form
+
+```
+metadata 'typedef' identifier typeParameters? '=' functionType ';'
+```
+
+This declaration introduces `identifier` into the enclosing library scope.
+
+Consider a parameterized typedef, i.e., a construct on the form
+
+```
+metadata 'typedef' identifier typeParameters '=' functionType ';'
+```
+
+Note that in this case the `typeParameters` cannot be omitted. This
+construct introduces a scope known as the *typedef scope*. Each typedef
+scope is nested inside the library scope of the enclosing library. Every
+formal type parameter declared by the `typeParameters` in this construct
+introduces a type variable into its enclosing typedef scope. The typedef
+scope is the current scope for the `typeParameters` themselves, and for the
+`functionType`.
+
+Consider a `functionType` specifying a generic function type, i.e., a
+construct on the form
+
+```
+returnType? 'Function' typeParameters parameterTypeList
+```
+
+Note again that `typeParameters` are present, not optional. This construct
+introduces a scope known as a *function type scope*. The function type
+scope is nested inside the current scope for the associated `functionType`.
+Every formal type parameter declared by the `typeParameters` introduces a
+type variable into its enclosing function type scope. The function type
+scope is the current scope for the entire `functionType`.
+
+*This implies that parameterized typedefs and function types are capable of
+specifying F-bounded type parameters, because the type parameters are in
+scope in the type parameter list itself.*
+
+## Static Analysis
+
+Consider a typedef declaration as introduced by this feature, i.e., a
+construct on the form
+
+```
+metadata 'typedef' identifier typeParameters? '=' functionType ';'
+```
+
+It is a compile-time error if a name *N* introduced into a library scope by
+a typedef has an associated `functionType` which depends directly or
+indirectly on *N*. It is a compile-time error if a bound on a formal type
+parameter in `typeParameters` is not a type. It is a compile-time error if
+a typedef has an associated `functionType` which is not a type when
+analyzed under the assumption that every identifier resolving to a formal
+type parameter in `typeParameters` is a type. It is a compile-time error if
+an instantiation *F<T1..Tk>* of a parameterized typedef is mal-bounded.
+
+*This implies that a typedef cannot be recursive. It can only introduce a
+name as an alias for a type which is already expressible as a
+`functionType`, or a name for a type-level function F where every
+well-bounded invocation `F<T1..Tk>` denotes a type which could be expressed
+as a `functionType`. In the terminology of
+[kind systems](https://en.wikipedia.org/wiki/Kind_(type_theory)), we
+could say that a typedef can define entities of kind ` * ` and of kind
+` * -> * `, and, when it is assumed that every formal type parameter of the
+typedef (if any) has kind ` * `, it is an error if the right hand side of the
+declaration denotes an entity of any other kind than ` * `; in particular,
+declarations of entities of kind ` * -> * ` cannot be curried.*
+
+It is a compile-time error if a name declared in a typedef, with or without
+actual type arguments, is used as a superclass, superinterface, or mixin. It
+is a compile-time error if a generic function type is used as a bound for a
+formal type parameter of a class or a function. It is a compile-time error if
+a generic function type is used as an actual type argument.
+
+*Generic function types can thus only be used in the following situations:*
+
+- *as a type annotation on an local, instance, static, or global variable.*
+- *as a function return or parameter type.*
+- *in a type test.*
+- *in a type cast.*
+- *in an on-catch clause.*
+- *as a parameter or return type in a function type.*
+
+*The motivation for having this constraint is that it ensures that the Dart type
+system admits only predicative types. It does admit non-prenex types, e.g.,
+`int Function(T function<T>(T) f)`. From research into functional calculi
+it is well-known that impredicative types give rise to undecidable subtyping,
+e.g.,
+[(Pierce, 1993)](http://www2.tcs.ifi.lmu.de/lehre/SS07/Typen/pierce93bounded.pdf),
+and even though the Dart type system is very different from F-sub, we cannot
+assume that these difficulties are absent.*
+
+## Dynamic Semantics
+
+The addition of this feature does not change the dynamic semantics of
+Dart.
+
+## Changes
+
+2017-May-31: Added constraint on usage of generic function types: They
+cannot be used as type parameter bounds nor as type arguments.
+
+2017-Jan-04: Adjusted the grammar to require named parameter types to have
+a type (previously, the type was optional).
+
+2016-Dec-21: Changed the grammar to prevent the new function type syntax
+in several locations (for instance, as a super class or as a mixin). The
+main change in the grammar is the introduction of `typeWithoutFunction`.
+
+2016-Dec-15: Changed the grammar to prevent the old style function types
+(derived from `functionSignature` in the grammar) from occurring inside
+the new style (`functionType`).