domenic at domenicdenicola.com (2013-07-19T15:37:13.565Z)
> 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.
// 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