recursion - español - Implementar la recursión en ASM sin procedimientos

call stack español

Question

Estoy tratando de implementar funciones y recursión en un lenguaje simplificado similar a ASM que no tiene procedimientos. Solo comandos simples de jumpz, jump, push, pop, add, mul type.

Aquí están los comandos:
(todas las variables y literales son enteros)

• set (establece el valor de una variable ya existente o declara e inicializa una nueva variable) ej. (set x 3)
• push (empuja un valor en la pila. Puede ser una variable o un entero), por ejemplo (push 3) o (push x)
• pop (coloca la pila en una variable), p. ej. (pop x)
• add (agrega el segundo argumento al primer argumento) ej. (agregue x 1) o (agregue xy)
• mul (igual que agregar pero para multiplicación)
• saltar (salta a una línea específica de código) ej. (salto 3) saltaría a la línea 3 o (salto x) saltaría a la línea # igual al valor de x
• jumpz (salta a un número de línea si el segundo argumento es igual a cero) ej. (jumpz 3 x) o (jumpz zx)

La variable ''IP'' es el contador del programa y es igual al número de línea de la línea actual de código que se está ejecutando.

En este lenguaje, las funciones son bloques de código en la parte inferior del programa que finalizan al mostrar un valor fuera de la pila y saltar a ese valor. (usando la pila como una pila de llamadas) Entonces las funciones se pueden llamar en cualquier otro lugar en el programa simplemente presionando el puntero de instrucción en la pila y luego saltando al comienzo de la función.

Esto funciona bien para funciones no recursivas.

¿Cómo podría modificarse esto para manejar la recursión?

He leído que implementar la recursión con una pila es una cuestión de empujar parámetros y variables locales en la pila (y en este caso de nivel inferior, también el puntero de instrucción, creo)

No podría hacer algo como x = f (n). Para hacer esto, tendría una variable y (que también se usa en el cuerpo de f), establezca y es igual a n, llame a f, que asigna su "valor de retorno" a y y luego devuelve el control al lugar donde se invocó f , donde luego establecemos x igual a y

(una función que cuadra un número cuya definición comienza en la línea 36)

1 - set y 3
2 - set returnLine IP
3 - add returnLine 2
4 - push returnLine
5 - jump 36
6 - set x y
...
36 - mul y 2
37 - pop returnLine
38 - jump returnLine

Esto no parece prestarse a la recursión. Los argumentos y los valores intermedios tendrían que ir a la pila y creo que varias instancias en la pila de la misma dirección resultarían de llamadas recursivas, lo que está bien.

Answer 1

El pastebin de Margaret se modificó ligeramente para ejecutarse en mi intérprete para este lenguaje: (problema de bucle infinito, probablemente debido a un error de transcripción de mi parte)

set n 3
push n
set initialCallAddress IP
add initialCallAddress 4
push initialCallAddress
jump fact
set finalValue 0
pop finalValue
print finalValue
jump 100
:fact
set rip 0
pop rip
pop n
push rip
set temp n
add n -1
jumpz end n
push n
set link IP
add link 4
push link
jump fact
pop n
mul temp n
:end
pop rip
push temp
jump rip

Transcripción exitosa de la calculadora de Fibonacci de Peter:

        String[] x = new String[] {
            //n is our input, which term of the sequence we want to calculate
                "set n 5",
            //temp variable for use throughout the program
                "set temp 0",
            //call fib
                "set temp IP",
                "add temp 4",
                "push temp",
                "jump fib",
            //program is finished, prints return value and jumps to end
                "print returnValue",
                "jump end",
            //the fib function, which gets called recursively
                ":fib",
            //if this is the base case, then we assert that f(0) = f(1) = 1 and return from the call
                "jumple base n 1",
                "jump notBase",
                ":base",
                "set returnValue n",
                "pop temp",
                "jump temp",
                ":notBase",
            //we want to calculate f(n-1) and f(n-2)
            //this is where we calculate f(n-1)
                "add n -1",
                "push n",
                "set temp IP",
                "add temp 4",
                "push temp",
                "jump fib",
            //return from the call that calculated f(n-1)
                "pop n",
                "push returnValue",
            //now we calculate f(n-2)
                "add n -1",
                "set temp IP",
                "add temp 4",
                "push temp",
                "jump fib",
            //return from call that calculated f(n-2)
                "pop n",
                "add returnValue n",
            //this is where the fib function ultimately ends and returns to caller
                "pop temp",
                "jump temp",
            //end label
                ":end"
        };

Answer 2

El siguiente código aumenta el número "base" al poder "exponente" recursivamente en "Asamblea de John Smith":

1 - set base 2            ;RAISE 2 TO ...
2 - set exponent 4        ;... EXPONENT 4 (2^4=16).
3 - set result 1          ;MUST BE 1 IN ORDER TO MULTIPLY.
4 - set returnLine IP     ;IP = 4.
5 - add returnLine 4      ;RETURNLINE = 4+4.
6 - push returnLine       ;PUSH 8.
7 - jump 36               ;CALL FUNCTION.
.
.
.
;POWER FUNCTION.
36 - jumpz 43 exponent    ;FINISH IF EXPONENT IS ZERO.

37 - mul result base      ;RESULT = ( RESULT * BASE ).
38 - add exponent -1      ;RECURSIVE CONTROL VARIABLE.
39 - set returnLine IP    ;IP = 39.
40 - add returnLine 4     ;RETURN LINE = 39+4.
41 - push returnLine      ;PUSH 43.
42 - jump 36              ;RECURSIVE CALL.

43 - pop returnLine
44 - jump returnLine
;POWER END.

Para probarlo, vamos a ejecutarlo manualmente:

 LINE | BASE EXPONENT RESULT RETURNLINE STACK
------|---------------------------------------
   1  |   2
   2  |         4
   3  |                  1
   4  |                           4
   5  |                           8
   6  |                                   8
   7  |
  36  |
  37  |                  2
  38  |         3
  39  |                          39
  40  |                          43
  41  |                                  43(1)
  42  |
  36  |
  37  |                  4
  38  |         2
  39  |                          39
  40  |                          43
  41  |                                  43(2)
  42  |
  36  |
  37  |                  8
  38  |         1
  39  |                         39
  40  |                         43
  41  |                                  43(3)
  42  |
  36  |
  37  |                 16
  38  |         0
  39  |                         39
  40  |                         43
  41  |                                  43(4)
  42  |
  36  |
  43  |                         43(4)
  44  |
  43  |                         43(3)
  44  |
  43  |                         43(2)
  44  |
  43  |                         43(1)
  44  |
  43  |                          8
  44  |
   8  |

Editar: parámetro para la función ahora en la pila (no lo ejecutó manualmente):

1 - set base 2            ;RAISE 2 TO ...
2 - set exponent 4        ;... EXPONENT 4 (2^4=16).
3 - set result 1          ;MUST BE 1 IN ORDER TO MULTIPLY.
4 - set returnLine IP     ;IP = 4.
5 - add returnLine 7      ;RETURNLINE = 4+7.
6 - push returnLine       ;PUSH 11.
7 - push base             ;FIRST PARAMETER.
8 - push result           ;SECOND PARAMETER.
9 - push exponent         ;THIRD PARAMETER.
10 - jump 36              ;FUNCTION CALL.
...
;POWER FUNCTION.
36 - pop exponent         ;THIRD PARAMETER.
37 - pop result           ;SECOND PARAMETER.
38 - pop base             ;FIRST PARAMETER.
39 - jumpz 49 exponent    ;FINISH IF EXPONENT IS ZERO.

40 - mul result base      ;RESULT = ( RESULT * BASE ).
41 - add exponent -1      ;RECURSIVE CONTROL VARIABLE.
42 - set returnLine IP    ;IP = 42.
43 - add returnLine 7     ;RETURN LINE = 42+7.
44 - push returnLine      ;PUSH 49.
45 - push base
46 - push result
47 - push exponent
48 - jump 36              ;RECURSIVE CALL.


49 - pop returnLine
50 - jump returnLine
;POWER END.

Answer 3

Su ASM proporciona suficientes recursos para implementar la secuencia de llamada / devolución de procedimiento habitual . Puede pulsar una dirección de retorno y saltar como una call , y mostrar una dirección de retorno (en una ubicación de cero) y hacer un salto indirecto a ella como un ret . Podemos simplemente hacer macros call y ret . (Excepto que generar la dirección de retorno correcta es complicado en una macro, es posible que necesitemos una etiqueta ( push ret_addr ), o algo así como set tmp, IP / add tmp, 4 / push tmp / jump target_function ). En resumen, es posible y deberíamos resumirlo en un poco de azúcar sintáctico para que no nos atasquemos al ver la recursión.

Con el azúcar sintáctico correcto, puede implementar Fibonacci(n) en el ensamblaje que realmente se ensamblará tanto para x86 como para su máquina de juguetes.

Estás pensando en términos de funciones que modifican variables estáticas (globales). La recursividad requiere variables locales, por lo que cada llamada anidada a la función tiene su propia copia de variables locales. En lugar de tener registros, su máquina tiene (aparentemente ilimitada) variables estáticas (como x e y ). Si desea programarlo como MIPS o x86, y copiar una convención de llamadas existente, simplemente use algunas variables nombradas como eax , ebx , ... o r0 .. r31 la forma en que una arquitectura de registro utiliza registros.

Luego implementa la recursión de la misma manera que lo hace en una convención de llamadas normal, donde la persona que llama o quien llama utiliza el comando push / pop para guardar / restaurar un registro en la pila para que pueda ser reutilizado. Los valores de retorno de función van en un registro. Los argumentos de función deberían ir en registros. Una alternativa fea sería presionarlos después de la dirección de retorno (creando una convención de llamadas de quien llama-limpia-de-la-pila), porque no tiene un modo de direccionamiento relativo a la pila para acceder a ellos de la misma manera que x86 does (encima de la dirección de retorno en la pila). O puede pasar las direcciones de retorno en un registro de enlace , como la mayoría de call instrucciones de call RISC (generalmente llamadas bl o similares, para bifurcar y vincular), en lugar de presionarlo como la call de x86. (Así que las calles que no son hojas tienen que empujar la lr entrante a la pila antes de hacer otra llamada)

A (tonto y lento) Fibonacci recursivo ingenuamente implementado podría hacer algo como:

int Fib(int n) {
    if(n<=1) return n;          // Fib(0) = 0;  Fib(1) = 1
    return Fib(n-1) + Fib(n-2);
}

## valid implementation in your toy language *and* x86 (AMD64 System V calling convention)

### Convenience macros for the toy asm implementation
# pretend that the call implementation has some way to make each return_address label unique so you can use it multiple times.
# i.e. just pretend that pushing a return address and jumping is a solved problem, however you want to solve it.
%define call(target)   push return_address; jump target; return_address:
%define ret            pop rettmp; jump rettmp    # dedicate a whole variable just for ret, because we can
# As the first thing in your program,  set eax, 0  / set ebx, 0 / ...

global Fib
Fib:
    # input: n in edi.
    # output: return value in eax
      # if (n<=1) return n;  // the asm implementation of this part isn''t interesting or relevant.  We know it''s possible with some adds and jumps, so just pseudocode / handwave it:
    ... set eax, edi and ret  if edi <= 1 ... # (not shown because not interesting)
    add     edi, -1
    push    edi        # save n-1 for use after the recursive call
    call    Fib        # eax = Fib(n-1)
    pop     edi        # restore edi to *our* n-1
    push    eax        # save the Fib(n-1) result across the call
    add     edi, -1
    call    Fib        # eax = Fib(n-2)
    pop     edi        # use edi as a scratch register to hold Fib(n-1) that we saved earlier
    add     eax, edi   # eax = return value = Fib(n-1) + Fib(n-2)
    ret

Durante una llamada recursiva a Fib(n-1) (con n-1 en edi como primer argumento), el n-1 arg también se guarda en la pila, para restaurarlo más tarde. Por lo tanto, el marco de pila de cada función contiene el estado que necesita para sobrevivir a la llamada recursiva y una dirección de retorno. Esto es exactamente de lo que se trata la recursión en una máquina con una pila.

El ejemplo de José tampoco lo demuestra, IMO, porque ningún estado necesita sobrevivir a la llamada de pow . Por lo tanto, termina presionando una dirección de retorno y args, luego apareciendo los argumentos, construyendo solo algunas direcciones de retorno. Luego, al final, sigue la cadena de direcciones de retorno. Podría extenderse para guardar el estado local en cada llamada anidada, no lo ilustra realmente.

Mi implementación es un poco diferente de cómo gcc compila la misma función C para x86-64 (usando la misma convención de llamadas de first arg en edi, ret value en eax). gcc6.1 con -O1 mantiene simple y en realidad realiza dos llamadas recursivas, como puede ver en el explorador del compilador Godbolt . ( -O2 y especialmente -O3 hacen algunas transformaciones agresivas). gcc guarda / restaura rbx en toda la función y mantiene n en ebx para que esté disponible después de la llamada Fib(n-1) . (y mantiene Fib(n-1) en ebx para sobrevivir a la segunda llamada). La convención de llamadas System V especifica rbx como un registro de llamada preservada, pero rbi como call-clobbered (y se usa para arg-passing).

Obviamente, puede implementar Fib (n) mucho más rápido de forma no recursiva, con complejidad de tiempo O (n) y complejidad de espacio O (1), en lugar de O (Fib (n)) complejidad de tiempo y espacio (uso de pila). Es un ejemplo terrible, pero es trivial.