堆栈的目的是什么?我们为什么需要它?

小开

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

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

小开

如果不遵循堆栈/堆的概念，数据被加载到随机内存位置或数据从随机内存位置存储…它将是非结构化和无管理的。

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

小开

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

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

实际的机器代码模型是混合的，既有堆栈又有寄存器。JIT代码优化器的一项重要工作是找到方法将栈上的变量存储在寄存器中，从而大大提高执行速度。而Dalvik抖动则有相反的问题。

机器堆栈是一种非常基本的存储设施，在处理器设计中已经存在很长时间了。它具有非常好的引用局部性，这是现代cpu的一个非常重要的特性，它处理数据的速度比RAM快得多，并且支持递归。语言设计很大程度上受到堆栈的影响，堆栈可见于对局部变量的支持，范围仅限于方法体。堆栈的一个重要问题就是这个站点的命名原因。

小开

最佳答案

更新:我非常喜欢这个问题，所以我把它改成这是我2011年11月18日博客的主题。谢谢你的好问题!

我一直在想:堆栈的目的是什么?

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

为什么要从内存转移到堆栈或“加载”?另一方面，为什么要从堆栈转移到内存或“存储”?为什么不把它们都放在内存里呢?

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

首先让我们来回答“为什么要有MSIL ?”为什么不直接让c#编译器写出机器代码呢?

因为这样做是更便宜的。假设我们不这么做;假设每种语言都必须有自己的机器代码生成器。你有20种不同的语言:c#， JScript . net, Visual Basic， IronPython， f#…假设你有10个不同的处理器。你需要编写多少代码生成器?20 x 10 = 200个代码生成器。工作量很大。现在假设您想要添加一个新的处理器。你必须为它编写20次代码生成器，每种语言一次。

此外，这是困难和危险的工作。为你不是专家的芯片编写高效的代码生成器是一项艰难的工作!编译器设计人员是语言语义分析的专家，而不是新芯片组的有效寄存器分配的专家。

现在假设我们采用CIL方法。您需要编写多少个CIL生成器?每种语言一个。你需要编写多少个JIT编译器?每个处理器一个。总数:20 + 10 = 30个代码生成器。此外，语言到CIL生成器很容易编写，因为CIL是一种简单的语言，而CIL到机器代码生成器也很容易编写，因为CIL是一种简单的语言。我们摆脱了c#和VB等所有复杂的东西，把所有东西都“降低”到一种容易编写的简单语言。

使用中间语言可以降低生成新语言编译器戏剧性的的成本。它还大大降低了支持新芯片的成本。你想要支持一个新的芯片，你找一些该芯片的专家让他们写一个CIL jitter，你就完成了;然后在芯片上支持所有这些语言。

好了，我们已经确定了为什么要有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”指令知道它将从堆栈中取出两个东西并放入一个东西，它可以是一个字节。一个使用两个操作数地址和一个结果地址的add指令将会非常庞大。

我们使用基于堆栈的操作码是因为堆栈解决了常见问题.;即:我想分配一些临时的存储空间，很快地使用它，然后在我用完之后迅速地摆脱它。通过假设我们有一个堆栈，我们可以使操作码非常小，代码非常简洁。

更新:一些额外的想法

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

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

小开

在堆栈问题上再加一点。堆栈概念源于CPU设计，其中算术逻辑单元(ALU)中的机器代码对位于堆栈上的操作数进行操作。例如，乘法操作可以从堆栈中取出两个顶部操作数，将它们相乘并将结果放回堆栈。机器语言通常有两个基本函数用于从堆栈中添加和删除操作数;推一推。在许多cpu的dsp(数字信号处理器)和机器控制器(如控制洗衣机)中，堆栈位于芯片本身。这样可以更快地访问ALU，并将所需的功能整合到单个芯片中。

小开

通过使用延续传球风格的编码，可以让一个系统在没有堆栈的情况下工作。然后调用帧成为在垃圾回收堆中分配的continuation(垃圾回收器将需要一些堆栈)。

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

(由于缓存问题，他今天可能会有一点错误)

小开

我寻找“中断”，没有人把它作为一个优势。对于中断微控制器或其他处理器的每个设备，通常都有寄存器被推入堆栈，调用中断服务例程，当它完成时，寄存器被弹出堆栈，并放回它们原来的位置。然后指令指针恢复，正常的活动从中断的地方恢复，几乎就像中断从未发生过一样。有了堆栈，你实际上可以让几个设备(理论上)互相中断，这一切都是正常工作的——因为堆栈。

还有一组基于堆栈的语言，叫做衔接语言。(我相信)它们都是函数式语言，因为堆栈是传入的隐式参数，更改后的堆栈也是每个函数的隐式返回值。出来和因素(这很好)都是例子，还有其他例子。Factor与Lua类似，用于编写游戏脚本，由Slava Pestov编写，他是苹果公司的一名天才。我已经看过几次了。他谈论Boa构造函数，但我不确定他的意思;-)。

我真的认为当前的一些虚拟机，比如JVM、微软的CIL，甚至我看到的为Lua编写的虚拟机，都应该用这些基于堆栈的语言来编写，以便它们能够移植到更多的平台上。我认为这些连接语言在某种程度上失去了它们作为虚拟机创建工具包和可移植性平台的使命。甚至还有pForth，一个用ANSI C编写的“可移植的”Forth，它可以用于更通用的可移植性。有人试过用Emscripten或WebAssembly编译吗?

使用基于堆栈的语言，有一种称为零点的代码风格，因为您可以只列出要调用的函数而不传递任何参数(有时)。如果这些函数完美地结合在一起，那么除了所有零点函数的列表之外，什么都没有，这就是您的应用程序(理论上)。如果你深入研究Forth或Factor，你就会明白我在说什么。

容易出是一个用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的书并实现它。商业上的Forth太复杂了，关于Forth最伟大的事情是可以从上到下理解整个系统。以某种方式，Forth在一个新的处理器上实现了一个完整的开发环境，尽管它的需要似乎已经在C上传递了所有东西，但从头开始编写Forth仍然是有用的。因此，如果您选择这样做，请尝试FigForth书籍——它是在各种处理器上同时实现几个forth。就像福斯的罗塞塔石碑。

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