Я могу суммировать выводы, к которым меня привел мой личный опыт, с оговоркой, что последующее может быть не совсем правильным объяснением.Ответ, кажется, заключается в различиях между стеком вызовов 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правило опробовано, но не соответствует, и второе определение полностью переписывает 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, что является хорошим признаком).И использование трассировки раскрывает причину:
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}]]}}}
, то есть эта версия не накапливает глубину промежуточного выражения, поскольку результаты хранятся в отдельном списке.