Mathematica中的尾调用优化？

Question

在制定另一个SO问题的答案时,我在Mathematica中遇到了一些关于尾递归的奇怪行为.

在数学文档暗示,尾调用优化的可能被执行.但我自己的实验给出了相互矛盾的结果.对比,例如,以下两个表达式.第一个崩溃7.0.1内核,可能是由于堆栈耗尽:

(* warning: crashes the kernel! *)
Module[{f, n = 0},
  f[x_] := (n += 1; f[x + 1]);
  TimeConstrained[Block[{$RecursionLimit = Infinity}, f[0]], 300, n]
]

第二个运行完成,似乎利用尾调用优化来返回有意义的结果:

Module[{f, n = 0},
  f[x_] := Null /; (n += 1; False);
  f[x_] := f[x + 1];
  TimeConstrained[Block[{$IterationLimit = Infinity}, f[0]], 300, n]
]

两个表达式都定义了尾递归函数f.在第一个函数的情况下,Mathematica显然认为复合语句的存在足以击败尾调用优化的任何机会.还要注意,第一个表达式由$RecursionLimit第二个表达式控制,第二个表达式由$IterationLimitMathematica以不同方式处理这两个表达式.(注意:上面提到的SO答案有一个较少设法的功能,成功利用尾部调用优化).

所以,问题是:有没有人知道Mathematica对递归函数进行尾调用优化的情况？在Mathematica文档或其他WRI材料中提及最终陈述将是理想的.投机也很受欢迎.

Answer 1

我可以总结一下我个人经历所带来的结论,并且免责声明后面的内容可能不是完全正确的解释.anwer似乎存在于Mathematica调用堆栈和传统调用堆栈之间的差异,传统调用堆栈源于Mathematica模式定义的函数,实际上是规则.所以,没有真正的函数调用.Mathematica需要一个堆栈的原因不同:因为正常的评估是从表达式树的底部发生的,所以它必须保留中间表达式,以防(sub)表达式的更深和更深的部分因规则应用而被替换(某些部分)表达从底部增长).特别是对于定义我们在其他语言中称为非尾递归函数的规则的情况就是这种情况.所以,再一次,Mathematica中的堆栈是一堆中间表达式,而不是函数调用.

这意味着,如果作为规则应用的结果,(子)表达式可以完整地重写,则表达式分支不需要保留在表达式堆栈上.这可能是Mathematica中所谓的尾调用优化 - 这就是为什么在这种情况下我们有迭代而不是递归(这是规则应用程序和函数调用之间差异的一个非常好的例子).规则就像f[x_]:=f[x+1]这种类型.但是,如果某个子表达式被重写,产生更多的表达式结构,则表达式必须存储在堆栈中.规则f[x_ /; x < 5] := (n += 1; f[x + 1])是这样的类型,直到我们还记得,这是一个有点隐藏的()立场CompoundExpression[].示意图这里发生的是f[1] -> CompoundExpression[n+=1, f[2]] -> CompoundExpression[n+=1,CompoundExpression[n+=1,f[3]]]->etc.即使每次调用f都是最后一次,它也会在完全CompoundExpression[]执行之前发生,所以这仍然必须保留在表达式堆栈上.有人可能会争辩说,这是一个可以进行优化的地方,为CompoundExpression做一个例外,但这可能不容易实现.

现在,为了说明我上面示意性描述的堆栈累积过程,让我们限制递归调用的数量:

Clear[n, f, ff, fff];
n = 0;
f[x_ /; x < 5] := (n += 1; f[x + 1]);

ff[x_] := Null /; (n += 1; False);
ff[x_ /; x < 5] := ff[x + 1];

fff[x_ /; x < 5] := ce[n += 1, fff[x + 1]];

跟踪评估:

In[57]:= Trace[f[1],f]
Out[57]= {f[1],n+=1;f[1+1],{f[2],n+=1;f[2+1],{f[3],n+=1;f[3+1],{f[4],n+=1;f[4+1]}}}}

In[58]:= Trace[ff[1],ff]
Out[58]= {ff[1],ff[1+1],ff[2],ff[2+1],ff[3],ff[3+1],ff[4],ff[4+1],ff[5]}

In[59]:= Trace[fff[1],fff]
Out[59]= {fff[1],ce[n+=1,fff[1+1]],{fff[2],ce[n+=1,fff[2+1]],{fff[3],ce[n+=1,fff[3+1]],   
{fff[4],ce[n+=1,fff[4+1]]}}}}

你可以从中看到的是表达式堆栈为f和积累fff(后者用于表明这是一个通用的机制,ce[]只有一些任意的头),但不是ff因为,为了模式匹配的目的,第一个定义ff是一个尝试但不匹配的规则,第二个定义完全重写ff[arg_],并且不会生成需要进一步重写的更深层子部分.所以,底线似乎是你应该分析你的函数,看它的递归调用是否会从底部增长评估表达式.如果是,就Mathematica而言,它不是尾递归的.

如果不显示如何手动执行尾调用优化,我的答案就不会完整.作为示例,让我们考虑Select的递归实现.我们将使用Mathematica链表来使其合理有效而不是玩具.下面是非尾递归实现的代码:

Clear[toLinkedList, test, selrecBad, sel, selrec, selTR]
toLinkedList[x_List] := Fold[{#2, #1} &, {}, Reverse[x]];
selrecBad[fst_?test, rest_List] := {fst,If[rest === {}, {}, selrecBad @@ rest]};
selrecBad[fst_, rest_List] := If[rest === {}, {}, selrecBad @@ rest];
sel[x_List, testF_] := Block[{test = testF}, Flatten[selrecBad @@ toLinkedList[x]]]

我使用Block和selrecBad的原因是为了更容易使用Trace.现在,这会炸掉我机器上的堆栈:

Block[{$RecursionLimit = Infinity}, sel[Range[300000], EvenQ]] // Short // Timing

您可以跟踪小列表以查看原因:

In[7]:= Trace[sel[Range[5],OddQ],selrecBad]

Out[7]= {{{selrecBad[1,{2,{3,{4,{5,{}}}}}],{1,If[{2,{3,{4,{5,{}}}}}==={},{},selrecBad@@{2,{3,{4, 
{5,{}}}}}]},{selrecBad[2,{3,{4,{5,{}}}}],If[{3,{4,{5,{}}}}==={},{},selrecBad@@{3,{4,{5, 
{}}}}],selrecBad[3,{4,{5,{}}}],{3,If[{4,{5,{}}}==={},{},selrecBad@@{4,{5,{}}}]},{selrecBad[4,
{5,{}}],If[{5,{}}==={},{},selrecBad@@{5,{}}],selrecBad[5,{}],{5,If[{}==={},{},selrecBad@@{}]}}}}}}

结果是,结果在列表中越来越深入.解决方案是不增加结果表达式的深度,实现这一目的的一种方法是使selrecBad接受一个额外的参数,即累积结果的(链接)列表:

selrec[{fst_?test, rest_List}, accum_List] := 
    If[rest === {}, {accum, fst}, selrec[rest, {accum, fst}]];
selrec[{fst_, rest_List}, accum_List] := 
    If[rest === {}, accum, selrec[rest, accum]]

并相应地修改主要功能:

selTR[x_List, testF_] := Block[{test = testF}, Flatten[selrec[toLinkedList[x], {}]]]

这将通过我们的功率测试就好了:

In[14]:= Block[{$IterationLimit= Infinity},selTR[Range[300000],EvenQ]]//Short//Timing

Out[14]= {0.813,{2,4,6,8,10,12,14,16,18,20,
<<149981>>,299984,299986,299988,299990,299992,299994,299996,299998,300000}}

(注意,这里我们必须修改$ IterationLimit,这是一个好兆头).并使用Trace揭示了原因:

In[15]:= Trace[selTR[Range[5],OddQ],selrec]

Out[15]= {{{selrec[{1,{2,{3,{4,{5,{}}}}}},{}],If[{2,{3,{4,{5,{}}}}}==={},{{},1},selrec[{2,{3,{4, 
{5,{}}}}},{{},1}]],selrec[{2,{3,{4,{5,{}}}}},{{},1}],If[{3,{4,{5,{}}}}==={},{{},1},selrec[{3, 
{4,{5,{}}}},{{},1}]],selrec[{3,{4,{5,{}}}},{{},1}],If[{4,{5,{}}}==={},{{{},1},3},selrec[{4, 
{5,{}}},{{{},1},3}]],selrec[{4,{5,{}}},{{{},1},3}],If[{5,{}}==={},{{{},1},3},selrec[{5, 
{}},{{{},1},3}]],selrec[{5,{}},{{{},1},3}],If[{}==={},{{{{},1},3},5},selrec[{},{{{{},1},3},5}]]}}}

也就是说,此版本不会累积中间表达式的深度,因为结果保存在单独的列表中.