Korekta vs kontynuacja vs generator

147

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

Mehdi Asgari
źródło
2
Zastanawiam się, czy programy i kontynuacje są faktycznie równoważne. Wiem, że można modelować programy z kontynuacjami, ale czy można modelować kontynuacje za pomocą programów, czy nie, ponieważ kontynuacje są bardziej wydajne?
nalply

Odpowiedzi:

127

Zacznę od generatorów, ponieważ są one najprostszym przypadkiem. Jak wspomniał @zvolkov, są to funkcje / obiekty, które można wielokrotnie wywoływać bez zwracania, ale po wywołaniu zwracają (zwracają) wartość, a następnie zawieszają ich wykonanie. Kiedy zostaną ponownie wezwani, zaczną od miejsca, w którym ostatnio zawiesili wykonanie, i zrobią swoje.

Generator jest zasadniczo ograniczonym (asymetrycznym) programem. Różnica między programem a generatorem polega na tym, że program może przyjmować argumenty po jego pierwotnym wywołaniu, podczas gdy generator nie może.

Trochę trudno jest wymyślić trywialny przykład użycia coroutines, ale oto moja najlepsza próba. Weźmy ten (zmyślony) kod Pythona jako przykład.

def my_coroutine_body(*args):
    while True:
        # Do some funky stuff
        *args = yield value_im_returning
        # Do some more funky stuff

my_coro = make_coroutine(my_coroutine_body)

x = 0
while True:
   # The coroutine does some funky stuff to x, and returns a new value.
   x = my_coro(x)
   print x

Przykładem zastosowania koreutynów są leksery i parsery. Bez koreprogramów w języku lub w jakiś sposób emulowanych, leksowanie i parsowanie kodu muszą być mieszane razem, mimo że są to tak naprawdę dwie odrębne kwestie. Ale używając coroutine, możesz oddzielić kod leksykalny i parsujący.

(Mam zamiar przeoczyć różnicę między symetrycznymi i asymetrycznymi korutynami. Wystarczy powiedzieć, że są równoważne, można konwertować z jednego do drugiego, a asymetryczne korutyny - które są najbardziej podobne do generatorów - są łatwiejsze do zrozumienia. Opisywałem, jak można zaimplementować asymetryczne programy w Pythonie).

Kontynuacje to właściwie całkiem proste bestie. Wszystkie one są funkcjami reprezentującymi inny punkt w programie, który, jeśli go wywołasz, spowoduje automatyczne przejście do punktu, który reprezentuje funkcja. Używasz ich bardzo ograniczonych wersji każdego dnia, nawet nie zdając sobie z tego sprawy. Na przykład wyjątki można traktować jako swego rodzaju kontynuację na odwrót. Dam ci przykład kontynuacji oparty na pseudokodzie w Pythonie.

Powiedzmy, że Python ma wywołaną funkcję callcc(), która pobiera dwa argumenty, pierwszy to funkcja, a drugi to lista argumentów, z którymi można ją wywołać. Jedynym ograniczeniem tej funkcji byłoby to, że ostatnim argumentem, który przyjmuje, będzie funkcja (która będzie naszą obecną kontynuacją).

def foo(x, y, cc):
   cc(max(x, y))

biggest = callcc(foo, [23, 42])
print biggest

To co by się stało, callcc()to z kolei wywołanie foo()z bieżącą kontynuacją ( cc), czyli odniesieniem do punktu w programie, w którym callcc()został wywołany. Kiedy foo()wywołuje bieżącą kontynuację, jest to w zasadzie to samo, co callcc()polecenie powrotu z wartością, z którą wywołujesz bieżącą kontynuację, a kiedy to robi, cofa stos do miejsca, w którym bieżąca kontynuacja została utworzona, tj. Kiedy zadzwoniłeś callcc().

Rezultatem tego wszystkiego byłby wydruk naszego hipotetycznego wariantu Pythona '42'.

Mam nadzieję, że to pomoże i jestem pewien, że moje wyjaśnienie można znacznie poprawić!

Keith Gaughan
źródło
6
Jedna nitka: rozgraniczone kontynuacje to funkcje, ale nieograniczone kontynuacje to nie: okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim
Frank
2
Trafne spostrzeżenie. To powiedziawszy, w większości praktycznych zastosowań, kiedy ludzie mówią „kontynuacja”, mają na myśli częściowe / ograniczone kontynuacje. Wprowadzenie różnych innych rodzajów kontynuacji nieco pogmatwałoby wyjaśnienie.
Keith Gaughan,
1
Kontynuacje nie są funkcjami, chociaż można je zreifikować w funkcje. „To powiedziawszy, w większości praktycznych zastosowań, kiedy ludzie mówią„ kontynuacja ”, mają na myśli częściowe / ograniczone kontynuacje”. Czy wskazałbyś na takie użycie terminu „kontynuacja”? Nigdy nie spotkałem się z takim użyciem. Podałeś również przykład nieograniczonej kontynuacji, używając call / cc. Operatory dla rozdzielonych kontynuacji to zwykle „reset” i „shift” (mogą mieć inne nazwy).
Ivancho
3
Zacznijmy od tego, że minęło pięć lat, odkąd to napisałem. Spóźniłeś się na imprezę. Po drugie, wiem, że nieograniczone kontynuacje nie są funkcjami, ale ty o tobie starasz się wyjaśnić, jak one działają, bez odnoszenia się do nich jako takich, jednocześnie zachowując prostotę języka. Z punktu widzenia przeciętnego programisty fakt, że nieograniczona kontynuacja nie zwraca, czyni ją po prostu funkcją jednorazową, co nie jest poprawne zgodnie z definicją funkcji, ale jest co najmniej zrozumiałe .
Keith Gaughan
2
Nie spóźniam się na imprezę, ponieważ to pierwszy wynik, jaki otrzymuję w google, gdy wyszukuję hasło „coroutine vs generator”. Miałem nadzieję, że znajdę dobre informacje na temat ich różnic. W każdym razie znalazłem to gdzie indziej. Nie jestem pierwszym, który wskazał, że twoje wyjaśnienie dotyczące kontynuacji jest błędne. Problem polega na tym, że ktoś pomyli się i prawdopodobnie będzie później zdezorientowany, gdy spotka się z tym samym słowem, które jest używane dla czegoś innego.
Ivancho,
33

Program jest jedną z kilku procedur, które wykonują swoją pracę na zmianę, a następnie zatrzymują się, aby przekazać kontrolę innym programom w grupie.

Kontynuacja to „wskaźnik do funkcji” przekazywany do jakiejś procedury do wykonania („kontynuacja z”) po zakończeniu tej procedury.

Generator (w .NET) to konstrukcja języka, która może wypluć wartość, „wstrzymać” wykonanie metody, a następnie przejść od tego samego punktu, gdy zostanie wyświetlony monit o podanie następnej wartości.

zvolkov
źródło
Zdaję sobie sprawę, że odpowiedź może nie być dokładna, ale na tym poziomie pytania starałem się zachować prostotę. Poza tym sam tego wszystkiego nie rozumiem :)
zvolkov
Generator w Pythonie jest podobny do wersji C #, ale jest zaimplementowany jako specjalna składnia do tworzenia instancji obiektu iteratora, który zwraca wartości zwracane przez podaną definicję „funkcji”.
Benson
2
Mała poprawka: „… w tym stos wywołań i wszystkie zmienne, ALE NIE ICH WARTOŚCI” (lub po prostu usuń „wszystkie zmienne”). Kontynuacje nie zachowują wartości, po prostu zawierają stos wywołań.
nalply
Nie, kontynuacje nie są „wskazówkami do funkcji”. W najbardziej naiwnej implementacji zawiera wskaźnik funkcji, a środowisko przechowuje zmienne lokalne. I nigdy nie zwraca, chyba że użyjesz czegoś takiego jak call / cc do przechwycenia go z wartością zwracaną.
NalaGinrut
9

W nowszej wersji Pythona możesz wysyłać wartości do Generatorów za pomocą generator.send(), co sprawia, że ​​Generatory Pythona są efektywnie dopasowane.

Główna różnica między generatorem Pythona a innym generatorem, powiedzmy Greenlet, polega na tym, że w Pythonie yield valuemożesz tylko wrócić do dzwoniącego. Będąc w greenlet, target.switch(value)może zabrać cię do określonego programu docelowego i podać wartość, przy której targetnadal będzie działać.

Yichuan Wang
źródło
3
Ale w Pythonie wszystkie yieldwywołania muszą mieć tę samą funkcję, która nazywa się „generatorem”. Nie możesz yieldz podfunkcji, dlatego Python nazywa się semi-coroutines , podczas gdy Lua ma asymetryczne coroutines . (Są propozycje rozmnażania plonów, ale myślę, że te tylko mętną wodę.)
cdunn2001
7
@ cdunn2001: (komentarz Winstona) Python3.3 wprowadził wyrażenie „yield from”, które pozwala uzyskać wydajność z generatora podrzędnego.
Linus Caldwell