无需程序即可在ASM中实施递归 [英] Implement recursion in ASM without procedures
问题描述
我正在尝试以一种没有过程的，类似于ASM的简化语言来实现函数和递归.只有简单的jumpz，jump，push，pop，add，mul类型命令.
I'm trying to implement functions and recursion in an ASM-like simplified language that has no procedures. Only simple jumpz, jump, push, pop, add, mul type commands.
以下是命令:
(所有变量和文字都是整数)
Here are the commands:
(all variables and literals are integers)
- set(设置一个已经存在的变量的值或声明并初始化一个新变量)，例如(设置x 3)
- push(将值推入堆栈.可以是变量或整数)，例如(按3)或(按x)
- pop(将堆栈弹出到变量中)，例如(弹出x)
- add(将第二个参数添加到第一个参数)，例如(加x 1)或(加x y)
- mul(与加法相同，但用于乘法)
- 跳转(跳转到特定的代码行)，例如(jump 3)跳到第3行，或(jump x)跳到与x值相等的行#
- jumpz(如果第二个参数等于零，则跳至行号)，例如(jumpz 3 x)或(jumpz z x)
变量"IP"是程序计数器，等于正在执行的当前代码行的行号.
The variable 'IP' is the program counter and is equal to the line number of the current line of code being executed.
在这种语言中，函数是程序底部的代码块，它们通过从堆栈中弹出一个值并跳转到该值来终止. (使用堆栈作为调用堆栈)，然后只需将指令指针推到堆栈上，然后跳转到函数的开头，即可在程序中的其他任何位置调用这些函数.
In this language, functions are blocks of code at the bottom of the program that are terminated by popping a value off the stack and jumping to that value. (using the stack as a call stack) Then the functions can be called anywhere else in the program by simply pushing the instruction pointer onto the stack and then jumping to the start of the function.
这对于非递归函数很好.
This works fine for non-recursive functions.
如何修改它以处理递归?
How could this be modified to handle recursion?
我已经读到，使用堆栈实现递归是将参数和局部变量推入堆栈的问题(在这种较低级别的情况下，我还认为是指令指针)
I've read that implementing recursion with a stack is a matter of pushing parameters and local variables onto the stack (and in this lower level case, also the instruction pointer I think)
我将无法执行x = f(n)之类的操作.为此，我要有一些变量y(也在f的主体中使用)，将y设置为n，调用f，将其返回值"分配给y，然后将控制跳回到从中调用f的位置. ，然后将x设置为y.
I wouldn't be able to do something like x = f(n). To do this I'd have some variable y (that is also used in the body of f), set y equal to n, call f which assigns its "return value" to y and then jumps control back to where f was called from, where we then set x equal to y.
(将定义从第36行开始的数字平方的函数)
(a function that squares a number whose definition starts at line 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
这似乎不适合递归.参数和中间值需要放在堆栈上，我认为递归调用会导致相同地址的堆栈上有多个实例.
This doesn't seem to lend itself to recursion. Arguments and intermediate values would need to go on the stack and I think multiple instances on the stack of the same address would result from recursive calls which is fine.
推荐答案
下一个代码在约翰·史密斯汇编"中递归地将数字"base"提高到幂指数":
Next code raises the number "base" to the power "exponent" recursively in "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.
为了对其进行测试，让我们手动运行它:
In order to test it, let's run it manually :
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 |
函数的参数现在已在堆栈上(没有手动运行):
Edit : parameter for function now on stack (didn't run it manually) :
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.
这篇关于无需程序即可在ASM中实施递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
