堆栈的用途是什么？我们为什么需要它？

有一篇关于此的非常有趣/详细的维基百科文章，堆栈机指令集的优点。我需要完全引用它，所以简单地放一个链接更容易。我只引用副标题

• 非常紧凑的目标代码
• 简单的编译器/简单的解释器
• 最小处理器状态

如果不遵循堆栈/堆的概念，并且将数据加载到随机内存位置，或者数据从随机内存位置存储...这将是非常非结构化和不受管理的。

这些概念用于将数据存储在预定义的结构中，以提高性能、内存使用率......因此称为数据结构。

请记住，当您谈论 MSIL 时，您谈论的是虚拟机的指令。.NET 中使用的 VM 是基于堆栈的虚拟机。与基于寄存器的 VM 相反，Android 操作系统中使用的 Dalvik VM 就是一个例子。

VM 中的堆栈是虚拟的，由解释器或实时编译器将 VM 指令转换为在处理器上运行的实际代码。在 .NET 的情况下，这几乎总是抖动，MSIL 指令集被设计为从一开始就被抖动。例如，与 Java 字节码相反，它对特定数据类型的操作有不同的指令。这使得它经过优化以进行解释。不过，MSIL 解释器实际上存在，它在 .NET Micro Framework 中使用。它在资源非常有限的处理器上运行，负担不起存储机器代码所需的 RAM。

实际的机器代码模型是混合的，既有堆栈又有寄存器。JIT代码优化器的一大工作是想出一种方法来存储保存在寄存器中的堆栈上的变量，从而大大提高执行速度。Dalvik 抖动则相反。

否则，机器堆栈是一个非常基本的存储设施，在处理器设计中已经存在了很长时间。它具有非常好的参考局部性，这是现代 CPU 的一个非常重要的功能，它咀嚼数据的速度比 RAM 提供数据的速度快得多，并且支持递归。语言设计在很大程度上受到堆栈的影响，堆栈在对局部变量的支持中可见，范围仅限于方法主体。堆栈的一个重大问题是该站点命名的那个问题。

更新：我非常喜欢这个问题，我在2011年11月18日将其作为博客的主题。谢谢你的好问题！

我一直在想：堆栈的目的是什么？

我假设您指的是 MSIL 语言的评估堆栈，而不是运行时的实际每线程堆栈。

为什么会从内存转移到堆栈或“加载”？另一方面，为什么会有从堆栈到内存或“存储”的转移？为什么不把它们都放在内存中呢？

MSIL 是一种“虚拟机”语言。像 C# 编译器这样的编译器会生成 CIL，然后在运行时，另一个称为 JIT（实时）编译器的编译器将 IL 转换为可以执行的实际机器代码。

因此，首先让我们回答“为什么有MSIL”这个问题？为什么不让 C# 编译器写出机器代码呢？

因为这样做更便宜。假设我们没有那样做;假设每种语言都必须有自己的机器码生成器。您有 20 种不同的语言：C#、JScript .NET、Visual Basic、IronPython、F#...假设你有十个不同的处理器。你需要编写多少个代码生成器？20 x 10 = 200 个代码生成器。这是一项艰巨的工作。现在假设您要添加一个新处理器。你必须为它编写代码生成器 20 次，每种语言一次。

此外，这是一项艰巨而危险的工作。为您不熟悉的芯片编写高效的代码生成器是一项艰巨的工作！编译器设计人员是语言语义分析方面的专家，而不是新芯片组的有效寄存器分配方面的专家。

现在假设我们以 CIL 方式进行操作。您必须编写多少个 CIL 生成器？每种语言一个。您必须编写多少个 JIT 编译器？每个处理器一个。总计：20 + 10 = 30 个代码生成器。此外，语言到 CIL 生成器很容易编写，因为 CIL 是一种简单的语言，而 CIL 到机器代码生成器也很容易编写，因为 CIL 是一种简单的语言。我们摆脱了 C# 和 VB 等的所有复杂性，并将所有内容“简化”为一种易于编写抖动的简单语言。

拥有中间语言可以大大降低生产新语言编译器的成本。它还大大降低了支持新芯片的成本。你想支持一个新芯片，你找到一些芯片上的专家，让他们写一个CIL抖动，你就完成了;然后，您可以在芯片上支持所有这些语言。

好的，我们已经确定了为什么我们有 MSIL;因为拥有中间语言可以降低成本。那么，为什么语言是“堆栈机器”呢？

因为堆栈机器在概念上对于语言编译器编写者来说非常简单。堆栈是一种简单易懂的计算描述机制。从概念上讲，堆栈机器对于JIT编译器编写者来说也非常容易处理。使用堆栈是一种简化的抽象，因此，它再次降低了我们的成本。

你问“为什么要有堆栈？为什么不直接在内存中做所有事情呢？好吧，让我们考虑一下。假设您要为以下项生成 CIL 代码：

int x = A() + B() + C() + 10;

假设我们有一个约定，即“add”、“call”、“store”等总是将它们的参数从堆栈中取出，并将它们的结果（如果有的话）放在堆栈上。为了生成此 C# 的 CIL 代码，我们只需这样说：

load the address of x // The stack now contains address of x
call A()              // The stack contains address of x and result of A()
call B()              // Address of x, result of A(), result of B()
add                   // Address of x, result of A() + B()
call C()              // Address of x, result of A() + B(), result of C()
add                   // Address of x, result of A() + B() + C()
load 10               // Address of x, result of A() + B() + C(), 10
add                   // Address of x, result of A() + B() + C() + 10
store in address      // The result is now stored in x, and the stack is empty.

现在假设我们在没有堆栈的情况下做到了。我们将按照您的方式进行操作，其中每个操作码都采用其操作数的地址以及存储结果的地址：

Allocate temporary store T1 for result of A()
Call A() with the address of T1
Allocate temporary store T2 for result of B()
Call B() with the address of T2
Allocate temporary store T3 for the result of the first addition
Add contents of T1 to T2, then store the result into the address of T3
Allocate temporary store T4 for the result of C()
Call C() with the address of T4
Allocate temporary store T5 for result of the second addition
...

你看这是怎么回事吗？我们的代码变得越来越庞大，因为我们必须显式分配所有临时存储，而这些存储通常按照惯例只会放在堆栈上。更糟糕的是，我们的操作码本身都变得越来越大，因为它们现在都必须将要写入结果的地址以及每个操作数的地址作为参数。一个“add”指令知道它将从堆栈中删除两个东西并放置一个东西，可以是一个字节。一个需要两个操作数地址和一个结果地址的添加指令将是巨大的。

我们使用基于堆栈的操作码，因为堆栈解决了常见问题。即：我想分配一些临时存储空间，尽快使用它，然后在完成后迅速将其删除。通过假设我们有一个堆栈可供使用，我们可以使操作码非常小，代码非常简洁。

更新：一些其他想法

顺便说一句，通过（1）指定虚拟机，（2）编写面向VM语言的编译器，以及（3）在各种硬件上编写VM的实现来大幅降低成本的想法根本不是一个新想法。它不是起源于 MSIL、LLVM、Java 字节码或任何其他现代基础设施。据我所知，这种策略的最早实现是 1966 年的 pcode 机器。

我个人第一次听说这个概念是在我了解到 Infocom 实现者如何设法让 Zork 在这么多不同的机器上运行得如此出色时。他们指定了一个名为 Z-machine 的虚拟机，然后为他们想要运行游戏的所有硬件制作了 Z-machine 模拟器。这还有一个额外的巨大好处，即他们可以在原始的 8 位系统上实现虚拟内存管理;游戏可能比内存大，因为他们可以在需要时从磁盘中分页代码，并在需要加载新代码时丢弃它。

在堆栈问题中添加更多内容。堆栈概念源自 CPU 设计，其中算术逻辑单元 （ALU） 中的机器代码在位于堆栈上的操作数上运行。例如，乘法运算可能会从堆栈中获取两个排名靠前的操作数，将它们乘以并将结果放回堆栈中。机器语言通常有两个基本函数，用于在堆栈中添加和删除操作数;推和弹出。在许多CPU的DSP（数字信号处理器）和机器控制器（例如控制洗衣机的控制器）中，堆栈位于芯片本身上。这样可以更快地访问 ALU，并将所需的功能整合到单个芯片中。

通过使用延续传递编码样式，可以使系统在没有堆栈的情况下工作。然后，调用帧成为在垃圾回收堆中分配的延续（垃圾回收器需要一些堆栈）。

参见 Andrew Appel 的旧著作： 使用延续和垃圾回收进行编译可以比堆栈分配更快

（由于缓存问题，他今天可能有点不对劲）

我寻找“中断”，但没有人将其视为优势。对于中断微控制器或其他处理器的每个设备，通常会将寄存器推送到堆栈上，调用中断服务例程，完成后，将寄存器从堆栈中弹出，并放回原处。然后指令指针被恢复，正常活动从中断的地方继续，几乎就像中断从未发生过一样。有了堆栈，你实际上可以让几个设备（理论上）相互中断，而且这一切都可以正常工作——因为堆栈。

还有一系列基于堆栈的语言，称为串联语言。它们都是（我相信）函数式语言，因为堆栈是传入的隐式参数，而且更改后的堆栈是每个函数的隐式返回。Forth 和 Factor（非常出色）都是示例，还有其他示例。Factor 的使用类似于 Lua，用于编写游戏脚本，由目前在 Apple 工作的天才 Slava Pestov 编写。他在 youtube 上的 Google TechTalk 我已经看了几次。他谈到了 Boa 构造函数，但我不确定他的意思;

我真的认为当前的一些VM，比如JVM，Microsoft的CIL，甚至是我看到的为Lua编写的VM，应该用一些基于堆栈的语言编写，以使它们可移植到更多的平台。我认为这些连接语言在某种程度上缺少了它们作为 VM 创建工具包和可移植性平台的使命。甚至还有pForth，一个用ANSI C编写的“可移植”Forth，可用于更通用的可移植性。有人尝试使用 Emscripten 或 WebAssembly 编译它吗？

对于基于堆栈的语言，有一种称为零点的代码样式，因为您可以只列出要调用的函数，而无需（有时）传递任何参数。如果这些函数完美地结合在一起，那么你将只剩下所有零点函数的列表，这将是你的应用程序（理论上）。如果你深入研究 Forth 或 Factor，你就会明白我在说什么。

在Easy Forth，一个用JavaScript编写的不错的在线教程中，这里有一个小示例（请注意“sq sq sq sq”作为零点调用风格的示例）：

: sq dup * ;  ok
2 sq . 4  ok
: ^4 sq sq ;  ok
2 ^4 . 16  ok
: ^8 sq sq sq sq ;  ok
2 ^8 . 65536  ok

此外，如果你看一下 Easy Forth 网页源代码，你会在底部看到它非常模块化，用大约 8 个 JavaScript 文件编写。

我花了很多钱买了几乎所有我能拿到的福斯书，试图吸收福斯，但现在我才刚刚开始更好地理解它。我想给后来的人提个醒，如果你真的想得到它（我发现这一点为时已晚），请获取关于 FigForth 的书并实现它。商业 Forths 太复杂了，而 Forth 最伟大的事情是可以理解整个系统，从上到下。不知何故，Forth 在新处理器上实现了整个开发环境，尽管 C 似乎已经满足了对这种需求的所有需求，但从头开始编写 Forth 仍然是一种有用的仪式。所以，如果你选择这样做，试试 FigForth 一书——它是在各种处理器上同时实现的几个 Forth。一种福斯的罗塞塔石碑。

为什么我们需要一个堆栈——效率、优化、零点、中断时保存寄存器，对于递归算法来说，它是“正确的形状”。