home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / prolog / 2286 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  2.5 KB
  1. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!att!allegra!alice!pereira
  2. From: pereira@alice.att.com (Fernando Pereira)
  3. Newsgroups: comp.lang.prolog
  4. Subject: Re: Occurs check
  5. Message-ID: <24461@alice.att.com>
  6. Date: 21 Dec 92 19:38:23 GMT
  7. Article-I.D.: alice.24461
  8. References: <1992Dec13.173016.8849@nntp.hut.fi> <1992Dec17.111142.24450@dcs.qmw.ac.uk> <24435@alice.att.com> <1h4g5tINN5l6@eagle.dfki.uni-sb.de>
  9. Reply-To: pereira@alice.UUCP ()
  10. Organization: AT&T, Bell Labs
  11. Lines: 38
  12.  
  13. In article <1h4g5tINN5l6@eagle.dfki.uni-sb.de> smolka@dfki.uni-sb.de (Gert Smolka) writes:
  14. >I seriously doubt that rational tree unification pays any significant
  15. >efficiency penalties in practise over Edinburgh-style unification
  16. >without occurs check.  As has been mentioned by Torkel before,
  17. >UNIFICATION IN SICSTUS IS RATIONAL TREE UNIFICATION, and Sicstus seems
  18. >to be rather efficient.
  19. I don't know what "rather efficient" means without actual numbers to
  20. back it up. But *all* the rational unification algorithms I know
  21. of need to make and trail more assignments, and chase more pointers,
  22. than the original Prolog unification without the occurs check.
  23. I would be happy it it were shown *over a well-chosen mix of programs*
  24. that the overhead in question is negligible. But I've not seen such
  25. a demonstration. 
  26. >However, given the efficiency and
  27. >the clean *logical* status of rational tree unification, I would expect
  28. >that rational tree unification is taken as default and finite tree
  29. >unification is accommodated as a built-in predicate
  30. .he reason is that the efficiency issues mentioned above have not
  31. been addressed to everyone's satisfaction.
  32. >By the way, was it Edinburgh or Marseille which first dropped
  33. >the occurs check?
  34. Marseille. A very detailed and interesting account of the design history
  35. of the first Prolog, written by Alain Colmerauer and Philipe Roussel,
  36. will appear in the forthcoming proceedings of the History of Programming
  37. Languages Conference (April 1993). Their choice was based on the
  38. considerations that I have mentioned before. However, Alain eventually
  39. changed his mind, as shown by the exclusive use of rational unification
  40. in Prolog II. Nevertheless, the efficiency tradeoffs might still be
  41. different for fast compiled Prologs than for interpreted systems
  42. like the original Prolog and Prolog II: when the cost of clause
  43. chasing goes down, the relative cost of term chasing goes up.
  44.  
  45. Fernando Pereira
  46. 2D-447, AT&T Bell Laboratories
  47. 600 Mountain Ave, PO Box 636
  48. Murray Hill, NJ 07974-0636
  49. pereira@research.att.com
  50.  
  51.