有一篇关于语言框架Parrot的很好的文章。Parrot不使用堆栈进行调用，这篇文章解释了这种技术的一点。原始链接已经失效，以下是Wayback Machine存档的版本：web.archive.org/web/20100706035639/http://www.linux-mag.com/…

在计算机科学中，堆栈是一种常见的数据结构，用于跟踪程序的执行。它是一种后进先出（LIFO）的结构，允许我们按照特定的顺序管理函数调用和变量的分配。

然而，堆栈的使用也带来了一些问题。首先，堆栈的大小是固定的，当我们的程序需要更多的内存时，可能会导致堆栈溢出。其次，堆栈的操作需要消耗额外的时间和空间。

为了解决这些问题，一些语言框架开始采用无堆栈的方法。这种方法通过使用其他数据结构来替代堆栈，从而避免了上述问题。例如，Parrot语言框架就是使用这种技术来实现无堆栈的调用。

具体而言，Parrot使用一个称为Continuation的数据结构来管理函数的调用。Continuation包含了函数的执行状态，包括当前指令的位置、局部变量的值等。通过使用Continuation，Parrot可以在函数之间切换执行，并且不需要使用堆栈进行函数调用。

这种无堆栈的方法带来了一些好处。首先，由于不需要维护堆栈，Parrot可以节省内存空间。其次，无堆栈的调用可以更加灵活，可以实现一些传统堆栈无法实现的功能，比如非局部跳转。

然而，无堆栈的方法也存在一些挑战。首先，由于Continuation中包含了函数的执行状态，因此它的大小可能会比堆栈大。这可能会导致内存消耗增加。其次，无堆栈的调用需要额外的操作来保存和恢复Continuation的状态，这可能会导致性能下降。

为了解决这些问题，Parrot采用了一些优化技术。例如，Parrot使用了一种称为“轻量级Continuation”的技术，它可以减小Continuation的大小，并提高性能。此外，Parrot还使用了一些编译器优化技术，以减少对Continuation的操作次数。

总之，无堆栈的调用是一种优化技术，可以避免堆栈溢出和额外的开销。Parrot语言框架通过使用Continuation来实现无堆栈的调用，并通过一些优化技术来解决性能和内存消耗的问题。这种方法为我们提供了一种更加灵活和高效的函数调用方式。

根据给定的内容，我们可以得出问题的原因是：如何实现一种无栈语言。而解决方法是通过使用尾递归优化、调用帧合并技巧和图缩减等技术来实现。

无栈语言是指不依赖于传统的调用栈来进行函数调用和返回的编程语言。在传统的编程语言中，每次函数调用都会在调用栈上创建一个新的调用帧，并将其压入栈中。当函数返回时，调用帧会从栈中弹出，控制权回到上一个调用点。

然而，一些编程语言希望能够在没有栈的情况下进行函数调用和返回。这可能是因为栈的使用会导致内存消耗过大，或者需要更高效地处理函数调用和返回。

为了解决这个问题，一些编程语言采取了尾递归优化的方法。尾递归是指函数的最后一个动作是一个函数调用，且没有任何其他操作。在尾递归优化中，编译器会将尾递归函数转化为一个循环，从而避免使用栈来保存调用帧。这样可以减少内存的使用，并提高函数调用的效率。

另一种解决方法是使用调用帧合并技巧。调用帧合并是指将多个相邻的函数调用合并为一个调用帧。这样可以减少在栈上分配的内存空间，并减少函数调用的开销。

还有一种解决方法是使用图缩减技术。图缩减是指将函数调用的过程表示为一个图，并对图进行优化。通过对图进行缩减，可以将多个函数调用合并为一个调用帧，并消除不必要的中间过程。这样可以减少内存的使用，并提高函数调用的效率。

实现无栈语言的方法包括尾递归优化、调用帧合并技巧和图缩减等。这些方法可以减少内存的使用，并提高函数调用的效率。

栈是计算机中常用的数据结构，用于保存函数调用的信息。然而，现代操作系统的栈模型在某些情况下是错误的，这就引发了对“无栈”语言的需求。传统的栈模型假设编译后的程序会在内存中的连续区域分配“栈帧”，使用机器指令来快速调整包含栈指针（和可选的栈帧指针）的寄存器。这样可以实现快速的函数调用/返回，但需要大量的连续内存空间作为栈。然而，99.99%的程序在运行时都可以很好地适应这种大栈模型，因此编译器、加载器甚至操作系统都对这个栈区域有所了解。

然而，使用大栈模型会面临一个常见问题：“我的栈应该有多大？”由于内存价格便宜，通常情况下会为栈分配大块内存（例如Windows默认为1MB），而典型的应用程序调用结构在使用栈时远未达到这个限制。但如果应用程序确实使用了所有的栈空间，就会出现内存引用错误，导致程序终止。

大多数所谓的“无栈”语言实际上并不是真正的无栈。它们只是不使用这些系统提供的连续栈。它们通过在每个函数调用时从堆中分配一个栈帧来解决这个问题。每次函数调用的成本会略微增加；如果函数通常很复杂，或者语言是解释性的，则这种额外的成本是微不足道的。（还可以在程序调用图中确定调用DAG，并分配一个堆段以覆盖整个DAG；这样，您既可以获得堆分配，又可以获得经典大栈函数调用的速度）。

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

1. 如果程序在解决特定问题时需要进行深度递归，事先预分配“大栈”区域非常困难，因为无法预知所需的大小。可以笨拙地安排函数调用以检查是否还有足够的栈空间，如果没有，则重新分配更大的块，复制旧栈并调整指向栈的所有指针；这样做很麻烦，我不知道是否有任何实现。

2. 程序分叉为子任务。每个子任务都需要自己的栈，因此不能使用提供的“大栈”。因此，需要为每个子任务分配栈。如果有数千个可能的子任务，可能需要数千个“大栈”，这样内存需求就变得荒谬。分配栈帧可以解决这个问题。通常，子任务的“栈”会引用父任务，以实现词法作用域；随着子任务的分叉，将创建一个“子栈”的树形结构，称为“仙人掌栈”。

3. 语言具有连续性。这要求在当前函数的词法作用域中可见的数据能够被保留以供以后重用。可以通过复制父栈帧、向上爬升仙人掌栈并继续实现这一点。

PARLANSE是一个实现了第1点和第2点的编程语言，作者正在研究第3点。有趣的是，PARLANSE从一个非常快速访问的堆（每个线程一个）中分配栈帧；这个过程通常只需要4条机器指令。当前的实现是基于x86架构的，分配的栈帧类似于其他传统的x86编程语言实现，放在了x86的EBP/ESP寄存器中。因此，它确实使用了硬件的“连续栈”（包括推入和弹出），只是以块的形式。对于许多Windoze和Linux的线程实现，它们都有相同的“大栈”假设（主要是因为“进程”只是一个带有关联地址空间的特殊线程）。因此，所有相同的问题都会出现。对于PARLANSE，作者将Window的线程复用到了数以万计的“粒子”中，每个粒子都使用自己分配的栈帧。

如果您只想分叉一些子任务，而这些子任务的数量由操作系统提供的线程数量限制（通常只有几百个），那么您可能可以使用线程提供的大栈模型。但如果您的并行/并发计算有很多交互，您可能需要成千上万个计算单元，那么操作系统的线程模型将无法满足您的需求。

Haskell实际上根本不使用调用栈，甚至不使用由堆空间链接的链表构成的栈。可以将其视为一个非常先进的宏替换语言。

栈不会在Windows上占用1MB的内存。它们会保留1MB的地址空间。栈还有第二个设置，即“commit”，它指定实际使用的RAM。默认值只有4KB（1页）。这是因为虚拟内存管理器了解栈的工作原理。特别是，将其他调用帧推入栈会引发CPU错误，然后通过这个错误来提交更多的RAM。如果默认的1MB地址空间被保留，这将至少成功256次，但不能保证在第257次调用时失败。这个保留是一个软限制。

有人说：“我确实理解了这一点。无论是软限制还是不是，它们都不能保证可以将栈扩展到软限制之外。我个人使用C程序进行深层嵌套的经验表明，它们并不会努力扩展栈超过软限制。我怀疑这样做的想法是，如果递归超过1MB，那么你的程序可能无法控制，将栈扩展到完整的64GB空间（如果可用）也不会改善情况。主要问题是，如果要确保可以进行深层递归，固定栈是一个糟糕的选择。数以万计的计算粒子会严重加剧这个问题。”

另一个人说：“这也是操作系统与编程语言之间的问题。Windows根本不关心您是否使用操作系统栈来保存指向调用帧的指针，而实际的调用帧在堆上。即使是结构化异常处理也可以处理这种情况。对于Win32来说，这是2个指针@4字节，可以给您每个线程的最大栈深度为128K个帧。您可能会先耗尽堆空间。主要缺点是您将丢失方便的push EAX命令，而必须使用EBP作为调用帧寄存器。（但这通常很常见）。”另一个人补充说：“大部分答案都是关于使用堆分配的记录，与您提到的方式不完全相同，但类似。”

关于DAG的问题，DAG代表有向无环图（Directed Acyclic Graph）。

还某些情况下：“那个链接为什么要放在回答的末尾？它对回答没有任何帮助，也没有与上下文相关。”另一个人回答说：“它提供了明确的证明，可以实现回答中提供的概念。”另一个人则认为：“该链接并没有提供任何支持回答中所做的声明的信息。您只是在做广告。”最后一个人表示：“您可以说你喜欢什么，但根据投票情况来看，读者似乎对这个回答很满意。我设计PARLANSE是为了解决复杂的并行性问题，这就要求使用无栈解决方案和仙人掌栈（非并行的回答不需要这个）。该链接展示了可以将这个实现为一个生产质量的工具。即使对您来说并不明显，它是隐含的证明。”