[PEAK] naming.lookup() vs config.lookupComponent()

[Doug Quale]

"Phillip J. Eby" <pje at telecommunity.com> writes:

> Another variation that occurs to me is that you could simply advance
> the slow pointer once out of every N fast advances, for some N, while
> using the 'fast' pointer as the yielded value.  That is, the fast
> pointer advances 1 each time, and the slow pointer effectively
> advances 1/N.  If N is as high or higher than the average component
> tree depth, the amortized cost wouldn't be much different than that of
> the "recursion limit" approach (i.e. decrementing a counter and
> checking it on each iteration).

That's a good idea.  It would certainly work for N=2.  I don't know
about larger N but I wouldn't be surprised if worked with any prime
number N > 1.

> So it's still somewhat interesting, although I don't feel intuitively
> positive that the algorithm is guaranteed to terminate, and don't see
> that it really adds anything over a recursion limit, since as a
> practical matter having super-deep component hierarchies requiring
> lots of iteration over to perform operations is probably something you
> want to know is happening, and do something about.

You're right, it isn't easy to see that it works.  It's clear that if
the fast and slow pointers ever become equal then there is a
circularity.  The hard part is to show that if there is a circularity
the fast and slow pointers are guaranteed to eventually meet.  I'm not
prepared to prove this but I'm confident it's true.  That property has
been used in Lisp implementations since sometime in the 1970s, if not
earlier.  Here's a link to some documentation from one of the (few
remaining) large Lisp vendors:
http://www.franz.com/support/documentation/6.2/ansicl/dictentr/list-len.htm.

> So, "Simplest Thing That Could Possibly Work" here seems to favor
> the counting approach.

I agree: The recursion limit is probably the best practical
engineering approach.  It's simple and fast, easy to understand and
code correctly.  As you note, a component hierarchy deeper than some
large number like 100 is probably a mistake, even if it isn't
circular.