Mogę podsumować wnioski, do których doprowadziły mnie moje osobiste doświadczenia, z zastrzeżeniem, że to, co następuje, może nie być w pełni słusznym wyjaśnieniem. Wydaje się, że anwer leży w różnicach pomiędzy stosami wywołania Mathematica i tradycyjnymi stosami wywołań, które wywodzą się z funkcji zdefiniowanych przez Mathematica, które są naprawdę regułami. Tak więc nie ma prawdziwych wywołań funkcji. Mathematica potrzebuje stosu z innego powodu: ponieważ normalna ocena odbywa się z dołu drzewa wyrażeń, musi zachowywać wyrażenia pośrednie w przypadku, gdy głębsze i głębsze części wyrażeń (pod) są zastępowane w wyniku zastosowania reguły (niektóre części wyrażenie rośnie od dołu). Dotyczy to w szczególności reguł definiujących funkcje, które nazwalibyśmy nie tailującymi rekurencyjnymi w innych językach. Tak więc, po raz kolejny stos w Mathematica to stos wyrażeń pośrednich, a nie wywołań funkcji.
Oznacza to, że jeśli w wyniku zastosowania reguły można w całości przepisać (pod) wyrażenie, gałąź wyrażeń nie musi być przechowywana na stosie wyrażeń. Jest to prawdopodobnie nazywane optymalizacją wywołania końcowego w Mathematica - i dlatego w takich przypadkach mamy raczej iterację niż rekursję (jest to bardzo dobry przykład różnic między aplikacjami reguł a wywołaniami funkcji). Reguły takie jak f[x_]:=f[x+1] są tego typu. Jeśli jednak niektóre podekspozycje zostaną przepisane ponownie, tworząc większą strukturę ekspresji, to wyrażenie musi być przechowywane na stosie. Reguła f[x_ /; x < 5] := (n += 1; f[x + 1]) jest tego rodzaju, która jest nieco ukryta, dopóki nie przypomnimy sobie, że () oznacza () oznacza () oznaczającą . Schematycznie to, co się tutaj dzieje, to f[1] -> CompoundExpression[n+=1, f[2]] -> CompoundExpression[n+=1,CompoundExpression[n+=1,f[3]]]->etc. Mimo że wywołanie f jest ostatnim za każdym razem, dzieje się to przed wykonaniem pełnego CompoundExpression[], więc to wciąż musi być przechowywane na stosie wyrażeń. Można by argumentować, że jest to miejsce, w którym można dokonać optymalizacji, aby zrobić wyjątek dla CompoundExpression, ale prawdopodobnie nie jest to łatwe do wdrożenia.
Teraz, aby zilustrować proces stos akumulacji które schematycznie opisany powyżej, pozwalają nam ograniczyć liczbę wywołań rekurencyjnych:
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]];
śledzenie ocena:
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]]}}}}
Co widać z jest to, że stos wyrażeń gromadzi się dla f i fff (ten drugi używany tylko po to, aby pokazać, że jest to ogólny mechanizm, z ce[] tylko dowolną dowolną głową), ale nie dla ff, ponieważ dla celów dopasowywania wzorców pierwszą definicją dla ff jest reguła wypróbowana, ale nie pasująca, a druga definicja przepisuje w całości ff[arg_] i nie generuje głębszych pod-części, które wymagają dalszego przepisywania. Tak więc, wygląda na to, że powinieneś przeanalizować swoją funkcję i sprawdzić, czy jej rekursywne wywołania będą rosły od dołu do wartościowanego wyrażenia. Jeśli tak, to nie jest rekursywna w odniesieniu do Mathematica.
Moja odpowiedź nie byłaby kompletna bez pokazywania, jak ręcznie optymalizować ogłaszanie połączeń. Jako przykład rozważmy rekurencyjną implementację Select. Będziemy pracować z listami połączonymi z Mathematica, aby uczynić je raczej skutecznymi niż zabawkami. Poniżej znajduje się kod dla braku realizacji ogona-rekurencyjne:
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]]]
Powodem Używam bloku i selrecBad jest, aby ułatwić korzystanie z obrys. Teraz, to wieje stos na moim komputerze:
Block[{$RecursionLimit = Infinity}, sel[Range[300000], EvenQ]] // Short // Timing
można prześledzić na małych list zrozumieć, dlaczego:
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]@{}]}}}}}}
Co się dzieje, że wynik zostanie zsumowany głębiej i głębiej w liście. Rozwiązaniem jest nie rosną głębokości wynikającej wypowiedzi, a jednym ze sposobów, aby to osiągnąć jest, aby selrecBad przyjąć jeden dodatkowy parametr, który jest (połączone) wykaz zgromadzonych wyników:
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]]
i modyfikować głównym funkcja odpowiednio:
selTR[x_List, testF_] := Block[{test = testF}, Flatten[selrec[toLinkedList[x], {}]]]
Przepuszcza nasz test zasilania dobrze:
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}}
(zauważ, że tutaj musieliśmy zmodyfikować $ iterationLimit, co jest dobrym znakiem). I za pomocą śledzenia ujawnia powód:
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}]]}}}
co jest, ta wersja nie kumuluje głębię ekspresji pośredniej, ponieważ wyniki są przechowywane w osobnej liście.
+1 bardzo ładna analiza. Zgadzam się, że CompoundExpression jest kandydatem do optymalizacji, chociaż udało mi się wymyślić sytuację, w której podwyrażenie dodało definicje do CompoundExpression, zmieniając jego semantykę (którą optymalizacja mogłaby udaremnić). Nacisk na "contrive" - nie jestem pewien, czy byłby to problem w praktyce. – WReach
Doskonałe wyjaśnienie! Teraz różnica między '$ RecursionLimit' i' $ IterationLimit' staje się jasna. A czym "stos" stał się znacznie jaśniejszy. –