🚀 go-pugleaf

In article <1992Dec17.185017.17766@cs.uoregon.edu> debray@majestix.cs.uoregon.edu (Saumya K. Debray) writes:
>Fernando Pereira writes:
>> Nonetheless, the efficiency reasons that led to Prolog's
>> unification not having the check are pretty compelling, so I do not advocate
>> adding it to Prolog in all cases. 
>While I believe this statement, it would be interesting to actually see some
>numbers (preferably for programs other than nrev) showing how much more
>expensive unification becomes with the occurs check.
Let me refine and qualify my assertion. In typical programs that I have
written or read, fairly large terms are passed around. With a naive
implementation of the occurs check, each such term has to be fully examined
whenever it is passed as an actual parameter to a predicate. For instance,
append becomes O(n^2) rather than O(n). However, in many of the cases
the complex term is being unified with a variable occuring only once in
the head, with a term the variables in which occur only once in the
head, or the same situations arise involving variable instances that can be
shown by global flow analysis to be ``new'' (that is not occuring
anywhere else in the current resolvent). In any of those cases, the occurs
check is not needed. This is just scratching the surface, much more
sophisticated analyses have been published.

Fernando Pereira
2D-447, AT&T Bell Laboratories
600 Mountain Ave, PO Box 636
Murray Hill, NJ 07974-0636
pereira@research.att.com