无堆栈语言如何工作? [英] How does a stackless language work?

问题描述

我听说过无堆栈语言.但是我不知道如何实现这种语言.有人可以解释吗?

解决方案

我们拥有的现代操作系统(Windows，Linux)以所谓的大堆栈模型"运行.这种模型有时是错误的，并激发了对无堆栈"语言的需求.

大堆栈模型"假设编译后的程序将使用内存指令快速调整包含堆栈指针(和可选堆栈帧指针)的寄存器，以在内存的连续区域中为函数调用分配堆栈帧".这导致快速的函数调用/返回，但代价是堆栈具有较大的连续区域.因为在这些现代OS上运行的所有程序的99.99％都可以在大型堆栈模型下很好地工作，所以编译器，加载程序甚至OS都知道"此堆栈区域.

所有此类应用程序都存在一个常见问题，即我的堆栈应该有多大?" .由于内存便宜，大多数情况是为堆栈预留了一个很大的块(MS默认为1Mb)，并且典型的应用程序调用结构永远无法耗尽它.但是，如果应用程序确实用完了它，则会由于到达堆栈的末尾而死于一个非法的内存引用(对不起，戴夫，我不能那样做").

大多数所谓的无栈"语言并不是真正的无栈.他们只是不使用这些系统提供的连续堆栈.他们要做的是在每个函数调用中从堆中分配一个堆栈框架.每个函数调用的成本有所增加；如果功能通常很复杂，或者语言是解释性的，那么这笔额外的费用就微不足道了. (还可以在程序调用图中确定调用DAG，并分配一个堆段以覆盖整个DAG；这样一来，您可以在调用DAG中获得堆分配和经典大堆栈函数调用的速度). /p>

将堆分配用于堆栈帧有几个原因:

1)如果程序根据要解决的特定问题进行深度递归， 预先预先分配大堆栈"区域非常困难，因为所需的大小未知.可以笨拙地安排函数调用以检查是否还有足够的堆栈，否则，请重新分配更大的块，复制旧堆栈并将所有指针重新调整到堆栈中；太尴尬了，我不知道任何实现. 分配堆栈帧意味着应用程序不必再对它感到抱歉，除非有 几乎没有剩余可分配的内存.

2)程序派生子任务.每个子任务都需要自己的堆栈，因此不能使用提供的一个大堆栈".因此，需要为每个子任务分配堆栈.如果您有成千上万个可能的子任务，那么现在可能需要成千上万个大堆栈"，并且内存需求突然变得可笑.分配堆栈帧可以解决此问题.通常，子任务堆栈"指代父任务以实现词法作用域.作为子任务分叉，将创建一个称为子堆栈"的树，称为仙人掌堆栈".

3)您的语言是连续的.这些要求以某种方式保留当前函数可见的词法范围内的数据，以供以后重用.这可以通过复制父堆栈框架，爬上仙人掌堆栈并继续进行操作来实现.

我实现的 PARLANSE 编程语言执行1)和2).我正在研究3).

I've heard of stackless languages. However I don't have any idea how such a language would be implemented. Can someone explain?

解决方案

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).

这篇关于无堆栈语言如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！