Jaki jest przykład kontynuacji niezaimplementowanej jako procedura?

15

Interesująca dyskusja na temat rozróżnienia między wywołaniami zwrotnymi a kontynuacjami w SO spowodowała, że ​​pytanie to się pojawiło. Z definicji kontynuacja jest abstrakcyjną reprezentacją logiki potrzebnej do ukończenia obliczeń. W większości języków manifestuje się to jako procedura jednopargumentowa, do której przekazujesz dowolną wartość wymagającą dalszego przetwarzania.

W czysto funkcjonalnym języku (gdzie wszystkie funkcje są czystymi obywatelami pierwszej klasy), pomyślałbym, że kontynuacja mogłaby być całkowicie modelowana jako funkcja. W końcu tak właśnie rozumiałem kontynuacje do tego momentu. Jednak świat jest pełen stanu (westchnienie ...), więc ogólna definicja nie wymaga, aby stan programu przechwytywania kontynuacji - wymagał jedynie zamiaru.

Aby pomóc mi zrozumieć, czy można podać przykład w języku funkcjonalnym, w którym kontynuacja jest wyrażona w sposób bardziej abstrakcyjny niż funkcja? Wiem, że Schemat pozwala uchwycić bieżącą kontynuację w pierwszorzędny sposób (call / cc), ale mimo to wydaje się, że procedura jednego argumentu przekazana do call / cc jest po prostu dana bieżącej kontynuacji w postaci innej procedura argumentu, do której funkcja call / cc'd może zastosować swój wynik.

David Cowden
źródło
Być może przecięcie kontynacji i defunkcjonalizacji jako: kontynuacje można przekształcić w struktury danych poprzez defunkcjonalizację; może być interesującym obszarem do obejrzenia.
Dan D.
@DanD. Czy masz jakieś sugestie dotyczące interesującej literatury, którą mogę przeczytać? Ten temat wydaje się przydatny.
David Cowden,

Odpowiedzi:

11

tl; dr; Typ jest nadrzędnym abstrakcji nad kontynuacją


Kontynuacją jest rodzaj danych wejściowych i wyjściowych

Najbardziej zbliżoną do kontynuacji nieopartej na procedurach jest prawdopodobnie monada kontynuacji w Haskell, ponieważ jest wyrażona jako typ, dla którego można użyć wielu funkcji do interakcji z typem w celu przerwania, wznowienia, cofnięcia i innych.

Możesz zamknąć to zamknięcie w typ, taki jak Conttyp w Haskell, w którym otrzymujesz abstrakcję monady jako „abstrakcję wyższego poziomu”, a istnieją inne formy abstrakcji nad kontynuacjami, które otrzymasz, gdy spojrzysz na kontynuację jako typ zamiast po prostu procedura , na przykład

  • Możesz wziąć dwie kontynuacje i zrobić alternatywę między nimi, jeśli typ przestrzega praw, aby być monoidem
  • Możesz streścić na typie, aby zmienić typ kontynuacji lub wejścia kontynuacji, jeśli zamkniesz zamknięcie w typie zgodnym z prawami funktora
  • Możesz dowolnie i częściowo zastosować lub ozdobić swoją kontynuację funkcjami, takimi jak walidacja lub konwersja danych wejściowych, jeśli zamkniesz zamknięcie w typie zgodnym z prawami funktora aplikacyjnego

Zamknięcie a procedura

Pod koniec dnia masz rację; kontynuacja jest „procedurą”, choć wolałbym nazywać ją „zamknięciem”. Często kontynuacje są najlepiej wyrażane jako zamknięcia pierwszej klasy, które otaczają ograniczone środowisko. W czysto funkcjonalnym języku można powiedzieć, że nie jest to szczególnie uzasadnione, ponieważ brakuje referencji; jest to prawda, ale można zawrzeć wartości, a pojedyncze przypisanie sprawia, że ​​zawarcie wartości względem odwołania jest dokładnie takie samo. To powoduje w Haskell:

(\x -> \y -> insideYIcanAccess x (and y))

Język, który nie ma możliwości zamknięcia wiążącego środowiska, może technicznie nie mieć zamknięć pierwszej klasy, ale nawet wtedy istnieje pewne środowisko (ogólnie globalne), które jest dostępne dla zamknięcia.

Powiedziałbym więc, że dokładniej jest opisać kontynuację jako: Zamknięcie jest używane w określony sposób.


Wniosek

Na pytanie „Czy kontynuację można wdrożyć w jakikolwiek inny sposób niż procedurę?” Nie. Jeśli nie masz funkcji pierwszej klasy , tak naprawdę nie możesz mieć kontynuacji jako takiej (tak wskaźniki funkcji liczą się jako funkcje pierwszej klasy, więc alternatywnie wystarczający może być dowolny dostęp do pamięci).

Teraz pytanie: „Czy są jakieś sposoby na wyrażenie kontynuacji w sposób bardziej abstrakcyjny niż procedura?” Wyrażenie go jako typu daje znacznie większą abstrakcję, pozwalając traktować kontynuację w bardzo ogólny sposób, dzięki czemu możesz wchodzić w interakcję z kontynuacją na wiele innych sposobów niż tylko jej wykonanie.

Jimmy Hoffa
źródło
1
Uogólnia to do „Kontynuacją może być po prostu wszystko, co pozwala uzyskać wynik pozostałej części programu”. Ponieważ zwykle wymaga to posiadania kodu (reszta programu), większość języków używa funkcji. Teoretycznie możesz zbudować kontynuację z czegokolwiek. Podczas konwersji kontynuacji w moich kompilatorach użyłem częściowo wypełnionych drzew.
Daniel Gratzer,
1
Częściowo wypełnione drzewa @jozefg są właściwą reprezentacją obliczeń jako wyrażeń, ale pod koniec dnia napisany kod jest rodzajem wyrażenia, które nie może być wyraźnie różne od procedury, takiej jak ja to rozumiem. Poza tym częściowo wypełnione drzewa stanowią kompilator; reprezentacja programistów jest oczekiwanym wyrażeniem obliczeniowym normatywnym ze składnią i semantyką języka, które wydaje się 99% programistów jako „procedura”, „funkcja” lub w inny sposób. Myślisz z perspektywy twórcy kompilatora heh
Jimmy Hoffa
2

Jednym z przykładów, które mogą ci się spodobać, są coroutines. Na przykład Coroutines z Lua lub iteratory / generatory z Python lub C # mają moc podobną do kontynuacji one-shot (kontynuacje, które można wywołać tylko raz), ale kontynuacja nie jest jawnie przekształcona w funkcję. Zamiast tego masz sposoby, aby przesunąć koronę do następnej instrukcji „wydajności”.

Rozważmy na przykład następujący program w języku Python:

def my_iterator():
   yield 1
   yield 2
   yield 3

def main():
   it = my_iterator()
   x = it.next()
   y = it.next()
   z = it.next()
   print x + y + z

Jest podobny do następującego programu Javascript z wyraźnymi wywołaniami zwrotnymi:

function my_iterator()
  return function(cb1){
    cb1(1, function(cb2){
      cb2(2, function(cb3){
        cb3(3, function(cb4){
          throw "stop iteration";
        });
      });
    });
  });
}

function main(){
   var getNext1 = my_iterator();
   getNext1(function(x, getNext2){
      getNext2(function(y, getNext3){
         getNext3(function(z, getNext4){
            console.log(x + y + z);
         });
      });
   });
}

Przykład Javascript jest trochę głośny, ponieważ każdy krok musi zwrócić następną kontynuację oprócz zwracanej wartości (w Pythonie śledzi kontynuację wewnątrz ite

hugomg
źródło