Como implementar a cauda de chamadas em uma VM personalizado

Question

Como posso implementar cauda de chamadas em um personalizado máquina virtual?

Eu sei que eu preciso retirar a função original de pilha local, então os argumentos, em seguida, empurre a novos argumentos.Mas, se eu retirar a função de pilha local, como vou empurrar os novos argumentos?Eles apenas foram exibidos na pilha.

Answer 1

Eu tomo como certo que estamos discutindo uma máquina virtual tradicional "baseada em pilha" aqui.

Você sai da pilha local da função atual preservando as peças ainda relevantes em "registros" ininterruptos (Onde as "partes relevantes" estão, claramente, o argumento para a próxima chamada de cauda recursiva), depois (uma vez que toda a pilha local e argumentos da função for limpa), você pressiona os argumentos para a chamada recursiva. Por exemplo, suponha que a função que você está otimizando é algo como:

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

que sem otimização pode produzir um código de byte simbolicamente como:

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

O call_fun2 significa "chame uma função com dois argumentos". Com a otimização, pode se tornar um tempo como:

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

É claro que estou inventando meus bytecodes simbólicos à medida que avança, mas espero que a intenção seja clara: POP_DISCARD n é o pop normal que apenas descarta o topo n entradas da pilha, mas POP_KEEP n é uma variante que os mantém "em algum lugar" (por exemplo, em uma pilha auxiliar que não é diretamente acessível ao aplicativo, mas apenas para a própria maquinaria da VM - o armazenamento com esse personagem às vezes é chamado de "um registro" ao discutir a implementação da VM) e uma correspondência correspondente PUSH_KEPT n que esvazia os "registros" de volta à pilha normal da VM.

Answer 2

Eu acho que você está olhando para isso da maneira errada.Em vez de estourar a idade de variáveis na pilha e, em seguida, empurrando os novos, simplesmente reatribuir já existentes (com cuidado).Este é aproximadamente o mesmo de otimização que aconteceria se você reescreveu o código a ser o equivalente iterativa do algoritmo.

Para que este código:

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

seria

 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"

Não há necessidade de pop ou empurrar alguma coisa na pilha, apenas reatribuir.
Claramente, isso pode ser ainda mais otimizada, colocando a sair da condição de segundo, permitindo-nos a saltar de um salto, resultando em menor número de operações.

 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

Olhando novamente, desta "assembléia" melhor reflete este C++, que claramente tem evitado as chamadas de recursividade

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