Ira*_*ter 85
我们拥有的现代操作系统(Windows,Linux)以我称之为"大堆栈模型"的方式运行.而且这种模式有时是错误的,并且激发了对"无堆叠"语言的需求.
"大堆栈模型"假定编译的程序将在连续的存储器区域中为函数调用分配"堆栈帧",使用机器指令非常快速地调整包含堆栈指针(和可选的堆栈帧指针)的寄存器.这导致快速的函数调用/返回,代价是具有堆栈的大的连续区域.因为在这些现代操作系统下运行的所有程序中99.99%适用于大堆栈模型,编译器,加载器甚至操作系统"都知道"这个堆栈区域.
所有这些应用程序的一个常见问题是,"我的堆栈应该有多大？" .由于内存很便宜,所以大多数情况下会发生大量的数据块(MS默认为1Mb),并且典型的应用程序调用结构永远不会接近使用它.但是如果一个应用程序确实全部使用它,它会因为非法内存引用而死("我很抱歉Dave,我不能这样做"),因为它已经到了堆栈的末尾.
大多数所谓的"无堆栈"语言并非真正无堆叠.它们只是不使用这些系统提供的连续堆栈.他们所做的是在每次函数调用时从堆中分配堆栈帧.每个函数调用的成本有所上升; 如果函数通常很复杂,或者语言是解释性的,那么这个额外的成本是微不足道的.(也可以在程序调用图中确定调用DAG并分配一个堆段来覆盖整个DAG;这样就可以获得堆分配和调用DAG内所有调用的经典大堆函数调用的速度).
使用堆分配堆栈帧有几个原因:
1)如果程序根据它正在解决的特定问题进行深度递归,则很难预先分配"大堆栈"区域,因为所需的大小是未知的.可以笨拙地安排函数调用以检查是否有足够的堆栈,如果没有,重新分配更大的块,复制旧堆栈并重新调整所有指针进入堆栈; 这太尴尬了,我不知道任何实现.分配堆栈帧意味着应用程序永远不必说对不起,直到实际上没有可分配的内存.
2)程序分叉子任务.每个子任务都需要自己的堆栈,因此不能使用提供的一个"大堆栈".因此,需要为每个子任务分配堆栈.如果你有数千个可能的子任务,你现在可能需要成千上万的"大堆栈",内存需求突然变得荒谬.分配堆栈帧解决了这个问题.子任务"堆栈"通常会引用父任务来实现词法作用域; 作为子任务fork,创建一个称为"仙人掌堆栈"的"substacks"树.
3)你的语言有延续.这些要求以某种方式保留当前函数可见的词法范围中的数据以供以后重用.这可以通过复制父堆栈帧,爬上仙人掌堆栈并继续进行来实现.
我实现的PARLANSE编程语言有1)和2).我正在努力3).
eph*_*ent 14
Stackless Python仍然有一个Python堆栈(虽然它可能有尾调用优化和其他调用框架合并技巧),但它完全脱离了解释器的C堆栈.
Haskell(通常实现)没有调用堆栈; 评估基于图表缩减.
在我或多或少熟悉的无堆栈环境（车床，装配体和Brainfuck）中，实现自己的堆栈很常见。在语言中内置堆栈并没有什么基础。
在最实用的汇编程序中，您只需选择一个可用的内存区域，将堆栈寄存器设置为指向底部，然后递增或递减以实现压入和弹出操作。
编辑：我知道某些体系结构具有专用的堆栈，但它们不是必需的。
你可以说我很古老，但我记得 FORTRAN 标准和 COBOL 不支持递归调用，因此不需要堆栈。事实上，我记得 CDC 6000 系列机器的实现没有堆栈，如果您尝试递归调用子例程，FORTRAN 会做奇怪的事情。
根据记录，CDC 6000 系列指令集使用指令RJ来调用子例程，而不是调用堆栈。这将当前 PC 值保存在调用目标位置，然后分支到其后面的位置。最后，子例程将执行间接跳转到调用目标位置。这会重新加载保存的 PC，有效地返回给调用者。
显然，这不适用于递归调用。我记得如果你尝试递归，CDC FORTRAN IV 编译器会生成损坏的代码。
但是 CDC 也有 Pascal 实现（我怀疑来自 ETH），其中递归>确实<起作用。因此，大概 Pascal 运行时 >did< 有一个正确的堆栈并且 >didn't< 使用RJ。我的记忆是它是一个编译器而不是解释器，但我只是一个本科生用户，而且那是很久以前的事了。