nyuichi commented 10 years ago

Abstract

This pull-request adds a simple syntax to pass values into a generator. As of this writing JSX has generators which only support produce outputs. In almost all cases generators are required, even if only 'generating' values is supported, they are enough useful in various situations such as incrementally producing values by need via a pipeline. Sometimes, however, the ability to pass information from outside would be more useful. Taking for example co, which is making the best use of ES6's generator, they realize async functions by beautiful hack. When you call co with a generator function and a yield expression is invoked inside, co 'injects' a code between the yield and its continuation so that they run the asynchronous task encapsulated in given promise in background.

Design

When you make a generator object by calling a generator function, you are allowed to call 'next' method with an optional argument value. If the generator object is in suspended state (i.e. neither newborn nor dead), the result of suspending yield expression will be the given value. If it is in newborn state, the value is simply ignored.

function * foo () : int {
  var i = yield 0;
  var j = yield i;
  yield j;
}
foo().next(42); // => 0; generator object neglects 42.
foo().next().next(1) // => 1
foo().next().next(1).next(2) // => 2

Since there hasn't been default type parameter in JSX, I designed the type of yield expressions to be same type as the yielding type. But If you want, I'm quite ready to let my design go and change the type to variant.

function * foo () : int {
  var i = yield 0; // the type of i is automatically inferred to be `int`. Passing information of different type than yielding type is not permitted.
}

Impl

The transformation is performed like below. Though there appear many redundant code emitted in the output, they are expected to be removed by the optimizer when --release flag is enabled.

Original

class _Main {
    static function main (args : string[]) : void {
        function * sum () : number {
            var a = 0;
            while (true) {
                a += yield a;
            }
        }

        var g = sum();
        g.next();   // initial run
        for (var i = 1; i < 5; ++i) {
            log g.next(i).value; // 1, 3, 6, 10, ...
        }
    }
}

After transformation

function _Main$main$AS(args) {
    var sum;
    var g;
    var i;
    function sum() {
        var a;
        var $generator;
        var $return;
        var $loop;
        $generator = new __jsx_generator_object$0();
        function $loop($next) {
            var $a1;
            var $a0;
            var $a2;
            var $a5;
            var $a4;
            var $a3;
            while (true) {
                switch ($next) {
                case 0:
                    $a1 = 0;
                    $a0 = a = $a1;
                    $a0;
                    $next = 1;
                    break;
                case 1:
                    $a2 = true;
                    if ($a2) {
                        $next = 2;
                        break;
                    } else {
                        $next = 3;
                        break;
                    }
                case 2:
                    $a5 = a;
                    $generator.__value = $a5;
                    $generator.__next = 4;
                    return;
                case 4:
                    $a4 = $generator.__value;
                    $a3 = a += $a4;
                    $a3;
                    $next = 1;
                    break;
                case 3:
                    $generator.__value = $return;
                    $generator.__next = -1;
                    return;
                }
            }
        }
        $generator.__next = 0;
        $generator.__loop = $loop;
        return $generator;
    }
    g = sum();
    g.next();
    for (i = 1; i < 5; ++i) {
        console.log(g.next(i).value);
    }
};

gfx commented 10 years ago

:dancer:

kazuho commented 10 years ago

:+1: Thanks a lot! will look into

kazuho commented 10 years ago

@wasabiz

I expect that people would want to specify different types for input and output of the generator functions (but not variant). Would it be possible to support such usage? If yes, do you have any ideas on how to define the syntax to specify the two types?

nyuichi commented 10 years ago

@kazuho

Unfortunately, no. I investigated other programming languages that support generator or coroutine to find the ways how they solve the problem of 'yield expression type', but all languages that are statically typed and have generators are not supporting yield expressions (they only support yield statement). So as far as I know there is no known workaround for that.

One possible solution is to add traditional function-ic syntax.

function foo () : Generator.<T, U> { // no 'star' here
  var u = yield t; // yield takes a T, and returns a U.
}

The good point of this method is the extensibility. In exchange of the requirement of writing an amount of code, you can specify the type of yield expressions by using additional type parameter. One of the bad parts is that it does not keep the compatibility to ES6's generator. From others it will be seen somehow retrograde.

If you are not against to adding another ortogonal syntax, another solution is that just use a comma to give additional type pameter to template class.

function * foo () : T, U { // '*' is mandatory here
  var u = yield t;
}

But I don't like this so much. Comma between types is too likely to look like a notation for multiple value. In the below case, comma notation will be little usable.

function foo () : T, U { // How about this case? What do you expect for this function?
}

So my opinion is "If yield returns variant, it would be catastrophically inconvenient but it works. If yield returns custom typed values, yeah of course it would be convenient for you! But it's impossible".

kazuho commented 10 years ago

@wasabiz

Is my understanding correct that you think the problem is in how we should define the syntax even though it is possible to implement the semantics to support both typed input to / output from generators?

If that is the case, I would really want to seek for an appropriate syntax to declare both of the types, since, enforcing type constraints over JavaScript is one of the key goals of JSX.

kazuho commented 10 years ago

Possibly, we could use some kind of operator to designate the two types; for example:

function* foo() : InputType * OutputType;  // input = yield(output)
function* foo() : OutputType;              // yield output; (no value is returned from yield)

nyuichi commented 10 years ago

@kazuho @gfx

'*' looks like a multiple value-returning operator, too. In the world of CS, star syntax is widely used for the notation of direct product, which is the theoritical fundation of what we know tuple.

If you like addtional generator-specific syntax, something like ~> is better than * or ,.

function * foo () : InputType ~> OutputType {
}

Otherwise, using yield keyword in type decl position might make thing clear.

function * foo () : InputType yield OutputType {
}

I dont have strong opinion about the place at which type should be put on right or left. 2014/03/07 13:41 "Kazuho Oku" notifications@github.com:

Possibly, we could use some kind of operator to designate the two types; for example:

function* foo() : InputType * OutputType

Reply to this email directly or view it on GitHubhttps://github.com/jsx/JSX/pull/303#issuecomment-36967646 .

kazuho commented 10 years ago

@wasabiz

Agreed that * is not a good candidate. Personally, I think your proposal to use:

function * foo () : InputType yield OutputType

is a good resort. Maybe we should start from this, and then switch to something else if we find out a better solution.

gfx commented 10 years ago

The order of types in function * foo () : InputType yield OutputType is not the same as var output = yield input;. How about fnction * foo() : OutputType yield InputType?

nyuichi commented 10 years ago

@gfx

function * foo () : InputType yield Output could read like "InputType yields OutputType"?

gfx commented 10 years ago

@wasabiz Yeah, in fact, it sounds like an English sentence, but different from the syntax of yield expression. I'd like to know what others who don't know JSX well think about it.

kazuho commented 10 years ago

@gfx @wasabiz

IMO what input or output is depends on the viewpoint. If you look from inside of the generator, then the input would be the argument passed to yield and the output would be the value being returned. If you look from outside of the generator, then they would be different (and the accessor is named next()).

So if we are to use the word yield, then I would suggest sticking to the first view, since that is how the word is used.

PS. if we are to use yields, the viewpoint would become more clear (that it is viewed from outside) and thus reversing the order from that of yield might not be a bad idea.

kazuho commented 10 years ago

Sorry, I might have been confused.

@gfx @wasabiz Consider a sentence: "business yields profit." The input is business and the output is profit.

So the following definition should be clear enough (in the sense of English).

function* g() : InputType yield OutputType {
  var input = yield output;
}

A more real-world example would be:

// convert number to strings
function* stringify(n : number) : number yield string {
  while (true)
     n = yield n as string;
}

gfx commented 10 years ago

@kazuho I'm sorry I was confused in the meaning of "input" and "output".

// convert number to strings
function* stringify(n : number) : number yield string {
  while (true)
     n = yield n as string;
}

The above sounds really clear!

nyuichi commented 10 years ago

@kazuho @gfx

Hi, progress report!

I just commited T yield U syntax (what I call yield type notation) now. My plan is something like:

As same as the former, generator functions return Generator objects.
Generator class takes two parameters: SeedT for input type, GenT for output.
T yield U is interpreted as Generator.<T,U> at the parser level. You can put yield type notation anywhere type declaration is legal.
yield type operator is set to be very low in precedence. You can write int yield string[] to make Generator.<int, string[]>
yield has right associativity. T yield U yield V is parsed Generator.<T, Generator.<U, V>>.

Below are things not implemented now:

Rational: since passing void as a template argument is not allowed for now, you can't make a generator whose yield expressions' results are not used (= void).
First we need to implement type parameter overloading, which is not specific for generator, but is a global language change.
Then we overload Generator.<SeedT,GenT> class with an additional template class Generator.<GenT>. If SeedT is omitted, it is inferred be denoting Generator.<void,GenT>.
If the lhs is void type, a yield type notation is converted into Generator.<Foo>. (i.e. void yield int is parsed into Generator.<int>.)
Add autolifting. If a generator function is going to return a non-generator type, like function * foo () : int { ... }, the analyzer automatically lift the return type up to Generator.<int>.

These to-be-implemented list is existing simply because you are not allowed to make a void typed member variables. But I found I could suppress compiler warnings on Generator.<void,T> if Nullable.<void> becomes legal (#307). Once #307 is accepted, I can discard above todo list.

gfx commented 10 years ago

:eyes:

kazuho commented 10 years ago

Sounds great! What would be the leftovers once #307 is merged? None?

nyuichi commented 10 years ago

@kazuho

Type autolifting remains (4th on the todo list).

kazuho commented 10 years ago

@wasabiz

Thank you for the clarification. As discussed, we will take the following steps:

wasabiz merges master into wasabiz/experiments/yield-expression
kazuho modifies the test runner so that the generator tests will run for both --enable-genator-enumaltion and on node harmony

Once the two changes start working (with all the tests running fine), we will merge this branch to master.

kazuho commented 10 years ago

@wasabiz looking at https://travis-ci.org/jsx/JSX/builds/22430626 the generator tests are failing with JSX_OPTS="--optimize release,-no-log,-no-assert --minify" regardless of whether or not --enable-generator-emulation is being specified.

FYI to run the tests in both --enable-generator-emulation and non-emulation mode, you should set $PATH or $NODE_RUNJS to point to node 0.11.x, as like the following.

$ PATH="/usr/local/node-0.11.11/bin:$PATH" t/util/test-runner t/run/generator.001.example.fib.jsx 
1..2
ok 1 - t/run/generator.001.example.fib.jsx (native generator)
ok 2 - t/run/generator.001.example.fib.jsx (generator emulation)

nyuichi commented 10 years ago

@kazuho

Thank you for the test-runner fix!

I just pushed the fixes around minification as you pointed, but I found esprima had no support for es6 generators and if jsx is invoked without --enable-generator-emulation option, when JSX minifier calls him after the code generation, he stops throwing errors that he couldn't parse '*' between 'function' and '()'.

https://travis-ci.org/jsx/JSX/jobs/22593273

How to fix it?

kazuho commented 10 years ago

If that is the case, I think we should stop calling _Minifier#minifyJavaScript if any of the unsupported features is used until esprima (and escodegen?) starts to supporting them.

It would be great if you could check the issue list of esprima so that we could track the problem.

kazuho commented 10 years ago

:+1:

gfx commented 10 years ago

:+1:

jsx / JSX

Yield expression #303

Abstract

Design

Impl