【Hacker News搬运】在计算机有堆栈或堆之前，古代世界的子程序调用

hackernews

Title: Subroutine calls in the ancient world, before computers had stacks or heaps

在计算机有堆栈或堆之前，古代世界的子程序调用

Text:

Url: https://devblogs.microsoft.com/oldnewthing/20240401-00/?p=109599

在古代世界中，计算机还没有堆栈或堆时，子程序调用的方法

标题：古代世界中的子程序调用，在计算机还没有堆栈或堆时
作者：Raymond Chen, Thomas Harte, Yuri Khan, Peter Raynham, Ian Boyd, Dave Gzorple, Mark Out West, Neil Rashbrook, Mark Yagnatinsky
发布日期：2024-04-01 00:00:00
顶部图片链接：[点击查看](https://devblogs.microsoft.com/oldnewthing/wp-content/uploads/sites/38/2019/02/ShowCover.jpg)
文本内容：

在古代世界中，计算机还没有堆栈或堆时，子程序调用是如何工作的？

Raymond Chen

2024年4月1日

我们现在理所当然地使用堆栈和堆，但在计算机的非常早期时代，计算机是在没有堆栈或堆的情况下运行的。

告诉一个 recent college graduate 这一点，你可能会觉得你是在告诉他们曾经有一个时代你无法即时访问数百万只猫的视频。

想象一下没有动态内存分配的计算机运作并不难。你就是使用固定大小的内存缓冲区来处理所有事情。如果你需要对可变大小的数据进行操作，你预留一个固定大小的缓冲区，容量足够大以容纳你可能处理的任何数据，如果有人要求更多，你就以致命错误退出程序。如果你真的很好，你可以在编译时提供配置，让你的客户根据他们的数据集调整最大容量。而如果你真的很 fancy，你编写了一个自定义分配器，它操作那个固定大小的缓冲区，让人们可以从这个缓冲区中“分配”和“释放”内存。

但没有堆栈的操作呢？在没有堆栈的情况下，你怎么调用函数？

运作方式就是这样。

首先，编译器为每个传入的函数参数定义了一个秘密全局变量，并为每个函数定义了一个秘密全局变量来保存返回地址。它还为每个函数的局部变量定义了一个秘密全局变量。

为了生成一个函数调用，编译器将参数值分配给相应的秘密全局变量，将返回地址分配给函数的秘密“返回地址变量”，然后跳转到函数的开始部分。

函数从它的秘密全局变量中读取参数，并使用预定义的秘密全局变量，对应于它的逻辑局部变量。当函数完成后，它跳转到函数秘密“返回地址变量”中保存的地址。

例如，假设你有以下用类似 C 语言编写的代码：

```c
int add_two_values(int a, int b) { int c = a + b; return c; }
void sample() {
    int x = add_two_values(31415, 2718);
}

编译器会将这段代码转换成类似这样的内容：

int a2v_a;
int a2v_b;
int a2v_c;
void* a2v_retaddr;

int add_two_values() {
    a2v_c = a2v_a + a2v_b;
    return_value_register = a2v_c;
    goto a2v_retaddr;
}

int sample_x;
void sample() {
    a2v_a = 31415;
    a2v_b = 2718;
    a2v_retaddr = &resume;
    goto add_two_values;
    resume:
    sample_x = return_value_register;
}

看吧：我们没有使用堆栈就完成了函数调用和返回！

现在，你可以通过，比如说，通过寄存器传递一些这些值而不是全局变量来优化 ABI。例如，大多数处理器都有一个特殊的“链接”寄存器和一条特殊的指令“带链接的分支”，它自动将链接寄存器设置为分支指令之后的地址。也许你优化了调用约定，将前两个参数通过寄存器传递，结果如下：

int a2v_a;
int a2v_b;
int a2v_c;
void* a2v_retaddr;

int add_two_values() {
    a2v_a = argument_register_1;
    a2v_b = argument_register_2;
    a2v_retaddr = link_register;
    a2v_c = a2v_a + a2v_b;
    return_value_register = a2

Post by: signa11

Comments:

dragontamer: I really liked the Art of Computer Programming with regards to this subject.While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for dynamically changing arrays or other data structures.The book also builds up to garbage collection and how to implements Lisp-lists. The kind of encyclopedic knowledge you'd expect from Knuth.-------One of my favorites is how to have two Arrays dynamically take up one space.Have one array grow normally from location#0, and the second array grow backwards from location#End.Now both arrays take up the statically allocated space efficiently sharing.This can be extended to an arbitrary number of arrays, but at that point you might as well use Malloc and Realloc. Or at least, the techniques therein are really close to a malloc-like routine IMO.

dragontamer: 就这门课而言，我真的很喜欢《计算机程序设计艺术》 虽然看起来已经过时，但有大量的预堆；用于动态改变阵列或其他数据结构的预堆栈算法 本书还介绍了垃圾收集以及如何实现Lisp列表。那种百科全书式的知识你；我期待Knuth -------我最喜欢的一个是如何让两个数组动态地占用一个空间 让一个数组从位置#0正常增长，第二个数组从地址#End向后增长 现在，这两个数组都有效地共享了静态分配的空间。＜p＞这可以扩展到任意数量的数组，但此时您还可以使用Malloc和Realloc。或者至少，其中的技术真的很接近malloc式的例程IMO。

joeatwork: Getting recursive functions into ALGOL turns out to have been a controversial move that made for a fun story: <a href="https://vanemden.wordpress.com/2014/06/18/how-recursion-got-into-programming-a-comedy-of-errors-3/" rel="nofollow">https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...</a>

joeatwork: 事实证明，将递归函数引入ALGOL是一个有争议的举动，它带来了一个有趣的故事：<a href=“https://；&#x2F；vanemden.wordpress.com&#x2F，2014&#x2F！06&#x2F？18&#x2F”how-recursorion-got-in-to-programming-a-commy-of-errors-3&#x2F“rel=”nofollow“>https://&#x2F；vanemden.wordpress.com&#x2F；2014年；06；18；递归是如何得到的</一

howerj: I wrote a Forth interpreter for a SUBLEQ machine (<a href="https://github.com/howerj/subleq">https://github.com/howerj/subleq</a>), and for a bit-serial machine (<a href="https://github.com/howerj/bit-serial">https://github.com/howerj/bit-serial</a>), both of which do not have a function call stack which is a requirement of Forth. SUBLEQ also does not allow indirect loading and stores as well and requires self-modifying code to do anything non-trivial. The approach I took for both machines was to build a virtual machine that could do those things, along with cooperative multithreading. The heap, if required, is written in Forth, along with a floating point word-set (various MCUs not having instructions for floating point numbers is still fairly common, and can be implemented as calls to software functions that implement them instead).I would imagine that other compilers took a similar approach which wasn't mentioned.EDIT: There were some BASIC interpreters which did this as well, implementing a VM and then targetting that instead. P-Code is a similar thing.

howerj: 我为SUBLEQ机器编写了一个Forth解释器（<a href=“https://；&#x2F；github.com&#x2F，howerj&#x2F”>https://；#xx2F；github.com&#x20F；howerj&x2F；subq</a>），并为位串行机器编写了Forth解释器。&#x2F；howerj&#x2F位串行</a>），两者都不具有作为Forth的要求的函数调用堆栈。SUBLEQ也不允许间接加载和存储，并且需要自修改代码来做任何非琐碎的事情。我对这两台机器采取的方法是构建一个可以做这些事情的虚拟机，以及协作的多线程。如果需要，堆与浮点字集一起用Forth编写（没有浮点数字指令的各种MCU仍然相当常见，可以作为对实现它们的软件函数的调用来实现） 我可以想象其他编译器采用了类似的方法；没有提到 编辑：有一些BASIC解释器也这样做了，实现了一个VM，然后转而针对它。P代码也是类似的东西。

derefr: Funny enough, I was forced to program in exactly this way, when I was first learning to program. But not in the 1970s... in the year 2001!Why? Because my first exposure to programming was the semi-graphical scripting "language" exposed by the game-development tool "RPG Maker 2000."For those who haven't seen RM2K scripting before: picture a cross between Scratch and Emacs Paredit mode. (E.g. <a href="https://forums.rpgmakerweb.com/data/attachments/21/21958-f8978e9d268a8359ef8547ff5736de90.jpg" rel="nofollow">https://forums.rpgmakerweb.com/data/attachments/21/21958-f89...</a>) It's presented as textual, but you can't edit it like text — only as blocks with associated properties dialogs.And, of course, that scripting language in RPG Maker doesn't have anything so fancy as a stack.Want some reusable subroutines? Well, you better believe you're allocating secret global variables for their parameters — no re-entrancy for you!---Mind you, thinking back on it, it's probably possible to implement both registers and a runtime stack in RPG Maker 2000, given sufficient stubbornness.Both features seem easy enough at first: you can do pseudo-"registers" like the zero page on a 6502; and you can do a stack through indirect variable access (<a href="https://rpgmaker.net/tutorials/523/" rel="nofollow">https://rpgmaker.net/tutorials/523/</a>).The problem with both of these, though, is that RM2K actually has concurrency in the form of "parallel process" scripts — so any use of either of these abstractions by these parallel processes, will have different "threads" stomping all over one-another's state.So you'd actually need multiple "zero pages" and "stacks" — one for each "virtual core" — and then you'd need to somehow assign/bind/schedule the "virtual cores" to parallel scripts (i.e. somehow get each script its own privately-known "stack pointer.") Which, to be stable in the face of race conditions, would normally require something like mutexes...Knowing the bloody-mindedness of RPG Maker gamedevs, I'm sure someone did come up with a way to trick some runtime feature into acting like a mutex. But I'm genuinely scared to know what it was they did.

derefr: 有趣的是，当我第一次学习编程时，我被迫以这种方式编程。但不是在20世纪70年代。。。在2001年 为什么？因为我第一次接触编程是半图形脚本“；语言“；由游戏开发工具“暴露”；RPG Maker 2000 对于那些没有；以前没有见过RM2K脚本：想象一下Scratch和Emacs Paredit模式之间的交叉。（例如<a href=“https://；&#x2F；论坛.rpgmakerweb.com&#x2F：数据&#x2F，附件&#x2F…21&#x2F！21958-f8978e9d268a8359ef8547ff5736de90.jpg”rel=“nofollow”>https://；论坛.rggmakerweb.com/&#x2F数据&#x2F:附件&#x2F:21&#x2F=21958-f89…</a>）；s以文本形式呈现，但您可以；不要像编辑文本一样编辑它——只能将其作为具有相关属性对话框的块 当然，RPG Maker中的脚本语言；没有什么比堆栈更奇特的了 想要一些可重复使用的子程序吗？好吧，你最好相信你；为它们的参数重新分配秘密全局变量——不需要重新进入 ---请注意，回想起来，它；如果有足够的顽固性，在RPG Maker 2000中实现寄存器和运行时堆栈的可能性可能＜i＞＜i＞ 两个功能＜i＞一开始似乎都很简单：你可以做伪“；寄存器”；就像6502上的零页；并且您可以通过间接变量访问来进行堆栈（<a href=“https://；&#x2F；rpgmaker.net&#x2F，tutorials&#x2F！523&#x2F”rel=“nofollow”>https:&#x2F 然而，这两者的问题在于，RM2K实际上具有“i”形式的并发性；并行处理”；脚本——因此这些并行进程对这些抽象中任何一个的任何使用都将具有不同的“；线程”；互相踩踏；s状态 所以你；d实际上需要倍数“；零页”；以及“；堆叠”——每个“一个”；虚拟核心”——然后你；d需要以某种方式分配；绑定；安排“；虚拟核心”；并行脚本（即以某种方式使每个脚本都有自己的私有“堆栈指针”），为了在竞争条件下保持稳定，通常需要类似互斥的东西 我知道RPG Maker游戏开发者的血腥思想；我确信确实有人想出了一种方法来欺骗一些运行时功能，使其表现得像互斥对象。但是我；我真的很害怕知道他们做了什么。

monocasa: > As I recall, some processors stored the return address at the word before the first instruction of the subroutine.Yep, that's what the PDP-8 did. The evolution of the PDP-8 is arguably a journey in hardware support for recursion.Initially the JMS instruction stuck the return address in the first word of the function (as an aside, a lot of time caller would put it's arguments after the JMS instruction, and the callee would read arguments offset of the return instruction, incrementing it with each read argument until the return address pointed to code again).Then it became relatively common to use one of the autoincrement locations (the PDP-8 had 8 memory locations that would increment any time you used them as a pointer) to create a simple stack, and function prologues/epilogues manually managed this stack to allow full recursion.Then later on hardware stacks were added in the microprocessor implementations like the Harris 6120 to make this more performant.

monocasa: &gt；我记得，一些处理器将返回地址存储在子例程的第一条指令之前的字上 是的，那个；这就是PDP-8所做的。PDP-8的发展可以说是硬件支持递归的一次旅程 最初，JMS指令将返回地址固定在函数的第一个字中（顺便说一句，很多时候调用方会将它的参数放在JMS指令之后，而被调用方会读取返回指令的参数偏移量，并随着每个读取的参数将其递增，直到返回地址再次指向代码） 然后，使用其中一个自动递增位置（PDP-8有8个内存位置，每当您将它们用作指针时，它们都会递增）来创建一个简单的堆栈变得相对常见，并且函数prologues；epilogues手动管理这个堆栈以允许完全递归 随后，在像Harris 6120这样的微处理器实现中添加了硬件堆栈，以使其更具性能。