Czy call / cc Scheme może implementować wszystkie znane struktury przepływu sterowania?

13

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.

csl
źródło
5
Jaka jest formalna definicja „struktury przepływu kontroli”?
Huck Bennett
4
Re: nieelimitowane kontynuacje. Czy czytałeś przywoływany artykuł Hayo Thielecke? Rzeczywiste twierdzenie jest takie, że nieokreślone kontynuacje przewidziane przezcall/cc nie 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ż tylko call/cc.)
rici
@Rici: Przejrzałem tylko kilka pierwszych stron. (Czytanie gazet zajmuje mi dużo czasu). Dziękuję za komentarz!
csl
@HuckBennett Nie mam formalnej definicji, ale nieoficjalnie mam na myśli to, co opisano na en.wikipedia.org/wiki/Control_flow - konkretnie mam na myśli, że możesz używać kontynuacji do wyrażania, a co ważniejsze, do implementacji, coroutines, zielone wątki, wyjątki, instrukcje zmiany znaczenia, amboperator i tak dalej.
csl
2
@csl Oprócz uściślenia, co oznacza „struktura kontroli przepływu”, musisz także wyjaśnić, co to znaczy „wyrazić” coś. To trudny problem, a odpowiedź na twoje pytanie zależy w dużej mierze od tego, co uznajesz za wyrażenie. W końcu zawsze możesz w jakiś sposób zakodować maszynę Turinga, która koduje interpreter języka z wyjątkami (np. Java). Ale prawdopodobnie nie to masz na myśli, więc musisz silnie ograniczyć koncepcję „ekspresji” (np. Kompozycyjność i / lub pełna abstrakcja).
Martin Berger

Odpowiedzi:

11

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ę.

Neel Krishnaswami
źródło
Ale jeśli definicja brzmi: „Czy można zaimplementować dowolną strukturę przepływu sterowania za pomocą schematu i wywołania / cc” (bez emulacji), wówczas odpowiedź musi być twierdząca ? Patrząc na dyskusję LtU lambda-the-ultimate.org/node/966 wydaje się, że Oleg Kiselyouv zaimplementował wszystkie cztery F-operatorów w Schemacie za pomocą call / cc: okmij.org/ftp/continuations/… - fragment "Kod opiera się na call / cc do przechwytywania nielimitowanych kontynuacji i wykorzystuje jedną globalną zmienną komórkę. Okazuje się, że jest to wystarczające do zaimplementowania [...] innych operatorów F. ”. ... „-F- do + F + F”.
csl
Przyjmuję do wiadomości, że użyłeś „makroekspresyjności” Felleisen jako ramy dla twojej odpowiedzi, ale jak widzisz, zmieniłem już moje pytanie, aby konkretnie znaczyło „zaimplementuj [w schemacie] za pomocą call / cc”. I podczas gdy Oleg Kiselyov musi wprowadzić globalną zmienną komórkę, aby zaimplementować wszystkie cztery operatory F dla ograniczonych kontynuacji, nie sądzę, że sprowadza się to do „poważnej, globalnej restrukturyzacji programu” - oczywiście mówiąc praktycznie.
csl
Przyjmuję tę odpowiedź. Chciałbym również wskazać tekst na okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim, który zawiera dodatkowe wskaźniki. Wydaje się również, że pierwszorzędne, ograniczone ciągłości, takie jak shift / reset, mogą być wykorzystane do wdrożenia dowolnej struktury przepływu sterowania. Z linku: „Pierwszej klasy ciągniki rozdzielane mogą wyrażać dowolny wyraźny efekt obliczeniowy, w tym wyjątki i stan zmienny”.
csl