Оптимизация вызовов в Mathematica?

Question

При формулировании answer to another SO question я столкнулся с каким-то странным поведением относительно рекурсии хвоста в Mathematica.

Mathematica documentation намекает, что tail call optimization может быть выполнен. Но мои собственные эксперименты дают противоречивые результаты. Контраст, например, следующие два выражения. Первый выходит из строя 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, а второе - $IterationLimit - признак того, что Mathematica обрабатывает два выражения по-разному. (Примечание: ответ SO, на который ссылается выше, имеет менее надуманную функцию, которая успешно использует оптимизацию хвостового вызова).

Итак, вопрос: Кто-нибудь знает обстоятельства, при которых Mathematica выполняет оптимизацию хвостовых вызовов рекурсивных функций? Идея была бы ссылкой на окончательное утверждение в документации Mathematica или другом материале WRI. Спекуляция также приветствуется.

Answer 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]]] 

Причина я использую блок и 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,{}}}}}==={},{},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}]]}}} 

что эта версия не аккумулировать глубину промежуточного выражения, так как результаты сохраняются в отдельном списке.

Answer 2

Идея этого ответа заключается в замене скобок() оболочкой, которая не приводит к увеличению наших выражений. Обратите внимание, что функция, на которую мы находим альтернативу, действительно представляет собой CompoundExpression, поскольку OP был правильным при замечании этой функции, разрушал хвостовую рекурсию (см. Также ответ Леонида). Предоставляются два решения.Это определяет первый обертка

SetAttributes[wrapper, HoldRest]; 
wrapper[first_, fin_] := fin 
wrapper[first_, rest__] := wrapper[rest] 

Тогда мы имеем, что

Clear[f] 
k = 0; 
mmm = 1000; 
f[n_ /; n < mmm] := wrapper[k += n, f[n + 1]]; 
f[mmm] := k + mmm 
Block[{$IterationLimit = Infinity}, f[0]] 

правильно вычисляет Total [Диапазон [1000]].

------ Примечание -----

Обратите внимание, что было бы неправильно установить

wrapper[fin_] := fin; 

Как и в случае

f[x_]:= wrapper[f[x+1]] 

Хвостовая рекурсия не делает (из-за того, что обертка, имеющая HoldRest, будет оценивать сингулярный аргумент перед применением правила, связанного с оберткой [fin_]).

Затем снова, определение выше для е не полезно, как можно было бы просто написать

f[x_]:= f[x+1] 

И есть нужный хвостовую рекурсию.

------ Другое примечание -----

В случае, если мы поставляем обертку с большим аргументов, он может быть медленнее, чем это необходимо. Пользователь может выбрать, чтобы написать

f[x_]:=wrapper[g1;g2;g3;g4;g5;g6;g7 , f[x+1]] 

ВТОРОМУ обертка

вторая обертка подают свои аргументы CompoundExpression и, следовательно, будет быстрее, чем первая обертка, если предусмотрены много аргументов. Это определяет вторую оболочку.

SetAttributes[holdLastWrapper, HoldAll] 
holdLastWrapper[fin_] := fin 
holdLastWrapper[other_, fin_] := 
Function[Null, #2, HoldRest][other, fin] 
holdLastWrapper[others__, fin_] := 
holdLastWrapper[ 
    Evaluate[CompoundExpression[others, Unevaluated[Sequence[]]]], fin] 

Примечание: Возвращение (пусто) Последовательности могут быть очень полезны при рекурсии вообще. Смотрите также мой ответ здесь

https://mathematica.stackexchange.com/questions/18949/how-can-i-return-a-sequence

Обратите внимание, что эта функция будет по-прежнему работать, если только один аргумент при условии, что он имеет атрибут саквояж, а не HoldRest, так что установка

f[x]:= holdLastWrapper[f[x+1]] 

даст хвостовая рекурсия (оболочка не имеет такого поведения).

Сравнение скорости

Давайте создадим хороший длинный список (на самом деле выражение с Head ДЕРЖАТЬ) инструкций

nnnn = 1000; 
incrHeld = 
    Prepend[DeleteCases[Hold @@ ConstantArray[Hold[c++], nnnn], 
    Hold, {2, Infinity}, Heads -> True], Unevaluated[c = 0]]; 

Для этих инструкций, мы можем сравнить производительность (и результаты) нашего оберток с CompoundExpression

holdLastWrapper @@ incrHeld // Timing 
CompoundExpression @@ incrHeld // Timing 
wrapper @@ incrHeld // Timing 

-> {{0,000856, 999}, {0,000783, 999}, {0.023752, 999}}

Заключение

Второй обертка лучше, если вы точно не уверены, когда хвостовая рекурсия будет или сколько аргументов вы будете кормить на обертку. Если вы намерены подавать аргументы оболочки 2, например, в том случае, когда вы понимаете, что вся вторая оболочка является фидом для CompoundExpression, и вы решили сделать это самостоятельно, первая оболочка лучше.

----- Конечная нота ----

В CompoundExpression [арг, невычисленный [выражение]], выражение все еще получает оценку, прежде чем CompoundExpression отпаривает, поэтому решения такого типа не имеет смысла.