Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I can summarize the conclusions I was led to by my personal experience, with a disclaimer that what follows may not be the entirely right explanation. The anwer seems to lie in the differences between Mathematica call stack and traditional call stacks, which originates from Mathematica pattern-defined functions being really rules. So, there are no real function calls. Mathematica needs a stack for a different reason: since normal evaluation happens from the bottom of an expression tree, it must keep intermediate expressions in case when deeper and deeper parts of (sub)expressions get replaced as a result of rule application (some parts of an expression grow from the bottom). This is the case, in particular, for rules defining what we'd call non tail-recursive functions in other languages. So, once again, the stack in Mathematica is a stack of intermediate expressions, not function calls.</p> <p>This means that if, as a result of rule application, an (sub)expression can be rewritten in its entirety, the expression branch need not be kept on the expression stack. This is probably what is referred as tail call optimization in Mathematica - and this is why in such cases we have iteration rather than recursion (this is one very good example of the differences between rule applications and function calls). Rules like <code>f[x_]:=f[x+1]</code> are of this type. If, however, some sub-expression get rewritten, producing more expression structure, then expression must be stored on the stack. The rule <code>f[x_ /; x &lt; 5] := (n += 1; f[x + 1])</code> is of this type, which is a bit hidden until we recall that <code>()</code>stand for <code>CompoundExpression[]</code>. Schematically what happens here is <code>f[1] -&gt; CompoundExpression[n+=1, f[2]] -&gt; CompoundExpression[n+=1,CompoundExpression[n+=1,f[3]]]-&gt;etc</code>. Even though the call to f is the last every time, it happens before the full <code>CompoundExpression[]</code> executes, so this still must be kept on the expression stack. One could perhaps argue that this is a place where optimization could be made, to make an exception for CompoundExpression, but this is probably not easy to implement.</p> <p>Now, to illustrate the stack accumulation process which I schematically described above, let us limit the number of recursive calls:</p> <pre><code>Clear[n, f, ff, fff]; n = 0; f[x_ /; x &lt; 5] := (n += 1; f[x + 1]); ff[x_] := Null /; (n += 1; False); ff[x_ /; x &lt; 5] := ff[x + 1]; fff[x_ /; x &lt; 5] := ce[n += 1, fff[x + 1]]; </code></pre> <p>Tracing the evaluation:</p> <pre><code>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]]}}}} </code></pre> <p>What you can see from this is that the expression stack accumulates for <code>f</code> and <code>fff</code> (the latter used just to show that this is a general mechanism, with <code>ce[]</code> just some arbitrary head), but not for <code>ff</code>, because, for the purposes of pattern matching, the first definition for <code>ff</code> is a rule tried but not matched, and the second definition rewrites <code>ff[arg_]</code> in its entirety, and does not generate deeper sub-parts that need further rewriting. So, the bottom line seems that you should analyze your function and see if its recursive calls will grow the evaluated expression from the bottom or not. If yes, it is not tail-recursive as far as Mathematica is concerned.</p> <p>My answer would not be complete without showing how to do the tail call optimization manually. As an example, let us consider recursive implementation of Select. We will work with Mathematica linked lists to make it reasonably efficient rather than a toy. Below is the code for the non tail-recursive implementation:</p> <pre><code>Clear[toLinkedList, test, selrecBad, sel, selrec, selTR] toLinkedList[x_List] := Fold[{#2, #1} &amp;, {}, 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]]] </code></pre> <p>The reason I use Block and selrecBad is to make it easier to use Trace. Now, this blows the stack on my machine: </p> <pre><code>Block[{$RecursionLimit = Infinity}, sel[Range[300000], EvenQ]] // Short // Timing </code></pre> <p>You can trace on small lists to see why:</p> <pre><code>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@@{}]}}}}}} </code></pre> <p>What happens is that the result gets accumulated deeper and deeper in the list. The solution is to not grow the depth of the resulting expression, and one way to achieve that is to make selrecBad accept one extra parameter, which is the (linked) list of accumulated results:</p> <pre><code>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]] </code></pre> <p>And modify the main function accordingly:</p> <pre><code>selTR[x_List, testF_] := Block[{test = testF}, Flatten[selrec[toLinkedList[x], {}]]] </code></pre> <p>This will pass our power test just fine:</p> <pre><code>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, &lt;&lt;149981&gt;&gt;,299984,299986,299988,299990,299992,299994,299996,299998,300000}} </code></pre> <p>(note that here we had to modify $IterationLimit, which is a good sign). And using Trace reveals the reason:</p> <pre><code>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}]]}}} </code></pre> <p>which is, this version does not accumulate the depth of the intermediate expression, since the results are kept in a separate list.</p>
    singulars
    1. This table or related slice is empty.
    1. POTail call optimization in Mathematica?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USLeonid Shifrin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POTail call optimization in Mathematica?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1 very nice analysis. I agree that CompoundExpression is a candidate for optimization although I was able to contrive a situation where a subexpression added definitions to CompoundExpression, changing its semantics (which the optimization would thwart). Emphasis on "contrive" -- I'm not sure it would be an issue in practice.
      singulars
      1. PO
      1. USWReach
    2. COExcellent explanation! Now the difference between `$RecursionLimit` and `$IterationLimit` become clear. And what is the `stack` has become significantly clearer.
      singulars
      1. PO
      1. USAlexey Popkov
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload