无堆栈语言如何工作？

StackOverflow https://stackoverflow.com/questions/1016218

题

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

有帮助吗？

解决方案

我们拥有的现代操作系统（Windows，Linux）以我称之为“大堆栈模型”的方式运行。并且该模型有时是错误的，并且激发了对“无堆叠”的需求。语言。

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

所有此类应用程序的一个常见问题是，“我的堆栈应该有多大？”。由于内存很便宜，所以大多数情况下会发生大量的数据块（MS默认为1Mb），而典型的应用程序调用结构永远不会接近使用它。但是如果一个应用程序确实全部使用它，它会因非法内存引用而死（“我很抱歉Dave，我不能这样做”），因为它已经到了堆栈的末尾。

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

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

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

2）程序分叉子任务。每个子任务都需要自己的堆栈，因此不能使用一个“大堆栈”。提供。因此，需要为每个子任务分配堆栈。如果你有数千个可能的子任务，你现在可能需要数千个“大堆栈”，并且内存需求突然变得荒谬。分配堆栈帧解决了这个问题。通常，子任务“堆叠”回到父任务来实现词法范围;作为子任务叉，一个“亚组”的树。被创建称为“仙人掌堆栈”。

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

我实施的 PARLANSE 编程语言1）和2）。我正在努力3）。

其他提示

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

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

在 http：// www上有一篇关于语言框架Parrot的文章很好.linux-mag.com /缓存/ 7373 / 1.HTML 。 Parrot没有使用堆栈进行调用，本文稍微解释了这个技术。

在无框架环境中，我或多或少熟悉（图灵机，汇编和Brainfuck），实现自己的堆栈很常见。将语言堆叠在语言中没有任何根本。

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

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

本文有一个易于理解的延续说明： http：// www。 defmacro.org/ramblings/fp.html

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

假设您想实现无堆栈 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) 看看你的珍贵电脑会发生什么情况。

叫我古老，但我记得FORTRAN标准和COBOL不支持递归调用，因此不需要堆栈。实际上，我记得没有堆栈的CDC 6000系列机器的实现，如果你试图以递归方式调用子程序，FORTRAN会做一些奇怪的事情。

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

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

如果我错了，请随意纠正我，但我认为在堆上为每个函数调用帧分配内存会导致极端的内存抖动。毕竟操作系统必须管理这个内存。我认为避免这种内存颠簸的方法是调用帧的缓存。因此，如果你还需要一个缓存，我们不妨在内存中使它成为一个堆栈。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top