Cómo implementar llamadas de cola en una costumbre VM

Question

¿Cómo puedo poner en práctica las llamadas de cola en una máquina virtual personalizada?

Yo sé que tengo que sobresalen de la pila local de la función original, entonces es argumentos, luego haga clic en los nuevos argumentos. Pero, si me pop fuera de pila local de la función, ¿cómo se supone que voy a empujar a los nuevos argumentos? Acaban de ser extraen de la pila.

Answer 1

Doy por sentado que estamos hablando de una máquina virtual tradicional "basado en pila" aquí.

pop fuera de pila local de la función actual preservar las partes todavía relevantes en la no-stack "registros" (donde las "partes pertinentes" son, claramente, el argumento para la próxima llamada de cola recursiva ), entonces (una vez que todos los argumentos y la pila local de la función se limpian) empuja los argumentos para la llamada recursiva. Por ejemplo, supongamos que la función que se está optimizando es algo como:

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

, que sin optimización podría producir el código de bytes simbólicamente 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

los medios CALL_FUN2 "llamar a una función con dos argumentos". Con la optimización, que podría convertirse en algún momento como:

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

Por supuesto que estoy haciendo mis códigos de bytes simbólicos sobre la marcha, pero espero que la intención es clara: POP_DISCARD n es la del pop normal que simplemente descarta las entradas de la parte superior de la pila n, pero POP_KEEP n es una variante que los mantiene "en algún lugar" (por ejemplo, en una pila auxiliar no puede acceder directamente a la solicitud, sino sólo a la maquinaria propia de la máquina virtual - almacenamiento con tal carácter a veces se llama "un registro" cuando se habla de aplicación VM) y un PUSH_KEPT n juego que vacía los "registros "de nuevo en la pila normal de la máquina virtual.

Answer 2

creo que estás mirando a mal. En lugar de hacer estallar las variables de edad de la pila y luego empujando los nuevos, simplemente reasignar los que ya existen (con cuidado). Esto es más o menos la misma optimización que pasaría si se reescribió el código para el algoritmo iterativo equivalente.

En este código:

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

sería

 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"

No hay necesidad de hacer estallar o meter nada en la pila, simplemente reasignar.
Claramente, esto puede ser optimizado aún más, poniendo la segunda condición de salida, lo que nos permite saltarse un salto, lo que resulta en un menor número de operaciones.

 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

Mirando de nuevo, esta "asamblea" refleja mejor esta C ++, lo que claramente ha evitado las llamadas de recursividad

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