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

Я просматривал всю сеть в поисках информации о продолжениях, и мне ошеломляет, как простейшие объяснения могут так сильно сбить с толку такого программиста на 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);
}

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

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

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

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, сопрограммы, генераторы, волокна и т. Д.

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

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

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

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

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

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()inside 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) вполне возможно иметь продолжения, которые принимают несколько значений.