2. О тетрисе (Battle Tetris)

Для конвертации в HTML/JS/Canvas на Хакатоне была выбрана игра, написанная под ДОС.

Конкретно этот тетрис был написан мною в ХПИ в 1994 году, когда я учился на 1 или 2 курсе. Тетрис написан на турбо-паскале (как и всё тогда), и пользовался популярностью в узких кругах.

Он имеет две особенности

1. С точки зрения пользователя:
   
   Можно играть вчетвером (или меньшим количеством) за одной клавиатурой. Причем игроки зарабатывают очки обычным образом, и тратят их в магазине, покупая разнобразные товары и услуги, которые затем в процессе дальнейшей игры по отдельной клавише запускаются в действие. Услуги эти разные: замедлить себе скорость или повысить скорость товарищу, купить себе фигуру "палка" или инвертировать левое Г на правое, поменять на время товарищу левую и правую кнопки, чтобы помучался итд.
   
2. С точки зрения архитектуры:
   
   Программа написана не в едином цикле, как все нормальные игры, а с использованием кооперативной многозадачности. Например, на каждый "стакан" (штука, куда падают фигуры) заводится отдельный цикл (while true), в котором опрашиваются клавиши именно того игрока к которому стакан принадлежит. Появляющиеся в процессе игры персональные для игрока меню (магазин) тоже ничего ни о чем не знают, крутятся себе в цикле "пока пользователь не закроет". Разлетающаяся в куски фигура (есть такой пункт в магазине) разлетается несколько кадров, а разлет реализуется маленьким тредом (потоком), покуда основной поток остановлен.
   
   В самой игре работает около 20 потоков одновременно в пике. Каждый имеет свой стек, самый настоящий, и всё управление потоками написано на ассемблере. После того, как супервизор был написан, написание игры превратилось в сплошное удовольствие. Получилось, как будто ерланг 8), с тем отличием, что я вставлял вызовы функции PleaseYield во все циклы, которые могли долго работать, имея в виду, что каждый поток от одного PleaseYield до следующего PleaseYield отработает 1 раз в кадр, потому что в одном из потоков дожидалось начала кадра, так было задумано.

Недостатком игры является несбалансированность цен, и криволинейное увеличение скорости игры, т.к. это не было для меня особо интересным тогда.

Игра в то время обитала в Харьковском FidoNet, а может и дальше, и я не знаю о ее судьбе. Наверное в нее игрывало несколько людей вне ХПИ, не знаю. Тогда не было ни твиттера, ни распространения email.

Тетрис был написан, поигран, и жил на дискетах в шкафу, откуда я его и спас с появлением интернета, и тех пор он болтался за мной в моем архиве. Как и всякий умственно усталый человек, я жалел его выбросить и с теплотой вспоминал о днях далекой юности.

Картинки или читать дальше:

1. About page:

2. Final scroller (во время выхода в ДОС):

3. Главное меню:

4. Собственно игра:

5. Турбо паскаль, вид на Task Manager:

6. Использование оного Task Manager:

7. Загрузка игры a-la Doom.

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

5. О том, что нас спасёт.

(если вы сразу пришли на эту страницу, вам рекомендуется читать сию историю с самого начала, .)

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

var yi = SOME_ROUTINE();

if (isGenerator(yi)) {

for (var i in yi) yield i;

}

чтобы уменьшить количество этих ненужных yield, расположенных в таких циклах. Но я думаю, что их там всё же останется порядочно.

Поэтому уже после Хакатона, было решено покопать в ортогональном направлении, и ... портануть на джаваскрипт интерпретатор джаваскрипта, работающий не в глубину стека, а на одном уровне, и эмулирующий стек в куче, и таким образом легко и прекрасно реализующий как continuations, так и co-routines (yield).

Этим интерпретатором оказался mozilla rhino. Это java-проект, который используется я не знаю где еще, но я им уже пользовался много лет назад. Для того, чтобы убедиться, что он не умрёт на больших файлах, я отключил тамошний оптимизатор, и запустил только интерпретатор. Да, главный цикл интерпретатора простой, никто никуда вглубь не идет, и по тексту программы видны сладкие слова: continuation, tail call и yield. Это оно.

С оптимизатором оно умеет генерировать .class файлы, и именно там я и увидел вывернутые наизнанку и порезанные функции, содержавшие yield. Я думаю, что мы не будем искушать судьбу, и не будем запускать оптимизатор на нашем тетрисе, а воспользуемся интерпретатором.

Вдобавок, перед нами еще стоит задача портировать эту махину на Javascript, чтобы оно работало под бровзером. К счастью, волшебная палочка, делающая сие уже есть, и она называется GWT (Google Web Toolkit). Статьи не хватит, чтобы описать всю крутизну сего гуглового проекта, в котором гугл четырьмя меткими ударами соединил трудносоединимое и получил то что есть. (дальше 4 пункта рекламы) Эти четыре удара:

1. использование java как базового языка (а не C, или C# или Php) , это позволяет использовать лучшую из IDE - IntelliJ IDEA, и полноценный компилятор и линкер из java в javascript, с базовыми java libraries. Использование языка со строгой типизацией (java) позволяет писать огроменные проекты для бровзера.
2. whole program optimization и permutations, генерящие очень ёмкий javascript конкретно под каждый бровзер (можно использовать другой, или в дополнение к этому, базис)
3. отладка прямо в бровзере программы на Java, не выходя из любимого IDE! При 99.99% гарантированном совпадении конечного результата с тем, что наблюдается в отладке, и это не кропотливая работа индусов, проверяющих точность какой-нибудь эмуляции, а выбранный гуглом более правильный подход, который не даст иного результата.
4. направление в компиляции, позволяющее делить или соединять куски программы, картинок, текста и данных в любом требуемом варианте. Например, одной из самых первых фич была добавлена возможность на этапе компиляции склеивать статические картинки участвующие в дизайне страницы так, чтобы потом программно они виделись разными, а на сайт ехали одним .gif -ом или jpeg-ом, и уже на месте прозрачно для программиста становились background-ами с требуемым offset-om, чтобы было видно только нужную часть этой большой картинки. Поразительным при этом было то, как мало требуется от программиста для того, чтобы перейти к этой технологии.

Продолжаем, нас пока интересует только компилятор из java в js. Естественно, он не поддерживает кучу java функционала, который неприменим на вебе. Нам придется изрядно покоцать интерпретатор, чтобы он скушался компилятором GWT..

От него ушел весь .class-генерящий оптимизатор, часть интерпретатора, которая работает с сорцами в потоках (супротив строк), всё security, все модули, требуемые по стандарту ECMA, включая функцию (или оператор?) require, ушла вся интеграция с Java native functions посредством reflection, потому что только reflection нам и не хватало (GWT строится на code reachability, как краеугольном принципе, строя графы вызовов, оттуда отсутствие поддержки reflection). Ушла вся оптимизация плавающей точки, потому что она юзала платформенное представление точки по битам, а в JS этого нету. Отправились в небытие также NativeRegexp и XML расширения скрипта, чтобы не перегружать runtime, осталось всего полтора мегабайта кода, или 46000 строк, и я верю, что можно отрезать добрую половину.

Целый день происходила битва с rhino, и вот он готов.

Сегодня запустилась тестовая программа на паскале, которая рисует фрактал. В ней заюзаны все механизмы, которые надо, и они типа работают.

Что мы имеем в результате?

1. PROG.PAS ----> Хаскильный транслятор -----> PROG.JS
2. PROG.JS + RHINO.JAVA ----> GWT -----> Executor.JS (embedded PROG.JS as string)
3. Executor.JS + Browser + Canvas -----> PROFIT!

Написана также еще одна ветка:

2. RHINO.JAVA + PROG.JS --> JAVA runtime --> анимация на GUI

Это чтобы в бровзер не лазить и GWT не дергать. Понятно, что устройство вывода абстрагировано, и представлено в JS разными реализациями.

Сорцы прилагаются:

PAPOROTN.PAS

paporotn.js (глючный, там продублировалась ф-я)

Компилятор, в pre-alpha стадии.

Итак, теперь результат. Повторяю, вы видите как работает интерпретатор многопоточного (yield) Javascript, сконвертированного (via Haskell) из Turbo Pascal, сам интерпретатор Javascript-а "Rhino" написан на Java, портирован (via gwt + ножницы) в Javascript.
Внизу работающая программа, проверено под Chrome, Mozilla. Если в опере загрузить ее отладчик DragonFly, то там отчего-то тоже начинает работать.
В программе можно кликнуть на папоротник, и нажать на ESC, чтобы прекратило кушать CPU.
Продолжение следует.

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.

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