Czym jest call/cc?

Aby porównać go do C, bieżąca kontynuacja jest podobna do bieżącego stanu stosu. Posiada wszystkie funkcje oczekujące na wynik bieżącej funkcji, aby mogły wznowić wykonywanie. Zmienna przechwycona jako bieżąca kontynuacja jest używana jak funkcja, z tym wyjątkiem, że pobiera podaną wartość i zwraca ją do stosu oczekującego. To zachowanie jest podobne do funkcji C longjmp gdzie można powrócić do niższych części stosu natychmiast.

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

Kluczową różnicą między stosem C a kontynuacją jest to, że kontynuacja może być użyta w dowolnym momencie programu, nawet jeśli stan stosu się zmienił. Oznacza to, że można zasadniczo przywracać wcześniejsze wersje stosu i używać ich ponownie i ponownie, co prowadzi do pewnego unikalnego przepływu programu.

(* 123 (+ 345 (* 789 (x 5)))) ; returns 7

  reason: it is because (x 5) replaces the existing continuation,
          (* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
          5 to x, creating (+ 2 5), or 7.

Możliwość zapisywania i przywracania stanu programu ma wiele wspólnego z wielowątkowością. W rzeczywistości możesz zaimplementować swój własny wątek scheduler korzystający z ciągów, jak starałem się zilustrować tutaj .

Trywialnym przykładem użycia continuation byłoby zaimplementowanie menedżera wątków (fiber, jeśli chcesz) na jednoprocesorowej maszynie. Scheduler okresowo przerywa proces wykonywania (lub, w przypadku włókien, jest wywoływany w różnych strategicznych punktach kodu), zapisuje Stan kontynuacji (odpowiadający bieżącemu wątkowi ), a następnie przełączy się na inny Stan kontynuacji (odpowiadający innemu wątkowi, którego stan był zapisane wcześniej.)

Odnosząc się do tła asemblera, Stan kontynuacyjny przechwytuje takie szczegóły, jak wskaźnik instrukcji, rejestry i kontekst stosu (wskaźnik), do zapisania i przywrócenia do woli.

Innym sposobem użycia continuation byłoby zastąpienie wywołań metod kilkoma encjami podobnymi do wątków , które współistnieją równolegle (uruchamiane lub zawieszone) przekazując kontrolę między sobą za pomocą kontekstów continuation zamiast "klasyczny" call paradygmat. Będą działać na globalnych (współdzielonych) danych, zamiast polegać na parametrach. Jest to do pewnego stopnia bardziej elastyczne niż call w tym sensie, że stos nie musi kończyć się w górę i w dół (callssą zagnieżdżone), ale kontrola może przebiegać dowolnie.

Próbując zobrazować to pojęcie w języku takim jak C, wyobraź sobie, że masz jedną dużą pętlę z pojedynczym switch(continuation_point) { case point1: ... } stwierdzeniem, gdzie każde case odpowiada ciągowi-savepoint, a gdzie kod wewnątrz każdego case może zmienić wartość continuation_point i zrezygnować z kontroli na to continuation_point przez breaking z switch i włączyć kolejną iterację w pętli.

Jaki jest kontekst twojego pytania? Interesują Cię jakieś konkretne scenariusze? Jakiś konkretny język programowania? Czy powyższy przykład wątku/włókna jest wystarczający?

Rzecz, która mi pomogła, to pomysł, że w tradycyjnym języku z wywołaniami funkcji można bezwarunkowo przekazać kontynuację za każdym razem, gdy wykonujesz wywołanie funkcji.

Przed skokiem do kodu funkcji zapisujesz jakiś stan na stosie (tzn. wciskasz swój adres zwrotny, a stos zawiera już Twoich mieszkańców). Jest to zasadniczo kontynuacja. Po zakończeniu funkcji musi określić, gdzie wysłać przepływ wykonania. Wykorzystuje kontynuację zapisaną na stosie, wyskakując adres zwrotny i wskakując do niego.

Inne języki uogólniają tę ideę kontynuacji, pozwalając jednoznacznie określić, gdzie należy kontynuować wykonywanie kodu, a nie pośrednio kontynuować, skąd wywołanie funkcji zostało wykonane.

EDIT based on comment:

Kontynuacja jest kompletnym stanem wykonania. W dowolnym momencie wykonania można podzielić program na dwie części (w czasie, a nie w przestrzeni) - tę, która do tego momentu działała, i wszystko to ucieknie stąd. "Bieżąca kontynuacja" to "wszystko, co będzie działać stąd" (możesz myśleć o tym jak o funkcji, która zrobi wszystko, co zrobiłaby reszta twojego programu). Tak więc funkcja, którą dostarczasz call/cc otrzymuje kontynuację, która była aktualna podczas wywoływania call/cc. Funkcja może użyć kontynuacji, aby zwrócić wykonanie instrukcji call/cc (bardziej prawdopodobne, że przekaże kontynuację do czegoś innego, ponieważ jeśli użyłem go bezpośrednio, zamiast tego mógłby zrobić prosty zwrot).

Kiedy próbowałem zrozumieć call/cc, okazało się, że ta strona call-with-current-continuation-for-C-programmers była pomocna.

Wyobraź sobie, że twój scenariusz jest sceną gier wideo. Call / cc jest jak bonus stage.

Gdy tylko go dotkniesz, zostaniesz przeniesiony do etapu bonusowego(tzn. definicja funkcji przekazywana jako argument do call / cc [F w tym przypadku]).

etapy bonusowe różnią się od zwykłych etapów ponieważ zwykle mają element (tzn. argument funkcji przekazanej do call/cc) , że jeśli go dotkniesz, stracisz i zostaniesz przetransportowany powrót do normalnego stanu.

Więc nie ma znaczenia, czy jest ich wiele args, kiedy dotrzesz do jednego z nich to koniec. Więc nasza egzekucja dociera (arg 42) i zwraca ją do sumy (+ 42 10).

Są też pewne uwagi, na które warto zwrócić uwagę:

• nie wszystkie funkcje mogą być używane z call / cc. Ponieważ oczekuje kontynuacja (czyli funkcja), nie można mieć takiego f: (define f (lambda (k) (+ k 42)), ponieważ nie możesz sum a funkcja.
• również nie możesz mieć (define f (lambda (k) (f 42 10))) ponieważ kontynuacja oczekuje tylko jednego argumentu.
• możesz skończyć bez touching żadnego wyjścia, w tym przypadku funkcja przebiega jak Dowolna zwykła funkcja (np. (define f (lambda (k) 42) kończy się i zwraca 42).

Najlepsze wyjaśnienie, jakie widziałem, znajduje się w książce Paula Grahama, On Lisp .

Istnieje wiele poziomów zrozumienia call / cc. Najpierw musisz zrozumieć warunki i sposób działania mechanizmu. Następnie zrozumienie, jak i kiedy call / cc jest używany w " prawdziwym życiu" potrzebne jest programowanie.

Pierwszy poziom można osiągnąć studiując CPS, ale są alternatywy.

Na drugi poziom polecam następujący klasyk Friedmana.

Daniel P. Friedman. "Zastosowania ciągłości: zaproszeni tutoriale". 1988 Principles of Języki programowania (POPL88). Styczeń 1988.

Model, którego użyłem do zrozumienia kontynuacji z imperatywnego punktu widzenia, jest kopią stosu wywołań połączonego ze wskaźnikiem a do następnej instrukcji.

Call / cc wywołuje funkcję (przekazywaną jako argument) z kontynuacją jako argumentem.

Spójrz na opis i implementację call / cc dla FScheme: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with-continuations.aspx