🚀 go-pugleaf

For two acyclic terms, can cyclic unification run in time proportional
to the size of the *smaller* term?

That is, if a program doesn't make use of cyclic terms then can it
run as efficiently on a Prolog that supports cyclic unification
as it would on a Prolog that doesn't support cyclic unification?

If true, it seems that cyclic unification would be preferable
to acyclic unification without the occur check.

Mark

P.S.: I constructed a small program to see if unifying two terms
of the form f(f(...f(f(_))...)) depended on the size of the larger
term.  I could detect no change in time required in Sicstus.


Mark Johnson
Cognitive Science, Box 1978
Brown University