所以在一般情况下，程序同时使用堆栈(自动管理)和堆(垃圾收集或手动管理)中的内存。
可以编译为仅以类似堆栈的方式使用内存而不进行堆分配的程序类别是什么？它是否仍然具有其他一些权衡(例如代码爆炸)的图灵完备，或者它是一个较弱的语言类？
最佳答案
如果堆栈指的是只能在顶部访问的抽象数据类型，那么您正在查看 pushdown automata .确定性PDAs只能处理确定性上下文无关语言，非确定性PDAs所有上下文无关语言，所以它们不是图灵完备的。
然而，真正的计算机架构中的“栈”并不是这样的。
分配和释放内存以 LIFO 方式发生，但所有分配的内存都是随机访问的，因此这种无界堆栈将与任何 RAM 一样是图灵完备的。 .当然，任何真实操作系统中的栈都是固定大小的，但是尽管有字大小和虚拟内存的限制，它可以设置任意大，所以如果你调用堆分配图灵完备的计算机，你应该没有麻烦调用这台机器图灵完成。
其实有些region systems非常接近这种方法。区域在概念级别上与堆栈分配不同，但是当区域嵌套( letregion ρ in ... )时，它们有效地遵守堆栈规则。 (纯)区域系统的常见问题是内部碎片:一个区域只有在其中的所有对象都死了时才能被释放，这导致某些程序的内存需求大大增加。所以没有代码爆炸，但内存爆炸。
最后，即使该语言只提供一个堆栈，获取“堆”也很简单，只需从堆栈中分配一个大字节数组并在其上实现您自己的、更灵活的内存管理。毕竟，这就是所有其他堆所做的。
关于compiler-construction - 可编译为无堆运行时的语言类，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28935020/