home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / prolog / 1520 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  2.4 KB
  1. Path: sparky!uunet!walter!att!att!allegra!alice!pereira
  2. From: pereira@alice.att.com (Fernando Pereira)
  3. Newsgroups: comp.lang.prolog
  4. Subject: Re: transitive and symetric relations
  5. Message-ID: <23435@alice.att.com>
  6. Date: 13 Aug 92 00:15:51 GMT
  7. Article-I.D.: alice.23435
  8. References: <SWK.92Aug10220513@seymour.mlb.semi.harris.com>
  9. Reply-To: pereira@alice.UUCP ()
  10. Distribution: comp.lang.prolog
  11. Organization: AT&T, Bell Labs
  12. Lines: 55
  13.  
  14. In article <SWK.92Aug10220513@seymour.mlb.semi.harris.com> swk@seymour.mlb.semi.harris.com (Song W. Koh) writes:
  15. >[...]  I am having trouble describing transitive and
  16. >symetric relations without stack overflows.  Things like:
  17. >
  18. >distance(X,Y,D) :- distance(Y,X,D).
  19. >
  20. >and
  21. >
  22. >distance(X,Z,D) :- distance(X,Y,D1), distance(Y,Z,D2), D is D1 + D2.
  23. >
  24. As some other posters have noted, if you see Prolog as a *programming
  25. language* with a particular operational semantics, the looping is
  26. not surprising. Compare for instance the C function
  27.  
  28. int distance(x, y)
  29. Point *x, *y;
  30. {
  31.    return distance(y, x);
  32. }
  33.  
  34. It will surely loop and very possibly run out of stack (unless the
  35. C compiler is clever enough do do some sort of last-call optimization).
  36.  
  37. Problems of the kind you describe, which involve computing closures of
  38. relations, are best processed with a bottom-up or memoizing execution method
  39. rather than the top-down execution method built into Prolog. These
  40. methods avoid looping by goals already attempted and conclusions already
  41. reached to avoid retrying them. These methods can be simulated in Prolog by
  42. using assert judiciously. My book
  43.  
  44. @book(Pereira+Shieber:Prolog,
  45.     Author={Fernando C. N. Pereira and Stuart M. Shieber},
  46.     Key={Pereira and Shieber},
  47.     Title={Prolog and Natural-Language Analysis},
  48.     Publisher={Center for the Study of Language and Information},
  49.     Number={10},
  50.     Address={Stanford, California},
  51.     Series={CSLI Lecture Notes},
  52.     Year={1985},
  53.     Note={Distributed by Chicago University Press}
  54. )
  55.  
  56. discusses some of those methods, althout it might be nice to have
  57. a tutorial introduction to them in a more general stetting (Is there
  58. one?)
  59.  
  60. Alternatively, for particular relations you can keep track of points/nodes
  61. already visited with an extra argument in the relevant predicates of
  62. your program (some other posting also referred to this technique).
  63.  
  64. Fernando Pereira
  65. 2D-447, AT&T Bell Laboratories
  66. 600 Mountain Ave, PO Box 636
  67. Murray Hill, NJ 07974-0636
  68. pereira@research.att.com
  69.