Re: Fix 380: Try to auto-detect cyclic references in header fields (issue 4951073)

[Reinhold Kainhofer]

Am Thursday, 15. September 2011, 02:33:59 schrieb David Kastrup:
> Reinhold Kainhofer <address@hidden> writes:
> > We never even really have a tree to traverse. The elements are only
> > created by interpret-markup, which will already cause the infinite
> > loop.
> 
> I don't get your point.  Whether the tree is explicit or implicit, the
> nodes are recognizable before evaluation.

Huh? So, you are saying that you can determine in g() whether the evaluation 
of f will terminate, without evaluating f?

int g(int i) {
  // Please determine here, whether this call will result in a 
  // loop or terminate, without evaluating f:
  return f(i);
}

int f(int i) {
  if (i==1) 
    return 1;
  else if (i%2 == 0)
    return g(i/2);
  else 
    return g(3*i+1);
}

Or in scheme:

(define (g i)
  ;; Please determine here wether this will result in a loop, without
  ;; evaluating f:
  (f i))

(define (f i)
  (cond ((= i 1) 1)
        ((even? i) (g (/ i 2)))
        (else (g (+1 (* 3 i))))))


This is exactly the situation with markup interpretation: g is in lilypond the 
interpret-markup function, while f can be any markup function, which might 
call interpret-markup again for sub-markups.

If we don't want to modify all markup functions, we can only adjust g. 
However, due to the recursion, I don't see how we can step through the nodes 
with two different speeds.
All I can imagine it to mark all combinations of already-called arguments. But 
that might be quite memory-intensive.

What makes the situation in lilypond even worse is that a markup function can 
invoke interpret-markup multiple times, so we have a call tree. And in markup 
functions we have more than one argument i. Rather, we have three arguments 
(layout, props, markup), which might or might not influence the result.

E.g. 
Case 1: A markup-function depends on the props, e.g. \fromproperty. 
Conclusion: To detect loops, we need to look not only on the markup itself, 
but also the properties.

Case 2: A markup-function modifies the props (e.g. increments one member of 
the chained alist by 1) and then calls itself. Since in case 1 we saw that we 
need to compare the props and the markup, we never detect that we are in a 
loop, because the props are constantly changing, even though they will not 
have any influence on the output.

> > Without running interpret-markup on a markup we don't know anything
> > about its contents (because the markup function might create anything
> > it wants), and as soon as we are running interpret-markup on a markup,
> > we might end up in a cycle.
> 
> And the topic of this issue is detecting this cycle.

Yes, but how can we do it short of changing how the evaluation is done?

> > So, I wouldn't characterize this as a loop detection, but rather
> > determining whether an arbitrary recursion ever terminates...
> 
> "cycle" and "loop" are two different names for the same thing.

Actually, I was also thinking about cases where we are not in a loop, but 
which still don't terminate. 

Cheers,
Reinhold

-- 
------------------------------------------------------------------
Reinhold Kainhofer, address@hidden, http://reinhold.kainhofer.com/
 * Financial & Actuarial Math., Vienna Univ. of Technology, Austria
 * http://www.fam.tuwien.ac.at/, DVR: 0005886
 * LilyPond, Music typesetting, http://www.lilypond.org