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

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

Но, поскольку мой язык является производной Lisp, вся оценка s-выражений выполняется в настоящее время рекурсивно (потому что это самый очевидный способ, которым я думал сделать этот нелинейный, высоко иерархический процесс). У меня есть функция eval, которая вызывает функцию Lambda:: apply каждый раз, когда она встречает вызов функции. Затем функция apply вызывает eval для выполнения тела функции и т.д. Взаимная сток-голодная нерегулярная рекурсия. Единственная итеративная часть, которую я сейчас использую, состоит в том, чтобы вычислить тело последовательных 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 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, возможно? Я действительно не знаю. Пожалуйста, не стесняйтесь, я в основном сам (Интернет), преподаваемый в программировании.

Ответ 1

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

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

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

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

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

MLOOP: MLOOP - основной цикл интерпретатора, или "батут". Игнорируя ** TICK **, его единственным заданием является вызов любой функции в ** ПК **. Снова и снова.

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

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

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

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

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

Ответ 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.

Ответ 3

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