私は私の個人的な経験によって導かれた結論を要約することができますが、それに続くのはまったく正しい説明ではないという免責事項があります。 Mathematicaの呼び出しスタックと従来の呼び出しスタックの違いは、Mathematicaのパターン定義関数が本当にルールになっていることにあります。したがって、実際の関数呼び出しはありません。 Mathematicaは別の理由からスタックを必要とします。通常の評価は式ツリーの一番下から行われるため、（サブ）式のより深くて深い部分がルール適用の結果として置き換えられる場合に中間式を保持する必要があります下から発現が増える）。これは、特に、他の言語で非末尾再帰関数と呼ぶものを定義する規則の場合です。だから、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の最初の定義は試行されていますが一致しないルールであり、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]]]
私はブロックとselrecBadを使用する理由は、それが簡単にトレースを使用するようにすることです。さて、これは私のマシン上でスタックを吹く：
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,{}}}}}==={},{},[email protected]@{2,{3,{4,
{5,{}}}}}]},{selrecBad[2,{3,{4,{5,{}}}}],If[{3,{4,{5,{}}}}==={},{},[email protected]@{3,{4,{5,
{}}}}],selrecBad[3,{4,{5,{}}}],{3,If[{4,{5,{}}}==={},{},[email protected]@{4,{5,{}}}]},{selrecBad[4,
{5,{}}],If[{5,{}}==={},{},[email protected]@{5,{}}],selrecBad[5,{}],{5,If[{}==={},{},[email protected]@{}]}}}}}}
何が起こることは、結果がリストに深く深く蓄積してしまうことです。解決策は、結果の式の深さを成長しないことであり、それを達成するための一つの方法は、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]]
を、メインを変更しますそれに応じて機能：
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を、修正しなければならなかったことに注意してください）。トレースを使用する理由を明らかにすると：
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}]]}}}
ある結果を別のリストに保持されているので、このバージョンは、中間表現の深さを蓄積しません。
+1非常に良い分析。私は、CompoundExpressionが最適化の候補であることに同意しますが、サブ表現がCompoundExpressionに定義を追加し、セマンティクス（最適化が妨害される）を変更する状況を考案できました。 「挑戦」を重視する - 実際にはそれが問題になるかどうかはわかりません。 – WReach
優秀な説明！ '$ RecursionLimit'と' $ IterationLimit'の違いが明らかになりました。そして、「スタック」とは何かがはっきりと分かりました。 –