Асинхронное программирование и стиль прохождения продолжения в JavaScript

    function loadAvatarImage(id) {
        var profile = loadProfile(id);
        return loadImage(profile.avatarUrl);
    }

    function loadAvatarImage(id, callback) {
        loadProfile(id, function (profile) {
            loadImage(profile.avatarUrl, callback);
        });
    }

    function loadAvatarImage(id, callback) {
        loadProfile(id, loadProfileAvatarImage);  // (*)
        function loadProfileAvatarImage(profile) {
            loadImage(profile.avatarUrl, callback);
        }
    }

JavaScript
поднимает функцию loadProfileAvatar (перемещает ее в начало функции). Следовательно, он может быть вызван в (*). Мы вложили loadProfileAvatarImage в loadAvatarImage, потому что ему нужен был доступ к обратному вызову. Вы будете видеть этот тип вложенности всякий раз, когда есть состояние, которое будет разделено между вызовами функций. Альтернативой является использование выражения функции немедленного вызова (IIFE,
[1] ):

    var loadAvatarImage = function () {
        var cb;
        function loadAvatarImage(id, callback) {
            cb = callback;
            loadProfile(id, loadProfileAvatarImage);
        }
        function loadProfileAvatarImage(profile) {
            loadImage(profile.avatarUrl, cb);
        }
        return loadAvatarImage;
    }();

Итерация по массиву

Следующий код содержит простой цикл for.

    function logArray(arr) {
        for(var i=0; i < arr.length; i++) {
            console.log(arr[i]);
        }
        console.log("### Done");
    }

Давайте преобразуем его в CPS в два этапа. Первым шагом является использование рекурсии для итерации. Это обычная техника в функциональном программировании. Следующий код все еще в прямом стиле.

    function logArray(arr) {
        logArrayRec(0, arr);
        console.log("### Done");
    }
    function logArrayRec(index, arr) {
        if (index < arr.length) {
            console.log(arr[index]);
            logArrayRec(index+1, arr);
        }
        // else: done
    }

Теперь стало проще конвертировать код в CPS. Мы делаем это, вводя вспомогательную функцию forEachCps.

    function logArray(arr) {
        forEachCps(arr, function (elem, index, next) {  // (*)
            console.log(elem);
            next();
        }, function () {
            console.log("### Done");
        });
    }
    function forEachCps(arr, visitor, done) {  // (**)
        forEachCpsRec(0, arr, visitor, done)
    }
    function forEachCpsRec(index, arr, visitor, done) {
        if (index < arr.length) {
            visitor(arr[index], index, function () {
                forEachCpsRec(index+1, arr, visitor, done);
            });
        } else {
            done();
        }
    }

Есть два интересных изменения: посетитель в (*) получает свое собственное продолжение next, которое запускает следующий шаг «внутрь» forEachCpsRec. Это позволяет нам делать CPS-вызовы в посетителе, например, для выполнения асинхронного запроса. Мы также должны предоставить продолжение сделано в (**), чтобы указать, что происходит после завершения цикла.

Отображение массива

Если немного переписать forEachCps, мы получим CPS-версию Array.prototype.map.

    function mapCps(arr, func, done) {
        mapCpsRec(0, [], arr, func, done)
    }
    function mapCpsRec(index, outArr, inArr, func, done) {
        if (index < inArr.length) {
            func(inArr[index], index, function (result) {
                mapCpsRec(index+1, outArr.concat(result),
                          inArr, func, done);
            });
        } else {
            done(outArr);
        }
    }

mapCps принимает массивоподобный объект и создает новый массив, применяя func к каждому элементу. Приведенная выше версия является неразрушающей, она создает новый массив для каждого шага рекурсии. Следующее является разрушительным вариантом:

    function mapCps(arrayLike, func, done) {
        var index = 0;
        var results = [];

        mapOne();

        function mapOne() {
            if (index < arrayLike.length) {
                func(arrayLike[index], index, function (result) {
                    results.push(result);
                    index++;
                    mapOne();
                });
            } else {
                done(results);
            }
        }
    }

mapCps используется следующим образом.

    function done(result) {
        console.log("RESULT: "+result);  // RESULT: ONE,TWO,THREE
    }
    mapCps(["one", "two", "three"],
        function (elem, i, callback) {
            callback(elem.toUpperCase());
        },
        done);

Вариация: параллельная карта. Последовательная версия mapCps не так эффективна, как могла бы быть. Например, если каждый шаг сопоставления включает запрос к серверу, он отправляет первый запрос, ожидает результата, отправляет второй запрос и т. Д. Вместо этого было бы лучше отправить все запросы, а затем дождаться результатов. Особое внимание необходимо уделить тому, чтобы они были добавлены в выходной массив в правильном порядке. Следующий код делает все это.

    function parMapCps(arrayLike, func, done) {
        var resultCount = 0;
        var resultArray = new Array(arrayLike.length);
        for (var i=0; i < arrayLike.length; i++) {
            func(arrayLike[i], i, maybeDone.bind(null, i));  // (*)
        }
        function maybeDone(index, result) {
            resultArray[index] = result;
            resultCount++;
            if (resultCount === arrayLike.length) {
                done(resultArray);
            }
        }
    }

В (*) мы должны скопировать текущее значение переменной цикла i. Если мы не будем копировать, мы всегда получим текущее значение i в продолжении. Например, arrayLike.length, если продолжение вызывается после завершения цикла. Копирование также может быть выполнено через IIFE или с использованием Array.prototype.forEach вместо цикла for.

Итерация по дереву

Дана следующая прямая функция стиля, которая рекурсивно обрабатывает дерево вложенных массивов.

    function visitTree(tree, visitor) {
        if (Array.isArray(tree)) {
            for(var i=0; i < tree.length; i++) {
                visitTree(tree[i], visitor);
            }
        } else {
            visitor(tree);
        }
    }

Эта функция используется следующим образом:

    > visitTree([[1,2],[3,4], 5], function (x) { console.log(x) })
    1
    2
    3
    4
    5

Если вы хотите разрешить посетителю делать асинхронные запросы, вам нужно переписать visitTree в CPS:

    function visitTree(tree, visitor, done) {
        if (Array.isArray(tree)) {
            visitNodes(tree, 0, visitor, done);
        } else {
            visitor(tree, done);
        }
    }
    function visitNodes(nodes, index, visitor, done) {
        if (index < nodes.length) {
            visitTree(nodes[index], visitor, function () {
                visitNodes(nodes, index+1, visitor, done);
            });
        } else {
            done();
        }
    }

У нас также есть возможность использовать forEachCps:

    function visitTree(tree, visitor, done) {
        if (Array.isArray(tree)) {
            forEachCps(
                tree,
                function (subTree, index, next) {
                    visitTree(subTree, visitor, next);
                },
                done);
        } else {
            visitor(tree, done);
        }
    }

Ловушка: выполнение продолжается после передачи результата

В прямом стиле возврат значения завершает функцию:

    function abs(n) {
        if (n < 0) return -n;
        return n;  // (*)
    }

Следовательно, (*) не выполняется, если n меньше нуля. Напротив, возврат значения в CPS в (**) не завершает функцию:

    // Wrong!
    function abs(n, success) {
        if (n < 0) success(-n);  // (**)
        success(n);
    }

Следовательно, если n <0, то вызываются и success (-n), и success (n). Исправить несложно — напишите полное утверждение if.

    function abs(n, success) {
        if (n < 0) {
            success(-n);
        } else {
            success(n);
        }
    }

Требуется некоторое привыкание к тому, что в CPS поток логического управления продолжается через продолжение, а поток физического управления — нет (пока).

CPS и контроль потока

CPS определяет «следующий шаг» — он «превращает его в вещь» (определение «reify»), с которым вы можете работать. В прямом стиле функция бессильна в отношении того, что происходит после ее вызова, в CPS она имеет полный контроль. Произошла так называемая «инверсия контроля». Давайте подробнее рассмотрим поток управления в обоих стилях.

Прямой стиль. Вы вызываете функцию, и она должна вернуться к вам, она не может избежать вложенности, которая происходит с вызовами функций. Следующий код содержит два таких вызова: f вызывает g, который вызывает h.

    function f() {
        console.log(g());
    }
    function g() {
        return h();
    }
    function h() {
        return 123;
    }

Поток управления в виде диаграммы:

Продолжение прохождения стиля. Функция определяет, куда идти дальше. Он может решить продолжить «как приказано» или сделать что-то совершенно другое. Следующий код является версией CPS предыдущего примера.

    function f() {
        g(function (result) {
            console.log(result);
        });
    }
    function g(success) {
        h(success);
    }
    function h(success) {
        success(123);
    }

Теперь поток управления совершенно другой. f вызывает g, вызывает h, который затем вызывает продолжение g, которое вызывает f. Поток управления в виде диаграммы:

Возвращение

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

    function searchArray(arr, searchFor, success, failure) {
        forEachCps(arr, function (elem, index, next) {
            if (compare(elem, searchFor)) {
                success(elem);  // (*)
            } else {
                next();
            }
        }, failure);
    }
    function compare(elem, searchFor) {
        return (elem.localeCompare(searchFor) === 0);
    }

CPS позволяет нам немедленно выйти из цикла в (*). В Array.prototype.forEach мы не можем этого сделать, мы должны дождаться окончания цикла. Если мы переписываем сравнение в CPS, то оно автоматически возвращается для нас из цикла.

    function searchArray(arr, searchFor, success, failure) {
        forEachCps(arr, function (elem, index, next) {
            compareCps(elem, searchFor, success, next);
        }, failure);
    }
    function compareCps(elem, searchFor, success, failure) {
        if (elem.localeCompare(searchFor) === 0) {
            success(elem);
        } else {
            failure();
        }
    }

Это довольно удивительно. Чтобы добиться аналогичного эффекта в прямом стиле, нам нужны исключения.

Попробуйте поймать

С CPS вы можете даже реализовать обработку исключений на языке — нет необходимости в специальной языковой конструкции. В следующем примере мы реализуем функцию printDiv в CPS. Он вызывает функцию CPS div, которая может вызвать исключение. Следовательно, он оборачивает этот вызов в tryIt, нашу реализацию try-catch.

    function printDiv(a, b, success, failure) {
        tryIt(
            function (succ, fail) {  // try
                div(a, b, function (result) {  // might throw
                    console.log(result);
                    succ();
                }, fail);
            },
            function (errorMsg, succ, fail) {  // catch
                handleError(succ, fail);  // might throw again
            },
            success,
            failure
        );
    }

Чтобы сделать обработку исключений, каждой функции нужно два продолжения; один для успешного завершения и один в случае сбоя. Функция try реализует оператор try-catch. Его первый аргумент — блок try, который имеет свои собственные локальные версии продолжения успеха и неудачи. Второй аргумент — это блок catch, который снова имеет локальные продолжения. Последние два аргумента являются продолжениями, которые применяются к функции в целом. Div деления CPS выдает исключение, если делитель равен нулю.

    function div(dividend, divisor, success, failure) {
        if (divisor === 0) {
            throwIt("Division by zero", success, failure);
        } else {
            success(dividend / divisor);
        }
    }

А теперь реализация обработки исключений.

    function tryIt(tryBlock, catchBlock, success, failure) {
        tryBlock(
            success,
            function (errorMsg) {
                catchBlock(errorMsg, success, failure);
            });
    }
    function throwIt(errorMsg, success, failure) {
        failure(errorMsg);
    }

Обратите внимание, что продолжения блока catch определены статически, они не передаются ему при вызове продолжения сбоя. Это те же продолжения, что и у полной функции tryIt.

Генератор

Генераторы — это функция ECMAScript.next, которую вы уже можете попробовать в текущей версии Firefox
[2] . Генератор — это объект, который упаковывает функцию. Каждый раз, когда вызывается метод next () для объекта, выполнение функции продолжается. Каждый раз, когда функция выполняет выходное
значение , выполнение приостанавливается, и next () возвращает
значение . Следующий генератор производит бесконечную последовательность чисел 0, 1, 2, …

    function* countUp() {
        for(let i=0;; i++) {
            yield i;
        }
    }

Обратите внимание на бесконечный цикл в функции, обернутый объектом генератора. Этот бесконечный цикл продолжается каждый раз, когда next () вызывается и приостанавливается каждый раз при использовании yield. Пример взаимодействия:

    > let g = countUp();
    > g.next()
    0
    > g.next()
    1

Если мы реализуем генераторы через CPS, различие между функцией генератора и объектом генератора становится более очевидным. Сначала напишем генератор как функцию countUpCps.

    function countUpCps() {
        var i=0;
        function nextStep(yieldIt) {
            yieldIt(i++, nextStep);
        }
        return new Generator(nextStep);
    }

countUpCps оборачивает объект генератора вокруг функции генератора, которая написана на CPS. Он используется следующим образом:

    var g = countUpCps();
    g.next(function (result) {
        console.log(result);
        g.next(function (result) {
            console.log(result);
            // etc.
        });
    });

Конструктор для объектов-генераторов может быть реализован следующим образом.

    function Generator(genFunc) {
        this._genFunc = genFunc;
    }
    Generator.prototype.next = function (success) {
        this._genFunc(function (result, nextGenFunc) {
            this._genFunc = nextGenFunc;
            success(result);
        });
    };

Обратите внимание, как мы храним текущее продолжение функции генератора внутри объекта. Мы не передаем это.

CPS и стек

Еще одним интересным аспектом CPS является то, что он делает стек устаревшим, потому что вы всегда продолжаете и никогда не возвращаетесь. Это означает, что если ваша программа полностью в CPS, то вам нужны только механизмы для перехода к функции и для создания среды (для хранения параметров и локальных переменных). Но нет стека. Другими словами, вызов функции в CPS очень похож на оператор goto. Давайте посмотрим на пример, который иллюстрирует это. Ниже приведена функция с циклом for:

    function f(n) {
        var i=0;
        for(; i < n; i++) {
            if (isFinished(i)) {
                break;
            }
        }
        console.log("Stopped at "+i);
    }

Та же самая программа, реализованная через goto, выглядит так:

    function f(n) {
        var i=0;
    L0: if (i >= n) goto L1;
        if (isFinished(i)) goto L1;
        i++;
        goto L0;
    L1: console.log("Stopped at "+i);
    }

Версия CPS (без учета isFinished) не сильно отличается:

    function f(n) {
        var i=0;
        L0();
        function L0() {
            if (i >= n) {
                L1();
            } else if (isFinished(i)) {
                L1();
            } else {
                i++;
                L0();
            }
        }
        function L1() {
            console.log("Stopped at "+i);
        }
    }

Хвостовые звонки

Давайте еще раз посмотрим на следующую функцию прямого стиля, которая использует рекурсию для перебора массива:

    function logArrayRec(index, arr) {
        if (index < arr.length) {
            console.log(arr[index]);
            logArrayRec(index+1, arr);  // (*)
        }
        // else: done
    }

В текущем JavaScript стек будет расти для каждого дополнительного элемента массива. Однако, если мы посмотрим поближе, мы поймем, что нет необходимости сохранять стек при выполнении саморекурсивного вызова в (*). Это последний вызов функции, поэтому возвращать нечего. Вместо этого можно удалить данные текущей функции из стека перед выполнением вызова, и стек не будет расти. Если вызов функции идет последним в функции, он называется
хвостовым вызовом . Большинство функциональных языков программирования осуществляют вышеупомянутую оптимизацию. Вот почему цикл через рекурсию так же эффективен в этих языках, как итеративная конструкция (например, цикл for). Все истинные вызовы функций CPS являются хвостовыми вызовами и могут быть оптимизированы. Факт, на который мы намекали, когда упоминали, что они похожи на заявления goto.

батуте

CPS является популярным промежуточным форматом для компиляторов языков функций, потому что многие конструкции потока управления могут быть элегантно выражены, а оптимизация хвостовых вызовов проста. При компиляции на язык без оптимизированных хвостовых вызовов можно избежать роста стека с помощью техники, называемой
trampolining . Идея состоит не в том, чтобы сделать последний вызов внутри функции, а в том, чтобы выйти и вернуть продолжение на
батут . Этот батут — просто петля, которая вызывает возвращенные продолжения. Следовательно, нет вложенных вызовов функций, и стек не будет расти. Например, предыдущий код CPS может быть переписан следующим образом для поддержки батута.

    function f(n) {
        var i=0;
        return [L0];
        function L0() {
            if (i >= n) {
                return [L1];
            } else if (isFinished(i)) {
                return [L1];
            } else {
                i++;
                return [L0];
            }
        }
        function L1() {
            console.log("Stopped at "+i);
        }
    }

В CPS каждый вызов функции всегда является хвостовым вызовом. Мы трансформируем каждый звонок

    func(arg1, arg2, arg3);

в обратном заявлении

    return [func, [arg1, arg2, arg3]];

Батут забирает возвращенные массивы и выполняет соответствующий вызов функции.

    function trampoline(result) {
        while(Array.isArray(result)) {
            var func = result[0];
            var args = (result.length >= 2 ? result[1] : []);
            result = func.apply(null, args);
        }
    }

Теперь мы вызываем f следующим образом:

    trampoline(f(14));

Очередь событий и прыжки на батуте

В браузерах и Node.js батут осуществляется через очередь событий. Если у вас много вызовов CPS в строке (без ожидания асинхронного результата через очередь событий), вы можете поместить продолжение в эту очередь и избежать переполнения стека. Следовательно, вместо

    continuation(result);

ты пишешь

    setTimeout(function () { continuation(result) }, 0);

Node.js даже имеет специальную функцию
process.nextTick () для этой цели:

    process.nextTick(function () { continuation(result) });

Вывод

Стиль асинхронного программирования в JavaScript эффективен, потому что вам не нужно создавать новые процессы. И это легко понять. Но это также может быстро стать громоздким. Поэтому полезно иметь больше информации об этом, что в этом сообщении в блоге объясняется стиль прохождения продолжения. Он также показал некоторые методы, которые делают CPS более терпимым, но есть и другие. Это будет тема следующего сообщения в блоге (быстрый тизер: обещания).

Связанное чтение

1. Область видимости переменной JavaScript и ее подводные камни
2. Испытание ECMAScript.next для цикла … в Firefox 13