62

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

4

8 回答 8

90

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

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

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

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

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

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

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

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

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

于 2009-06-27T16:38:20.913 回答
14

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

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

于 2009-06-19T03:29:47.573 回答
6

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

于 2009-06-27T20:24:45.760 回答
5

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

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

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

于 2009-06-19T03:24:56.880 回答
4

称我为古老的，但我记得 FORTRAN 标准和 COBOL 何时不支持递归调用，因此不需要堆栈。确实，我记得没有堆栈的 CDC 6000 系列机器的实现，如果您尝试递归调用子例程，FORTRAN 会做一些奇怪的事情。

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

显然，这不适用于递归调用。（我记得如果您尝试递归，CDC FORTRAN IV 编译器会生成损坏的代码......）

于 2009-09-09T04:20:05.143 回答
2

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

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

于 2009-06-27T20:35:47.890 回答
2

假设您想实现无堆栈 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)，看看您宝贵的计算机会发生什么。

于 2014-01-29T11:44:26.733 回答
1

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

于 2009-09-12T04:41:39.067 回答