🚀 go-pugleaf

In article <1h4g5tINN5l6@eagle.dfki.uni-sb.de> smolka@dfki.uni-sb.de (Gert Smolka) writes:
>I seriously doubt that rational tree unification pays any significant
>efficiency penalties in practise over Edinburgh-style unification
>without occurs check.  As has been mentioned by Torkel before,
>UNIFICATION IN SICSTUS IS RATIONAL TREE UNIFICATION, and Sicstus seems
>to be rather efficient.
I don't know what "rather efficient" means without actual numbers to
back it up. But *all* the rational unification algorithms I know
of need to make and trail more assignments, and chase more pointers,
than the original Prolog unification without the occurs check.
I would be happy it it were shown *over a well-chosen mix of programs*
that the overhead in question is negligible. But I've not seen such
a demonstration. 
>However, given the efficiency and
>the clean *logical* status of rational tree unification, I would expect
>that rational tree unification is taken as default and finite tree
>unification is accommodated as a built-in predicate
.he reason is that the efficiency issues mentioned above have not
been addressed to everyone's satisfaction.
>By the way, was it Edinburgh or Marseille which first dropped
>the occurs check?
Marseille. A very detailed and interesting account of the design history
of the first Prolog, written by Alain Colmerauer and Philipe Roussel,
will appear in the forthcoming proceedings of the History of Programming
Languages Conference (April 1993). Their choice was based on the
considerations that I have mentioned before. However, Alain eventually
changed his mind, as shown by the exclusive use of rational unification
in Prolog II. Nevertheless, the efficiency tradeoffs might still be
different for fast compiled Prologs than for interpreted systems
like the original Prolog and Prolog II: when the cost of clause
chasing goes down, the relative cost of term chasing goes up.

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