4. О том, как делать кооперативную многозадачность на Javascript, и почему она не работает

update от 5 августа

В исходном тетрисе кооперативная многозадачность была. Выглядела она вот так:

procedure HighScores;
begin
   while true do
   begin
       ClearHighScoresDisplay;
       for i:= 1 to 10 do 
       begin
            ShowHighScoreElement(i)
            for j := 1 to 20 do PleaseYield;
       end;
   end
end;

procedure ChooseMenu;
const
  selected: integer  = -1;
  current: integer = 0;
begin
   while selected = -1 do
   begin
       if (keyPressed[keyUp]) then dec(current);
       if (keyPressed[keyDown]) then inc(current);
       if (keyPressed[keyEnter]) then selected := current;
       displaySelection(current);
       PleaseYield;
   end
end;

procedure MainProc;
begin
        TaskManager.addTask(@HighScores);
        TaskManager.addTask(@ChooseMenu);
        TaskManager.runTasks();
end;

Очевидной особенностью этой многозадачности является сохранение контекста внутри каждого цикла при переключении между двумя (или более задачами).

end of update

Вследствие того, что на JS многозадачности нет, а Web Workers - урезанные, задача переноса указанного паскаля в JS кажется невыполнимой, но на помощь приходит Javascript 1.7 (в том смысле что в 1.7 точно оно есть).

Сначала сразу объясню, почему Web Workers урезанные. Потенциально можно запустить их в параллель, но они сожрут всё ЦПУ, а операции sleep в джаваскрипте нету. Вместо sleep нам предлагают использовать setTimeout, который не подходит, потому что после sleep хочется продолжить в том же цикле, с теми же переменными, и со всеми переменными выше по стеку (в вызывающих функциях). По мне так они жлобы, эти разработчики Web Workers, потому что там-то уж, внутри worker-a, ничто не мешает разрешить sleep, пусть даже через отдельную JS-переменную, которая для этих workers предоставляет API.

Так вот, в JS 1.7 есть yield! Он позоволяет заморозить выполнение в середине цикла, вернуть управление супервизору, и потом восстановить выполнение том же месте цикла.

В JS 1.7 это преподносится как "генераторы":

function f() {
    var z = 5;
    for (var q = 1; q < 20; q++) {
        z = z + q;
        if (z % 2 == 0) yield (z * 3); else yield (z / 5);
    }
}

Вот я написал пример генератора, который между итерациями сохраняет состояние. А вызывается это так:

var g1 = f();
try {
    while (true) {
        print(g1.next());
    }
} catch (ex) {   /* end of sequence */
}

Многозадачность реализуется посредством получения сразу нескольких генераторов (вызовов функций, которые требуется запустить паралелльно), и потом по очереди вызывания на них next().

Всё бы хорошо, но наши PleaseYield нельзя менять однозначно на yield, потому что, как оказалось, если PleaseYield можно рефакторить (скажем, оформлять куски его содержащие в отдельную процедуру), то yield нельзя, потому что лишь наличие yield в теле конкретной функции делает ее генератором, и в этой же функции нельзя пользовать "return value", т.к. получается когнитивный диссонанс. Мне кажется, такое ограничение, выраженное в "нельзя использовать", свидетельствует об убогости дизайна yield, потому что какая-либо нормальная реализация того же механизма не вступала бы в противоречие с уже существующими, как например введение препроцессора в С не вступает в противоречие с синтаксисом С.

Так вот, для того, чтобы Yield можно было свободно встречать в любом месте, нам нужно сделать так, чтобы если yield встречается глубоко во время вызова какой-то функции, чтобы оно "пробросилось на самый верх", к тому генератору, который собственно вызван пользователем. Это делается так:

var yi = SOME_ROUTINE();
if (isGenerator(yi)) {
    for (var i in yi) yield i;
}

Как уже говорилось в предыдущем посте, наш javascript генерится в plain text вместо AST. Это значит, что мы не можем пройтись по всему дереву и насчитать, какие процедуры у нас бывают генераторами, а какие - нет.

На хакатоне времени особо не было переписывать генерацию JS, потому решили сделать все процедуры генераторами, а все функции - не генераторами. Оригинальный код был подправлен. Теперь процедуры возвращали out-variables посредством throw, снаружи оно ловилось, или приходило обычное возвращаемое значение, всё это анализировалось и присваивались выходные переменные, или же работали yields, как в примере выше. Это всё настолько страшно, что я даже не буду вставлять куски кода для примера.

Наверное так же точно подумали и бровзеры, и тот же google-traceur, потому что они стали валиться по недостатку памяти.

Что же они делают? Дальше идут мои предположения. Наверняка их реализация javascript-а такова, что вызовы javascript функций происходят на нативном стеке. То есть интерпретатор (путь даже JIT) расходует нативный стек, когда вычисляет глубокую рекурсию. Наверняка все конторы вложились основательно в JS реализации бровзеров. И вот в этот момент их застала новая JS-спецификация где было введена операция yield, которую так просто не реализовать на нативном стеке. Поэтому они вынуждены делать преобразование кода, выворачивая yield наизнанку. То есть, такой кусок кода:

function x() {
    something1();
    yield 1;
    something2();
    yield 2;
    something3();
}

Превращается в:

function x1_1(ctx) {
    something1(ctx.context++);
    return 1;
}
function x1_2(ctx) {
    something2(ctx.context++);
    return 2;
}
function x1_3(ctx) {
    something3(ctx.context++);
    throw new GenerationStop();
}
function x() {
    var ctx = {context: 2}
    return builtin_iterate_parts(ctx, [x1_1, x1_2, x1_3]);
}

Я такое преобразование сам видел, оно возможно, и наверняка есть какая-то теория под это всё. Ужас в том, что оно очень громоздко.

В нашем коде получается очень много yield. Наверное такой код не так просто вывернуть наизнанку, и получаются мегабайты, оттого и проблемы с бровзерами.

На этом мы закончили Hackaton.

Читать дальше.