Ответ 1
Я могу обобщить выводы, которые я привел к моему личному опыту, с отказом от ответственности, что последующее может быть не совсем правильным объяснением. Кажется, что anwer заключается в различиях между стеком вызовов Mathematica и традиционными столами вызовов, который исходит из определенных Mathematica функций, которые действительно являются правилами. Таким образом, нет реальных вызовов функций. Mathematica нуждается в стеке по другой причине: поскольку нормальная оценка происходит из нижней части дерева выражений, она должна сохранять промежуточные выражения в случае, когда более глубокие и более глубокие части (под) выражений заменяются в результате применения правила (некоторые части выражение вырастает снизу). Это относится, в частности, к правилам, определяющим то, что мы будем называть недворекурсивными функциями на других языках. Итак, еще раз, стек в Mathematica представляет собой стек промежуточных выражений, а не вызовы функций.
Это означает, что если в результате применения правила выражение (sub) может быть переписано полностью, ветвь выражения не должна храниться в стеке выражений. Вероятно, это то, что называется "оптимизацией хвостового вызова" в 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,{}}}}}==={},{},[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 принять один дополнительный параметр, который является (связанным) списком накопленных результатов:
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}]]}}}
то есть эта версия не накапливает глубину промежуточного выражения, так как результаты хранятся в отдельном списке.