无栈语言是如何工作的？

Question

我听说过无栈语言，但我不知道这样的语言如何实现。有人可以解释一下吗？

- rlbond

---

寄存器 - 在新的64位平台上有很多。首先为体系结构调用约定需要保留一些。可能会使用一些来引用外部数据。然后，您剩下的任何寄存器都可以与静态缓冲区结合使用以形成虚拟堆栈 - 或者仅将函数限制为X字节的本地存储。 - Christoffer Bubach

Answer 1

我们现在使用的现代操作系统（Windows、Linux）采用了我所谓的“大栈模型”。这种模型有时是错误的，并促使需要“无栈”语言的需求。 “大栈模型”假设编译程序将为函数调用在内存中分配“栈帧”，使用机器指令快速调整包含堆栈指针（和可选的堆栈帧指针）的寄存器，从而导致快速的函数调用/返回，但价格是必须有一个大的连续区域来存储栈。因为99.99％的所有在这些现代操作系统下运行的程序都能很好地与大栈模型配合工作，所以编译器、加载器甚至操作系统都“知道”这个堆栈区域。 所有这类应用程序共同面临的一个常见问题是“我的栈应该有多大？”由于内存非常便宜，通常会为栈设置一个较大的块（MS默认为1Mb），而典型的应用程序调用结构永远不会接近使用完它。但是，如果应用程序确实使用了所有空间，则会出现非法内存引用的错误（“对不起，Dave，我不能这样做”），因为它已经超出了其堆栈的末尾。 大多数所谓的“无栈”语言实际上并非真正没有堆栈。它们只是不使用这些系统提供的连续堆栈。相反，它们在每次函数调用时从堆上分配一个堆栈帧。每次函数调用的成本会略微增加；如果函数通常比较复杂或语言是解释性的，则此额外成本是微不足道的。（还可以在程序调用图中确定调用DAG，并分配一个堆段以覆盖整个DAG；这样，您既可以获得堆分配，又可以获得传统大栈函数调用的速度，适用于调用DAG内的所有调用）。

使用堆分配栈帧有几个原因：

1. 如果程序在解决特定问题时进行深度递归，很难预先分配“大堆栈”区域，因为所需大小未知。人们可以笨拙地安排函数调用来检查是否还有足够的堆栈空间，如果没有，就重新分配一个更大的块，复制旧堆栈并调整指向堆栈的所有指针；这样的操作非常笨拙，我不知道是否有任何实现。分配堆栈帧意味着应用程序直到没有可分配的内存为止都不必说抱歉。

2. 程序分叉子任务。每个子任务都需要自己的堆栈，因此不能使用提供的一个“大堆栈”。因此，需要为每个子任务分配堆栈。如果有数千个可能的子任务，你可能现在需要数千个“大堆栈”，而内存需求突然变得荒谬起来。分配堆栈帧解决了这个问题。通常子任务的“堆栈”会引用父任务来实现词法作用域；当子任务分叉时，创建了一个称为“仙人掌堆栈”的“子堆栈”树。

3. 你的语言有continuations。这要求当前函数中词法作用域中可见的数据在以后可以被保留以供重复使用。这可以通过复制父堆栈帧，向上爬升仙人掌堆栈并继续进行来实现。

我实现的PARLANSE编程语言可以完成1)和2)。目前正在开发3)。有趣的是，PARLANSE会从一个非常快速访问的线程专用堆栈中分配堆栈帧；这通常只需要4个机器指令。当前实现基于x86架构，分配的帧与其他传统的x86编程语言实现类似，被放置在x86 EBP/ESP寄存器中。因此，它确实使用硬件的“连续堆栈”（包括推入和弹出），只是以块的形式进行。对于大量已知堆栈需求的实用程序代码，它还会生成“框架本地”子例程调用，不会切换堆栈。

- Ira Baxter

---

我看到的所有Windows和Linux线程实现都有相同的“大堆栈”假设（主要是因为“进程”只是具有关联地址空间的特殊线程）。因此，所有相同的问题都会出现。对于PARLANSE，我将Window的线程多路复用到数以亿计的“颗粒”中，每个颗粒都使用自己分配的堆栈帧。 - Ira Baxter

也许需要澄清的是，如果您满意使用由线程提供的大堆栈模型来分叉受操作系统提供的线程数量限制（通常为几百个）的多个子任务，那么您可以继续使用它。但是，如果您的并行/并发计算涉及大量交互，则可能需要数千个计算元素，此时操作系统线程模型将无法满足您的需求。 - Ira Baxter

Haskell严格来说根本不使用调用堆栈，甚至没有通过堆空间链接列表构成的调用堆栈。把它想象成一种非常高级的宏替换语言 :) - ephemient

@IraBaxter为什么在回答的结尾放了一个指向你公司产品的链接？这并没有为回答增加任何内容，也不符合上下文。 - xaxxon

你可以说你喜欢什么；根据投票，读者似乎喜欢这个答案。我专门设计了PARLANSE来解决需要使用仙人掌栈（非并行答案不需要）的难以并行化的程序。链接显示可以将其实现为生产质量工具。它是并行的，并且具有无限递归/分叉，这是隐含的证明，即使对您来说这并不明显。 - Ira Baxter

Answer 2

Stackless Python仍然有一个Python栈（虽然它可能具有尾递归优化和其他调用帧合并技巧），但它与解释器的C栈完全分离。

Haskell（通常实现）没有调用栈；计算是基于图形缩减进行的。

- ephemient

---

注意：Haskell确实有调用堆栈：https://dev59.com/wXNA5IYBdhLWcg3wUL5Y#1016234 - amindfv

Answer 3

有一篇关于语言框架Parrot的好文章。 Parrot不使用堆栈进行调用，本文解释了这种技术。

- Roman Plášil

---

链接已失效。这是Wayback Machine存档的版本：https://web.archive.org/web/20100706035639/http://www.linux-mag.com/cache/7373/1.html - Jakub

Answer 4

Call me old-fashioned, but I can remember a time when FORTRAN standards and COBOL did not support recursive calls, which meant that there was no need for a stack. I recall implementations for CDC 6000 series machines where there wasn't a stack, and FORTRAN would behave strangely if you tried to call a subroutine recursively.

For your information, instead of using a call-stack, the CDC 6000 series instruction set utilized the RJ instruction to call a subroutine. This instruction saved the current PC value at the call target location and then branched to the location following it. At the end, the subroutine would perform an indirect jump to the call target location, reloading the saved PC and effectively returning to the caller.

Obviously, this method does not work with recursive calls. In fact, my recollection is that the CDC FORTRAN IV compiler would generate faulty code if you attempted recursion.

- Stephen C

---

好的。只要限制调用树的大小，就可以在理论上静态分配激活记录所需的所有空间（大多数应用程序仍然具有有限的调用树，但如果存在从A间接调用A的情况，编译器几乎无法找到这样的布局）。但是现在所有现代版本的FORTRAN和COBOL都允许递归，必须在某个地方实现类似堆栈的行为。 - Ira Baxter

@IraBaxter - 确实如此...但这不是他们过去的做法。请看我的更新。 - Stephen C

在“旧时代”，他们所做的就是将函数所需的任何存储空间分配为静态全局变量。这为他们提供了一个放置返回地址和任何参数的位置，并为评估复杂表达式时需要的临时值提供了一个位置。只要在调用链中没有两次调用子程序，这种方法就可以工作。（是的，一些非常古老的调用指令将返回地址放置在有效地址处，并将PC设置为地址加1。这些指令已经从现代指令集中消失了，因为它会产生所谓的“自修改代码”。） - Ira Baxter

真正的自修改代码是FORTRAN的“计算跳转”语句。CDC RJ只是FORTRAN的实现产物。它没有自修改的恶劣（代码意大利面！）方面，只要你不打破语言的递归限制。如果代码段是只读的，那么这种方法就行不通了，但硬件不支持这种方式。（系统一次只运行一个作业，OS的核心/特权部分在称为PPU的单独处理器上运行。） - Stephen C

Answer 5

在我比较熟悉的无栈环境中（图灵机、汇编和Brainfuck），实现自己的栈是很常见的。语言内置栈并不是必须的基本特性。

在这些环境中最实用的汇编语言中，你只需要选择一个可用的内存区域，将堆栈寄存器设置为指向底部，然后递增或递减来实现推入和弹出操作。

编辑：我知道一些体系结构有专用堆栈，但它们并不是必需的。

- Matthew Flaschen

---

一些汇编语言内置了push/pop和call/return命令，并且堆栈指针是专用的CPU寄存器。这是我在编写z80程序时注意到的。 - Breton

你说得对，如果必要的话，我想你可以使用其他操作来实现它们。 - Breton

事实上，将大多数功能集成到大多数语言中并没有什么根本性的东西。 Wolfram的最小图灵机http://www.wolframscience.com/prizes/tm23/background.html足以实现任何东西。 语言特性的重点是使复杂的计算更容易表达。 “堆栈”在大多数语言中不被提及作为特性，但允许递归，因为您可以使用它来解决许多有用的问题。 如果您具有递归，则不希望手动编程“类似堆栈”的行为。 - Ira Baxter

Answer 6

假设你想要实现无栈C。首先需要意识到的是这不需要一个堆栈：

a == b

但是，这样做吗？

isequal(a, b) { return a == b; }

不需要。因为聪明的编译器会将对isequal的调用内联，将其转换为a == b。那么，为什么不将所有内容都内联呢？当然，这将生成更多的代码，但如果你认为摆脱堆栈是值得的，那么这个小妥协很容易实现。

递归怎么办？没问题。像这样的尾递归函数：

bang(x) { return x == 1 ? 1 : x * bang(x-1); }

仍然可以内联，因为它实际上只是一个伪装成for循环的函数：

bang(x) {
    for(int i = x; i >=1; i--) x *= x-1;
    return x;
}

在理论上，一个非常智能的编译器可以为你找出来这个问题。但是一个不太聪明的编译器可能会把它压缩成一个 goto 语句：

ax = x;
NOTDONE:
if(ax > 1) {
    x = x*(--ax);
    goto NOTDONE;
}

有一种情况下，您需要做出一些小的妥协。这个无法内联：

fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }

Stackless C无法做到这一点。你会失去很多吗？其实不会。普通的C语言也做不好这件事。如果你不相信，只需调用fib(1000)，看看你珍贵的计算机会发生什么。

- Michael Fox

---

“Stackless” PARLANSE 可以很好地完成这个（fib）（请参见我的答案）。关于 fib(1000) 的抱怨是正确的，但不相关；在一个体面的“无栈”实现上，有许多递归函数可以实现（就像在“有栈”实现上一样）。[我们经常进行超过一百万次的递归，只是不包括 fib]。 - Ira Baxter

Answer 7

这篇文章中有一个易于理解的关于continuations的描述：http://www.defmacro.org/ramblings/fp.html。

Continuations是一种你可以在基于堆栈的语言中传递到函数中的东西，但也可以被语言自身的语义所使用，使其成为“无堆栈”语言。当然，堆栈仍然存在，但正如Ira Baxter所描述的那样，它不是一个大的连续段。

- harms

Answer 8

如果我错了，请随意纠正，但我认为为每个函数调用帧在堆上分配内存会导致极度的内存抖动。毕竟操作系统必须管理这些内存。我认为避免这种内存抖动的方法是使用调用帧缓存。因此，如果您需要缓存，我们可以将其连续地放置在内存中并称之为堆栈。

- ssteidl

---

如果你让它连续，就必须对其大小进行限制。而这个限制将阻止你处理大规模的复杂递归应用程序。如果你想要无限递归，你需要一个无限连续的堆栈，或者在某些地方将其分成几部分。 - Ira Baxter

是的，应该使用某种激活记录池来帮助确保局部性。这样就不会出现频繁的页面调度。 - Ira Baxter