Strona „Advanced Scheme: Some Naughty Bits” stanowi:
Kontynuacje są potężnym konstruktem sterowania przepływem, z którego można wyprowadzić prawie każdą inną strukturę przepływu sterowania [...].
Myślałem, że Scheme call/cc, związane (*) z operatorem J Petera Landina, może być wykorzystane do wdrożenia dowolnej znanej struktury przepływu sterowania?
W „strukturze kontroli przepływu” szczególnie myślę o ich opisie w Wikipedii , np. Wyjątki, coroutines, zielone wątki i tak dalej.
W szczególności, czy istnieją jakieś przykłady struktur przepływu sterowania, których nie można zaimplementować call/cc?
(*) Nie byłem w stanie wykopać żadnego papieru, który wykazałby, że call/ccjest tak potężny jak operator J. Artykuł Felleisen (którego nie przeczytałem i co prawda mam problemy ze zrozumieniem go w pełni) bada to i wydaje się, że dochodzi do wniosku, że mimo iż należą one do różnych klas złożoności, są formalnie równoważne.
(Pamiętaj również, że zaktualizowałem pytanie w oparciu o poniższe komentarze)
Aktualizacja
Opierając się na doskonałej odpowiedzi @Neel poniżej, przyjrzałem się stronom komentującym ograniczone i nieodelimowane kontynuacje , i rzeczywiście wydaje się, że chociaż call/ccbrak ograniczenia, nie jest wystarczający. Tymczasem, jak się wydaje, można wykorzystać pierwszorzędne, ograniczone (kontynuowane shift/reset) kontynuacje ( wyrażenia) do wyrażenia dowolnej struktury przepływu sterowania.
call/ccnie mogą wyrażać wyjątków przy braku stanu . (Jak zauważa Thielecke, wyjątki można wdrożyć, przekazując dwie kontynuacje, jedną dla programu, a drugą dla procedury obsługi wyjątków, ale to wymaga więcej niż tylkocall/cc.)amboperator i tak dalej.Odpowiedzi:
W tej odpowiedzi rozumiem „ekspresywny” w znaczeniu „makroekspresyjny” w sensie Felleisen 1991, On The Expressive Power of Programming Languages . (Intuicyjnie funkcja języka jest wyrażalna makro, jeśli można zdefiniować ją jako lokalną transformację źródłową, bez użycia transformacji całego programu).
Przy tej definicji odpowiedź brzmi „ nie” : kontrola rozdzielana nie jest wyrażalna w makrach w rachunku lambda + wywołanie / cm3. Aby wyrazić rozdzielone operatory sterowania za pomocą połączenia / cc. Aby zaimplementować ograniczniki kontrolne (część resetowania shift / reset), potrzebny jest pewien stan do symulacji znaków kontynuacji, w zasadzie do zakodowania stosu, aby zasymulować dynamiczne czasy życia znaków kontynuacji.
Jednak kontrola ograniczona jest efektem uniwersalnym, w następującym znaczeniu. W swojej pracy doktorskiej , Andrzej Filiński pokazał, że każdy eksprymowanej skutkiem ubocznym jest kodowane przy użyciu albo rozdzielonych kontynuacje lub zadzwoń / CC i pojedynczą komórkę państwa. Z grubsza „wyraźnym efektem ubocznym” jest każdy efekt, którego typ monadyczny można zdefiniować w kategoriach rodzajów języka programowania.
Co zaskakujące, pomysł ten wydaje się dość interesujący w praktyce. W ciągu ostatniej dekady Gordon Plotkin i John Power opowiadali się za algebraiczną semantyką teorii efektów : chodzi o to, że określasz działania niepożądane, którymi jesteś zainteresowany, i równania, które oczekujesz, że będą spełnione, a następnie możesz ogólnie uzyskać semantykę, biorąc wolną monadę nad tą teorią.
Matija Pretnar i Andrej Bauer przyjęli to matematyczne podejście, a następnie wdrożyli je w swoim języku Eff, aby wymyślić nowy konstrukt językowy nazwany „programami obsługi efektów”: możesz napisać kod, który używa zestawu funkcji imperatywnych, a następnie nadać tym funkcjom semantykę pisząc zestaw procedur obsługi, które mówią, jak zaimplementować każdą skuteczną operację.
źródło