Jaki jest przykład kontynuacji niezaimplementowanej jako procedura?

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.

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.

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