Jaka jest różnica między kontynuacją a oddzwonieniem?

Przeglądałem całą sieć w poszukiwaniu oświecenia na temat kontynuacji i jest zdumiewające, jak najprostsze wyjaśnienia mogą tak kompletnie zmylić programistę JavaScript, jak ja. Jest to szczególnie ważne, gdy większość artykułów wyjaśnia kontynuacje kodu w Scheme lub używa monad.

Teraz, kiedy w końcu wydaje mi się, że zrozumiałem istotę kontynuacji, chciałem wiedzieć, czy to, co wiem, jest w rzeczywistości prawdą. Jeśli to, co myślę, że jest prawdą, nie jest w rzeczywistości prawdą, to jest to ignorancja, a nie oświecenie.

Oto, co wiem:

W prawie wszystkich językach funkcje jawnie zwracają wartości (i sterowanie) do obiektu wywołującego. Na przykład:

var sum = add(2, 3);

console.log(sum);

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

Teraz w języku z funkcjami pierwszej klasy możemy przekazać kontrolę i zwrócić wartość do wywołania zwrotnego zamiast jawnie zwracać się do wywołującego:

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

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

Dlatego zamiast zwracać wartość z funkcji, kontynuujemy pracę z inną funkcją. Dlatego funkcja ta nazywana jest kontynuacją pierwszej.

Jaka jest różnica między kontynuacją a oddzwonieniem?

Uważam, że kontynuacje to szczególny przypadek callbacków. Funkcja może wywołać dowolną liczbę funkcji, dowolną liczbę razy. Na przykład:

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

Jeśli jednak funkcja wywołuje inną funkcję jako ostatnia czynność, wówczas druga funkcja jest nazywana kontynuacją pierwszej. Na przykład:

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

Jeśli funkcja wywołuje inną funkcję jako ostatnia rzecz, którą robi, nazywa się to wywołaniem ogonowym. Niektóre języki, takie jak Scheme, wykonują optymalizacje połączeń końcowych. Oznacza to, że wywołanie ogonowe nie pociąga za sobą pełnego narzutu wywołania funkcji. Zamiast tego jest zaimplementowany jako proste goto (z ramką stosu funkcji wywołującej zastąpioną ramką stosu wywołania końcowego).

Bonus : przejście do kontynuacji stylu podań. Rozważ następujący program:

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

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

Otóż, gdyby każda operacja (w tym dodawanie, mnożenie itp.) Była zapisana w postaci funkcji, otrzymalibyśmy:

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

Ponadto, gdybyśmy nie mogli zwrócić żadnych wartości, musielibyśmy użyć kontynuacji w następujący sposób:

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

Ten styl programowania, w którym nie możesz zwracać wartości (i dlatego musisz uciekać się do przekazywania kontynuacji) jest nazywany stylem przekazywania kontynuacji.

Istnieją jednak dwa problemy ze stylem przekazywania kontynuacji:

1. Przekazywanie kontynuacji zwiększa rozmiar stosu wywołań. Jeśli nie używasz języka takiego jak Scheme, który eliminuje wywołania końcowe, ryzykujesz brak miejsca na stosie.
2. Pisanie funkcji zagnieżdżonych jest uciążliwe.

Pierwszy problem można łatwo rozwiązać w JavaScript, wywołując kontynuacje asynchronicznie. Wywołując kontynuację asynchronicznie, funkcja zwraca przed wywołaniem kontynuacji. Stąd rozmiar stosu wywołań nie zwiększa się:

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

Drugi problem jest zwykle rozwiązywany za pomocą funkcji o nazwie, call-with-current-continuationktóra jest często określana skrótem callcc. Niestety callccnie można go w pełni zaimplementować w JavaScript, ale moglibyśmy napisać funkcję zastępującą dla większości jego przypadków użycia:

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

callccFunkcja przyjmuje funkcję fi zastosowanie go do current-continuation(w skrócie cc). Jest current-continuationto funkcja kontynuacji, która po wywołaniu zamyka resztę treści funkcji callcc.

Rozważmy treść funkcji pythagoras:

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

current-continuationDrugiego callccjest:

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

Podobnie current-continuationpierwszy callccto:

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

Ponieważ current-continuationpierwszy callcczawiera inny callcc, należy go przekonwertować na styl przekazywania kontynuacji:

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

Zasadniczo więc callcclogicznie konwertuje całą treść funkcji z powrotem do tego, od czego zaczęliśmy (i nadaje tym anonimowym funkcjom nazwę cc). Funkcja Pitagorasa używająca tej implementacji callcc staje się wtedy:

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

Ponownie nie możesz zaimplementować callccw JavaScript, ale możesz zaimplementować styl przekazywania kontynuacji w JavaScript w następujący sposób:

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

Ta funkcja callccmoże być używana do implementacji złożonych struktur przepływu sterowania, takich jak bloki try-catch, coroutines, generatory, włókna itp.

Pomimo cudownego zapisu, myślę, że trochę mylisz swoją terminologię. Na przykład, masz rację, że wywołanie ogonowe ma miejsce, gdy wywołanie jest ostatnią rzeczą, którą funkcja musi wykonać, ale w odniesieniu do kontynuacji wywołanie ogonowe oznacza, że ​​funkcja nie modyfikuje kontynuacji, z którą jest wywoływana, tylko że aktualizuje wartość przekazaną do kontynuacji (jeśli sobie tego życzy). Dlatego konwersja funkcji rekurencyjnej ogona na CPS jest tak łatwa (wystarczy dodać kontynuację jako parametr i wywołać kontynuację na wyniku).

Trochę dziwne jest również nazywanie kontynuacji specjalnym przypadkiem wywołań zwrotnych. Widzę, jak łatwo je pogrupować, ale kontynuacja nie wynikała z potrzeby odróżnienia od callback. Kontynuacja w rzeczywistości reprezentuje instrukcje pozostałe do zakończenia obliczenia lub pozostałą część obliczenia od tego momentu. Możesz myśleć o kontynuacji jako o dziurze, którą należy wypełnić. Jeśli mogę uchwycić bieżącą kontynuację programu, mogę wrócić do dokładnie tego, jak wyglądał program, kiedy przechwyciłem kontynuację. (To z pewnością ułatwia pisanie debugerów).

W tym kontekście odpowiedzią na twoje pytanie jest to, że oddzwonienie jest ogólną rzeczą, która jest wywoływana w dowolnym momencie określonym przez jakąś umowę dostarczoną przez dzwoniącego [oddzwonienia]. Wywołanie zwrotne może mieć dowolną liczbę argumentów i mieć dowolną strukturę. Kontynuacją jest zatem koniecznie procedura jeden argument to rozwiązanie wartości przekazywane do niego. Kontynuacja musi zostać zastosowana do pojedynczej wartości, a aplikacja musi nastąpić na końcu. Gdy kontynuacja kończy wykonywanie wyrażenia, jest zakończone i, w zależności od semantyki języka, mogą, ale nie muszą, zostać wygenerowane efekty uboczne.

Krótka odpowiedź jest taka, że ​​różnica między kontynuacją a wywołaniem zwrotnym polega na tym, że po wywołaniu wywołania zwrotnego (i jego zakończeniu) wykonanie jest wznawiane w miejscu, w którym zostało wywołane, podczas gdy wywołanie kontynuacji powoduje wznowienie wykonywania w miejscu, w którym kontynuacja została utworzona. Innymi słowy: kontynuacja nigdy nie powraca .

Rozważ funkcję:

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

(Używam składni Javascript, mimo że JavaScript w rzeczywistości nie obsługuje pierwszorzędnych kontynuacji, ponieważ w tym właśnie podałeś swoje przykłady i będzie bardziej zrozumiały dla osób niezaznajomionych ze składnią Lisp.)

Teraz, jeśli przekażemy mu callback:

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

wtedy zobaczymy trzy alerty: „przed”, „5” i „po”.

Z drugiej strony, gdybyśmy przekazali mu kontynuację, która robi to samo, co wywołanie zwrotne, na przykład:

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

wtedy widzielibyśmy tylko dwa alerty: „przed” i „5”. Wywołanie c()wewnątrz add()kończy wykonywanie add()i powoduje callcc()powrót; wartość zwrócona przez callcc()to wartość przekazana jako argument c(czyli suma).

W tym sensie, nawet jeśli wywołanie kontynuacji wygląda jak wywołanie funkcji, jest w pewnym sensie bardziej podobne do instrukcji return lub zgłaszania wyjątku.

W rzeczywistości call / cc może służyć do dodawania instrukcji return do języków, które ich nie obsługują. Na przykład, jeśli JavaScript nie miał instrukcji return (zamiast tego, podobnie jak wiele języków Lisp, po prostu zwracał wartość ostatniego wyrażenia w treści funkcji), ale miał wywołanie / cc, moglibyśmy zaimplementować return w ten sposób:

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

Wywołanie return(i)wywołuje kontynuację, która przerywa wykonywanie funkcji anonimowej i powoduje callcc()zwrócenie indeksu, iw którym targetzostał znaleziony w myArray.

(Uwaga: jest kilka sposobów, w których analogia „powrotu” jest nieco uproszczona. Na przykład, jeśli kontynuacja wymyka się z funkcji, w której została utworzona - powiedzmy, zapisując ją w jakimś globalnym miejscu - możliwe jest, że funkcja który utworzył kontynuację, może powrócić wiele razy, mimo że został wywołany tylko raz ).

Call / cc może służyć podobnie do implementacji obsługi wyjątków (rzut i try / catch), pętli i wielu innych struktur kontrolnych.

Aby wyjaśnić niektóre możliwe nieporozumienia:

• Optymalizacja wywołań ogonowych nie jest w żaden sposób wymagana do obsługi najwyższej klasy kontynuacji. Weź pod uwagę, że nawet język C ma (ograniczoną) formę kontynuacji w postaci setjmp(), która tworzy kontynuację, ilongjmp() która ją wywołuje!

  • Z drugiej strony, jeśli naiwnie spróbujesz napisać swój program w stylu przekazywania kontynuacji bez optymalizacji wywołań końcowych, jesteś skazany na ostateczne przepełnienie stosu.

• Nie ma szczególnego powodu, dla którego kontynuacja miałaby mieć tylko jeden argument. Po prostu argument (y) kontynuacji stają się wartościami zwracanymi przez call / cc, a call / cc jest zwykle definiowane jako mające jedną zwracaną wartość, więc naturalnie kontynuacja musi mieć dokładnie jedną. W językach obsługujących wiele zwracanych wartości (takich jak Common Lisp, Go lub w istocie Scheme) byłoby całkowicie możliwe, aby kontynuacje przyjmowały wiele wartości.