Блог

Я создаю свой собственный интерпретируемый язык, подобный Lisp, и я хочу выполнить оптимизацию конечных вызовов. Я хочу освободить свой интерпретатор от стека C, чтобы я мог управлять своими собственными переходами от функции к функции и своей собственной магией стека для достижения TCO. (Я действительно не имею в виду stackless как таковой, просто тот факт, что вызовы не добавляют фреймы в стек C. Я хотел бы использовать свой собственный стек, который не увеличивается с конечными вызовами). Похоже на 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? Я действительно не знаю. Пожалуйста, потерпите меня, я в основном обучаюсь программированию самостоятельно (через Интернет).

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

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

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

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

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

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

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

ВОССТАНОВЛЕНИЕ: RESTORE восстанавливает «регистры» в том виде, в каком они были сохранены в ** CLINK **. Это похоже на восстановление стекового фрейма на языке, основанном на стеке. Итак, это в основном «return», за исключением того, что какая-то функция явно вставила возвращаемое значение в ** VALUE ** . (** ЗНАЧЕНИЕ **, очевидно, не блокируется RESTORE .) Также обратите внимание, что RESTORE не всегда должен возвращаться к вызывающей функции. Некоторые функции фактически СЭКОНОМЯТ совершенно новые вычисления, которые RESTORE с радостью «восстановит».

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

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

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

То, что вы ищете, называется стилем передачи продолжения. Этот стиль добавляет дополнительный элемент к каждому вызову функции (вы могли бы думать об этом как о параметре, если хотите), который обозначает следующий фрагмент кода для запуска (продолжение 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.

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