Recursive closure?

[Chris Buckett]

Hi, I just found myself writing a recursive closure, but I get an
error if I try to refer to the variable which contains the closure
from within the closure.

For example - this gives me an error:;
var myFunc = () {
if (foo) {
myFunc();
}
else {
//recurse back out
}
};
myFunc(); //start everything running

This gives a warning "cannot resolve myFunc()"



but I can do it using a temporary variable to first store the function


var myFunc = null; //create the function variable
var tmpFunc = () { //setup the function in a temp variable
if (foo) {
myFunc(); //call the function variable
}
else {
//recurse back out
}
};
myFunc = tmpFunc; //assign the tmp to the real function variable
myFunc(); //start everything running


Is this expected behaviour?

Cheers,
Chris.

[Ladislav Thon]

Hi,  I just found myself writing a recursive closure, but I get an
error if I try to refer to the variable which contains the closure
from within the closure.

Not sure about your problem, but the following worked for me:

main() {

  var myFun = fact(i) => i > 1 ? i * fact(i - 1) : 1;

  var fact = myFun(5);

  print("fact 5 = $fact");

}

LT

[Justin Fagnani]

I don't think so. I saw a check-in recently, maybe to Frog, that fixed
a bug like this. Are you running with Frog, dartc, or the VM?

-Justin

>
> Cheers,
> Chris.

[Chris Buckett]

This is on dart editor build 4349 on windows, running as a script (so dart vm), and also occurs here:  http://try.dartlang.org/s/_zIs 

I'll try with the latest dart editor build, and if it still fails, I'll raise a bug.

Cheers,

Chris.

[Stephen Adams]

On Tue, Feb 21, 2012 at 1:39 PM, Chris Buckett <chrisb...@gmail.com> wrote:

You should also be able to define the function directly:

myFunc() {

   if (foo) {
       myFunc();
   }
   else {
       //recurse back out
   }
};
myFunc(); //start everything running

[Chris Buckett]

Thanks - I didn't realise I could define a named function directly
within another function. I thought I had to assign it to a variable.

(for reference to others, this is a working version of my initial
sample by declaring the function directly).
http://try.dartlang.org/s/TXcs <--- working, but without the var
(and this was the one not working)
http://try.dartlang.org/s/_zIs <-- not working - with the var.

Cheers,
Chris.

[poltomb]

So the problem here is that he is attempting to refer to a variable
outside the scope of the closure:
main() {
  var myFunc = (foo) => {
    if (foo) myFunc();
  }
}

Ladislav's example works, because the closure name is within the scope
of the closure:

main() {
  var myFun = fact(i) => i > 1 ? i * fact(i - 1) : 1;
  var fact = myFun(5);
  print("fact 5 = $fact");
}

Whereas if he were to change it to below, it would cause a compilation
error:
main() {
  var myFun = fact(i) => i > 1 ? i * myFun(i - 1) : 1;

  var fact = myFun(5);
  print("fact 5 = $fact");
}

This example also works, because it is using a named closure, like
Ladislav's example:
main() {
bool blah = false;
myFunc() { //no var myFunc= () ...
print("in myfunc");
if (blah) {
myFunc();
}

};

myFunc();
}


I guess the moral of the story is, if you are going to call the
closure from within itself, it must be named (as in Ladislav's
example) and not anonymous (as in Chris's Example).

On Feb 21, 4:06 pm, Chris Buckett <chrisbuck...@gmail.com> wrote:
> Thanks - I didn't realise I could define a named function directly
> within another function.  I thought I had to assign it to a variable.
>
> (for reference to others, this is a working version of my initial

> sample by declaring the function directly).http://try.dartlang.org/s/TXcs <--- working, but without the var
> (and this was the one not working)http://try.dartlang.org/s/_zIs  <-- not working - with the var.

[Chris Buckett]

I've been thinking about this some more, and I'm not sure that

var myFunc = () {
myFunc();
}

should ever work,

as it's effectively the same as

var i = i;
which I wouldn't expect to work either, as i hasn't yet finished being
declared when it's being referenced. The same goes with myFunc above
- the var hasn't finished being declared, but it's being referenced.

Cheers,
Chris.

[A Matías Quezada]

I think the problem here is than the variable myFunc does not exist when the clousure is created

var myFunc = () {

   if (foo) {
       myFunc();
   }
   else {
       //recurse back out
   }
};

Is executed as...

create closure X with body () {
   if (foo) {
       // What is my funct? it does not exists nowhere yet

       myFunc();
   }
   else {
       //recurse back out
   }
};

create variable myFunc
assing closure X to myFunc

now myFunc exists, but when the closure was created it did not so the closure does not know which variable to refer, its not like javascript where

var funct = function() {
  funct();
}

is executed as

create variable funct;
create closure X with body function() {
  // funct exists but it is null, now I know which variable I'm referencing
  funct();
}
assing closure X to funct;

now funct has a closure and closure has funct.

[A Matías Quezada]

Ladislav solution works because he has a named closure.

myFunc() {
   myFunct();
}

Is executed as...

create closure myFunct with body () {
  // Ok, I know you are referencing myself
  myFunct();
}

[poltomb]

So what you are saying is that in the example:

main() {

var myFunc = (foo) {
   if (foo > 0) {
 myFunc(foo - 1);
   }
    else {
       //recurse back out
   }
};
myFunc(5);
}

the compiler cannot tell that myFunc has been declared, and thus
cannot dynamically invoke the closure that (eventually) is contained
in myFunc. That smells like a bug. I would assume that there would
be a sort of lazy evaluation of the variable myFunc(foo - 1); line.
In a dynamic language, shouldn't this be the case? Does the call site
need to be bound at compile time? By the time myFunc(5); is executed,
myFunc has been fully declared. Then, by extension, by the time
myFunc(foo - 1); is called for the first time, myFunc has been fully
declared.


(Forgive me if I am using improper terminology, as I am new to the
compiler lingo.)

[Bob Nystrom]

I'm coming to this thread late so forgive me if I repeat something already said...

On Wed, Feb 22, 2012 at 12:36 PM, poltomb <paul.bjo...@gmail.com> wrote:

So what you are saying is that in the example:

main() {

 var myFunc = (foo) {
    if (foo > 0) {
      myFunc(foo - 1);
     }
     else {
        //recurse back out
    }
 };
 myFunc(5);
}

the compiler cannot tell that myFunc has been declared,

It could, but it's specified not to. It's a question of scope. When a variable declaration has an initializer, that expression is evaluated in a scope before the variable is declared. So if you have code like:

var a = b + c;

That is interpreted a bit like:

1. Evaluate b + c.

2. Declare variable a.

3. Assign result of 1 to 2.

That means that when you're evaluating the initializer, the name of the variable you're about to declare hasn't been bound yet. This is good, because if it was available, what would it's value be?

var a = a;

print(a);

What should that do?

 

and thus cannot dynamically invoke the closure that (eventually) is contained
in myFunc.  That smells like a bug.

It's a feature. :) For what it's worth, most functional languages work this way as far as I know.

 

I would assume that there would be a sort of lazy evaluation of the variable myFunc(foo - 1); line.

It's not lazy evaluation, but, yes, most language have special support to allow recursive calls. In JavaScript, this is "hoisting". In C it's forward declarations. Dart has something similar for function declarations, but not for function expressions. So this works:

main() {

  countdown(i) {

    print(i);

    if (i > 0) countdown(i - 1);

  }

  countdown(10);

}

But this does not:

main() {

  var countdown = (i) {

    print(i);

    if (i > 0) countdown(i - 1);

  }

  countdown(10);

}

Does the call site need to be bound at compile time?

Yes, exactly right. Because Dart (like most languages) is lexically scoped, it needs to be able to resolve an identifier's binding statically. 

- bob

[Jan]

var a = a;

print(a);

What should that do?

var a = null;

a = a;

print(a); // null

I'm probably missing the point here

[Josh Gargus]

On Wed, Feb 22, 2012 at 12:46 PM, Bob Nystrom <rnys...@google.com> wrote:

It's not lazy evaluation, but, yes, most language have special support to allow recursive calls. In JavaScript, this is "hoisting". In C it's forward declarations. Dart has something similar for function declarations, but not for function expressions. So this works:

main() {

  countdown(i) {

    print(i);

    if (i > 0) countdown(i - 1);

  }

  countdown(10);

}

But this does not:

main() {

  var countdown = (i) {

    print(i);

    if (i > 0) countdown(i - 1);

  }

  countdown(10);

}

That makes sense.  Just to make sure, this should work, right?

main() {
  var countdown;

  countdown = (i) {

    print(i);

    if (i > 0) countdown(i-1);

  }

  countdown(10);
}

 

Cheers,

Josh

 

[Bob Nystrom]

Yup, that works fine. Closures close over variables, not values, so it will see that countdown has been rebound to the function.

- bob

[Bob Nystrom]

Dart's semantics right now are pretty much let in Scheme, and I believe what you're describing is (more or less) letrec. That would work too, but I think would be surprising to most programmers coming from an imperative background. In C++, Java, C#, and JS (with Harmony's let) I believe the variable is not in scope in the initializer. In particular, when you're trying to shadow a variable, the difference here might cause an unpleasant surprise.

I could be wrong here though. I haven't thought a lot about why Dart has the binding semantics it does. They just seemed reasonable to me.

- bob

[Stephen Adams]

One consequence of the let-like binding rules, and the specific rules for desugaring of local functions into assignments, is that the 'obvious' expression of mutually recursive local functions does not work.  I find this surprising considering the lengths to which Dart goes to generally make functions convenient and comfortable.

I think what we really want is 'let' for variables and 'letrec' for functions.

I described this in Issue 315.

http://code.google.com/p/dart/issues/detail?id=315

 

- bob

[Rémi Forax]

On 02/22/2012 10:43 PM, Bob Nystrom wrote:
>
>
> On Wed, Feb 22, 2012 at 1:25 PM, Jan <potom...@gmail.com
> <mailto:potom...@gmail.com>> wrote:
>
> var a = a;
> print(a);
>
>
> What should that do?
>
> var a = null;
> a = a;
> print(a); // null
>
> I'm probably missing the point here
>
>
> Dart's semantics right now are pretty much let in Scheme, and I
> believe what you're describing is (more or less) letrec. That would
> work too, but I think would be surprising to most programmers coming
> from an imperative background. In C++, Java, C#, and JS (with
> Harmony's let) I believe the variable is not in scope in the
> initializer. In particular, when you're trying to shadow a variable,
> the difference here might cause an unpleasant surprise.
>

> I could be wrong here though. I haven't thought a lot about /why/ Dart

> has the binding semantics it does. They just seemed reasonable to me.

In Java,
the typechecker inserts the declared variable in the scope but
a later pass the one that verifies that all variables are initialized
before being used
reports an error.

Also the current lambda prototype (for Java 8) has currently a special rule
to allow to use the current lambda inside of itself so variable are
declared as 'let'
in case of classical variable and 'letrec' if it's a lambda.

From the implementation side (this is Java specific), you may have
an unsafe publication of the lambda when creating it
(another thread can see the lambda not fully initialized :( )
so the creation of a recursive lambda requires a memory barrier.

Given that, I'm not sure this rule will be still be there when Java 8
will be released.

>
> - bob
>

cheers,
R�mi