MATLAB是否执行尾部呼叫优化？ [英] Does MATLAB perform tail call optimization?

问题描述

最近我学习了Haskell，并试图在可能的情况下将纯粹的功能风格转换为我的其他代码。其中一个重要方面是将所有变量视为不可变的，即常量。为了做到这一点，许多使用循环必须执行的计算必须使用递归来执行，这通常会由于为每个函数调用分配一个新的栈帧而导致内存损失。但是，在尾部调用（即被调用函数的返回值立即返回给被调用者的调用者）的特殊情况下，该惩罚可以被称为尾部调用优化的过程绕过（在一种方法中，这可以通过基本上在正确设置堆栈后用jmp替换一个调用）。如果我定义了一个简单的尾递归函数，那么MATLAB会默认执行TCO，或者有办法告诉它吗？

解决方案

函数：

 函数tailtest（n）
 if n == 0;功能memstats;返回;结束
 tailtest（n-1）; 
 end 
  

并且调用它以便它可以递归得很深：

  set（0，'RecursionLimit'，10000）; 
 tailtest（1000）; 
  

然后它看起来好像堆栈帧正在吃掉很多内存。然而，如果我让它递归得更深：

  set（0，'RecursionLimit'，10000）; 
 tailtest（5000）; 
  

然后（在我的机器上，今天）MATLAB简单崩溃：进程无故死亡。

我不认为这与MATLAB做任何TCO是一致的;只有在一个地方，一个函数尾随自己调用的情况下，除了一个参数之外没有局部变量，就像任何人所希望的那样简单。

所以：不，看来MATLAB至少在默认情况下根本不会执行TCO。我还没有（到目前为止）寻找可能启用它的选项。如果有任何问题，我会感到惊讶。

在我们没有把堆栈吹出来的情况下，递归花费多少钱？ Bill Cheatham的回答见我的评论：看起来时间开销不平凡但并非疯狂。

...除了Bill Cheatham在我离开评论后删除了他的答案。好。所以，我采用了Fibonacci函数的简单迭代实现和一个简单的尾递归函数，在两者中进行基本相同的计算，并在 fib（60） 。递归实现比迭代实现花费的时间要长2.5倍。当然，对于做更多工作的函数来说，相对开销要小于每次迭代的一次加法和一次减法。

（我同意delnan的观点：高度递归的代码在Haskell中感觉自然的那种类型通常在MATLAB中可能是单一的。）

I've recently learned Haskell, and am trying to carry the pure functional style over to my other code when possible. An important aspect of this is treating all variables as immutable, i.e. constants. In order to do so, many computations that would be implemented using loops in an imperative style have to be performed using recursion, which typically incurs a memory penalty due to the allocation a new stack frame for each function call. In the special case of a tail call (where the return value of a called function is immediately returned to the callee's caller), however, this penalty can be bypassed by a process called tail call optimization (in one method, this can be done by essentially replacing a call with a jmp after setting up the stack properly). Does MATLAB perform TCO by default, or is there a way to tell it to?

解决方案

If I define a simple tail-recursive function:

function tailtest(n)
  if n==0; feature memstats; return; end
  tailtest(n-1);
end

and call it so that it will recurse quite deeply:

set(0,'RecursionLimit',10000);
tailtest(1000);

then it doesn't look as if stack frames are eating a lot of memory. However, if I make it recurse much deeper:

set(0,'RecursionLimit',10000);
tailtest(5000);

then (on my machine, today) MATLAB simply crashes: the process unceremoniously dies.

I don't think this is consistent with MATLAB doing any TCO; the case where a function tail-calls itself, only in one place, with no local variables other than a single argument, is just about as simple as anyone could hope for.

So: No, it appears that MATLAB does not do TCO at all, at least by default. I haven't (so far) looked for options that might enable it. I'd be surprised if there were any.

In cases where we don't blow out the stack, how much does recursion cost? See my comment to Bill Cheatham's answer: it looks like the time overhead is nontrivial but not insane.

... Except that Bill Cheatham deleted his answer after I left that comment. OK. So, I took a simple iterative implementation of the Fibonacci function and a simple tail-recursive one, doing essentially the same computation in both, and timed them both on fib(60). The recursive implementation took about 2.5 times longer to run than the iterative one. Of course the relative overhead will be smaller for functions that do more work than one addition and one subtraction per iteration.

(I also agree with delnan's sentiment: highly-recursive code of the sort that feels natural in Haskell is typically likely to be unidiomatic in MATLAB.)

这篇关于MATLAB是否执行尾部呼叫优化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！