Patrzę na techniki implementacji języków programowania, a ostatnio natknąłem się na stosy spaghetti, które podobno dobrze pasują do modelu stylu kontynuacji przechodzenia (biorąc pod uwagę ich zastosowanie np. W Scheme i SML / NJ ). Dla uproszczenia rozważmy tylko jedno-wątkowe procesy dla tego pytania.
Jestem jednak nieco zdezorientowany schematem na Wikipedii (również znalezionym gdzie indziej ). W szczególności nie rozumiem, w jaki sposób może powstać taka sytuacja. Mogę sobie tylko wyobrazić, że wyszarzone gałęzie są nieosiągalne i należy je wyrzucać do śmieci. Z drugiej strony, z moim niejasnym zrozumieniem, jak wdrożyć CPS przy użyciu stosów spaghetti, nie wyobrażam sobie, jak można uzyskać pętlę w tej strukturze. Muszę dojść do wniosku, że zamiast „drzewa wskaźników nadrzędnych”, jest to w rzeczywistości ukierunkowany wykres acykliczny, z tyloma źródłami nie śmieciowymi, ile jest wątków i tyle pochłaniaczy, ile jest (potencjalnych) „punktów wyjścia”.
Ale moje rozumienie tej implementacji jest dość niejasne, więc chyba coś mi umknęło. Mam nadzieję, że ktoś mnie tu oświeci na „stosach wywołań spaghetti”, przez co rozumiem strukturę danych stosowaną w Schemacie i / lub SML / NJ do implementacji procesów opartych na CPS.
Biorąc pod uwagę następujący stos wywołań spaghetti:
[exit point] <-- ... <-- [frame A] <-- [frame B (active)] ^ `---- [frame C]O ile rozumiem, jakakolwiek kontrola przepływu z B albo rozwija stos, przeskakując do rodzica (A staje się aktywny, nieosiągalny B jest teraz śmieciem), lub zastępując aktywną ramkę subgrafem, połączonym tylko przy użyciu referencji przechowywanych przez B lub referencji do nowych ramek. Wykonanie nie może przejść do ramki C, co musi oznaczać, że ramka C jest śmieciem.
Zamiast poprzedniej sytuacji pomyślałem, że może powstać następująca sytuacja bez śmieci:
[exit point] <-- ... <-- [frame W] <-- [frame X] <-- [frame Z (active)] ^ | `---- [frame Y] <---´Na przykład mogę sobie wyobrazić, że ramka Z należy do jakiejś funkcji decyzyjnej, która albo kontynuuje ramkę X, albo ramkę Y (każda z nich powróciłaby do W). Oznacza to, że stosy wywołań spaghetti nie są „nadrzędnymi drzewami wskaźnikowymi ”.
Nie mogę sobie jednak wyobrazić żadnej sytuacji, w której można zbudować pętlę. Weźmy na przykład następującą sytuację:
[exit point] <-- ... <-- [frame P] --> [frame Q (active)] ^ | | v `---- [frame R]Wiem, że wiązania rekurencyjne to coś, ale bardzo wątpię, czy jest to rozsądne. Jeśli Q ma powrócić do R, ramka Q jest „wydana”. Gdyby R powrócił do P, a P nie może po prostu wrócić do Q, ponieważ najpierw trzeba by go ponownie zainicjować. Jako takie, pętle spowodowałyby niespójne stany. (Chyba że, oczywiście, nie zrozumiem celu tej struktury danych, a użyte w niej węzły będą służyć jako szablon dla bieżącej ramki).
Z tych obserwacji muszę wywnioskować, że stos wywołań spaghetti (bez śmieci) to tak naprawdę DAG. Czy to jest poprawne? Czy też źle rozumiem cel tej struktury danych?
Aktualizacje:
Przejrzałem kopię następującego artykułu:
EA Hauck i BA Dent. 1968. Mechanizm stosu Burroughsa B6500 / B7500. W Proceedings z 30 kwietnia do 2 maja 1968 r. Wiosenna wspólna konferencja komputerowa (AFIPS '68 (wiosna)). ACM, Nowy Jork, NY, USA, 245–251. DOI = http://dx.doi.org/10.1145/1468075.1468111
Ten dokument wydaje się definiować system stosu Suguaro. Jak się okazuje, ten system stosu Suguaro to tradycyjny stos wywołań, który pozwala wielu „zadaniom” przejść przez ramki częściowo współdzielonego stosu; nie ma absolutnie żadnego związku z kontynuacjami.
Poniższy artykuł (i towarzyszący mu dokument z 1996 r.) Najwyraźniej wyjaśnia, co się dzieje w kompilatorze SML / NJ:
Zhong Shao i Andrew W. Appel. 2000. Wydajna i bezpieczna konwersja zamknięcia w przestrzeń. ACM Trans. Program. Lang. Syst. 22, 1 (styczeń 2000), 129-161. DOI = http://dx.doi.org/10.1145/345099.345125
Myślę, że powinienem przeczytać ten artykuł ( kopię na stronie autora ), zanim zrobię cokolwiek innego z tym pytaniem. Koncepcja „Bezpiecznie połączonych zamknięć” jest bardzo podobna do systemu stosu Suguaro, ponieważ zawsze jest bardzo płytka i ma na celu udostępnianie dowolnych zmiennych:
Nasz nowy algorytm konwersji zamknięcia wykorzystuje bezpiecznie połączone zamknięcia (trzecia kolumna na ryc. 1), które zawierają tylko zmienne faktycznie potrzebne w funkcji, ale unikają kopiowania zamknięcia przez grupowanie zmiennych o tym samym czasie życia w rekordzie, który można udostępnić. [...] W przeciwieństwie do połączonych zamknięć, poziom zagnieżdżenia bezpiecznie połączonych zamknięć nigdy nie przekracza więcej niż dwóch (jedna warstwa dla samego zamknięcia; druga dla zapisów o różnym czasie życia), więc nadal cieszą się bardzo szybkim, zmiennym czasem dostępu.
Artykuł wyraźnie wspomina również, że nie używa „żadnego stosu środowiska wykonawczego”:
Zamiast tego traktujemy wszystkie rekordy aktywacji jako zamknięcia funkcji kontynuacji i alokujemy je w rejestrach na stercie.
Myślę, że źle zrozumiałem i / lub źle przeczytałem artykuł w Wikipedii, ponieważ stosy spaghetti nie są używane do kontroli przepływu. Jednak po uważnym przeczytaniu artykułów przez Appela i Shao, być może mógłbym powtórzyć pytanie w odniesieniu do wykresu zależności zamknięć zamiast „stosu wywołań spaghetti” (który najwyraźniej nie jest rzeczą).