Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Issues with local functions: spec incorrect, mutual recursion not possible. #315

Closed
rakudrama opened this issue Nov 3, 2011 · 4 comments
Assignees
Labels
area-language Dart language related items (some items might be better tracked at github.com/dart-lang/language).
Milestone

Comments

@rakudrama
Copy link
Member

(Filing as defect because the spec / implementation do not agree.
Happy if it gets retriaged as a feature request.)

Local function do not currently permit mutual recursion.
I expected this function to work as an alternative to print, but doing a nicer job for Lists.

pr(thing) {
  var out = [];
  printOne(thing) {
    if (thing is List)
      printList(thing); // ←
    else
      out.add(thing.toString());
  }
  printList(list) {
    var sep = '';
    out.add('[');
    for (thing in list) {
      out.add(sep);
      printOne(thing);
      sep = ',';
    }
    out.add(']');
  }
  printOne(thing);
  print(Strings.concatAll(out));
}

It does not run because printList is not in scope in the body of printOne.

Alternatives are (1) declaring the functions as local variables and assigning closures to them or (2) writing a class.
Both seem like needless make-work that is unnecessary in JavaScript and many other languages.

The spec and the three implementations do not agree local functions.

The spec says a function declaration of the form id(T1 a1, …, Tn an, [Tn+1 xn+1 = d1, …, Tn+k xn+k = dk]){s} is equivalent to a variable declaration of the form final F id = (T1 a1, …, Tn an, [Tn+1 xn+1 = d1, …, Tn+k xn+k = dk]){s} where F is the function type alias typedef F(T1 a1, …, Tn an, [Tn+1 xn+1, …, Tn+k xn+k])

This desugaring is incorrect for local functions (and too restrictive IMO.)
var x;
final f = () { x = f; }; // by rule above, desugaring of f() { x = f; }
f();
The VM and compilers complain that the reference to f in the closure body is not declared in the scope, which agrees with how I read the scope rules.

However,

var x;
f() { x = f; }
f();
will run and assigns the closure for f to x.
Further, the VM prohibits f = null; saying f is not assignable.
So it is not possible to express local functions purely as syntactic sugar.
The rewrite is rather:

var f;
f = () { x = f; };
//! magically f becomes final.

Several times now I have stumbled across the restriction that local functions cannot be mutually recursive, like the print example.
f() {... g() ...}
g() {... f() ...}
becomes:
var f;
f = () {... g() ...}; // < g is not in scope.
//! magically f becomes final.
var g;
g = () {... f() ...};
//! magically g becomes final.

I think it would be enormously useful if adjacent local functions were de-sugared as a block:

var f;
var g;
f = () {... g() ...};
g = () {... f() ...};
//! magically f and g become final.

This would permit most practical local mutual recursion and still provide the security that all 'final' variables (magical and non-magical) have been initialized before being referenced.

@gbracha
Copy link
Contributor

gbracha commented Nov 3, 2011

Added Accepted label.

@gbracha
Copy link
Contributor

gbracha commented Mar 8, 2012

All true. The current spec is incorrect, as pointed out, because the rewritten code is violates the rule that a variable's initializer may not refer to the variable. It would be nice to relax the scope rules for closures to allow mutual recursion.

@anders-sandholm
Copy link
Contributor

Added this to the M1 milestone.

@gbracha
Copy link
Contributor

gbracha commented Sep 10, 2012

 We've taken another look at this, and decided to keep the semantics as intended. The spec has been fixed to reflect this. So now we have a correct spec, but mutual recursion iss till not possible. This is easily dealt with on the rather rare occasions where this comes up.


Added Done label.

This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-language Dart language related items (some items might be better tracked at github.com/dart-lang/language).
Projects
None yet
Development

No branches or pull requests

4 participants