Como implementar a cauda de chamadas em uma VM personalizado
-
26-09-2019 - |
Pergunta
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.
Solução
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.
Outras dicas
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;
}