私の個人的な経験から導き出された結論を要約することができますが、以下の説明が完全に正しい説明ではない可能性があるという免責事項があります. その答えは、Mathematica のコール スタックと従来のコール スタックとの違いにあるようです。これは、Mathematica のパターン定義関数が実際には規則であることに由来します。したがって、実際の関数呼び出しはありません。Mathematica は別の理由でスタックを必要とします.通常の評価は式ツリーの最下部から行われるため,(サブ)式のより深い部分がルール適用の結果として置き換えられる場合に備えて,中間式を保持しなければなりません.式は下から成長します）。これは特に、他の言語で非末尾再帰関数と呼ばれるものを定義するルールの場合です。では、もう一度、
これは、ルール適用の結果として、(サブ) 式を完全に書き換えることができる場合、式ブランチを式スタックに保持する必要がないことを意味します。これはおそらく、Mathematica で末尾呼び出しの最適化と呼ばれるものです。これが、このような場合に再帰ではなく反復を使用する理由です (これは、ルールの適用と関数呼び出しの違いの非常に良い例の 1 つです)。のようなルール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]]}}}}
ここからわかることは、式のスタックはfand fff(これが一般的なメカニズムであることを示すために使用されたもので、ce[]任意のヘッドがあるだけです) については蓄積されますが、 については蓄積されないffということです。の定義ffは試行されたが一致しなかったルールであり、2 番目の定義は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@@{}]}}}}}}
何が起こるかというと、結果がリストの奥深くに蓄積されていくということです。解決策は、結果の式の深さを増やさないことです。これを達成する 1 つの方法は、selrecBad が 1 つの追加パラメーターを受け入れるようにすることです。これは、蓄積された結果の (リンクされた) リストです。
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]]
それに応じて main 関数を変更します。
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}]]}}}
つまり、このバージョンでは、結果が別のリストに保持されるため、中間式の深さは蓄積されません。