Need clarification about instantiation of local and top level functions

[stereotype441]

All of the discussion in the language spec about closurization refers specifically to closurizing instance methods. However, it appears that static methods, top level functions, and local functions are also allowed to be closurized, as illustrated by the test below, which passes on the VM, dart2js, and DDC:

import 'package:expect/expect.dart';
int f(int i) => i + 1;
class C {
  static int f(int i) => i + 2;
  int g(int i) => i + 3;
}
main() {
  int h(int i) => i + 4;
  int Function(int) func;
  func = f;
  Expect.equals(func(10), 11);
  func = C.f;
  Expect.equals(func(10), 12);
  func = new C().g;
  Expect.equals(func(10), 13);
  func = h;
  Expect.equals(func(10), 14);
}

In particular, the closurization of local functions seems to contradict the commentary text that says:

Closures derived from members via closurization are colloquially known as tear-offs.

The question arose in the code review of https://dart-review.googlesource.com/c/sdk/+/29744, which adds the ability for the front end to implicitly instantiate generic parameters when performing closurization of a method/function, e.g.:

import 'package:expect/expect.dart';
T f<T extends num>(T i) => i + 1;
class C {
  static T f<T extends num>(T i) => i + 2;
  T g<T extends num>(T i) => i + 3;
}
main() {
  T h<T extends num>(T i) => i + 4;
  int Function(int) func;
  func = f;
  Expect.equals(func(10), 11);
  func = C.f;
  Expect.equals(func(10), 12);
  func = new C().g;
  Expect.equals(func(10), 13);
  func = h;
  Expect.equals(func(10), 14);
}

It would be helpful to have clarification on the following questions:

• Is it intended that closurization be possible with instance methods, static methods, top level functions, and local functions? Or should some of the code in the first example lead to an error?
• Is it intended that implicit instantiation of closurizations be possible with instance methods, static methods, top level functions, and local functions? Or should some of the code in the second example lead to an error?
• Is "tear-off" synonymous with "closurization" or does "tear-off" only refer to cases where a class member has been closurized?

CC: @leafpetersen @lrhn @kmillikin

[leafpetersen]

The short answer is that my understanding is that yes, that test should pass.

For all of the syntactic constructs that you mention there, an escaping occurrence is allowed (but not required) to produce a value which has a different identity from the original thing, but is required to be equal to the original thing. Tearoff is an odd name for it when it's not a method, and I wouldn't usually expect the non instance method uses to produce a new value at that site, but the spec allows it, as best I understand it.

All of those places are also the places where we intend to allow inference to fill in a partial instantiation. The reasoning is that partial instantiation also changes the identity, and so limiting it to "closurization" sites avoids surprising users with an unexpected and syntactically invisible change in identity (or at least, not more unexpected and syntactically invisible than it already was).

At least, that's my understanding of it, from discussions with various folks, and I believe that's the intent of the spec.

[lrhn]

I agree that the test should pass.

The specification says, about the identifier expression e denoting a declaration d:

• If d is a static method, top-level function or local function then e evaluates to the function defined by d.

And about getter access:

If method lookup succeeds then i evaluates to the closurization of method f on object o
(16.18.7)

A static function declaration (class-scoped or top-level) always has the same run-time-scope, so no matter how many times you closurize it, the resulting function will do the same thing. For that reason, we treat static methods as compile-time constants and canonicalize their function values. The spec is explict about that - you get identical function values when you refer to a static function multiple times.

I don't remember where the spec says what the equality is of the function values of local function declarations (or if it says anything at all). A quick check suggests that implementations, at least VM and dart2js, also canonicalizes the function values of local function declarations per run-time scope.
That is:

main() {
  foo() {}
  print(identical(foo, foo)); // prints "true".
}

Instance methods don't live in a run-time scope, but they do close over this, so they are equivalent (==) if it's the same method torn from the same object. We could go for identity here too, but that would require caching per instance, so we don't. (Static functions only requires one cache cell per function, and it's statically detectable whether it's necessary, and for local functions, it's very locally detectable whether the function value is used or not).

I also agree that instantiating a generic function should work the same no matter where the generic function comes from, as long as you refer to a function declaration. We do not expect the following to work:

T Function<T>(T) id = <T>(T x) => x;
int Function(int) add0 = id; 

Here the assignment of a generic function to an instantiated type isn't referencing a function declaration, just a variable holding a function value.

[kmillikin]

I don't agree that the existing spec is actually clear about this. It defines functions as various bits of syntax:

Functions include function declarations (9.1), methods (10.1, 10.7), getters (10.2), setters (10.3), constructors (10.6) and function literals (16.10).

Then the spec refers to functions as if they were objects in ways that don't make sense at all if we interpret them as syntax. I have always read these latter references to mean some kind of value that represents a syntactic function in a context. There is wiggle room in what that value is.

None of the implementations are really canonicalizing anything. They're just treating the local function declaration as if it were:

main() {
  final foo = () {};
  print(identical(foo, foo));
}

With different scope rules for the right-hand side of the variable declaration so that foo is in scope there. I mean, this is canonicalized in a sense, but not by creating a tear-off at the first occurrence of foo and remembering it to make sure to use it again. Nothing at all happens at the uses of foo except a variable reference.

Inspecting the code of dart2js, DDC, and the VM shows that they currently handle local functions uniformly with function-valued local variables.

[leafpetersen]

cc @rakudrama

Stephen feels that it would be easier to implement this if we didn't allow partial instantiations of .call, so that not all functions need to support partial instantiation.

I'm fine with this restriction, we can always relax it later if desired.

[leafpetersen]

For context DDC supports partial instantiation of any generic function typed thing. We (the language team) agreed to restrict this to places where there was already an implicit change in identity (or at least, where an implicit change in identity was already allowed). My understanding (possibly incorrect) was that the places where an implicit change in identity is allowed by the spec are:

• closurization of methods
• escaping occurrences of top level functions
• escaping occurrences of static methods
• escaping occurrences of method local functions

Is the disagreement about which of the above already (in Dart 1.0) admit (but not require) a change in identity?

I'm happy to drop local functions from the list of allowed partial instantiations, I don't think it's very useful. Eliminating any of the others would be fairly unfortunate.

In general, it's quite convenient to be able to use polymorphic functions monomorphically.

[lrhn]

I'm not sure what "partial instantiation of .call" means here.
Is it:

class Id {
   T call<T>(T x) => x;
}
main() {
  var idder = new Id();
  int Function(int) intId = idder;  // and not: `= idder.call`
}

If we say that callable objects are not functions, but assignment to a function type is equivalent to a tear-off of the call method, then it should be equivalent to = idder.call, and that is a tear-off.

Or is the problem with the implicit call method on function values, so you can do:

T Function<T>(T) id = <T>(T x) => x;
int Function(int) intId = id.call;

That allows partial instantiation of any function, not just function declarations.

Whatever we do, we should be consistent.
If we allow other instance methods to be instantiated at tear-off, then we should allow it for the instance method named call too.
If we say that function values have a call method, then it should work for that too.

My personal preference is to make call an operator, so we don't get into these silly problems to begin with, but barring that, maybe say that function values do not have a call method. Functions values is a thing in their own, and the spec will tell you how to invoke them, not say that method invocation is the only kind of invocation, and every other invocation is an implicit invocation of a (possibly synthetic) call method.

[lrhn]

• closurization of methods
• escaping occurrences of top level functions
• escaping occurrences of static methods
• escaping occurrences of method local functions

Is the disagreement about which of the above already (in Dart 1.0) admit (but not require) a change in identity?

"Change in identity" is not how I would phrase it.

Instance methods do not have identity separate from the object they are on. They only gain identity when being torn off. We chose not to canonicalize them, just ensure equality if you tear the same method of the same object twice. (That's because of the general rule of not requiring an open-ended number of objects to be canonicalized, and this would require caching the method per instance of the class).

Top-level function and static functions do not "change identity" because for each, there is only one object representing them. You can say that it's a place where you go from function declaration to function value. We do canonicalize the values - the same static/top-level function declaration referred to twice gives the same object, so there is no difference in identity. (The specification actually doesn't say that, it's just something we decided at some point, but it was never written down formally).

Local functions are treated like top-level functions, except it's a different function declaration each time its surrounding scope is entered (since that changes the variables it closes over). This is not specified anywhere, but we probably want to keep it that way.

So, all of these are situations where a function declaration is referred to and it creates a function value. The value-identity of these values is not really important, it's the declaration-to-value, or name-to-value, transition that is common to them, and why we want those places as generic partial instantiation points. It's something you do to a name. The alternative is to do it to a value, and then it should work on all generic function values.

[leafpetersen]

Or is the problem with the implicit call method on function values, so you can do:

yes, I believe this is what @rakudrama was concerned about: every function value needs to be support partial instantiation.

My personal preference is to make call an operator, so we don't get into these silly problems to begin with, but barring that, maybe say that function values do not have a call method.

I'd be very happy to get rid of call methods on functions, but suspect that we don't have budget for this. There's some code somewhere that uses .call on a dynamic thing which includes function objects.

"Change in identity" is not how I would phrase it.

It may not be how you'd phrase it, but I think it's how you just described it. @floitschG was the one who initially proposed this restriction, so you could ask him for his perspective, but based on your description above, I believe that the following captures the spec requirements:

class A {
  void method() {}
}
void global() {};
void test() {
  void local() {}
  var a = new A();
  // Either answer is spec compliant
  assert(identical(global, global) || !identical(global, global)); 
  assert(identical(local, local) || !identical(local, local));
  assert(identical(a.method, a.method) || !identical(a.method, a.method));
  var closure = () {};
  // Must be identical
  assert(identical(closure, closure));
}

The motivation that was presented to me for restricting partial instantiations to the first set of cases (plus static methods, I didn't put them in there) was that the spec already didn't specify identity for those cases.

[kmillikin]

I don't like an operational semantics that cares about declarations because declarations are not first class.

This code:

test() {
  T id<T>(T x) => x;
  return () {
    int Function(int) f = id;
    String Function(String) g = id;
    // ...
  };
}

looks like the nested function has a free variable of type T Function<T>(T) and a programmer would (reasonably) expect that they could define a helper function like:

help(T id<T>(T)) {
  int Function(int) f = id;
  String Function(String) g = id;
  // ...
}

test() {
  T id<T>(T x) => x;
  return help(id);
}

but that doesn't seem to work.

[leafpetersen]

I don't like an operational semantics that cares about declarations because declarations are not first class.

I don't particularly care for it either (hence the initial DDC implementation not making this restriction :), but Dart 1.0 already seemed to care:

void foo() {}
void main() {
  // My understanding is that either answer is Dart 1.0 spec compliant
  assert(identical(foo, foo) || !identical(foo, foo)); 
  var f = foo;
  // This identity must hold
  assert(identical(f, f));
}

So I believe the argument was that making this restriction would make the change in identity less surprising moving from Dart 1.0 to 2.0.

[lrhn]

void foo() {}
void main() {
  // My understanding is that either answer is Dart 1.0 spec compliant
  assert(identical(foo, foo) || !identical(foo, foo)); 
}

It was decided at some point that identical(foo, foo) must be true. The foo is a compile-time constant, and even if the specification did not (and does not) say that it's canonicalized, we did decide that it is (and we should make sure the Dart 2 spec says so too).

[leafpetersen]

It was decided at some point that identical(foo, foo) must be true.

Ah, well then, I don't have anything else. :)

Is the following then what is intended, or should local functions also move down to the "must be identical" category?

class A {
  void method() {}
  static void staticMethod() {}
}
void global() {};
void test() {
  void local() {}
  var a = new A();
  // Either answer is spec compliant
  assert(identical(local, local) || !identical(local, local));
  assert(identical(a.method, a.method) || !identical(a.method, a.method));
  var closure = () {};
  // Must be identical
  assert(identical(A.staticMethod, A.staticMethod)); // ?? 
  assert(identical(global, global)); 
  assert(identical(closure, closure));
}

[lrhn]

The guiding principle was to canonicalize where possible, but never in a way that would require unlimited caching when there is no local way to detect whether it's necessary.

That means that dereferencing static functions (top-level or class-level static) should always give the same result. That requires at most one value cache per source location.

We specifically did not require instance methods to give identical values for separate tear-offs. That would require a cache entry per instance, which is theoretically unbounded.

The closure above is trivial, it's a value stored in a variable. All values are identical to themselves.

That leaves just the local function, which I don't think we considered at the time.
I would say that we should make dereferencing a local function return identical values every time it's done (per instance of the scope that the function is declared in). It seems like it would require unbounded caching again, but it's statically detectable whether the function is ever accessed as a value (more than once), and it's possible to do a local rewrite of the function into:

void foo() { ... }
var $foo = foo;

or

var foo = () { ... };  // if not a recursive function, otherwise separate decl and assignment.

and make all value-accesses to foo use $foo instead. That's the code I would write anyway, if the language doesn't promise canonicalization, I'll have to start writing the code when I dereference a function more than once (and I already did because we haven't promised it).

So, to help users, all value-accesses to function declarations should "canonicalize", tear-offs of instance methods should create == function values, and closure expressions generate a completely new function every time (because a function expression is only evaluated once in the scope it's in).

[kmillikin]

I would say that we should make dereferencing a local function return identical values every time it's done (per instance of the scope that the function is declared in). It seems like it would require unbounded caching again,

As I said above, none of the implementations treat a reference to a local function as constructing a closure at the point of the reference. Rather, the value of the local function is the closure itself (it's "eagerly torn off"). They treat your declaration as if it were:

final void Function() foo = () { ... };

with a different scoping rule that allows foo to be in scope for its initializer, which is always a function expression so foo will be initialized before it can ever be applied. identical works for free and you'd have to have a special case to break it.

[lrhn]

@kmillikin Yes, we already do what I propose, I just suggest that we formalize it in the specification as well (and make sure that any future implementation can still handle it efficiently, even if they pick a different implementation strategy).

We will need to handle generic instantiation like:

foo() {
  T id<T>(T x) => x;  // Local generic function declaration.
  int Function(int) intId() => id;
  T Function(T) tId<T>() => id;  // specialize id to <T>.
  var id = intId();
  var id2 = tId<int>();
  print(identical(id, id2));  // Likely not identical.
}

[leafpetersen]

cc @crelier @sjindel-google

[eernstg]

I've created a dartLangSpec.tex CL for clarifying that tear-offs are supported for all kinds of functions, not just instance methods. This should not be controversial, and implementations have been doing this "forever" anyway. There was even an old comment in dartLangSpec.tex whose wording does not make sense without this feature, so obviously that has been intended to work all the time.

The generic part is more controversial. Samir told me that generic function instantiation (where type arguments are passed and the result is a non-generic function) cannot readily be supported for all kinds of functions. In particular, the VM approach will work just fine for generic function instantiation on instance methods, and it may work on global and static functions, but it does not work well on local functions.

We may wish to push on and simply say "this must work, but it's not yet implemented", or we may decide that Dart simply does not support all cases, or we may decide that a simplistic source-2-source implementation (that may perform less well, and for which we need to think carefully about identity and equality) is acceptable.

Note that generic function instantiation on local functions may not be very important, because you'd just write a non-generic function there anyway (because the relevant type variables are already in scope). So maybe it's not much of a problem to say (1) this is not supported, or (2) we'll settle for a slow & naive translation.

That discussion can go to the comment track of an upcoming CL where I'm adding a new feature spec on generic function instantiation.

[sjindel-google]

Thanks for the update. Please keep us posted on the progress of the upcoming CL.

Let's remember that the source-to-source translation will require copying the default values from the callee into the wrapper function. There's a discussion of the problems with this here: #31027.

[kmillikin]

This should not be controversial, and implementations have been doing this "forever" anyway.

It is somewhat controversial, because as I said above a few times, implementations have not been doing this at all. None of them.

What all the implementations have implemented: local function declarations introduce a binding from the name to a function value. Evaluating an identifier in a scope where it is the name of a local function works exactly the same as evaluating an identifier in a scope where it is the name of a local variable. It's just looked up in some environment.

Your CL introduces the idea of closurization of a declaration. This is new (before we only had closurization of methods) and is not currently done in any implementation. If we want to go down this path (I hope we don't) we have to define closurization of a declaration. We'll need some new machinery for this because we can't just say it's as if the programmer wrote a function expression.

(Specifically, I don't think you can say that the closurization of the function declaration f() {} is equivalent to () => f() because the evaluation of the call to f in there is defined to evaluate f which is now defined to closurize the declaration of f which is equivalent to () => f()....)

[eernstg]

implementations have not been doing this at all. None of them.

When I said 'not controversial', I was referring to the ability to evaluate a reference to a global/static/local function and obtain a function object which could subsequently be passed around (assigned to variables, etc) and invoked, e.g.,

import 'package:expect/expect.dart';
int f(int i) => i + 1;
class C {
  static int f(int i) => i + 2;
}
main() {
  int h(int i) => i + 4;
  int Function(int) func;
  func = f;
  Expect.equals(func(10), 11);
  func = C.f;
  Expect.equals(func(10), 12);
  func = h;
  Expect.equals(func(10), 14);
}

Do we have an implementation that does not support this? I thought you already verified that it works everywhere.

What all the implementations have implemented: local function
declarations introduce a binding from the name to a function value

OK, so let's consider locals in particular.

It sounds like void f() => print('x'); would be specified to work like void Function() f = () => print('x');. But I would consider that to be a perfectly legitimate implementation choice. With this implementation, evaluation of f would amount to a local variable read operation, and that variable holds the value which is obtained from evaluation of a function literal, and that evaluation amounts to a closurization (of an inline declaration, which is the function literal itself). So it's a matter of allowing implementations to pre-compute and cache the closurization, it doesn't magically remove the need for a closurization of a declaration in the first place. Also, I don't see how that would conflict with the spec (including the CL).

So the semantics you describe is a perfectly legitimate way to implement the spec (relative to what I intended to specify — if the spec actually says something else then I'd need to fix it).

However, an implementation could also do "lambda lifting" on local functions to make them global, and then pass more arguments at call sites (maybe some variables in the environment aren't used anyway, or maybe we could use some kind of block move to set up a bunch of arguments to that lambda-lifted function more quickly than regular argument passing), and then we might get better performance by not having a heap representation at all for local functions that aren't used as first class values.

So I'd say that it is not an obviously good idea to specify local functions in terms of the expansion to a local variable, because that would (probably) preclude some optimizations.

For other functions than local ones, we'd need to specify a similar operation, for instance:

// Surface level declarations can declare functions.
void foo(int i) => print(i);

// Semantically, we would say that this declaration is just sugar for the
// following variable declaration, such that the function object is always
// available.
const void Function(int) foo = (int i) => print(i);

We would have to require the value to be const in order to support the same constant expressions as today, so we would need to introduce function literals as const values (which has been discussed many times, but never landed).

We might need to resolve some conflicts between the constness and the need to create cycles (for mutually recursive functions), too.

In any case, we have then again reduced one kind of function declaration to a variable and a function literal, so we still need to specify closurization of at least one kind of declaration, namely function literals.

I suspect that we might still get some problems if we insist that every function declaration (except instance methods) is just sugar for a variable and a function literal. In particular, we would rely on type inference which gives preference to the type-from-context in order to give those function literals the declared return type at all, and this means that we cannot really say anything about it in today's language specification (and it seems overly complex to re-establish the return type like that, if we could easily specify a sufficiently precise semantics for closurization of all kinds of function declarations).

[eernstg]

I've created a proposal for a new feature specification about the generic parts of the topics of this issue, complementing the CL about tear-offs which updates dartLangSpec.tex to support the non-generic parts.

I'm currently adding a missing part to the feature specification: It needs to say that generic function instantiation is supported for instance methods.

Note that the dartLangSpec.tex CL also needs an extension: It does not yet explicitly specify the notion of a closurization, nor the notion of a function object.

[eernstg]

Note that I've modified the feature spec of generic function instantiation to specify that local functions are supported as well. Some reasons for that change are given in a comment on patch set 15.

[eernstg]

FYI: Said feature spec was landed in July in b8098e9.
Also, the following is no longer true as of 543d877 (May 2018):

All of the discussion in the language spec about closurization refers
specifically to closurizing instance methods

For the questions originally posed in this issue, we have some answers:

• Is it intended that closurization be possible with instance methods,
  static methods, top level functions, and local functions? Or should some
  of the code in the first example lead to an error?

Yes, closurization applies to all functions. No errors.

• Is it intended that implicit instantiation of closurizations be possible with
  instance methods, static methods, top level functions, and local functions?
  Or should some of the code in the second example lead to an error?

Yes, generic function instantiation applies to all kinds of functions as well, no errors.

• Is "tear-off" synonymous with "closurization" or does "tear-off" only refer to
  cases where a class member has been closurized?

"Tear-off" is not normative, but I see no reason why it shouldn't be usable with all kinds of functions. There is no reason to assume that a library function or static method would have a corresponding function object unless a property extraction like C.myStaticMethod or an identifier myLibraryFunction is evaluated, that is, we are actually doing something, and then I don't see why we shouldn't call that "to tear off the function".

@stereotype441, I suspect that we can close this issue. Could you take a look and see if you agree? Maybe the remaining bits and pieces, if any, should go into new issues, just so they don't disappear in the sheer volume of stuff here?