generators vs forEach

classic Classic list List threaded Threaded
28 messages Options
12
Reply | Threaded
Open this post in threaded view
|

generators vs forEach

Claus Reinke
[prompted by this nodejs list thread
 "Weird error with generators (using suspend or galaxy)"
 https://groups.google.com/forum/#!topic/nodejs/9omOdgSPkz4 ]

1. higher order functions are used to model control structures

2. generators/yield are designed to allow for suspend/resume
    of control structure code

These two statements come in conflict if one considers the restriction
that generators be based on flat continuations, which is sufficient to
span built-in control structures like "for" but not predefined control
structures like "forEach". The support for nested generators ("yield*")
differs from normal function call operation.

I have not seen this conflict discussed here, so I wanted to raise it
in case it was an oversight and something can be done about it. As
far as I can tell, there are two issues:

- current predefined operations like "forEach", "map", "filter", ..
    are not fully integrated with generators, even though they
    model synchronous operations; expecting users to duplicate
    their functionality for use with generators seems wrong;

- is it even possible to define higher-order operations that can be
    used both normally (without "yield" inside their callbacks, without
    "yield" wrapping their result) and with generators (with "yield"
    inside their callbacks, with "yield" wrapping their result)?

Claus
http://clausreinke.github.com/
 
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Jeremy Martin
Alternatively, could `yield` simply be lexically bound to the nearest GeneratorFunction scope, rather than the nearest Function?

E.g., instead of:

suspend(function* (resume) {
yield setTimeout(resume, 1000);
console.log('foo');
yield setTimeout(resume, 1000);
console.log('bar');
})();

... we could write:

suspend(function* (resume) {
['foo', 'bar'].forEach(function(word) {
yield setTimeout(resume, 1000);
console.log(word);
});
})();

The current state of things here is pretty ugly, and I'd really like to avoid having to add something like `suspend.forEach(Array, GeneratorFunction)` with `yield*` in the body.

On Mon, Jul 15, 2013 at 11:33 AM, Claus Reinke <[hidden email]> wrote:
[prompted by this nodejs list thread "Weird error with generators (using suspend or galaxy)"
https://groups.google.com/forum/#!topic/nodejs/9omOdgSPkz4 ]

1. higher order functions are used to model control structures

2. generators/yield are designed to allow for suspend/resume
   of control structure code

These two statements come in conflict if one considers the restriction
that generators be based on flat continuations, which is sufficient to
span built-in control structures like "for" but not predefined control
structures like "forEach". The support for nested generators ("yield*")
differs from normal function call operation.

I have not seen this conflict discussed here, so I wanted to raise it
in case it was an oversight and something can be done about it. As
far as I can tell, there are two issues:

- current predefined operations like "forEach", "map", "filter", ..
   are not fully integrated with generators, even though they
   model synchronous operations; expecting users to duplicate
   their functionality for use with generators seems wrong;

- is it even possible to define higher-order operations that can be    used both normally (without "yield" inside their callbacks, without
   "yield" wrapping their result) and with generators (with "yield"
   inside their callbacks, with "yield" wrapping their result)?

Claus
http://clausreinke.github.com/

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



--
Jeremy Martin
661.312.3853
@jmar777

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

RE: generators vs forEach

Domenic Denicola-2
I believe duplicating the `Array.prototype` built-ins as generator versions, in user-code, is the expected path forward. Perhaps an "itertools"-like module will be standardized and added in ES7, after that cowpath has been paved.

This pain is somewhat alleviated by generator expressions (which cover filter and map) and `for`-`of` (which covers the rest, more manually).
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Mark S. Miller-2
In reply to this post by Jeremy Martin
This would make generators deep, violating the non-interleaving assumptions of intermediate callers on the call stack. This is why we accepted generators only on condition that they be shallow. We knew at the time that this privileges built-in control structures over user defined ones. The alternative would have been to omit generators completely. We agree that shallow generators were worth it, despite this non-uniformity.

Put another way, shallow generators are equivalent to a local cps transform of the generator function itself. Deep generators would require the equivalent of CPS transforming the world -- violating the stateful assumptions of existing code.



On Mon, Jul 15, 2013 at 9:09 AM, Jeremy Martin <[hidden email]> wrote:
Alternatively, could `yield` simply be lexically bound to the nearest GeneratorFunction scope, rather than the nearest Function?

E.g., instead of:

suspend(function* (resume) {
yield setTimeout(resume, 1000);
console.log('foo');
yield setTimeout(resume, 1000);
console.log('bar');
})();

... we could write:

suspend(function* (resume) {
['foo', 'bar'].forEach(function(word) {
yield setTimeout(resume, 1000);
console.log(word);
});
})();

The current state of things here is pretty ugly, and I'd really like to avoid having to add something like `suspend.forEach(Array, GeneratorFunction)` with `yield*` in the body.

On Mon, Jul 15, 2013 at 11:33 AM, Claus Reinke <[hidden email]> wrote:
[prompted by this nodejs list thread "Weird error with generators (using suspend or galaxy)"
https://groups.google.com/forum/#!topic/nodejs/9omOdgSPkz4 ]

1. higher order functions are used to model control structures

2. generators/yield are designed to allow for suspend/resume
   of control structure code

These two statements come in conflict if one considers the restriction
that generators be based on flat continuations, which is sufficient to
span built-in control structures like "for" but not predefined control
structures like "forEach". The support for nested generators ("yield*")
differs from normal function call operation.

I have not seen this conflict discussed here, so I wanted to raise it
in case it was an oversight and something can be done about it. As
far as I can tell, there are two issues:

- current predefined operations like "forEach", "map", "filter", ..
   are not fully integrated with generators, even though they
   model synchronous operations; expecting users to duplicate
   their functionality for use with generators seems wrong;

- is it even possible to define higher-order operations that can be    used both normally (without "yield" inside their callbacks, without
   "yield" wrapping their result) and with generators (with "yield"
   inside their callbacks, with "yield" wrapping their result)?

Claus
http://clausreinke.github.com/

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



--
Jeremy Martin
<a href="tel:661.312.3853" value="+16613123853" target="_blank">661.312.3853
@jmar777

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss




--
    Cheers,
    --MarkM

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Jeremy Martin
Correct me if I'm wrong, but wouldn't the lexical-scoping restraint satisfy the shallow generator requirement?  As I understand it, the issue with deep generators and CPS transformations is that the transformations have to be applied to functions that aren't even lexically inside the GeneratorFunction.  Additionally, can't the nested CPS transformations issue by alleviated with a reference to the GeneratorFunction stack frame itself (a la SpiderMonkey)?

On Mon, Jul 15, 2013 at 12:45 PM, Mark S. Miller <[hidden email]> wrote:
This would make generators deep, violating the non-interleaving assumptions of intermediate callers on the call stack. This is why we accepted generators only on condition that they be shallow. We knew at the time that this privileges built-in control structures over user defined ones. The alternative would have been to omit generators completely. We agree that shallow generators were worth it, despite this non-uniformity.

Put another way, shallow generators are equivalent to a local cps transform of the generator function itself. Deep generators would require the equivalent of CPS transforming the world -- violating the stateful assumptions of existing code.



On Mon, Jul 15, 2013 at 9:09 AM, Jeremy Martin <[hidden email]> wrote:
Alternatively, could `yield` simply be lexically bound to the nearest GeneratorFunction scope, rather than the nearest Function?

E.g., instead of:

suspend(function* (resume) {
yield setTimeout(resume, 1000);
console.log('foo');
yield setTimeout(resume, 1000);
console.log('bar');
})();

... we could write:

suspend(function* (resume) {
['foo', 'bar'].forEach(function(word) {
yield setTimeout(resume, 1000);
console.log(word);
});
})();

The current state of things here is pretty ugly, and I'd really like to avoid having to add something like `suspend.forEach(Array, GeneratorFunction)` with `yield*` in the body.

On Mon, Jul 15, 2013 at 11:33 AM, Claus Reinke <[hidden email]> wrote:
[prompted by this nodejs list thread "Weird error with generators (using suspend or galaxy)"
https://groups.google.com/forum/#!topic/nodejs/9omOdgSPkz4 ]

1. higher order functions are used to model control structures

2. generators/yield are designed to allow for suspend/resume
   of control structure code

These two statements come in conflict if one considers the restriction
that generators be based on flat continuations, which is sufficient to
span built-in control structures like "for" but not predefined control
structures like "forEach". The support for nested generators ("yield*")
differs from normal function call operation.

I have not seen this conflict discussed here, so I wanted to raise it
in case it was an oversight and something can be done about it. As
far as I can tell, there are two issues:

- current predefined operations like "forEach", "map", "filter", ..
   are not fully integrated with generators, even though they
   model synchronous operations; expecting users to duplicate
   their functionality for use with generators seems wrong;

- is it even possible to define higher-order operations that can be    used both normally (without "yield" inside their callbacks, without
   "yield" wrapping their result) and with generators (with "yield"
   inside their callbacks, with "yield" wrapping their result)?

Claus
http://clausreinke.github.com/

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



--
Jeremy Martin
<a href="tel:661.312.3853" value="+16613123853" target="_blank">661.312.3853
@jmar777

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss




--
    Cheers,
    --MarkM



--
Jeremy Martin
661.312.3853
@jmar777

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Brandon Benvie-2
On 7/15/2013 10:24 AM, Jeremy Martin wrote:
> Correct me if I'm wrong, but wouldn't the lexical-scoping restraint
> satisfy the shallow generator requirement?  As I understand it, the
> issue with deep generators and CPS transformations is that the
> transformations have to be applied to functions that aren't even
> lexically inside the GeneratorFunction.  Additionally, can't the
> nested CPS transformations issue by alleviated with a reference to the
> GeneratorFunction stack frame itself (a la SpiderMonkey)?

Consider the following:

       function* yieldEach(array){
         array.forEach(n => {
           yield n;
         });
       }

In order for this to work, not only does `yieldEach` have to be
suspended for the inner yield, but forEach does as well. That means CPS
transforming functions based on whether they call a yielding function.
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Jeremy Martin
> That means CPS transforming functions based on whether they call a yielding function.

Well, yes :)  Admittedly, that does seem messy.  Not to sound defeatist, but I'm sensing that I don't actually have the necessary knowledge to further argue this.  I'll just end with saying that it'll be unfortunate if we're going to have to endure the clunkiness of nested generators anywhere higher-order functions are called for.  Regardless of whatever solutions may or may not be appropriate, I at a minimum echo Claus' sentiment - it seems like there's a nice opportunity here to improve the modeling of control structures.

On Mon, Jul 15, 2013 at 3:01 PM, Brandon Benvie <[hidden email]> wrote:
On 7/15/2013 10:24 AM, Jeremy Martin wrote:
Correct me if I'm wrong, but wouldn't the lexical-scoping restraint satisfy the shallow generator requirement?  As I understand it, the issue with deep generators and CPS transformations is that the transformations have to be applied to functions that aren't even lexically inside the GeneratorFunction.  Additionally, can't the nested CPS transformations issue by alleviated with a reference to the GeneratorFunction stack frame itself (a la SpiderMonkey)?

Consider the following:

      function* yieldEach(array){
        array.forEach(n => {
          yield n;
        });
      }

In order for this to work, not only does `yieldEach` have to be suspended for the inner yield, but forEach does as well. That means CPS transforming functions based on whether they call a yielding function.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



--
Jeremy Martin
661.312.3853
@jmar777

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Brendan Eich-3
Jeremy Martin wrote:
>  Regardless of whatever solutions may or may not be appropriate, I at
> a minimum echo Claus' sentiment - it seems like there's a nice
> opportunity here to improve the modeling of control structures.

You're right, but the problem Mark cites is a big one and it stops any
general call/cc or coroutine extension from going into JS.

I'd just add that call/cc in Scheme is a power tool, and (I'm told)
you're supposed to use macros built on it, usually. The macros for
delimited continuations address a sweet spot for control abstractions,
and Dave Herman did give them careful consideration. Dave alludes to
that work here:

https://mail.mozilla.org/pipermail/es-discuss/2010-December/012284.html

viz, "I pretty much abandoned that line of investigation with the
conclusion that generators: ...", which I believe refers to

http://wiki.ecmascript.org/doku.php?id=strawman:shallow_continuations

which is deferred and pretty much defunct due to generators.

/be
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Bruno Jouhier
In reply to this post by Claus Reinke
There is no need to CPS transform functions and there is no need for deferred functions either. It can all be done with today's generators and a little helper library.

With the C# async/await notation:
  • The yield keyword is your "await" keyword.
  • The little * in function* is your "async" keyword.
With this you can write:

function* asyncEach(array, fn) {
  for (var i = 0; i < array.length; i++) yield fn(array[i], i);
}

and you can call it as:

function* myFunc(array) {
  yield asyncEach(array, function*(elt, i) {
    var foo = yield asyncBar(elt);
    // more ...
  })
}

Note that there is *no* helper API in all these async functions that call other async functions; The helper API is only needed to interface this with the classical callback world: at the very bottom of the stack when you call low level callbacks-based I/O functions, and at the top of the stack when the event loop runs one of your generator functions.

The trick is that you need a clever run function to do the little yield/next dance with generator functions that call other generator functions.

I've implemented this in https://github.com/bjouhier/galaxy/blob/master/lib/galaxy.js (the run and invoke functions)

The only thing I don't like about it is the awkward syntax:
  • yield precedence does not work well
  • yield is prefix, which does not chain well
  • and yield is heavy anyway
In short, this is a hack to get going but I'm still waiting for the full concurrency proposal and its awesome ! syntax.

Bruno

> Consider the following:
>
>       function* yieldEach(array){
>         array.forEach(n => {
>           yield n;
>         });
>       }
>
> In order for this to work, not only does `yieldEach` have to be suspended for the inner yield, but forEach does as well. That means CPS transforming functions based on whether they call a yielding function.


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

RE: generators vs forEach

Ron Buckton-2
Bruno, wouldn't yield* work here to delegate the inner yields?

Sent from my Windows Phone

From: [hidden email]
Sent: ‎7/‎15/‎2013 4:12 PM
To: [hidden email]
Subject: Re: generators vs forEach

There is no need to CPS transform functions and there is no need for deferred functions either. It can all be done with today's generators and a little helper library.

With the C# async/await notation:
  • The yield keyword is your "await" keyword.
  • The little * in function* is your "async" keyword.
With this you can write:

function* asyncEach(array, fn) {
  for (var i = 0; i < array.length; i++) yield fn(array[i], i);
}

and you can call it as:

function* myFunc(array) {
  yield asyncEach(array, function*(elt, i) {
    var foo = yield asyncBar(elt);
    // more ...
  })
}

Note that there is *no* helper API in all these async functions that call other async functions; The helper API is only needed to interface this with the classical callback world: at the very bottom of the stack when you call low level callbacks-based I/O functions, and at the top of the stack when the event loop runs one of your generator functions.

The trick is that you need a clever run function to do the little yield/next dance with generator functions that call other generator functions.

I've implemented this in https://github.com/bjouhier/galaxy/blob/master/lib/galaxy.js (the run and invoke functions)

The only thing I don't like about it is the awkward syntax:
  • yield precedence does not work well
  • yield is prefix, which does not chain well
  • and yield is heavy anyway
In short, this is a hack to get going but I'm still waiting for the full concurrency proposal and its awesome ! syntax.

Bruno

> Consider the following:
>
>       function* yieldEach(array){
>         array.forEach(n => {
>           yield n;
>         });
>       }
>
> In order for this to work, not only does `yieldEach` have to be suspended for the inner yield, but forEach does as well. That means CPS transforming functions based on whether they call a yielding function.


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

RE: generators vs forEach

Ron Buckton-2
I assume you are referring to something like Q.async/Q.spawn to turn the generator into an async function using promises?

Sent from my Windows Phone

From: [hidden email]
Sent: ‎7/‎15/‎2013 5:02 PM
To: [hidden email]; [hidden email]
Subject: RE: generators vs forEach

Bruno, wouldn't yield* work here to delegate the inner yields?

Sent from my Windows Phone

From: [hidden email]
Sent: ‎7/‎15/‎2013 4:12 PM
To: [hidden email]
Subject: Re: generators vs forEach

There is no need to CPS transform functions and there is no need for deferred functions either. It can all be done with today's generators and a little helper library.

With the C# async/await notation:
  • The yield keyword is your "await" keyword.
  • The little * in function* is your "async" keyword.
With this you can write:

function* asyncEach(array, fn) {
  for (var i = 0; i < array.length; i++) yield fn(array[i], i);
}

and you can call it as:

function* myFunc(array) {
  yield asyncEach(array, function*(elt, i) {
    var foo = yield asyncBar(elt);
    // more ...
  })
}

Note that there is *no* helper API in all these async functions that call other async functions; The helper API is only needed to interface this with the classical callback world: at the very bottom of the stack when you call low level callbacks-based I/O functions, and at the top of the stack when the event loop runs one of your generator functions.

The trick is that you need a clever run function to do the little yield/next dance with generator functions that call other generator functions.

I've implemented this in https://github.com/bjouhier/galaxy/blob/master/lib/galaxy.js (the run and invoke functions)

The only thing I don't like about it is the awkward syntax:
  • yield precedence does not work well
  • yield is prefix, which does not chain well
  • and yield is heavy anyway
In short, this is a hack to get going but I'm still waiting for the full concurrency proposal and its awesome ! syntax.

Bruno

> Consider the following:
>
>       function* yieldEach(array){
>         array.forEach(n => {
>           yield n;
>         });
>       }
>
> In order for this to work, not only does `yieldEach` have to be suspended for the inner yield, but forEach does as well. That means CPS transforming functions based on whether they call a yielding function.


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Bruno Jouhier
I thought about yield* but it was not available at the time I wrote this. But it does not fit the bill because it deals with the synchonous part of the generator dance, not the async part. My run loop is if a bit more than the yield* loop (but not much more). The differences are the tests that deal with the PENDING case (https://github.com/bjouhier/galaxy/blob/master/lib/galaxy.js lines 83 and 88).

I'm not using Q. I wanted to have minimal runtime overhead so I designed it so that it does not allocate any extra objects. It's all done with a simple loop.


2013/7/16 Ron Buckton <[hidden email]>
I assume you are referring to something like Q.async/Q.spawn to turn the generator into an async function using promises?


Sent from my Windows Phone

From: [hidden email]
Sent: 7/15/2013 5:02 PM
To: [hidden email]; [hidden email]
Subject: RE: generators vs forEach

Bruno, wouldn't yield* work here to delegate the inner yields?

Sent from my Windows Phone

From: [hidden email]
Sent: 7/15/2013 4:12 PM
To: [hidden email]
Subject: Re: generators vs forEach

There is no need to CPS transform functions and there is no need for deferred functions either. It can all be done with today's generators and a little helper library.

With the C# async/await notation:
  • The yield keyword is your "await" keyword.
  • The little * in function* is your "async" keyword.
With this you can write:

function* asyncEach(array, fn) {
  for (var i = 0; i < array.length; i++) yield fn(array[i], i);
}

and you can call it as:

function* myFunc(array) {
  yield asyncEach(array, function*(elt, i) {
    var foo = yield asyncBar(elt);
    // more ...
  })
}

Note that there is *no* helper API in all these async functions that call other async functions; The helper API is only needed to interface this with the classical callback world: at the very bottom of the stack when you call low level callbacks-based I/O functions, and at the top of the stack when the event loop runs one of your generator functions.

The trick is that you need a clever run function to do the little yield/next dance with generator functions that call other generator functions.

I've implemented this in https://github.com/bjouhier/galaxy/blob/master/lib/galaxy.js (the run and invoke functions)

The only thing I don't like about it is the awkward syntax:
  • yield precedence does not work well
  • yield is prefix, which does not chain well
  • and yield is heavy anyway
In short, this is a hack to get going but I'm still waiting for the full concurrency proposal and its awesome ! syntax.

Bruno

> Consider the following:
>
>       function* yieldEach(array){
>         array.forEach(n => {
>           yield n;
>         });
>       }
>
> In order for this to work, not only does `yieldEach` have to be suspended for the inner yield, but forEach does as well. That means CPS transforming functions based on whether they call a yielding function.



_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Claus Reinke
In reply to this post by Mark S. Miller-2
    // this doesn't work
    function* generator(){
        [1,2,3].forEach( function(x){ yield x } )
    }

> This would make generators deep, violating the non-interleaving assumptions
> of intermediate callers on the call stack. This is why we accepted
> generators only on condition that they be shallow. We knew at the time that
> this privileges built-in control structures over user defined ones. The
> alternative would have been to omit generators completely. We agree that
> shallow generators were worth it, despite this non-uniformity.

While I understand the compromise, and the wish to get in some form
of generators anyway, the discrimination against user-defined control
structures troubles me deeply. It introduces a new language construct
that defies abstraction. It means that we can no longer use functional
abstraction freely, but have to worry about interactions with generators.

For the specific case of forEach et al, another way to avoid intermediate
stack frames would be guaranteed inlining. If we always inline .forEach
before execution, then specialize the resulting code wrt the callback,
any yields in the callback would be directly in the caller. Consider this
chain of code transformations:

    // inline forEach; this still doesn't work
    function* generator(){
        (function forEach(arr,cb) {
            for (var i=0; i<arr.length; i++) cb(arr[i]);
        })([1,2,3], function(x){ yield x } );
    }

    // instantiate inlined forEach; still doesn't work
    function* generator(){
        let arr = [1,2,3];
        let cb = function(x){ yield x };
        for (var i=0; i<arr.length; i++) cb(arr[i]);
    }

    // inline cb; still doesn't work
    function* generator(){
        let arr = [1,2,3];
        for (var i=0; i<arr.length; i++) (function(x){ yield x})(arr[i]);
    }

    // instantiate inlined cb; this should work
    function* generator(){
        let arr = [1,2,3];
        for (var i=0; i<arr.length; i++) yield arr[i];
    }

If such inlining and instantiating functions in ES6 changes the validity
of code, then the opposite path -building abstractions from concrete
code examples- is also affected. I find that worrying.

The final form of the code can be handled with shallow generators,
and it should be semantically equivalent to the initial form (just
function application and variable instantiation in between). So why
shouldn't both forms be valid and doable without overcomplicating
the shallow generator ideal?

In pragmatic terms, perhaps introducing inline annotations for
operations like .forEach and for their callback parameters could avoid
nested stack frames her without forcing user-side code duplication.
Such annotation-enforced inlining should also help with performance
of .forEach et al (currently behind for-loops).

[in conventional pre-compiling FPL implementations, such worker/
 wrapper staging plus inlining is done at compile time (stage recursive
 higher-order function into non-recursive wrapper and recursive but
 not higher-order worker; inline wrapper to instantiate the functional
 parameters in the nested worker; finally apply standard optimizer);

 it is an easy way to avoid deoptimizations caused by higher-order
 parameters interfering with code analysis; provided the library
 author helps with code staging and inline annotations ]

> Put another way, shallow generators are equivalent to a local cps
> transform of the generator function itself. Deep generators would
> require the equivalent of CPS transforming the world -- violating
> the stateful assumptions of existing code.

FYI:

I'm not sure what you mean by "violating the stateful assumptions"
but there is an even more local transform than that for ES6 generators:
writing code in monadic style always captures the local continuation
only. That allows for generator monads that compose those local
continuations back together.

An example of such a generator monad can be found here (using a
list of steps for simplicity; code is TypeScript v0.9, to make use of
ES6 classes with class-side inheritance and arrow functions)

    https://gist.github.com/clausreinke/5984869#file-monadic-ts-L91-L125

with example code (using user-defined forOf) at

    https://gist.github.com/clausreinke/5984869#file-monadic-ts-L492-L529

This differs from ES6 generators in using a functional API (next returns
{done,value,next}) and in building on expressions and user-defined
control-flow operations instead of statement blocks and built-in
control-flow structures. Still, this style does seem to allow more reuse
of existing ES5 array operations than ES6 generators will, as this
small example demonstrates:

    console.log("\n// mixing yield with higher-order array ops (prefix ^)");
    var generator4 = ()=> [1,2,3].map( x=> G.yield(x) )
                                 .reduce( (x,y)=> x.then( _=> y ), G.of(undefined) ) ;
    MonadId.forOf( generator4(), y=> (console.log("^ "+y), MonadId.of(y)) );

append example to the end of that gist, execute with tsc -e (TS v0.9
required, playground or npm will do):

    ...
    // mixing yield with higher-order array ops (prefix ^)
    ^ 1
    ^ 2
    ^ 3

That gist doesn't depend on language extensions, though some form
of syntax sugar for monad comprehensions would help readability.
And such monadic syntax sugar would help all monads, eg, there is
a Promise monad in that same file.

Claus
 
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Mark S. Miller-2
On Tue, Jul 16, 2013 at 10:54 AM, Claus Reinke <[hidden email]> wrote:
   // this doesn't work
   function* generator(){
       [1,2,3].forEach( function(x){ yield x } )

   }

This would make generators deep, violating the non-interleaving assumptions
of intermediate callers on the call stack. This is why we accepted
generators only on condition that they be shallow. We knew at the time that
this privileges built-in control structures over user defined ones. The
alternative would have been to omit generators completely. We agree that
shallow generators were worth it, despite this non-uniformity.

While I understand the compromise, and the wish to get in some form
of generators anyway, the discrimination against user-defined control
structures troubles me deeply.

Troubles me too. As of ES6 the only possible alternative would be to remove generators from the language. I can't see that happening.


 
It introduces a new language construct
that defies abstraction. It means that we can no longer use functional
abstraction freely, but have to worry about interactions with generators.

For the specific case of forEach et al, another way to avoid intermediate
stack frames would be guaranteed inlining.

If this was the only motivation for introducing something like a guaranteed inline-ability annotation, I would not think it worth the price. However, such an annotation may serve multiple purposes. The key constraint it would need to impose is that the function is closed -- it doesn't capture any lexical variables other than the ES* defined globals. This is a minimal requirement for inlining, for parallelizability by Rivertrail, and for safe mobile code as in Q.there.

In any case, since functions by default are encapsulated, some explicit annotation or syntax of some sort is required for the function to waive its encapsulation.


 
If we always inline .forEach before execution, then specialize the resulting code wrt the callback,
any yields in the callback would be directly in the caller. Consider this
chain of code transformations:

   // inline forEach; this still doesn't work
   function* generator(){
       (function forEach(arr,cb) {
           for (var i=0; i<arr.length; i++) cb(arr[i]);
       })([1,2,3], function(x){ yield x } );
   }

   // instantiate inlined forEach; still doesn't work
   function* generator(){
       let arr = [1,2,3];
       let cb = function(x){ yield x };
       for (var i=0; i<arr.length; i++) cb(arr[i]);
   }

   // inline cb; still doesn't work
   function* generator(){
       let arr = [1,2,3];
       for (var i=0; i<arr.length; i++) (function(x){ yield x})(arr[i]);
   }

   // instantiate inlined cb; this should work
   function* generator(){
       let arr = [1,2,3];
       for (var i=0; i<arr.length; i++) yield arr[i];
   }

If such inlining and instantiating functions in ES6 changes the validity of code, then the opposite path -building abstractions from concrete
code examples- is also affected. I find that worrying.

The final form of the code can be handled with shallow generators,
and it should be semantically equivalent to the initial form (just
function application and variable instantiation in between). So why
shouldn't both forms be valid and doable without overcomplicating
the shallow generator ideal?

In pragmatic terms, perhaps introducing inline annotations for operations like .forEach and for their callback parameters could avoid nested stack frames her without forcing user-side code duplication. Such annotation-enforced inlining should also help with performance of .forEach et al (currently behind for-loops).

[in conventional pre-compiling FPL implementations, such worker/
wrapper staging plus inlining is done at compile time (stage recursive higher-order function into non-recursive wrapper and recursive but not higher-order worker; inline wrapper to instantiate the functional parameters in the nested worker; finally apply standard optimizer);
it is an easy way to avoid deoptimizations caused by higher-order parameters interfering with code analysis; provided the library
author helps with code staging and inline annotations ]


Put another way, shallow generators are equivalent to a local cps transform of the generator function itself. Deep generators would require the equivalent of CPS transforming the world -- violating the stateful assumptions of existing code.

FYI:

I'm not sure what you mean by "violating the stateful assumptions"
but there is an even more local transform than that for ES6 generators:
writing code in monadic style always captures the local continuation
only. That allows for generator monads that compose those local
continuations back together.
An example of such a generator monad can be found here (using a list of steps for simplicity; code is TypeScript v0.9, to make use of
ES6 classes with class-side inheritance and arrow functions)

   https://gist.github.com/clausreinke/5984869#file-monadic-ts-L91-L125

with example code (using user-defined forOf) at

   https://gist.github.com/clausreinke/5984869#file-monadic-ts-L492-L529

This differs from ES6 generators in using a functional API (next returns
{done,value,next}) and in building on expressions and user-defined
control-flow operations instead of statement blocks and built-in
control-flow structures. Still, this style does seem to allow more reuse
of existing ES5 array operations than ES6 generators will, as this
small example demonstrates:

   console.log("\n// mixing yield with higher-order array ops (prefix ^)");
   var generator4 = ()=> [1,2,3].map( x=> G.yield(x) )
                                .reduce( (x,y)=> x.then( _=> y ), G.of(undefined) ) ;
   MonadId.forOf( generator4(), y=> (console.log("^ "+y), MonadId.of(y)) );

append example to the end of that gist, execute with tsc -e (TS v0.9 required, playground or npm will do):

   ...
   // mixing yield with higher-order array ops (prefix ^)
   ^ 1
   ^ 2
   ^ 3

That gist doesn't depend on language extensions, though some form of syntax sugar for monad comprehensions would help readability. And such monadic syntax sugar would help all monads, eg, there is a Promise monad in that same file.

Claus




--
    Cheers,
    --MarkM

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Brendan Eich-3
Mark S. Miller wrote:

> On Tue, Jul 16, 2013 at 10:54 AM, Claus Reinke
> <[hidden email] <mailto:[hidden email]>> wrote:
>
>        // this doesn't work
>        function* generator(){
>            [1,2,3].forEach( function(x){ yield x } )
>
>        }
>
>         This would make generators deep, violating the
>         non-interleaving assumptions
>         of intermediate callers on the call stack. This is why we accepted
>         generators only on condition that they be shallow. We knew at
>         the time that
>         this privileges built-in control structures over user defined
>         ones. The
>         alternative would have been to omit generators completely. We
>         agree that
>         shallow generators were worth it, despite this non-uniformity.
>
>
>     While I understand the compromise, and the wish to get in some form
>     of generators anyway, the discrimination against user-defined control
>     structures troubles me deeply.
>
>
> Troubles me too. As of ES6 the only possible alternative would be to
> remove generators from the language. I can't see that happening.

That would be somewhere between "making the perfect the enemy of the
good" and "cutting off your nose to spite your face".

If we want call/cc (plus macros to sugar it into usability), there's the
door -- it ain't in JS outside of Rhino, and (for good reasons you
adduce) it won't be added.

But we have good use cases for generators, including to implement
iterators independent of async. programming.

For async we're looking at defer/await for ES7.

This is how living languages evolve. Sorry to preach to the choir (I
hope :-P).

/be
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

David Bruant-5
In reply to this post by Claus Reinke
Le 16/07/2013 19:54, Claus Reinke a écrit :
>    // this doesn't work
>    function* generator(){
>        [1,2,3].forEach( function(x){ yield x } )
>    }
I have been thinking and with for..of, I can't find a good reason to use
.forEach instead of for..of.
for..of does what you need here with generators too.

>> This would make generators deep, violating the non-interleaving
>> assumptions
>> of intermediate callers on the call stack. This is why we accepted
>> generators only on condition that they be shallow. We knew at the
>> time that
>> this privileges built-in control structures over user defined ones. The
>> alternative would have been to omit generators completely. We agree that
>> shallow generators were worth it, despite this non-uniformity.
>
> While I understand the compromise, and the wish to get in some form
> of generators anyway, the discrimination against user-defined control
> structures troubles me deeply. It introduces a new language construct
> that defies abstraction. It means that we can no longer use functional
> abstraction freely, but have to worry about interactions with generators.
>
> For the specific case of forEach et al
What do you mean by "et al"? I don't believe .map, .reduce or .filter
are any interesting to use alongside generators.

Even if so, for..of can work too and is decently elegant (YMMV):

     function* g(){
         [1,2,3].map(x => {yield transform(x)})
     }

becomes

     function* g(){
         for(x of [1,2,3]) yield transform(x);
     }

David
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Rick Waldron



On Tue, Jul 16, 2013 at 3:45 PM, David Bruant <[hidden email]> wrote:
Le 16/07/2013 19:54, Claus Reinke a écrit :

   // this doesn't work
   function* generator(){
       [1,2,3].forEach( function(x){ yield x } )
   }
I have been thinking and with for..of, I can't find a good reason to use .forEach instead of for..of.
for..of does what you need here with generators too.


I've been looking at this example and thinking the same thing. Additionally, I'm curious to know what this would've looked like without being a contrived example of mis-used yield, considering Array.prototype.forEach returns undefined and the callback returns undefined as well (regardless of whether or not user code specifies a return).

Rick


 


This would make generators deep, violating the non-interleaving assumptions
of intermediate callers on the call stack. This is why we accepted
generators only on condition that they be shallow. We knew at the time that
this privileges built-in control structures over user defined ones. The
alternative would have been to omit generators completely. We agree that
shallow generators were worth it, despite this non-uniformity.

While I understand the compromise, and the wish to get in some form
of generators anyway, the discrimination against user-defined control
structures troubles me deeply. It introduces a new language construct
that defies abstraction. It means that we can no longer use functional
abstraction freely, but have to worry about interactions with generators.

For the specific case of forEach et al
What do you mean by "et al"? I don't believe .map, .reduce or .filter are any interesting to use alongside generators.

Even if so, for..of can work too and is decently elegant (YMMV):

    function* g(){
        [1,2,3].map(x => {yield transform(x)})
    }

becomes

    function* g(){
        for(x of [1,2,3]) yield transform(x);
    }

David

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Claus Reinke
In reply to this post by David Bruant-5
>>    // this doesn't work
>>    function* generator(){
>>        [1,2,3].forEach( function(x){ yield x } )
>>    }
> I have been thinking and with for..of, I can't find a good reason to use
> .forEach instead of for..of.
> for..of does what you need here with generators too.

Perhaps you're right that .forEach is going to die (there are also
generator expressions to consider, covering some of the other
standard methods). It was the smallest example I could think of
to illustrate the point.

However, the argument is not about a specific operation but about
being able to define such operations in user code (eg, array
comprehensions can usually be mapped to uses of .map, .concat,
.filter; loops can be mapped to tail recursion; ...). User-defined
control structures can be extended/modified without waiting for
the language as a whole to evolve. If the equivalence between
built-in and user-defined operation is broken, that option is no
longer fully functional.

>> For the specific case of forEach et al
> What do you mean by "et al"? I don't believe .map, .reduce or .filter
> are any interesting to use alongside generators.

And why not? Because yield is a statement, and because those
operations have not been (cannot be) extended to work with
generators. Why shouldn't I be able to traverse an array, using the
ES5 standard operations for doing so, yielding intermediate results
from the traversal (recall also that yield can return data sent in via
.next, for incorporation into such traversals)?
 
> Even if so, for..of can work too and is decently elegant (YMMV):
>
>     function* g(){
>         [1,2,3].map(x => {yield transform(x)})
>     }

I fell for this, too:-) arrow functions have no generator equivalents.
 
> becomes
>
>     function* g(){
>         for(x of [1,2,3]) yield transform(x);
>     }

Methods can be replaced by built-ins. It is the reverse that
is now broken.

Claus
 
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

Claus Reinke
In reply to this post by Rick Waldron
>>     // this doesn't work
>>>    function* generator(){
>>>        [1,2,3].forEach( function(x){ yield x } )
>>>    }
>>>
>> I have been thinking and with for..of, I can't find a good reason to use
>> .forEach instead of for..of.
>> for..of does what you need here with generators too.
>
> I've been looking at this example and thinking the same thing.

That's what you get for trying to use examples:-) long code doesn't
get read, short code is taken too seriously. As I said in my reply to
David, my point is not dependent on this example. Still, given the
readyness to abandon .forEach completely, it might be worthwhile
to try and find a more realistic example, to see how big the damage
is in practice.

Since we're talking about not completely implemented features, I
don't have anything concrete yet, but perhaps in the direction of
other callback-based APIs? Is there a way to use generators to
enumerate directory trees in nodejs, or is it back to iterators?

Better examples welcome,
Claus
 
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: generators vs forEach

David Bruant-5
In reply to this post by Claus Reinke
2013/7/17 Claus Reinke <[hidden email]>

For the specific case of forEach et al
What do you mean by "et al"? I don't believe .map, .reduce or .filter are any interesting to use alongside generators.

And why not? Because yield is a statement, and because those
operations have not been (cannot be) extended to work with
generators. Why shouldn't I be able to traverse an array, using the
ES5 standard operations for doing so, yielding intermediate results
from the traversal (recall also that yield can return data sent in via .next, for incorporation into such traversals)?
I think that considering map, filter or reduce (especially reduce!) as traversal mechanism is a misuse of these methods.
This is pretty much why find/findIndex has been added (every/some were "misused" as traversal mechanism with early ending to achieve what find/findIndex do).



Even if so, for..of can work too and is decently elegant (YMMV):

    function* g(){
        [1,2,3].map(x => {yield transform(x)})
    }

I fell for this, too:-) arrow functions have no generator equivalents.
... oops, yeah sorry. So happy to use arrow function that I went out of my way :-)

 

becomes

    function* g(){
        for(x of [1,2,3]) yield transform(x);
    }

Methods can be replaced by built-ins. It is the reverse that
is now broken.


Maybe a solution would be that Array.prototype.map returns a generator when passed a generator as argument? The result generator would generate the new values. Could work with filter too (generate only filtered elements). reduce could empty out the generator to build the value.

  function* filterG(e){ yield e %2 === 0 }
  function* mapG(e){ yield e *e }
  function* reduceG(acc, e){ yield acc + e }
 
  myArray.filter(filterG).map(mapG).reduce(reduceG)

hmm... my code doesn't work because generators don't have a .map and .reduce methods. Maybe we can invent ArrayGenerators? which would be a generator and have Array.prototype someowhere in its prototype chain (array methods would output an ArrayGenerator if provided either a generator or an ArrayGenerator)?

Interestingly, "myArray.filter(filterG).map(mapG)" could be sort-of a lazy value. Actual computation filterG and mapG happens only when generating values from the




_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
12