Added informal generic method syntax and generic function type specs.

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

+# Feature: Generic Function Type Alias
+
+**Status**: Under implementation.

[floitsch, 2017/06/01 09:28:02]

Implemented.

[eernst, 2017/07/06 10:02:13]

Done.

+
+**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`.  This feature is being introduced into Dart starting Q4, 2016.
+
+**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
+declaration itself, as well as in the declared type. 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 everywhere a type is expected, including
+type annotations, return types, actual type arguments, and formal type
+parameter bounds. Currently there is no way to specify a generic function
+type in these situations. Even in the case where a generic 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. 
+
+*We may deprecate the old form after a while, or we may choose
+to keep it, because it is more concise. We may even change the old form to
+allow omitting the name and not the type when only one identifier is
+specified, if this is not too much of a breaking change. As an intermediate
+step we could change the old form to always require both the type and the
+name, such that no type expressions will silently change meaning.*
+
+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 type-level
+function: It accepts a type argument at compile time and returns a type,
+which may be used, say, as a type annotation. 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;
+```
+
+Here, 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. We intend to handle them by the following disambiguation rule
+in the parser: 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 by detecting that it
+is looking at the identifier `Function` followed by `<` or `(`, or that 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 "diet 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` are present, not optional. 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`. Following
+[common terminology](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.
+
+## Dynamic Semantics
+
+The addition of this feature does not change the dynamic semantics of
+Dart.
+
+## Changes
+
+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`).