home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / prolog / 2303 < prev    next >
Encoding:
Text File  |  1992-12-23  |  1.1 KB  |  32 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!brunix!brunix!mj
  3. From: mj@cs.brown.edu (Mark Johnson)
  4. Subject: Cost of cyclic unification?
  5. Message-ID: <1992Dec23.155044.15225@cs.brown.edu>
  6. Sender: news@cs.brown.edu
  7. Organization: Brown University Department of Computer Science
  8. References: <TORKEL.92Dec21175440@bast.sics.se> <1992Dec21.195646.3776@cs.brown.edu> <1992Dec23.010930.2892@cs.sfu.ca>
  9. Date: Wed, 23 Dec 1992 15:50:44 GMT
  10. Lines: 20
  11.  
  12. For two acyclic terms, can cyclic unification run in time proportional
  13. to the size of the *smaller* term?
  14.  
  15. That is, if a program doesn't make use of cyclic terms then can it
  16. run as efficiently on a Prolog that supports cyclic unification
  17. as it would on a Prolog that doesn't support cyclic unification?
  18.  
  19. If true, it seems that cyclic unification would be preferable
  20. to acyclic unification without the occur check.
  21.  
  22. Mark
  23.  
  24. P.S.: I constructed a small program to see if unifying two terms
  25. of the form f(f(...f(f(_))...)) depended on the size of the larger
  26. term.  I could detect no change in time required in Sicstus.
  27.  
  28.  
  29. Mark Johnson
  30. Cognitive Science, Box 1978
  31. Brown University
  32.