logo标签列表

C语言运行需要堆和栈吗？

cheap-memorystack-memory
14

人们谈论堆栈和堆之间的区别。但我很好奇，如果CPU不支持堆栈和堆结构，那么C语言是否可以在没有堆栈和堆的情况下正常运行？

5
通常，提出“我应该从哪里开始”的问题过于宽泛，不适合在本网站上提问。每个人解决问题的方法都不同，因此没有“正确答案”。请仔细阅读Where to Start，然后再发表您的帖子。 - Stargateur
1
但这个问题太广泛了。您一次性询问多种编程语言的答案。我建议您将其删除。 - Spikatrix
1
因为原作者已经编辑了问题，所以投票重新开启。 - Spikatrix
2
实现堆栈或堆所需的全部只是随机访问内存，因此即使您的CPU不“本地”支持堆栈或堆，您仍然可以将它们作为C运行时库的一部分实现。 - Chris Dodd
在很大程度上，机器是否提供“堆栈”和“堆”是命名语义学的问题。虽然标准中没有提到这些术语，但是从 'SP' 寄存器开始，它们已经深入编程中。如果没有“堆栈”（或其概念），该寄存器可能会有不同的缩写。要进行良好的历史回顾，请参见堆栈概念在处理器寄存器中的普遍性。 - David C. Rankin
显示剩余5条评论
3个回答
14
不，它不需要。让我们先谈堆，那很容易。
如果一个实现没有提供任何堆，只需要在调用malloc（或任何其他内存分配函数）时返回NULL。这是符合标准的完全可接受的行为。
在堆栈方面，它也不需要提供堆栈。ISO C11中零次提到“堆栈”这个词。
实现需要做的就是成为标准中指定所有事物的正确“虚拟机”。尽管没有堆栈会非常困难，但这并非不可能。作为一个极端情况，没有任何东西说你不能递归地内联每个函数调用。那将使用相当大量的代码和特定于函数的数据空间，但肯定可以做到。
然而，这可能是一件让我转向另一种架构的事情，其中有堆栈（以及堆）。
话虽如此，即使一个架构既不提供堆也不提供堆栈，这两者都可以从基本的内存I / O操作中构建出来。事实上，我作为青少年拥有的最早的计算机之一，搭载了RCA 1802 CPU，它没有专用的堆栈。它甚至没有call或ret指令。

然而，使用其标准调用和返回技术（SCRT），它可以相当不错地处理子例程和堆栈（“不错”这个词的定义因人而异）。有关此美丽之物（或者说是丑陋的怪兽，取决于您的观点）的工作原理以及其他一些不寻常的架构细节，请参见此处。

IBM Z（又称System z、zSeries或者像本周他们所称呼的任何名称）实际上拥有一个堆（某种程度上，您可以从操作系统中分配内存），但没有堆栈。它实际上通过使用此堆内存以及某些寄存器（类似于上面链接中引用的RCA芯片）来实现一个链接列表堆栈，这意味着函数前奏使用STORAGE OBTAIN分配本地函数内存，而函数结尾使用STORAGE RELEASE释放它。

不用说，这会为每个函数的前奏和结尾增加不少额外代码。

9

根据其他答案所述，C11标准并不要求使用堆栈或堆（参见n1570）。但是，在实践中，两者都是有用的。

关于调用堆栈，它非常常见，但可以“避免”：

  • 一些优化编译器可能足够聪明（尤其是在整个程序优化或链接时优化的情况下），可以检测到整个程序不需要任何调用栈的情况（一个简单的例子是没有函数指针和递归的整个程序：在这种情况下，每个“调用帧”都可以在编译时静态分配）。许多优化编译器甚至对未标记为inline的函数进行内联调用（有效地消除了这些调用的调用栈需求）。

  • 许多现代处理器（x86或x86-64、AVR、SPARC、ColdFire即mc68K...）都有一个硬件调用栈（例如某些 "堆栈指针" 寄存器，已知于函数调用）。在那些没有这样的硬件堆栈指针的处理器上（例如IBM Z系列大型机、PowerPC、MIPS、RISC-V，或者也许是ARM），调用约定（或ABI）可能会传统地将一些寄存器指定为堆栈指针的角色。顺便说一下，C甚至可以在随机访问机器上理论上实现（这些机器没有任何寄存器或堆栈指针）。

  • 人们可以想象一个编译器使用延续传递风格来避免调用栈（有效地在堆中或者某些堆中“分配”一些“调用帧”，也许需要一些垃圾收集器的帮助）。Appel的旧书Compiling with Continuations详细解释了这个想法。我不能列出任何使用此方法的C编译器，但标准允许这种方法。如果您编写了从C到SML（或某些Lisp）的编译器，您就可以拥有这样的编译器。

关于 C 堆，malloc 函数可能会失败，这仍然符合标准。我认为这样的 malloc 是无用的，但可能是最快的。此外，C 标准允许独立实现不包含任何 malloc。
如果你想寻找一个几乎与C语言必需的特性相似的功能，我建议调查二进制表示。我倾向于认为，为十进制计算机（如旧版IBM 1620）或三进制计算机（如Setun）实现C11编译器将非常不切实际（但原则上是可能的，因为你可以在三进制或十进制计算机上“模拟”二进制计算机；所有这些都是Turing-complete）。然而，这样的古老计算机（晚1950年代，早1960年代）只能在博物馆中找到，在C语言发明之前就已经消失了。

顺便提一下，在C语言出现几十年前，ALGOL和Lisp（以及IPL-V）的实现中已经存在了调用栈和堆。

1
有趣的研究...太遗憾了，我只能点赞一次，而且似乎每个人都已经离开度周末了（或者可能在观看环法赛的到达） - chqrlie
4
C语言需要一些机制来实现自动存储并跟踪函数调用返回点（正如chqrlie所指出的）。在实践中，这几乎总是使用堆栈。但它并不需要堆。
只有当您使用类似于malloc的库函数时才通常需要堆；而C语言本身则不需要。事实上，堆没有什么神奇之处——您可以在纯C中编写malloc和free。它只有一个大块静态内存，并且有一种算法从该块中分配空间。
你问：“如果CPU不支持堆栈和堆结构怎么办？” 好吧，堆栈和堆只是由内存和指针构建的。我认为您不会找到任何被视为“CPU”的处理器的例子，它没有这种能力。
4
我不太同意：单词“stack”在C标准中甚至都不存在。需要一些机制来实现自动存储并跟踪函数调用返回点，但这不一定是CPU堆栈。 - chqrlie
@chqrlie 这是一个非常有趣的观点。我会编辑我的答案。但我怀疑在实践中所有的C实现都使用堆栈。你知道有没有不使用堆栈的吗？ - James
1
不，我不知道有任何的方法，但是C解释器可以使用双向链表框架。许多处理器没有内置堆栈：例如，许多RISC体系结构没有具有隐式堆栈的“call”/“ret”机制，而是使用链接寄存器，可以通过适当生成的代码以各种方式保存。 - chqrlie
1
IBM System Z使用动态分配来实现自动存储。我知道至少有一个不完全模糊的系统/C实现是这样工作的，但必须谷歌一下它是什么。这让我来到了这个问答页面，特别是Paxdiablo的回答和这个回答稍微夸大了事实，说“总是这样”。 - Peter Cordes
一些8位微处理器没有完整的指针寄存器，例如6502和8080 / Z80。正如在为什么C到Z80编译器会产生糟糕的代码？中讨论的那样，在C实现中支持递归/重入可能是可能的，但非常笨拙。这并不是因为那些系统的编译器老旧，并需要在狭小的系统上运行，限制了它们发现针孔优化的能力，当完整的一般情况慢版本不需要时，但有些事情在这些机器上很难。 - Peter Cordes
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接