Ответ 1
Упрощение написания компилятора и виртуальной машины - это регистрация и трамплин вашего переводчика. Поскольку у вас есть интерпретатор, а не компилятор (я полагаю), вам нужна только пара простых преобразований, чтобы получить надлежащую поддержку для вызовов хвоста.
Вам придется сначала написать все в стиле продолжения, который может быть странным думать и делать на C/С++. Дан Фридман ParentheC поможет вам преобразовать высокоуровневую, рекурсивную программу в форму, которая может быть переведена на компьютер C.
В конце вы по существу реализуете простую виртуальную машину, где вместо обычных вызовов функций для выполнения eval, applyProc и т.д. вы передаете аргументы, задавая глобальные переменные, а затем делаете goto для следующего аргумента ( или использовать контур верхнего уровня и счетчик программ)...
return applyProc(rator, rand)
становится
reg_rator = rator
reg_rand = rand
reg_pc = applyProc
return
Таким образом, все ваши функции, которые обычно называют друг друга рекурсивно, сводятся к псевдосети, в которой они являются просто блоками кода, которые не повторяются. Контур верхнего уровня управляет программой:
for(;;) {
switch(reg_pc) {
case EVAL:
eval();
break;
case APPLY_PROC:
applyProc();
break;
...
}
}
Изменить: Я прошел один и тот же процесс для моего интерпретатора схемы хобби, написанного на JavaScript. Я воспользовался многими анонимными процедурами, но это может помочь в качестве конкретной ссылки. Посмотрите на историю фиксации FoxScheme, начиная с 2011-03-13 (30707a0432563ce1632a) до 2011-03-15 (5dd3b521dac582507086).
Изменить ^ 2: Рекурсия без хвоста будет по-прежнему потреблять память, даже если она не находится в стеке.