home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / prolog / 2261 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  1.9 KB
  1. Path: sparky!uunet!spool.mu.edu!uwm.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: <24438@alice.att.com>
  6. Date: 18 Dec 92 14:25:23 GMT
  7. Article-I.D.: alice.24438
  8. References: <1992Dec13.173016.8849@nntp.hut.fi> <1992Dec17.111142.24450@dcs.qmw.ac.uk> <24435@alice.att.com> <1992Dec17.185017.17766@cs.uoregon.edu>
  9. Reply-To: pereira@alice.UUCP ()
  10. Organization: AT&T, Bell Labs
  11. Lines: 26
  12.  
  13. In article <1992Dec17.185017.17766@cs.uoregon.edu> debray@majestix.cs.uoregon.edu (Saumya K. Debray) writes:
  14. >Fernando Pereira writes:
  15. >> Nonetheless, the efficiency reasons that led to Prolog's
  16. >> unification not having the check are pretty compelling, so I do not advocate
  17. >> adding it to Prolog in all cases. 
  18. >While I believe this statement, it would be interesting to actually see some
  19. >numbers (preferably for programs other than nrev) showing how much more
  20. >expensive unification becomes with the occurs check.
  21. Let me refine and qualify my assertion. In typical programs that I have
  22. written or read, fairly large terms are passed around. With a naive
  23. implementation of the occurs check, each such term has to be fully examined
  24. whenever it is passed as an actual parameter to a predicate. For instance,
  25. append becomes O(n^2) rather than O(n). However, in many of the cases
  26. the complex term is being unified with a variable occuring only once in
  27. the head, with a term the variables in which occur only once in the
  28. head, or the same situations arise involving variable instances that can be
  29. shown by global flow analysis to be ``new'' (that is not occuring
  30. anywhere else in the current resolvent). In any of those cases, the occurs
  31. check is not needed. This is just scratching the surface, much more
  32. sophisticated analyses have been published.
  33.  
  34. Fernando Pereira
  35. 2D-447, AT&T Bell Laboratories
  36. 600 Mountain Ave, PO Box 636
  37. Murray Hill, NJ 07974-0636
  38. pereira@research.att.com
  39.