# In what cases is graph rewriting not enough to avoid duplicate work?

As I understand, evaluating something like the following in normal order evaluation is inefficient due to duplicate work:

double x = (x,x)
main     = double some_hard_computation


I remember someone telling me

• That there are two ways to avoid this: strictness analysis (to recognise that double is strict in its one argument, and then deviating from normal order evaluation and evaluate the argument first) and graph rewriting (store pointers to some_hard_computation such that both elements of the tuple point to the same computation, and evaluating one side of the tuple automatically evaluates the other side as well).

• That neither of the ways are sufficient on their own to avoid all cases where duplicate work can be introduced, and that it is best to apply both when writing a compiler.

I can imagine that strictness analysis can be hard, but in what concrete case can duplicate work be introduced when utilising graph rewriting? Or is either of the two bullet points above incorrect?

Note: while strictness analysis is done statically (as far as I know), graph rewriting is an evaluation strategy, not a compiler optimisation. It attempts to solve the same problem as the strictness analyser, but on a different level (runtime vs. compile time).

• Detecting duplicate work is probably not computable, so neither method can be complete. – Raphael Sep 26 '16 at 19:45
• @Raphael it definitely wouldn't surprise me if it weren't computable, but graph rewriting seems so straightforward - I cannot think of a concrete case where it would not work. – user23039 Sep 26 '16 at 19:50
• Luckily, we can proof undecidability without giving a counter-example. (In fact, that won't work anyway.) – Raphael Sep 26 '16 at 19:52

Consider this program:

f (m : Nat) x y = (x, if H(m,m) then x else y)

my_f = f my_number
my_f hard harder


where H(x,x) returns True if Turing machine number x halts on input x and False otherwise. Detecting duplicate work (always) would mean solving the halting problem, no matter whether you want to do the analysis statically or dynamically.

Hence, no method can be complete.

• Maybe there are less convoluted example for the two methods at hand. – Raphael Sep 26 '16 at 19:52
• Sorry, but I don't see how this would be a problem for graph rewriting. As I understand, the graph will look like this after rewriting. If H(m,m) evaluates to false, hard will only be used once, otherwise, twice. If it is used twice, the second argument to if and the first to Tuple point to the same node, so there is no duplicate work. If it is used once, one reference is removed, but we still don't need to compute anything twice, right? – user23039 Sep 26 '16 at 20:02
• @CamilStaps Does it leave the if in there, though? This way, you can construct big programs that can not be evaluated/shrunk at all. Basically, I assumed, that we'd want to remove ifs as early as possible. Maybe that's an invalid assumption, in which case I don't understand well enough which techniques exactly you are talking about in the question. – Raphael Sep 26 '16 at 20:09
• Oh, I see what you mean now. That would make this a question about static analysis and compiler optimisations. I meant to ask about evaluation strategies. I will edit my question to clarify this, it can be confusing because strictness analysis is done statically as far as I know. – user23039 Sep 26 '16 at 20:12
• I will see if I can find in my notes who told me the two bullet points from my question and ask them for clarification. That is perhaps easier, especially if I'm not able to put my thoughts into clear words. Thanks anyway though! – user23039 Sep 26 '16 at 20:18