home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / prolog / 2260 < prev    next >
Encoding:
Text File  |  1992-12-21  |  1.5 KB  |  36 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!infonode!ingr!capalo!quintus!quintus!ludemann
  3. From: ludemann@quintus.com (Peter Ludemann)
  4. Subject: Re: Occurs check
  5. Message-ID: <1992Dec18.190711.1063@quintus.com>
  6. Sender: news@quintus.com (USENET news account)
  7. Nntp-Posting-Host: ebisu
  8. Organization: Quintus Corporation, Palo Alto, CA
  9. References: <1992Dec13.173016.8849@nntp.hut.fi> <1992Dec17.111142.24450@dcs.qmw.ac.uk> <24435@alice.att.com> <1992Dec17.185017.17766@cs.uoregon.edu>
  10. Date: Fri, 18 Dec 1992 19:07:11 GMT
  11. Lines: 23
  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. > 
  19. > While I believe this statement, it would be interesting to actually see some
  20. > numbers (preferably for programs other than nrev) ...
  21.  
  22. An extreme example is "append" for difference lists (no flames on the
  23. terminology, please!).  Without the occurs check, the cost is O(1);
  24. with the occurs check, the cost is O(n) on the size of the terms (in 
  25. other words, it gets the same cost as regular append).  Normally, the
  26. programmer knows that the occurs check isn't needed, so this is a big win.
  27.  
  28. Without the occurs check, "infinite" or "rational" terms can be produced.
  29. I've seen one practical use for them, for representing the fixpoint
  30. of a recursive program as a term.  No doubt, there are other uses.
  31.  
  32. -----
  33.  
  34. Peter Ludemann
  35.  
  36.