Как реализовать хвостовые вызовы в пользовательской виртуальной машине

Question

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

Я знаю, что мне нужно извлечь локальный стек исходной функции, затем ее аргументы, а затем выдвинуть новые аргументы. Но если я вытолкну из локального стека функции, как я должен выдвинуть новые аргументы? Они только что выскочили из стека.

Answer 1

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

Вы вытаскиваете из локального стека текущей функции, сохраняя все еще релевантные части в не-стековых "регистрах" (где "релевантные части", несомненно, являются аргументом для предстоящего рекурсивного вызова хвоста), затем (когда все локальные функции функции стек и аргументы очищены) вы выдвигаете аргументы для рекурсивного вызова. Например, предположим, что оптимизируемая вами функция выглядит примерно так:

def aux(n, tot):
  if n <= 1: return tot
  return aux(n-1, tot * n)

который без оптимизации может создать байт-код символически, например:

AUX:   LOAD_VAR   N
       LOAD_CONST 1
       COMPARE
       JUMPIF_GT  LAB
       LOAD_VAR   TOT
       RETURN_VAL
LAB:   LOAD_VAR   N
       LOAD_CONST 1
       SUBTRACT
       LOAD_VAR   TOT
       LOAD_VAR   N
       MULTIPLY
       CALL_FUN2  AUX
       RETURN_VAL

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

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

Конечно, я создаю свои символические байт-коды по мере продвижения, но я надеюсь, что цель ясна: POP_DISCARD n это нормальный поп, который просто отбрасывает верх n записи из стека, но POP_KEEP n это вариант, который хранит их "где-то" (например, во вспомогательном стеке, не доступном непосредственно для приложения, но только для собственного механизма виртуальной машины - хранилище с таким символом иногда называют "регистром" при обсуждении реализации виртуальной машины) и соответствие PUSH_KEPT n который очищает "регистры" обратно в обычный стек виртуальной машины.

Answer 2

Я думаю, что вы смотрите на это неправильно. Вместо того, чтобы выталкивать старые переменные из стека и затем выталкивать новые, просто переназначьте уже существующие (осторожно). Это примерно та же самая оптимизация, которая произошла бы, если бы вы переписали код, чтобы он стал эквивалентным итерационным алгоритмом.

Для этого кода:

 int fact(int x, int total=1) {
     if (x == 1)
         return total;
     return fact(x-1, total*x);
 }

было бы

 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total
 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
   jmp fact               #"recurse"

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

 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total

Опять же, эта "сборка" лучше отражает этот C++, который явно избегает рекурсивных вызовов.

int fact(int x, int total=1)
    for( ; x>1; --x)
        total*=x;
    return total;
}