recursion - 在ASM中实现无过程递归

Question

我正在尝试使用类似 ASM 的没有过程的简化语言来实现函数和递归。只有简单的jumpz、jump、push、pop、add、mul类型命令。

以下是命令:
(所有变量和文字都是整数)

• set(设置已存在变量的值或声明并初始化新变量)例如(套装 x 3)
• push(将一个值压入堆栈。可以是变量或整数)例如(按 3)或(按 x)
• pop(将堆栈弹出到变量中)例如(弹出x)
• add(将第二个参数添加到第一个参数)例如(加 x 1)或(加 x y)
• mul(与 add 相同，但用于乘法)
• jump(跳转到特定代码行)例如(jump 3) 将跳转到第 3 行，或者 (jump x) 将跳转到 # 等于 x 值的行
• jumpz(如果第二个参数等于零，则跳转到行号)例如(jumpz 3 x) 或 (jumpz z x)

变量“IP”是程序计数器，等于当前正在执行的代码行的行号。

在这种语言中，函数是程序底部的代码块，通过从堆栈中弹出一个值并跳转到该值来终止。 (使用堆栈作为调用堆栈)然后，只需将指令指针压入堆栈，然后跳转到函数的开头，就可以在程序中的任何其他位置调用函数。

这对于非递归函数来说效果很好。

如何修改它来处理递归？

我读到，使用堆栈实现递归是将参数和局部变量插入堆栈的问题(在这种较低级别的情况下，我认为也是指令指针)

我无法做像 x = f(n) 这样的事情。为此，我需要一些变量 y (也在 f 的主体中使用)，将 y 设置为 n，调用 f 将其“返回值”分配给 y，然后将控制跳回调用 f 的位置，然后我们将 x 设置为等于 y。

(对数字进行平方的函数，其定义从第 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

这似乎不适合递归。参数和中间值需要进入堆栈，我认为同一地址的堆栈上的多个实例将由递归调用产生，这很好。

Answer 1

下一个代码在“John Smith Assembly”中递归地计算数字“基数”的“指数”次方:

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.

为了测试它，让我们手动运行它:

 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  |

编辑:函数的参数现在位于堆栈上(未手动运行):

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.