blocks|key|1310761|text|Stackless+Python仍然有一个Python堆栈(尽管它可能具有尾部调用优化和其他调用框架合并技巧)，但它完全脱离了解释器的C堆栈。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1310762|Haskell+(通常实现)没有调用堆栈；计算是基于graph+reduction的。|1310763|entityMap|0|LINK|mutability|MUTABLE|url|http://www.stackless.com/|1|http://en.wikibooks.org/wiki/Haskell/Graph_reduction^0|0|G|0|0|Q|F|1|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]]|C|$]]|$1|F|3|-4|5|6|7|X|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]|N|$5|I|J|K|C|$L|O]]]]

<a href="http://www.stackless.com/" rel="noreferrer">Stackless Python</a> still has a Python stack (though it may have tail call optimization and other call frame merging tricks), but it is completely divorced from the C stack of the interpreter.

Haskell (as commonly implemented) does not have a call stack; evaluation is based on <a href="http://en.wikibooks.org/wiki/Haskell/Graph_reduction" rel="noreferrer">graph reduction</a>.

blocks|key|1310789|text|有一篇很好的关于language+framework+Parrot的文章。Parrot不使用堆栈进行调用，本文将对该技术进行一些说明。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1310790|entityMap|0|LINK|mutability|MUTABLE|url|https://web.archive.org/web/20100706035639/http://www.linux-mag.com/cache/7373/1.html^0|8|P|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

There is a nice article about the <a href="https://web.archive.org/web/20100706035639/http://www.linux-mag.com/cache/7373/1.html" rel="nofollow noreferrer">language framework Parrot</a>. Parrot does not use the stack for calling and this article explains the technique a bit.

blocks|key|1310704|text|在我或多或少熟悉的无堆栈环境中(图灵机、汇编和Brainfuck)，实现自己的堆栈是很常见的。在语言中内置堆栈并不是最基本的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1310705|在其中最实用的汇编中，您只需选择可用的内存区域，将堆栈寄存器设置为指向底部，然后递增或递减以实现您的推送和弹出。|1310706|编辑:我知道有些架构有专门的堆栈，但它们不是必需的。|1310707|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

In the stackless environments I'm more or less familiar with (Turing machine, assembly, and Brainfuck), it's common to implement your own stack. There is nothing fundamental about having a stack built into the language.

In the most practical of these, assembly, you just choose a region of memory available to you, set the stack register to point to the bottom, then increment or decrement to implement your pushes and pops. 

EDIT: I know some architectures have dedicated stacks, but they aren't necessary.

blocks|key|1525937|text|我记得FORTRAN标准和COBOL不支持递归调用，因此不需要堆栈。事实上，我记得CDC6000系列机器的实现没有堆栈，如果你试图递归调用子例程，FORTRAN会做一些奇怪的事情。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1525938|作为记录，CDC+6000系列指令集使用RJ指令调用子例程，而不是调用堆栈。这会将当前PC值保存在呼叫目标位置，然后转移到后面的位置。最后，子例程将执行到调用目标位置的间接跳转。重新加载保存的PC，有效地返回给调用者。|1525939|显然，这不适用于递归调用。(我的记忆是，如果您确实尝试递归，CDC+FORTRAN+IV编译器将生成损坏的代码...)|1525940|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Call me ancient, but I can remember when the FORTRAN standards and COBOL did not support recursive calls, and therefore didn't require a stack. Indeed, I recall the implementations for CDC 6000 series machines where there wasn't a stack, and FORTRAN would do strange things if you tried to call a subroutine recursively.

For the record, instead of a call-stack, the CDC 6000 series instruction set used the RJ instruction to call a subroutine. This saved the current PC value at the call target location and then branches to the location following it. At the end, a subroutine would perform an indirect jump to the call target location. That reloaded saved PC, effectively returning to the caller.

Obviously, that does not work with recursive calls. (And my recollection is that the CDC FORTRAN IV compiler would generate broken code if you did attempt recursion ...)

blocks|key|1525887|text|本文对延续的描述很容易理解：http://www.defmacro.org/ramblings/fp.html|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1525888|延续是可以在基于堆栈的语言中传递到函数中的东西，但也可以由语言自己的语义使用，使其“无堆栈”。当然，堆栈仍然存在，但正如Ira+Baxter所描述的，它不是一个大的连续部分。|1525889|entityMap|0|LINK|mutability|MUTABLE|url|http://www.defmacro.org/ramblings/fp.html^0|E|15|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

There is an easy to understand description of continuations on this article: <a href="http://www.defmacro.org/ramblings/fp.html" rel="nofollow noreferrer">http://www.defmacro.org/ramblings/fp.html</a>

Continuations are something you can pass into a function in a stack-based language, but which can also be used by a language's own semantics to make it "stackless". Of course the stack is still there, but as Ira Baxter described, it's not one big contiguous segment.

blocks|key|1526050|text|假设你想实现stackless+C，首先要意识到的是，这不需要堆栈：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1526051|a+==+b|code-block|syntax|javascript|1526052|但是，这是真的吗？|1526053|isequal(a,+b)+{+return+a+==+b;+}|1526054|不是的。因为智能编译器将内联对isequal的调用，将它们转换为a+==+b。那么，为什么不直接内联所有内容呢？当然，你会生成更多的代码，但如果摆脱堆栈对你来说是值得的，那么这是很容易的，只需要很小的权衡。|offset|length|style|CODE|1526055|那么递归呢？没问题。像这样的尾递归函数：|1526056|bang(x)+{+return+x+==+1+?+1+:+x+*+bang(x-1);+}|1526057|仍然可以是内联的，因为它实际上只是一个伪装的for循环：|1526058|bang(x)+{
++++for(int+i+=+x;+i+>=1;+i--)+x+*=+x-1;
++++return+x;
}|1526059|从理论上讲，一个真正聪明的编译器可以帮你解决这个问题。但一个不太聪明的人仍然可以把它扁平化为goto：|1526060|ax+=+x;
NOTDONE:
if(ax+>+1)+{
++++x+=+x*(--ax);
++++goto+NOTDONE;
}|1526061|有一种情况下，你必须做一个小的权衡。这不能被内联：|1526062|fib(n)+{+return+n+<=+2+?+n+:+fib(n-1)+%2B+fib(n-2);+}|1526063|Stackless+C根本不能做到这一点。你放弃了很多吗？不怎么有意思。这也是普通的C不能很好地完成的事情。如果你不相信我，就打电话给fib(1000)，看看你珍贵的电脑发生了什么事。|1526064|entityMap^0|0|0|0|0|F|7|W|6|0|0|0|0|0|0|0|0|0|1V|9|0^^$0|@$1|2|3|4|5|6|7|1A|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1B|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|1C|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|1D|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|1E|8|@$M|1F|N|1G|O|P]|$M|1H|N|1I|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1J|8|@]|9|@]|A|$]]|$1|S|3|T|5|D|7|1K|8|@]|9|@]|A|$E|F]]|$1|U|3|V|5|6|7|1L|8|@]|9|@]|A|$]]|$1|W|3|X|5|D|7|1M|8|@]|9|@]|A|$E|F]]|$1|Y|3|Z|5|6|7|1N|8|@]|9|@]|A|$]]|$1|10|3|11|5|D|7|1O|8|@]|9|@]|A|$E|F]]|$1|12|3|13|5|6|7|1P|8|@]|9|@]|A|$]]|$1|14|3|15|5|D|7|1Q|8|@]|9|@]|A|$E|F]]|$1|16|3|17|5|6|7|1R|8|@$M|1S|N|1T|O|P]]|9|@]|A|$]]|$1|18|3|-4|5|6|7|1U|8|@]|9|@]|A|$]]]|19|$]]

Say you wanted to implement stackless C. The first thing to realize is that this doesn't need a stack:

<pre><code>a == b
</code></pre>

But, does this?

<pre><code>isequal(a, b) { return a == b; }
</code></pre>

No. Because a smart compiler will inline calls to <code>isequal</code>, turning them into <code>a == b</code>. So, why not just inline everything? Sure, you will generate more code but if getting rid of the stack is worth it to you then this is easy with a small tradeoff.

What about recursion? No problem. A tail-recursive function like:

<pre><code>bang(x) { return x == 1 ? 1 : x * bang(x-1); }
</code></pre>

Can still be inlined, because really it's just a for loop in disguise:

<pre><code>bang(x) {
 for(int i = x; i &gt;=1; i--) x *= x-1;
 return x;
}
</code></pre>

In theory a really smart compiler could figure that out for you. But a less-smart one could still flatten it as a goto:

<pre><code>ax = x;
NOTDONE:
if(ax &gt; 1) {
 x = x*(--ax);
 goto NOTDONE;
}
</code></pre>

There is one case where you have to make a small trade off. This can't be inlined:

<pre><code>fib(n) { return n &lt;= 2 ? n : fib(n-1) + fib(n-2); }
</code></pre>

Stackless C simply cannot do this. Are you giving up a lot? Not really. This is something normal C can't do well very either. If you don't believe me just call <code>fib(1000)</code> and see what happens to your precious computer.

blocks|key|1525987|text|如果我错了，请随时纠正我，但我认为在堆上为每个函数调用帧分配内存将导致极端的内存颠簸。毕竟，操作系统必须管理这个内存。我认为避免这种内存颠簸的方法应该是对调用帧进行缓存。因此，如果你需要一个缓存，我们不妨在内存中将其设置为连续的，并将其称为堆栈。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1525988|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Please feel free to correct me if I'm wrong, but I would think that allocating memory on the heap for each function call frame would cause extreme memory thrashing. The operating system does after all have to manage this memory. I would think that the way to avoid this memory thrashing would be a cache for call frames. So if you need a cache anyway, we might as well make it contigous in memory and call it a stack.

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

How does a stackless language work?

编译器

解释器

Python

我听说过无栈语言。然而，我不知道这样的语言是如何实现的。有人能解释一下吗？

问无栈语言是如何工作的？
EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问无栈语言是如何工作的？EN

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问无栈语言是如何工作的？
EN