🚀 go-pugleaf

In article <190@syllogi.syllogic.nl> fdb@syllogic.nl (Frank de Bruijn) writes:
>ken@aiai.ed.ac.uk (Ken Johnson) writes:
>Indeed I did; as an experiment / toy: it works fine for relations where
>the number of transitive "hops" and the number of times the predicate is
>called remain small. When you go into serious AI-related search problems
>(possibly exploring multiple worlds/alternatives) where the number of calls
>to these relations goes beyond 100 K calls (not counting recursive subcalls)
>the cost of inspecting the call stack will become prohibitive.

I considered using Brent's method for doing this at one time.
Brent is a mod of Floyd. Both try to find cycles in graphs.

The basic idea is to run two processes through the graph -- one
that runs slower than the other. Floyd chooses 1/2 speed; Brent
chooses exponentially slower.

In terms of implementation Floyd would have you merely check
the current goal against the SINGLE goal at 1/2 the depth of the
call stack. If there's a match then you have a cycle. Brent
would use an extra O(log N) (N=max depth of call stack) of
storage and compare the current goal to the top of this second
stack. The idea of using the second stack is that sometimes you
can't dig into the call stack willy-nilly. And the second stack
has O(log N) size rather than being the full O(N).

-kym