🚀 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) ...

An extreme example is "append" for difference lists (no flames on the
terminology, please!).  Without the occurs check, the cost is O(1);
with the occurs check, the cost is O(n) on the size of the terms (in 
other words, it gets the same cost as regular append).  Normally, the
programmer knows that the occurs check isn't needed, so this is a big win.

Without the occurs check, "infinite" or "rational" terms can be produced.
I've seen one practical use for them, for representing the fixpoint
of a recursive program as a term.  No doubt, there are other uses.

-----

Peter Ludemann