Jak zaimplementować język interpretowany "bez stosu"?

Question

Jak zaimplementować język interpretowany "bez stosu"?

Tworzę swój własny język interpretowany w stylu Lispu i chcę zrobić optymalizację wywołań ogonowych. Chcę uwolnić interpreter ze stosu C, aby móc zarządzać własnymi skokami z funkcji do funkcji i własną magią stosu, aby osiągnąć TCO. (Naprawdę nie mam na myśli stackless per se, tylko fakt, że wywołania nie dodają ramek do stosu C. Chciałbym użyć własnego stosu, który nie rośnie z wywołaniami ogonowymi). Jak Python bez stosu i w przeciwieństwie do Ruby or... standardowy Python I Zgadnij.

Ale, ponieważ mój język jest pochodną Lispu, wszystkie oceny wyrażeń s są obecnie wykonywane rekurencyjnie(ponieważ jest to najbardziej oczywisty sposób, jaki wymyśliłem, aby zrobić ten nieliniowy, wysoce hierarchiczny proces). Mam funkcję eval, która wywołuje funkcję Lambda:: apply za każdym razem, gdy napotka wywołanie funkcji. Funkcja apply następnie wywołuje eval, aby wykonać ciało funkcji, i tak dalej. Wzajemna rekurencja bez ogona C. Jedyną częścią iteracyjną, której obecnie używam, jest eval ciało sekwencyjne s-wyrażenia.

(defun f (x y)
    (a x y)) ; tail call! goto instead of call. 
             ; (do not grow the stack, keep return addr)

(defun a (x y)
    (+ x y))

; ...

(print (f 1 2)) ; how does the return work here? how does it know it's supposed to
                ; return the value here to be used by print, and how does it know
                ; how to continue execution here??

Jak więc uniknąć użycia rekurencji C? Czy mogę użyć jakiegoś goto, który przeskakuje przez funkcje c? może longjmp? Naprawdę Nie wiem. Proszę o cierpliwość, Jestem głównie samo - (Internet -) uczony w programowaniu.

16

stack recursion interpreter lisp stack-overflow

Author: salvador p, 2011-05-13

Source

3 answers

To, czego szukasz, nazywa się kontynuacja-styl przejścia . Ten styl dodaje dodatkowy element do każdego wywołania funkcji (możesz myśleć o nim jako o parametrze, jeśli chcesz), który wyznacza następny bit kodu do uruchomienia (kontynuacja k może być traktowana jako funkcja, która pobiera pojedynczy parametr). Na przykład możesz przepisać swój przykład w CPS w następujący sposób:

(defun f (x y k)
    (a x y k))

(defun a (x y k)
    (+ x y k))

(f 1 2 print)

Implementacja + obliczy sumę x i y, a następnie przekaże wynik do k coś w rodzaju (k sum).

Główna pętla interpretera nie musi być w ogóle rekurencyjna. Będzie on, w pętli, stosować każdą aplikację funkcji jeden po drugim, przekazując kontynuację wokół.

Potrzeba trochę pracy, żeby to ogarnąć. Polecam lekturę takich materiałów jak znakomity SICP .

9

Author: Greg Hewgill,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-05-13 00:51:56

Rekurencję ogonową można traktować jako ponowne użycie dla callee tej samej ramki stosu, której obecnie używasz dla wywołującego. Więc można po prostu ponownie ustawić argumenty i goto do początku funkcji.

6

Author: Adam,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-07-23 19:01:35

score 12 · Accepted Answer

Jednym z rozwiązań jest to, co czasami nazywa się "stylem trampolinowanym". Trampolina jest pętlą najwyższego poziomu, która wysyła do małych funkcji, które wykonują mały krok obliczeń przed powrotem.

Siedzę tu prawie pół godziny, próbując wymyślić dobry, krótki przykład. Niestety, muszę zrobić coś nieprzydatnego i wysłać cię na link:

Http://en.wikisource.org/wiki/Scheme:_An_Interpreter_for_Extended_Lambda_Calculus/Section_5

The paper is nazywa się "Scheme: an Interpreter for Extended Lambda Calculus", a sekcja 5 implementuje działający interpreter scheme w przestarzałym dialekcie Lispu. Sekret tkwi w tym, jak używają **CLINK** zamiast stosu. Pozostałe globale służą do przekazywania danych pomiędzy funkcjami implementacyjnymi, takimi jak rejestry procesora. Zignorowałbym * * Kolejka**,** kleszcz **i** proces**, ponieważ te dotyczą wątków i fałszywych przerwań. ** EVLIS * * i * * UNEVLIS * * są, w szczególności, używane do oceny argumenty funkcji. Nieocenione args są przechowywane w * * UNEVLIS**, dopóki nie zostaną ocenione i nie zostaną przekształcone w * * EVLIS**.

Funkcje, na które warto zwrócić uwagę, z kilkoma małymi uwagami:

MILOOP: MILOOP jest główną pętlą interpretera, czyli "trampoliny". Ignorując * * TICK**, jego jedynym zadaniem jest wywołanie dowolnej funkcji w * * PC**. W kółko i w kółko.

SAVEUP: SAVEUP pobiera wszystkie rejestry do * * CLINK**, co jest w zasadzie takie samo jak wtedy, gdy C zapisuje rejestry na stosie przed wywołaniem funkcji. * * CLINK * * jest właściwie "kontynuacją" dla tłumacza. (Kontynuacja jest tylko stanem obliczeń. Zapisana ramka stosu jest również technicznie kontynuacją. Dlatego niektóre Lispy zapisują stos na stercie, aby zaimplementować call / cc.)

RESTORE: RESTORE przywraca "rejestry" zapisane w **CLINK**. Jest to podobne do przywracania ramki stosu w języku opartym na stosie. Tak, to jest w zasadzie "return", z wyjątkiem niektórych funkcji wyraźnie zatrzymany Zwraca wartość do * * wartość**. (**Wartość * * nie jest oczywiście zablokowana przez RESTORE.) Zauważ również, że RESTORE nie zawsze ma, aby powrócić do funkcji wywołującej. Niektóre funkcje rzeczywiście uratują zupełnie nowe obliczenia, które przywrócą z radością "przywrócą".

AEVAL: AEVAL jest funkcją EVAL.

EVLIS: EVLIS istnieje w celu oceny argumentów funkcji i zastosowania funkcji do tych args. Aby uniknąć rekurencji, zapisuje EVLIS-1. EVLIS-1 byłby zwykłym starym kodem po zastosowaniu funkcji, jeśli kod został napisany rekurencyjnie. Aby jednak uniknąć rekurencji i stosu, jest to osobna "kontynuacja".

Mam nadzieję, że pomogłem. Szkoda tylko, że moja odpowiedź (i link) nie była krótsza.