因此，在一般情况下，程序同时使用堆栈中的内存（自动管理）和堆（垃圾收集或手动管理）。
哪类程序可以编译为仅以类似堆栈的方式使用内存而没有堆分配？它仍然是图灵完备的，还有其他一些权衡（例如代码爆炸）还是一个较弱的语言类？
问问题
131 次
1 回答
4
如果堆栈是指只能在顶部访问的抽象数据类型，那么您正在查看下推自动机。确定性 PDA 只能处理确定性上下文无关语言，非确定性 PDA 都是上下文无关语言，因此它们不是图灵完备的。
然而，真正的计算机架构中的“堆栈”并非如此。分配和释放内存以 LIFO 方式发生，但所有分配的内存都是随机访问的，因此这种无界堆栈将与任何RAM一样具有图灵完备性。当然，任何实际操作系统中的堆栈都是固定大小的，但不受字长和虚拟内存的限制，可以任意设置大，所以如果你调用具有堆分配图灵完备的计算机，你不应该有麻烦称这台机器图灵完成。
事实上，一些区域系统非常接近这种方法。区域与概念级别的堆栈分配不同，但是当区域嵌套时（letregion ρ in ...），它们有效地遵循堆栈规则。（纯）区域系统的常见问题是内部碎片：只有当区域中的所有对象都死了时才能释放区域，这导致某些程序的内存需求大大增加。所以没有代码爆炸，但内存爆炸。
最后，即使该语言只提供了一个堆栈，获得一个“堆”就像从堆栈中分配一个大字节数组并在其上实现您自己的、更灵活的内存管理一样简单。毕竟，这就是所有其他堆所做的事情。
于 2015-03-09T11:13:50.383 回答