В чем разница между продолжением и обратным вызовом?

Question

Я просматривал всю сеть в поисках просвещения о продолжениях, и это ошеломляет, как простейшие объяснения могут так сильно запутать программиста JavaScript, как я. Это особенно верно, когда большинство статей объясняют продолжения с помощью кода в Scheme или используют монады.

Теперь, когда я наконец-то понял, что понял суть продолжения, я хотел узнать, действительно ли то, что я знаю, является правдой. Если то, что я считаю правдой, на самом деле не является правдой, то это невежество, а не просветление.

Итак, вот что я знаю:

Почти во всех языках функции явно возвращают значения (и контроль) их вызывающей стороне. Например:

var sum = add(2, 3);

console.log(sum);

function add(x, y) {
    return x + y;
}

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

add(2, 3, function (sum) {
    console.log(sum);
});

function add(x, y, cont) {
    cont(x + y);
}

Таким образом, вместо возврата значения из функции мы продолжаем с другой функцией. Поэтому эта функция называется продолжением первой.

Так в чем же разница между продолжением и обратным вызовом?

Answer 1

Я считаю, что продолжения - это особый случай обратных вызовов. Функция может вызывать любое количество функций, любое количество раз. Например:

var array = [1, 2, 3];

forEach(array, function (element, array, index) {
    array[index] = 2 * element;
});

console.log(array);

function forEach(array, callback) {
    var length = array.length;
    for (var i = 0; i < length; i++)
        callback(array[i], array, i);
}

Однако, если функция вызывает в качестве последней функции другую функцию, тогда вторая функция называется продолжением первой. Например:

var array = [1, 2, 3];

forEach(array, function (element, array, index) {
    array[index] = 2 * element;
});

console.log(array);

function forEach(array, callback) {
    var length = array.length;

    // This is the last thing forEach does
    // cont is a continuation of forEach
    cont(0);

    function cont(index) {
        if (index < length) {
            callback(array[index], array, index);
            // This is the last thing cont does
            // cont is a continuation of itself
            cont(++index);
        }
    }
}

Если функция вызывает другую функцию как последнее, что она делает, она называется хвостовым вызовом. Некоторые языки, такие как Scheme, выполняют оптимизацию хвостовых вызовов. Это означает, что хвостовой вызов не влечет за собой полную нагрузку при вызове функции. Вместо этого он реализован в виде простого перехода (с заменой кадра стека вызывающей функции на кадр стека хвостового вызова).

Бонус: переход к продолжению прохождения стиля. Рассмотрим следующую программу:

console.log(pythagoras(3, 4));

function pythagoras(x, y) {
    return x * x + y * y;
}

Теперь, если бы каждая операция (включая сложение, умножение и т. Д.) Была записана в виде функций, то мы бы получили:

console.log(pythagoras(3, 4));

function pythagoras(x, y) {
    return add(square(x), square(y));
}

function square(x) {
    return multiply(x, x);
}

function multiply(x, y) {
    return x * y;
}

function add(x, y) {
    return x + y;
}

Кроме того, если бы нам не разрешали возвращать какие-либо значения, нам пришлось бы использовать продолжения следующим образом:

pythagoras(3, 4, console.log);

function pythagoras(x, y, cont) {
    square(x, function (x_squared) {
        square(y, function (y_squared) {
            add(x_squared, y_squared, cont);
        });
    });
}

function square(x, cont) {
    multiply(x, x, cont);
}

function multiply(x, y, cont) {
    cont(x * y);
}

function add(x, y, cont) {
    cont(x + y);
}

Этот стиль программирования, в котором вам не разрешено возвращать значения (и, следовательно, вы должны прибегать к передаче продолжения), называется стилем передачи продолжения.

Однако есть две проблемы со стилем передачи продолжения:

1. Передача продолжения увеличивает размер стека вызовов. Если вы не используете такой язык, как Scheme, который исключает хвостовые вызовы, вы рискуете исчерпать пространство стека.
2. Больно писать вложенные функции.

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

Function.prototype.async = async;

pythagoras.async(3, 4, console.log);

function pythagoras(x, y, cont) {
    square.async(x, function (x_squared) {
        square.async(y, function (y_squared) {
            add.async(x_squared, y_squared, cont);
        });
    });
}

function square(x, cont) {
    multiply.async(x, x, cont);
}

function multiply(x, y, cont) {
    cont.async(x * y);
}

function add(x, y, cont) {
    cont.async(x + y);
}

function async() {
    setTimeout.bind(null, this, 0).apply(null, arguments);
}

Вторая проблема обычно решается с помощью функции под названием call-with-current-continuation который часто сокращается как callcc, к несчастью callcc не может быть полностью реализован в JavaScript, но мы могли бы написать функцию замены для большинства его случаев использования:

pythagoras(3, 4, console.log);

function pythagoras(x, y, cont) {
    var x_squared = callcc(square.bind(null, x));
    var y_squared = callcc(square.bind(null, y));
    add(x_squared, y_squared, cont);
}

function square(x, cont) {
    multiply(x, x, cont);
}

function multiply(x, y, cont) {
    cont(x * y);
}

function add(x, y, cont) {
    cont(x + y);
}

function callcc(f) {
    var cc = function (x) {
        cc = x;
    };

    f(cc);

    return cc;
}

callcc функция принимает функцию f и применяет его к current-continuation (сокращенно как cc). current-continuation является функцией продолжения, которая оборачивает остальную часть тела функции после вызова callcc,

Рассмотрим тело функции pythagoras:

var x_squared = callcc(square.bind(null, x));
var y_squared = callcc(square.bind(null, y));
add(x_squared, y_squared, cont);

current-continuation второго callcc является:

function cc(y_squared) {
    add(x_squared, y_squared, cont);
}

Точно так же current-continuation из первых callcc является:

function cc(x_squared) {
    var y_squared = callcc(square.bind(null, y));
    add(x_squared, y_squared, cont);
}

Так как current-continuation из первых callcc содержит другой callcc это должно быть преобразовано в стиль передачи продолжения:

function cc(x_squared) {
    square(y, function cc(y_squared) {
        add(x_squared, y_squared, cont);
    });
}

Так по сути callcc логически преобразует все тело функции обратно в то, с чего мы начали (и дает этим анонимным функциям имя cc). Функция pythagoras, использующая эту реализацию callcc, становится тогда:

function pythagoras(x, y, cont) {
    callcc(function(cc) {
        square(x, function (x_squared) {
            square(y, function (y_squared) {
                add(x_squared, y_squared, cont);
            });
        });
    });
}

Опять вы не можете реализовать callcc в JavaScript, но вы можете реализовать его в стиле передачи продолжения в JavaScript следующим образом:

Function.prototype.async = async;

pythagoras.async(3, 4, console.log);

function pythagoras(x, y, cont) {
    callcc.async(square.bind(null, x), function cc(x_squared) {
        callcc.async(square.bind(null, y), function cc(y_squared) {
            add.async(x_squared, y_squared, cont);
        });
    });
}

function square(x, cont) {
    multiply.async(x, x, cont);
}

function multiply(x, y, cont) {
    cont.async(x * y);
}

function add(x, y, cont) {
    cont.async(x + y);
}

function async() {
    setTimeout.bind(null, this, 0).apply(null, arguments);
}

function callcc(f, cc) {
    f.async(cc);
}

Функция callcc может использоваться для реализации сложных структур управления потоками, таких как блоки try-catch, сопрограммы, генераторы, волокна и т. д.

Answer 2

Несмотря на замечательную рецензию, я думаю, что вы немного путаете свою терминологию. Например, вы правы в том, что хвостовой вызов происходит, когда вызов - это последнее, что должна выполнить функция, но в отношении продолжений хвостовой вызов означает, что функция не изменяет продолжение, с которым она вызывается, только то, что она обновляет значение, переданное продолжению (если оно того пожелает). Вот почему конвертировать хвостовую рекурсивную функцию в CPS так легко (вы просто добавляете продолжение в качестве параметра и вызываете продолжение в результате).

Также немного странно называть продолжения частным случаем обратных вызовов. Я вижу, как их легко сгруппировать, но продолжения не возникли из-за необходимости отличать их от обратного вызова. Продолжение фактически представляет инструкции, остающиеся для завершения вычисления, или оставшуюся часть вычисления с этого момента времени. Вы можете думать о продолжении как о дыре, которую нужно заполнить. Если я смогу зафиксировать текущее продолжение программы, тогда я смогу вернуться к тому, какой была программа, когда я захватил продолжение. (Это, несомненно, облегчает написание отладчиков.)

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

Answer 3

Короткий ответ заключается в том, что различие между продолжением и обратным вызовом состоит в том, что после того, как обратный вызов вызван (и завершился), выполнение возобновляется с той точки, в которой оно было вызвано, а при вызове продолжения выполнение возобновляется с того момента, когда было создано продолжение. Другими словами: продолжение никогда не возвращается.

Рассмотрим функцию:

function add(x, y, c) {
    alert("before");
    c(x+y);
    alert("after");
}

(Я использую синтаксис Javascript, хотя Javascript на самом деле не поддерживает первоклассные продолжения, потому что это было то, что вы привели в качестве примеров, и это будет более понятным для людей, не знакомых с синтаксисом Lisp.)

Теперь, если мы передадим ему обратный вызов:

add(2, 3, function (sum) {
    alert(sum);
});

тогда мы увидим три предупреждения: "до", "5" и "после".

С другой стороны, если мы передадим ему продолжение, которое делает то же самое, что и обратный вызов, например:

alert(callcc(function(cc) {
    add(2, 3, cc);
}));

тогда мы увидим только два предупреждения: "до" и "5". Вызов c() внутри add() заканчивает исполнение add() и причины callcc() возвращать; значение, возвращаемое callcc() был оценен как аргумент c (а именно сумма).

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

Фактически, call/cc может использоваться для добавления операторов возврата к языкам, которые их не поддерживают. Например, если в JavaScript не было оператора return (вместо этого, как и во многих языках Lips, просто возвращающих значение последнего выражения в теле функции), но имел call/cc, мы могли бы реализовать return следующим образом:

function find(myArray, target) {
    callcc(function(return) {
        var i;
        for (i = 0; i < myArray.length; i += 1) {
            if(myArray[i] === target) {
                return(i);
            }
        }
        return(undefined); // Not found.
    });
}

призвание return(i) вызывает продолжение, которое прекращает выполнение анонимной функции и вызывает callcc() вернуть индекс i в котором target был найден в myArray,

(NB: есть некоторые способы, в которых аналогия "возврата" немного упрощена. Например, если продолжение выходит из функции, в которой оно было создано - будучи сохраненным где-то в глобальном, скажем, - возможно, что функция создавшее продолжение может возвращаться несколько раз, даже если оно было вызвано только один раз.)

Call / cc также может быть использован для реализации обработки исключений (throw и try/catch), циклов и многих других управляющих структур.

Чтобы устранить некоторые возможные заблуждения:

• Оптимизация хвостового вызова не требуется для поддержки первоклассных продолжений. Учтите, что даже язык C имеет (ограниченную) форму продолжений в форме setjmp(), который создает продолжение, и longjmp(), который вызывает один!

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

• Нет особой причины, по которой продолжение требует только одного аргумента. Просто аргумент (ы) продолжения становятся возвращаемыми значениями call/cc, а call / cc обычно определяется как имеющий одно возвращаемое значение, поэтому, естественно, продолжение должно принимать ровно одно. В языках с поддержкой нескольких возвращаемых значений (таких как Common Lisp, Go или даже Scheme) вполне возможно иметь продолжения, которые принимают несколько значений.