17
$\begingroup$

I would like to be able to get the current iteration count, the one that if exceeds $IterationLimit makes the evaluation stop.

After not finding a magical variable that stores this value, or a magical built-in that retrieves it, I thought about TraceScan.

According to the documentation of $IterationLimit,

$IterationLimit gives an upper limit on the length of any list that can be generated by Trace

However, a quick test shows that this is not so simple. Let's define

ClearAll[f]
f[i_] := f[i - 1]
f[0] := "Yeah"

Now,

Block[{$IterationLimit = 20},
 Trace[f[18]] // Length//Print;
 Trace[f[18], TraceDepth -> 1] // Length//Print;
 f[18]
 ]

prints 56 and 38 respectively, while f[18]'s evaluation finishes successfully.

Looking at the output of the last trace, we see that the before and after argument evaluation are being traced. So,

Trace[f[3], TraceDepth -> 1]   
(* {f[3],f[3-1],f[2],f[2-1],f[1],f[1-1],f[0],Yeah} *)

Notice that the "two outputs per iteration" rule doesn't hold if we add a definition like f[3]=f[1], in which case

Trace[f[5], TraceDepth -> 1]
(* {f[5],f[5-1],f[4],f[4-1],f[3],f[1],f[1-1],f[0],Yeah} *)

If this happened, a hacky workround could exist along the lines of

SetAttributes[trackIterations, HoldFirst];
trackIterations[code_] := Block[{iterationCounter = 0},
  TraceScan[iterationCounter += 1/2, code, TraceDepth -> 1]
  ]

Question

How can I get that counter, or alternatively, how can I make Trace only trace once each iteration?

$\endgroup$
7
  • $\begingroup$ I wanted to be the one to answer this but I'm stumped. $\endgroup$
    – Mr.Wizard
    Jan 25, 2013 at 0:39
  • 1
    $\begingroup$ Take a look at verbeia.com/mathematica/tips/HTMLLinks/Tricks_Misc_3.html. He says "I don't discuss how counting iterarions and recursions fit into the evaluation process because I have never seen an explanation of when that happens." $\endgroup$ Jan 25, 2013 at 0:44
  • 1
    $\begingroup$ @belisarius (She says...) verbeia.com/mathematica/bios.html $\endgroup$ Jan 25, 2013 at 1:13
  • $\begingroup$ @DanielLichtblau I thought it was Ted's $\endgroup$ Jan 25, 2013 at 1:18
  • $\begingroup$ @belisarius Sorry, you are probably correct. I thought you were referring to Verbeia and did not check to see specifically who wrote what. $\endgroup$ Jan 25, 2013 at 1:23

1 Answer 1

7
+50
$\begingroup$

I'm not sure whether you can generalize this or how stable this approach is, but it seems if you use Trace to look how often the exactly the form f is evaluated then that does the trick.

ClearAll[f]
f[i_] := f[i - 1]
f[0] := "Yeah"

Block[{$IterationLimit = 20},
 Cases[Trace[f[100], f, TraceOriginal -> True], HoldForm[f], Infinity] // Length // Print;
 f[100]]

The idea behind this is as follows: I was reading Rojos question and inspecting the trace of depth 1

(* {f[5],f[5-1],f[4],f[4-1],f[3],f[3-1],f[2],f[2-1],f[1],f[1-1],f[0],Yeah} *)

The problem was that although f was called fewer times, every evaluation step is shown and the length of the above list cannot be used. Therefore, I though about a way to count how often the Head of the expression, i.e. the symbol f itself was evaluated. Usually, the evaluation of the Head is not shown, since its form does not change.

This can be turned on using TraceOriginal

Trace[f[3],f,TraceOriginal->True]
(* {f[3],{f},f[3],f[3-1],{f},f[2],f[2-1],{f},f[1],f[1-1],{f},f[0],Yeah} *)

Now we can count each single instance of f which occurs in the output. In my first example I used Cases because I was just adapting Rojos examples with its //Length//Print. Of course, and as suggested by Mr.Wizard Count is the better alternative here

Block[{$IterationLimit = 20}, 
 Count[Trace[f[100], f, TraceOriginal -> True], {HoldForm[f]}]
]

While I was writing this, another idea came to my mind. When the problem is, that the head does not change and it therefore does not appear in the usual output, why not fixing this? Therefore, here an alternative approach which adjusts the function to be evaluated and makes a use of options to Trace unnecessary:

ClearAll[f, g]
g = f;
f[i_] := g[i - 1]
f[0] := "Yeah"

Block[{$IterationLimit = 25},
 Count[Flatten[Trace[g[100]]], HoldForm[g]]
]
$\endgroup$
5
  • $\begingroup$ Interesting. I suggest you change Cases to Count for brevity. Also, do you need Infinity or would scanning at level 1 be sufficient? $\endgroup$
    – Mr.Wizard
    Mar 18, 2013 at 6:01
  • $\begingroup$ @Mr.Wizard likely the Infinity is required otherwise it won't scan deep enough. $\endgroup$
    – rcollyer
    Mar 18, 2013 at 13:49
  • $\begingroup$ NiiiiIIiIIiiIIIiiiiice. A ThreadDepth->2 might help it be more efficient $\endgroup$
    – Rojo
    Mar 18, 2013 at 19:58
  • $\begingroup$ @Mr.Wizard I explained that Count is better now. I just wanted to wait, whether it helps Rojo at all. You might be interested in the last part I added. $\endgroup$
    – halirutan
    Mar 18, 2013 at 21:21
  • $\begingroup$ I can't think of a way to generalize the last approach, I prefer the first :) $\endgroup$
    – Rojo
    Mar 18, 2013 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.