如何做一个无堆栈语言工作？如何做一个无堆栈语言工作？(How does a stackless la

我听说stackless的语言。 但是我没有任何想法，这样的语言将如何执行。 有人能解释一下吗？

Answer 1:

The modern operating systems we have (Windows, Linux) operate with what I call the "big stack model". And that model is wrong, sometimes, and motivates the need for "stackless" languages.

The "big stack model" assumes that a compiled program will allocate "stack frames" for function calls in a contiguous region of memory, using machine instructions to adjust registers containing the stack pointer (and optional stack frame pointer) very rapidly. This leads to fast function call/return, at the price of having a large, contiguous region for the stack. Because 99.99% of all programs run under these modern OSes work well with the big stack model, the compilers, loaders, and even the OS "know" about this stack area.

One common problem all such applications have is, "how big should my stack be?". With memory being dirt cheap, mostly what happens is that a large chunk is set aside for the stack (MS defaults to 1Mb), and typical application call structure never gets anywhere near to using it up. But if an application does use it all up, it dies with an illegal memory reference ("I'm sorry Dave, I can't do that"), by virtue of reaching off the end of its stack.

Most so-called called "stackless" languages aren't really stackless. They just don't use the contiguous stack provided by these systems. What they do instead is allocate a stack frame from the heap on each function call. The cost per function call goes up somewhat; if functions are typically complex, or the language is interpretive, this additional cost is insignificant. (One can also determine call DAGs in the program call graph and allocate a heap segment to cover the entire DAG; this way you get both heap allocation and the speed of classic big-stack function calls for all calls inside the call DAG).

There are several reasons for using heap allocation for stack frames:

1) If the program does deep recursion dependent on the specific problem it is solving, it is very hard to preallocate a "big stack" area in advance because the needed size isn't known. One can awkwardly arrange function calls to check to see if there's enough stack left, and if not, reallocate a bigger chunk, copy the old stack and readjust all the pointers into the stack; that's so awkward that I don't know of any implementations. Allocating stack frames means the application never has to say its sorry until there's literally no allocatable memory left.

2) The program forks subtasks. Each subtask requires its own stack, and therefore can't use the one "big stack" provided. So, one needs to allocate stacks for each subtask. If you have thousands of possible subtasks, you might now need thousands of "big stacks", and the memory demand suddenly gets ridiculous. Allocating stack frames solves this problem. Often the subtask "stacks" refer back to the parent tasks to implement lexical scoping; as subtasks fork, a tree of "substacks" is created called a "cactus stack".

3) Your language has continuations. These require that the data in lexical scope visible to the current function somehow be preserved for later reuse. This can be implemented by copying parent stack frames, climbing up the cactus stack, and proceeding.

The PARLANSE programming langauge I implemented does 1) and 2). I'm working on 3).

Answer 2:

无堆栈的Python仍然具有一个Python堆（尽管它可以具有尾调用优化的和其他呼叫帧合并花样），但它完全从解释器的C堆栈离婚。

哈斯克尔（如通常实现的）没有一个调用堆栈; 评价是基于图规约 。

Answer 3:

有一个关于在语言框架鹦鹉一个很好的文章http://www.linux-mag.com/cache/7373/1.html 。 鹦鹉不使用堆栈调用和本文介绍的技术位。

Answer 4:

在无堆叠的环境中，我与（图灵机，组装和Brainfuck）或多或少熟悉，它的共同实现自己的堆栈。 没有任何关于其语言内置的堆栈的基础。

在最实用的这些，装配，你只要选择的可用存储空间的区域给你，设置堆栈寄存器指向下方，然后递增或递减来实现你的push和pop。

编辑：我知道一些架构有专门的堆栈，但他们是没有必要的。

Answer 5:

有一个简单的了解这篇文章的延续的描述： http://www.defmacro.org/ramblings/fp.html

延续的东西，你可以进入一个函数在一个基于堆栈的语言，但它也可以通过语言的自己的语义来使其“无堆栈”。 当然，堆栈仍然存在，但艾拉巴克斯特描述，它不是一个大的连续段。

Answer 6:

假设你想实现的无堆栈下实现的第一件事是，这并不需要一个堆栈：

a == b

但是，做到这一点？

isequal(a, b) { return a == b; }

不是。因为一个聪明的编译器将内联呼吁isequal ，使它们成为a == b 。 那么，为什么不只是内联的一切吗？ 当然，你会产生更多的代码，但如果摆脱堆栈是值得你那么这很容易用一个小的权衡。

怎么样递归？ 没问题。 甲尾递归功能，如：

bang(x) { return x == 1 ? 1 : x * bang(x-1); }

可还是被内联，因为它实际上只是一个为变相循环：

bang(x) {
    for(int i = x; i >=1; i--) x *= x-1;
    return x;
}

从理论上讲一个真正聪明的编译器可以明白这一点你。 但是，聪明的小一仍然可以将其压平作为转到：

ax = x;
NOTDONE:
if(ax > 1) {
    x = x*(--ax);
    goto NOTDONE;
}

还有，你必须做一个小的权衡一个案例。 这不能被内联：

fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }

无堆栈ç根本无法做到这一点。 你放弃了很多？ 并不是的。 这是正常的事情C不能做的很好很无论是。 如果你不相信我只是叫fib(1000)并看看会发生什么你那珍贵的计算机。

Answer 7:

叫我古，但我还记得当FORTRAN标准和COBOL不支持递归调用，因此并不需要一个堆栈。 事实上，我记得对于其中没有一个堆栈CDC 6000系列机器的实现，如果你试图递归调用子程序FORTRAN会做奇怪的事情。

为了记录在案，而不是调用堆栈，疾病预防控制中心6000系列指令集使用RJ指令调用的子程序。 这在呼叫目标位置之后它保存在当前的PC值，然后跳转到该位置。 最后，子程序将执行间接跳转到呼叫目标位置。 这重装上阵保存的PC，有效地返回给调用者。

显然，这不递归调用工作。 （和我的回忆是，如果你没有尝试递归CDC FORTRAN编译器IV将产生断码...）

Answer 8:

请随时纠正我，如果我错了，但我认为在堆中的每个函数调用帧分配内存会导致极端的内存抖动。 操作系统也毕竟要管理这个内存。 我认为要避免这种存储器中颠簸的方式将是调用帧缓存。 所以，如果你需要一个高速缓存，无论如何，我们不妨让它contigous在内存中，并称之为一个堆栈。

文章来源: How does a stackless language work?