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

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;
}