Jak wdrożyć kontynuacje?

Dobre podsumowanie jest dostępne w Implementation Strategies for First-Class Continuations, artykuł autorstwa Clingera, Hartheimera i Ost. Polecam przyjrzeć się w szczególności realizacji programu Chez.

Kopiowanie stosu nie jest tak skomplikowane i istnieje wiele dobrze zrozumiałych technik, które mogą poprawić wydajność. Korzystanie z ramek przydzielanych stercie jest również dość proste, ale robisz kompromis w tworzeniu narzutu dla "normalnej" sytuacji, w której nie używasz wyraźne kontynuacje.

Jeśli przekonwertujesz kod wejściowy na kontynuację stylu przekazywania (CPS), możesz uniknąć całkowitego wyeliminowania stosu. Chociaż CPS jest elegancki, dodaje kolejny etap przetwarzania w przedniej części i wymaga dodatkowej optymalizacji, aby przezwyciężyć pewne implikacje wydajności.

Jeśli zaczynasz od zera, naprawdę powinieneś przyjrzeć się transformacji stylu kontynuowania (CPS).

Dobrymi źródłami są "LISP w małych kawałkach" i Schemat marca Feeleya w 90-minutowej prezentacji.

Wydaje się, że teza Dybviga nie jest do tej pory wymieniona. To przyjemność czytać. Model oparty na stercie jest najłatwiejszy do wdrożenia, ale stos oparty jest bardziej wydajny. Ignoruj model oparty na łańcuchu.

R. Kent Dybvig. "Trzy modele wdrażania programu". http://www.cs.indiana.edu/ ~ dyb/papers / 3imp. pdf

Zobacz też dokumenty wdrożeniowe na ReadScheme.org. http://library.readscheme.org/page8.html

Streszczenie jest jak następuje:

Niniejsza praca przedstawia trzy modele realizacji programu Język programowania. Rst jest modelem stosowanym w niektórych formie w większości dotychczasowych wdrożeń schematów. drugi to nowy model oparty na stosie, który jest znacznie bardziej wydajny niż model oparty na stercie przy wykonywaniu większości programów; a trzeci to nowy model oparty na łańcuchu przeznaczony do stosowania w wielu procesorach wdrożenie programu.

Model oparty na stercie przydziela kilka ważnych struktur danych w sterty, w tym rzeczywiste listy parametrów, środowiska wiązania i wywołania ramki.

Model oparty na stosie przydziela te same struktury na stosie o ile to możliwe. Skutkuje to mniejszą alokacją sterty, mniejszą pamięcią referencje, krótsze sekwencje instrukcji, mniej śmieci, i bardziej efektywne wykorzystanie pamięci.

Model oparty na łańcuchach przydziela wersje tych struktur bezpośrednio w tekst programu, który jest reprezentowany jako ciąg symboli. W model oparty na łańcuchach, programy Scheme są tłumaczone na FFP język zaprojektowany specjalnie do obsługi programu. Programy w tym języka są wykonywane bezpośrednio przez maszynę FFP, a wieloprocesorowy komputer z redukcją strun.

Model oparty na stosie ma natychmiastowe korzyści praktyczne; jest to model zastosowany przez autorski system Chez Scheme, wysokowydajny wdrożenie programu. Model oparty na łańcuchach będzie przydatne dla zapewnienie programu jako wysokiej klasy alternatywa dla FFP na maszynie FFP gdy maszyna zostanie zrealizowana.

Poza ładnymi odpowiedziami, jakie do tej pory otrzymałeś, polecam kompilację Andrew appela z kontynuacjami. Jest bardzo dobrze napisany i choć nie zajmuje się bezpośrednio C, jest źródłem naprawdę fajnych pomysłów dla twórców kompilatorów.

Chicken Wiki ma również strony, które znajdziesz bardzo interesujące, takie jak wewnętrzna struktura i proces kompilacji (gdzie CPS jest wyjaśnione rzeczywistym przykładem kompilacji).

Przykłady, na które można spojrzeć to: Chicken (implementacja schematu, napisana w języku C, która wspiera kontynuacje); Paul Graham ' s On Lisp - gdzie tworzy transformator CPS do implementacji podzbioru ciągów w Common Lispie; oraz Weblocks - Framework internetowy oparty na kontynuacji, który również implementuje ograniczoną formę ciągów w Common Lispie.

Kontynuacje nie są problemem: możesz zaimplementować te z regularnymi funkcjami wyższego rzędu za pomocą CPS. Problem z naiwną alokacją stosu polega na tym, że wywołania ogonowe nigdy nie są optymalizowane, co oznacza, że nie można być scheme.

Najlepszym obecnym podejściem do mapowania stosu spaghetti scheme na stosie jest użycie trampolin: zasadniczo dodatkowej infrastruktury do obsługi wywołań innych niż C i wyjść z procedur. Zobacz Styl Trampolinowy (ps) .

Jest jakiś kod zilustrowanie obu tych idei.

Tradycyjnym sposobem jest użycie setjmp i longjmp, choć istnieją zastrzeżenia.

Oto dość dobre wyjaśnienie

Kontynuacje zasadniczo składają się z zapisanego stanu stosu i rejestrów procesora w punkcie przełączników kontekstowych. Przynajmniej nie musisz kopiować całego stosu na stertę podczas przełączania, możesz tylko przekierować wskaźnik stosu.

Kontynuacje są trywialnie realizowane za pomocą włókien. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 . Jedyne, co wymaga starannej hermetyzacji, to przekazywanie parametrów i zwracanie wartości.

W Windows włókna są wykonywane przy użyciu rodziny połączeń CreateFiber / SwitchToFiber. w systemach zgodnych z Posix można to zrobić za pomocą makecontext / swapcontext.

Boost::coroutine ma działającą implementację coroutine dla C++ , która może służyć jako punkt odniesienia dla implementacji.

Zamiast tego używaj jawnego stosu.

Patrick ma rację, jedynym sposobem, aby to zrobić, jest użycie jawnego stosu w interpreterze i wciągnięcie odpowiedniego segmentu stosu do sterty, gdy trzeba przekonwertować go na kontynuację.

Jest to w zasadzie to samo, co to, co jest potrzebne do obsługi zamknięć w językach, które je obsługują(zamknięcia i kontynuacje są nieco ze sobą powiązane).

Jak wskazano soegaard, Głównym odniesieniem pozostaje Ten

Idea jest taka, że kontynuacja jest zamknięciem, które utrzymuje swój stos kontroli oceny. Stos kontrolny jest wymagany do kontynuowania oceny od momentu utworzenia kontynuacji za pomocą call/cc.

Często wywołanie kontynuacji powoduje długi czas wykonania i wypełnia pamięć duplikowanymi stosami. Napisałem ten głupi kod, aby udowodnić, że w mit-scheme to sprawia, że schemat crash,

Kod sumuje pierwsze 1000 liczb 1+2+3+...+1000.

(call-with-current-continuation 
 (lambda (break)
   ((lambda (s) (s s 1000 break))
    (lambda (s n cc)
      (if (= 0 n)
          (cc 0)
          (+ n
             ;; non-tail-recursive,
             ;; the stack grows at each recursive call
             (call-with-current-continuation
              (lambda (__)
                (s s (- n 1) __)))))))))

Jeśli przełączysz się z 1000 na 100 000, kod wyda 2 sekundy, a jeśli zwiększysz liczbę wejściową, spowoduje to awarię.