Как реализовать интерпретируемый язык без стеков?

Question

Я делаю свой собственный интерпретируемый язык, похожий на Лисп, и хочу оптимизировать хвостовой вызов.Я хочу освободить мой интерпретатор из стека C, чтобы я мог управлять своими собственными переходами от функции к функции и своей магией стека для достижения TCO.(Я на самом деле не имею в виду отсутствие стека как такового, просто тот факт, что вызовы не добавляют фреймы в стек C. Я хотел бы использовать свой собственный стек, который не увеличивается при использовании хвостовых вызовов).Как и в Stackless Python, и в отличие от Ruby или ... стандартного Python, я думаю.

Но, поскольку мой язык является производным от Lisp, все вычисления s-выражений в настоящее время выполняются рекурсивно (потому что это наиболее очевидный способ, которым ямысль сделать этот нелинейный, очень иерархический процесс).У меня есть функция eval, которая вызывает функцию Lambda :: apply каждый раз, когда сталкивается с вызовом функции.Затем функция apply вызывает eval для выполнения тела функции и т. Д.Взаимная голодная не хвостовая C рекурсия.Единственная итеративная часть, которую я сейчас использую, - это оценка тела последовательных s-выражений.

(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??

Итак, как мне избежать использования C-рекурсии?Или я могу использовать какое-то goto, которое перепрыгивает через функции c?longjmp, возможно?Я действительно не знаю.Пожалуйста, потерпите меня, я в основном программирую на себе (в Интернете).

Answer 1

Одним из решений является то, что иногда называют «батутным стилем».Батут представляет собой цикл верхнего уровня, который отправляет небольшим функциям, которые выполняют небольшой шаг вычисления перед возвратом.

Я сидел здесь почти полчаса, пытаясь придумать хороший, короткий пример.К сожалению, я должен сделать бесполезную вещь и отправить вам ссылку:

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

Статья называется «Схема: интерпретатор для расширенного лямбда-исчисления», а раздел 5 реализуетрабочий интерпретатор схем на устаревшем диалекте Лиспа.Секрет в том, как они используют ** CLINK ** вместо стека.Другие глобальные переменные используются для передачи данных между функциями реализации, такими как регистры ЦП.Я бы проигнорировал ** QUEUE **, ** TICK ** и ** PROCESS **, поскольку они имеют дело с многопоточными и фальшивыми прерываниями.** EVLIS ** и ** UNEVLIS **, в частности, используются для оценки аргументов функции.Неоцененные аргументы хранятся в ** UNEVLIS **, пока они не будут оценены и переданы в ** EVLIS **.

Функции, на которые следует обратить внимание, с некоторыми небольшими примечаниями:

MLOOP: MLOOPэто основной цикл интерпретатора, или «батут».Игнорируя ** TICK **, его единственная задача - вызывать любую функцию в ** PC **.Снова и снова и снова.

SAVEUP: SAVEUP объединяет все регистры в ** CLINK **, что в основном совпадает с тем, когда C сохраняет регистры в стек перед вызовом функции.** CLINK ** на самом деле является «продолжением» для переводчика.(Продолжение - это просто состояние вычисления. Технически, сохраненный кадр стека также является продолжением. Следовательно, некоторые Лиспы сохраняют стек в кучу для реализации call / cc.)

RESTORE: RESTORE восстанавливает "регистры ", как они были сохранены в ** CLINK **.Это похоже на восстановление стекового фрейма на основе стекового языка.Таким образом, это в основном «возврат», за исключением того, что некоторая функция явно вставила возвращаемое значение в ** VALUE **.(** VALUE ** явно не перекрывается RESTORE.) Также обратите внимание, что RESTORE не всегда имеет для возврата к вызывающей функции.Некоторые функции фактически СОХРАНЯЮТ совершенно новые вычисления, которые RESTORE с радостью «восстановит».

AEVAL: AEVAL - это функция EVAL.

EVLIS: EVLIS существует для оценки аргументов функции и примененияфункция этих аргументов.Чтобы избежать рекурсии, это ЭКОНОМИЯ ЭВЛИС-1.EVLIS-1 был бы просто обычным старым кодом после применения функции, если код был написан рекурсивно.Однако, чтобы избежать рекурсии и стека, это отдельное «продолжение».

Надеюсь, я вам чем-то помог.Я просто хотел бы, чтобы мой ответ (и ссылка) был короче.

Answer 2

То, что вы ищете, называется стиль продолжения . Этот стиль добавляет дополнительный элемент к каждому вызову функции (вы можете думать о нем как о параметре, если хотите), который обозначает следующий бит кода для запуска (можно подумать о продолжении k как функция, которая принимает один параметр). Например, вы можете переписать свой пример в CPS следующим образом:

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

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

(f 1 2 print)

Реализация + вычислит сумму x и y, а затем передаст результат в k вроде (k sum).

Тогда ваш основной цикл интерпретатора не должен быть рекурсивным. В цикле он будет применять каждое приложение функции один за другим, передавая продолжение.

Требуется немного усилий, чтобы обдумать это. Я рекомендую некоторые материалы для чтения, такие как превосходный SICP .

Answer 3

Хвостовая рекурсия может рассматриваться как повторное использование для вызываемого абонента того же самого стекового фрейма, который вы в настоящее время используете для вызывающего абонента. Таким образом, вы можете просто переустановить аргументы и перейти к началу функции.