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


136

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?


4
Część mnie uważa, że ​​to naprawdę dobre pytanie, a część uważa, że ​​jest za długie i prawdopodobnie skutkuje odpowiedzią „tak / nie”. Jednak ze względu na wysiłek i badania związane z tym, idę z moim pierwszym uczuciem.
Andras Zoltan

2
Jakie jest Twoje pytanie? Wygląda na to, że całkiem dobrze to rozumiesz.
Michael Aaron Safyan

3
Tak, zgadzam się - myślę, że prawdopodobnie powinien to być wpis na blogu bardziej podobny do „Kontynuacji JavaScript - jak je rozumiem”.
Andras Zoltan

9
Cóż, jest zasadnicze pytanie: „Jaka jest więc różnica między kontynuacją a oddzwonieniem?”, Po którym następuje „Wierzę…”. Odpowiedź na to pytanie może być interesująca?
Zamieszanie

3
Wygląda na to, że może być lepiej opublikowany na programmers.stackexchange.com.
Brian Reischl,

Odpowiedzi:


165

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.


10
Jestem tak wdzięczny, że słowa nie mogą tego opisać. W końcu zrozumiałem na poziomie intuicji wszystkie koncepcje związane z kontynuacją za jednym zamachem! Znowu, kiedy kliknął, miał być prosty i zobaczyłem, że użyłem tego wzoru wiele razy, zanim nieświadomie, i tak było po prostu. Dziękuję bardzo za wspaniałe i jasne wyjaśnienie.
ata

2
Trampoliny to dość proste, ale potężne rzeczy. Proszę sprawdzić post Reginalda Braithwaite'a o nich.
Marco Faustinelli

1
Dziękuję za odpowiedź. Zastanawiam się, czy mógłbyś w większym stopniu wspierać stwierdzenie, że callcc nie może być zaimplementowane w JavaScript? Ewentualnie wyjaśnienie, jaki JavaScript będzie potrzebny, aby go zaimplementować?
John Henry

1
@JohnHenry - cóż, właściwie jest implementacja call / cc w JavaScript wykonana przez Matta Mighta ( matt.might.net/articles/by-example-continuation-passing-style - przejdź do ostatniego akapitu), ale proszę nie robić zapytaj mnie, jak to działa i jak go używać :-)
Marco Faustinelli

1
@JohnHenry JS potrzebowałby kontynuacji pierwszej klasy (pomyśl o nich jako o mechanizmie do przechwytywania pewnych stanów stosu wywołań). Ale ma tylko funkcje i zamknięcia pierwszej klasy, więc CPS jest jedynym sposobem na naśladowanie kontynuacji. W Schemacie kontury są niejawne, a częścią zadania callcc jest „reifikacja” tych niejawnych kont, tak aby funkcja konsumująca miała do nich dostęp. Dlatego callcc w Scheme oczekuje funkcji jako jedynego argumentu. Wersja callcc CPS w JS różni się, ponieważ cont jest przekazywany jako jawny argument func. Więc callcc Aadita jest wystarczające dla wielu aplikacji.
scriptum

27

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.


3
Dziękuję Ci za wyjaśnienie. Masz rację. Kontynuacja jest w rzeczywistości reifikacją stanu sterowania programu: migawką stanu programu w określonym momencie. Fakt, że można go nazwać normalną funkcją, nie ma znaczenia. Kontynuacje w rzeczywistości nie są funkcjami. Z drugiej strony wywołania zwrotne są w rzeczywistości funkcjami. To prawdziwa różnica między kontynuacjami a oddzwonieniami. Niemniej jednak JS nie obsługuje pierwszorzędnych kontynuacji. Tylko funkcje pierwszej klasy. Stąd kontynuacje napisane w CPS w JS to po prostu funkcje. Dziękuję za wkład. =)
Aadit M Shah

4
@AaditMShah tak, źle powiedziałem. Kontynuacja nie musi być funkcją (lub procedurą, jak ją nazwałem). Z definicji jest to po prostu abstrakcyjna reprezentacja rzeczy, które dopiero nadejdą. Jednak nawet w Scheme kontynuacja jest wywoływana jak procedura i przekazywana jako jedna. Hmm ... pojawia się równie interesujące pytanie, jak wygląda kontynuacja, która nie jest funkcją / procedurą.
dcow

@AaditMShah na tyle interesujące, że kontynuowałem dyskusję tutaj: programmers.stackexchange.com/questions/212057/ ...
dcow

14

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.


2
Przepraszamy za błędy w przykładach JavaScript. Napisanie tej odpowiedzi z grubsza podwoiło całkowitą ilość napisanego przeze mnie JavaScript.
cpcallen

Czy dobrze rozumiem, że w tej odpowiedzi mówisz o nieograniczonych kontynuacjach, a przyjęta odpowiedź mówi o ograniczonych kontynuacjach?
Jozef Mikušinec

1
„wywołanie kontynuacji powoduje wznowienie wykonywania w miejscu, w którym kontynuacja została utworzona” - myślę, że mylisz „tworzenie” kontynuacji z przechwytywaniem bieżącej kontynuacji .
Alexey

@Alexey: popieram ten rodzaj pedanterii. Ale większość języków nie zapewnia żadnego innego sposobu tworzenia (zreifikowanej) kontynuacji niż przechwytywanie bieżącej kontynuacji.
cpcallen

1
@jozef: Z pewnością mówię o nieograniczonych kontynuacjach. Myślę, że taka była również intencja Aadita, chociaż jak zauważa dcow, przyjęta odpowiedź nie odróżnia kontynuacji od (blisko spokrewnionych) ogonów, a ja zauważam, że rozgraniczona kontynuacja jest i tak równoważna funkcji / procedurze: community.schemewiki.org/ ? tutorial-kontynuacji-
kompozycji
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.