无堆栈语言如何工作？

Question

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

Answer 1

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

Answer 2

Stackless Python 仍然有一个 Python 堆栈（尽管它可能有尾调用优化和其他调用框架合并技巧），但是它完全脱离了解释器的C堆栈。

Haskell（通常实现的）没有调用堆栈； 评估基于图缩减。

Answer 3

有一篇关于 Parrot 语言框架。 Parrot 不使用堆栈进行调用，本文对此技术进行了一些解释。

Answer 4

在我或多或少熟悉的无堆栈环境（图灵机、汇编和 Brainfuck）中，实现自己的堆栈是很常见的。 将堆栈内置到语言中并没有什么基础的。

在最实用的汇编中，您只需选择可用的内存区域，将堆栈寄存器设置为指向底部，然后递增或递减以实现推送和弹出。

编辑：我知道有些架构有专用堆栈，但它们不是必需的。

Answer 5

你可以说我很古老，但我记得 FORTRAN 标准和 COBOL 不支持递归调用，因此不需要堆栈。 事实上，我记得 CDC 6000 系列机器的实现没有堆栈，如果您尝试递归调用子例程，FORTRAN 会做奇怪的事情。

根据记录，CDC 6000 系列指令集使用 RJ 指令来调用子例程，而不是调用堆栈。 这将当前 PC 值保存在调用目标位置，然后分支到其后面的位置。 最后，子例程将执行间接跳转到调用目标位置。 这会重新加载保存的 PC，有效地返回给调用者。

显然，这对于递归调用不起作用。 我记得如果你尝试递归，CDC FORTRAN IV 编译器会生成损坏的代码。

但是 CDC 也有 Pascal 实现（我怀疑来自 ETH），其中递归 >did< 工作。 所以大概 Pascal 运行时>做了< 有一个正确的堆栈并且>没有< 使用RJ。 我的记忆是它是一个编译器而不是解释器，但我只是一个本科生用户，而且那是很久以前的事了。

Answer 6

本文有一个易于理解的延续描述：http://www.defmacro.org /ramblings/fp.html

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

Answer 7

假设您想实现无堆栈 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;
}

理论上，一个真正聪明的编译器可以为您解决这个问题。 但不太聪明的人仍然可以将其扁平化为首选：

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) 看看您珍贵的计算机会发生什么情况。

Answer 8

我们拥有的现代操作系统（Windows、Linux）采用我所说的“大堆栈模型”运行。 有时，这种模型是错误的，并且激发了对“无堆栈”语言的需求。

“大堆栈模型”假设编译的程序将在连续的内存区域中为函数调用分配“堆栈帧”，使用机器指令非常快速地调整包含堆栈指针（和可选的堆栈帧指针）的寄存器。 这会导致快速的函数调用/返回，但代价是需要一个大的、连续的堆栈区域。 因为在这些现代操作系统下运行的所有程序中 99.99% 都可以与大堆栈模型很好地配合，所以编译器、加载器甚至操作系统都“知道”这个堆栈区域。

所有此类应用程序都存在的一个常见问题是，“我的堆栈应该有多大？”。 由于内存非常便宜，最常见的情况是为堆栈预留了一大块（MS 默认为 1Mb），而典型的应用程序调用结构永远不会接近用完它。 但是，如果应用程序确实用完了所有内存，它会由于超出堆栈末尾而因非法内存引用而终止（“对不起戴夫，我不能这样做”）。

大多数所谓的“无堆栈”语言并不是真正的无堆栈。 他们只是不使用这些系统提供的连续堆栈。 相反，他们所做的是在每次函数调用时从堆中分配一个堆栈帧。 每个函数调用的成本有所上升； 如果函数通常很复杂，或者语言是解释性的，则这种额外成本是微不足道的。 （我们还可以确定程序调用图中的调用 DAG，并分配一个堆段来覆盖整个 DAG；这样，对于调用 DAG 内的所有调用，您可以获得堆分配和经典大堆栈函数调用的速度）。

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

1. 如果程序根据其正在解决的特定问题进行深度递归，
   提前预分配“大堆栈”区域非常困难，因为所需的大小未知。 人们可以笨拙地安排函数调用来检查是否有足够的堆栈剩余，如果没有，则重新分配更大的块，复制旧堆栈并将所有指针重新调整到堆栈中； 这太尴尬了，我不知道有任何实现。
   分配堆栈帧意味着应用程序永远不必说对不起，直到有
   实际上已经没有剩余可分配内存了。

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

3. 你的语言有延续。 这些要求以某种方式保留当前函数可见的词法范围内的数据以供以后重用。 这可以通过复制父堆栈帧、爬上 cactus 堆栈并继续进行来实现。

我实现的 PARLANSE 编程语言执行 1) 和 2)。 我正在研究3）。 有趣的是，PARLANSE 从非常快速访问的每线程堆中分配堆栈帧； 它通常需要 4 条机器指令。 当前的实现是基于 x86 的，分配的帧被放置在 x86 EBP/ESP 寄存器中，就像其他传统的基于 x86 的语言实现一样。 因此，它确实以块的形式使用硬件“连续堆栈”（包括压入和弹出）。 它还生成“帧本地”子例程调用，不会为预先知道堆栈需求的大量生成的实用程序代码切换堆栈。