Was ist der Unterschied zwischen einer Fortsetzung und einem Rückruf?

Ich habe im ganzen Web nach Aufklärung über Fortsetzungen gesucht, und es ist verblüffend, wie die einfachsten Erklärungen einen JavaScript-Programmierer wie mich so völlig verwirren können. Dies gilt insbesondere dann, wenn die meisten Artikel Fortsetzungen mit Code im Schema erläutern oder Monaden verwenden.

Jetzt, da ich endlich denke, ich habe die Essenz von Fortsetzungen verstanden, wollte ich wissen, ob das, was ich weiß, tatsächlich die Wahrheit ist. Wenn das, was ich für wahr halte, nicht wirklich wahr ist, dann ist es Unwissenheit und keine Erleuchtung.

Also, hier ist was ich weiß:

In fast allen Sprachen geben Funktionen explizit Werte (und Steuerelemente) an ihren Aufrufer zurück. Beispielsweise:

var sum = add(2, 3);

console.log(sum);

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

In einer Sprache mit erstklassigen Funktionen können wir das Steuerelement und den Rückgabewert an einen Rückruf übergeben, anstatt explizit an den Aufrufer zurückzukehren:

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

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

Anstatt einen Wert von einer Funktion zurückzugeben, fahren wir mit einer anderen Funktion fort. Daher wird diese Funktion als Fortsetzung der ersten bezeichnet.

Was ist der Unterschied zwischen einer Fortsetzung und einem Rückruf?

Ich glaube, dass Fortsetzungen ein Sonderfall von Rückrufen sind. Eine Funktion kann eine beliebige Anzahl von Funktionen und eine beliebige Anzahl von Malen zurückrufen. Beispielsweise:

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);
}

Wenn eine Funktion jedoch als letztes eine andere Funktion zurückruft, wird die zweite Funktion als Fortsetzung der ersten bezeichnet. Beispielsweise:

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);
        }
    }
}

Wenn eine Funktion als letztes eine andere Funktion aufruft, wird sie als Tail-Aufruf bezeichnet. Einige Sprachen wie Scheme führen Tail-Call-Optimierungen durch. Dies bedeutet, dass der Endaufruf nicht den vollen Aufwand eines Funktionsaufrufs verursacht. Stattdessen wird es als einfaches goto implementiert (wobei der Stapelrahmen der aufrufenden Funktion durch den Stapelrahmen des Endaufrufs ersetzt wird).

Bonus : Weiter zum Weiterbestehen. Betrachten Sie das folgende Programm:

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

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

Wenn nun jede Operation (einschließlich Addition, Multiplikation usw.) in Form von Funktionen geschrieben wäre, hätten wir:

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;
}

Wenn wir keine Werte zurückgeben könnten, müssten wir außerdem die folgenden Fortsetzungen verwenden:

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);
}

Dieser Programmierstil, bei dem Sie keine Werte zurückgeben dürfen (und daher auf die Weitergabe von Fortsetzungen zurückgreifen müssen), wird als Weitergabestil für Fortsetzungen bezeichnet.

Es gibt jedoch zwei Probleme mit dem Weitergabestil:

1. Das Weitergeben von Fortsetzungen erhöht die Größe des Aufrufstapels. Wenn Sie keine Sprache wie Scheme verwenden, die Tail Calls eliminiert, besteht die Gefahr, dass Ihnen der Stapelspeicher ausgeht.
2. Es ist mühsam, verschachtelte Funktionen zu schreiben.

Das erste Problem kann in JavaScript leicht gelöst werden, indem Fortsetzungen asynchron aufgerufen werden. Durch asynchrones Aufrufen der Fortsetzung kehrt die Funktion zurück, bevor die Fortsetzung aufgerufen wird. Daher nimmt die Größe des Aufrufstapels nicht zu:

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);
}

Das zweite Problem wird normalerweise mit einer Funktion gelöst, call-with-current-continuationdie oft als abgekürzt wird callcc. Leider callcckann nicht vollständig in JavaScript implementiert werden, aber wir könnten für die meisten Anwendungsfälle eine Ersatzfunktion schreiben:

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;
}

Die callccFunktion nimmt eine Funktion auf fund wendet sie auf die current-continuation(abgekürzt als cc) an. Dies current-continuationist eine Fortsetzungsfunktion, die den Rest des Funktionskörpers nach dem Aufruf von einschließt callcc.

Betrachten Sie den Hauptteil der Funktion pythagoras:

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

Das current-continuationzweite callccist:

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

In ähnlicher Weise ist current-continuationder erste callcc:

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

Da der current-continuationerste callcceinen anderen enthält callcc, muss er in den Fortsetzungsstil konvertiert werden:

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

callccKonvertiert also im Wesentlichen logisch den gesamten Funktionskörper zurück zu dem, von dem wir ausgegangen sind (und gibt diesen anonymen Funktionen den Namen cc). Die Pythonagoras-Funktion, die diese Implementierung von callcc verwendet, wird dann:

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

Auch hier können Sie nicht callccin JavaScript implementieren , aber Sie können den Continuation-Passing-Stil in JavaScript wie folgt implementieren:

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);
}

Die Funktion callcckann verwendet werden, um komplexe Kontrollflussstrukturen wie Try-Catch-Blöcke, Coroutinen, Generatoren, Fasern usw. zu implementieren .

Trotz des wunderbaren Aufsatzes denke ich, dass Sie Ihre Terminologie ein wenig verwirren. Sie haben beispielsweise Recht, dass ein Tail-Aufruf erfolgt, wenn der Aufruf das letzte ist, was eine Funktion ausführen muss. In Bezug auf Fortsetzungen bedeutet ein Tail-Aufruf jedoch, dass die Funktion die Fortsetzung, mit der sie aufgerufen wird, nicht ändert, sondern nur, dass sie aufgerufen wird aktualisiert den an die Fortsetzung übergebenen Wert (falls gewünscht). Aus diesem Grund ist das Konvertieren einer rekursiven Endfunktion in CPS so einfach (Sie fügen einfach die Fortsetzung als Parameter hinzu und rufen die Fortsetzung des Ergebnisses auf).

Es ist auch etwas seltsam, Fortsetzungen als Sonderfall von Rückrufen zu bezeichnen. Ich kann sehen, wie leicht sie gruppiert werden können, aber Fortsetzungen entstanden nicht aus der Notwendigkeit, von einem Rückruf zu unterscheiden. Eine Fortsetzung stellt tatsächlich die verbleibenden Anweisungen dar, um eine Berechnung abzuschließen , oder den Rest der Berechnung ab diesem Zeitpunkt. Sie können sich eine Fortsetzung als eine Lücke vorstellen, die ausgefüllt werden muss. Wenn ich die aktuelle Fortsetzung eines Programms erfassen kann, kann ich genau zu dem zurückkehren, wie das Programm war, als ich die Fortsetzung erfasst habe. (Das erleichtert das Schreiben von Debuggern.)

In diesem Zusammenhang lautet die Antwort auf Ihre Frage, dass ein Rückruf eine generische Sache ist, die zu jedem Zeitpunkt aufgerufen wird, der in einem vom Anrufer [des Rückrufs] bereitgestellten Vertrag festgelegt ist. Ein Rückruf kann so viele Argumente haben, wie er möchte, und so strukturiert sein, wie er möchte. Eine Fortsetzung ist also notwendigerweise eine Prozedur mit einem Argument, die den übergebenen Wert auflöst. Eine Fortsetzung muss auf einen einzelnen Wert angewendet werden und die Anwendung muss am Ende erfolgen. Wenn eine Fortsetzung abgeschlossen ist, ist die Ausführung des Ausdrucks abgeschlossen, und abhängig von der Semantik der Sprache können Nebenwirkungen erzeugt worden sein oder nicht.

Die kurze Antwort lautet, dass der Unterschied zwischen einer Fortsetzung und einem Rückruf darin besteht, dass nach dem Aufrufen (und Beenden) eines Rückrufs die Ausführung an dem Punkt fortgesetzt wird, an dem sie aufgerufen wurde, während beim Aufrufen einer Fortsetzung die Ausführung an dem Punkt fortgesetzt wird, an dem die Fortsetzung erstellt wurde. Mit anderen Worten: Eine Fortsetzung kehrt niemals zurück .

Betrachten Sie die Funktion:

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

(Ich verwende die Javascript-Syntax, obwohl Javascript keine erstklassigen Fortsetzungen unterstützt, da Sie dies in Ihren Beispielen angegeben haben und es für Personen verständlicher ist, die mit der Lisp-Syntax nicht vertraut sind.)

Nun, wenn wir es einen Rückruf übergeben:

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

dann sehen wir drei Warnungen: "vor", "5" und "nach".

Auf der anderen Seite, wenn wir eine Fortsetzung bestehen würden, die dasselbe tut wie der Rückruf, wie folgt:

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

dann würden wir nur zwei Warnungen sehen: "vor" und "5". Das Aufrufen von c()inside add()beendet die Ausführung von add()und führt callcc()zur Rückkehr. Der von zurückgegebene Wert callcc()war der Wert, an den als Argument übergeben wurde c(nämlich die Summe).

In diesem Sinne ähnelt das Aufrufen einer Fortsetzung, obwohl es wie ein Funktionsaufruf aussieht, in gewisser Weise eher einer return-Anweisung oder dem Auslösen einer Ausnahme.

Tatsächlich kann call / cc verwendet werden, um return-Anweisungen zu Sprachen hinzuzufügen, die sie nicht unterstützen. Wenn JavaScript beispielsweise keine return-Anweisung hatte (stattdessen wie viele Lips-Sprachen nur den Wert des letzten Ausdrucks im Funktionskörper zurückgab), aber call / cc hatte, könnten wir return wie folgt implementieren:

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.
    });
}

Der Aufruf return(i)ruft eine Fortsetzung auf, die die Ausführung der anonymen Funktion beendet und callcc()den Index zurückgibt, ibei dem targetin gefunden wurde myArray.

(NB: Es gibt einige Möglichkeiten, wie die "Rückgabe" -Analogie etwas vereinfacht ist. Wenn beispielsweise eine Fortsetzung aus der Funktion entweicht, in der sie erstellt wurde, indem sie beispielsweise irgendwo in einem globalen Speicher gespeichert wird, ist es möglich, dass die Funktion das die Fortsetzung erstellt hat, kann mehrfach zurückkehren, obwohl es nur einmal aufgerufen wurde .)

Call / cc kann ebenfalls verwendet werden, um die Ausnahmebehandlung (throw und try / catch), Schleifen und viele andere Steuerungsstrukturen zu implementieren.

Um mögliche Missverständnisse auszuräumen:

• Eine Tail Call-Optimierung ist keinesfalls erforderlich, um erstklassige Fortsetzungen zu unterstützen. Bedenken Sie, dass sogar die C-Sprache eine (eingeschränkte) Form von Fortsetzungen in Form von hat setjmp(), die eine Fortsetzung erzeugt und eine longjmp()aufruft!

  • Auf der anderen Seite, wenn Sie naiv versuchen, Ihr Programm im Continuation-Passing-Stil ohne Tail-Call-Optimierung zu schreiben, sind Sie dazu verdammt, den Stapel irgendwann zu überlaufen.

• Es gibt keinen besonderen Grund, warum eine Fortsetzung nur ein Argument braucht. Es ist nur so, dass Argumente für die Fortsetzung zu den Rückgabewerten von call / cc werden, und call / cc wird normalerweise so definiert, dass sie einen einzelnen Rückgabewert haben, daher muss die Fortsetzung natürlich genau einen annehmen. In Sprachen mit Unterstützung für mehrere Rückgabewerte (wie Common Lisp, Go oder Scheme) ist es durchaus möglich, dass Fortsetzungen vorhanden sind, die mehrere Werte akzeptieren.