home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / prolog / 2302 < prev    next >
Encoding:
Text File  |  1992-12-23  |  2.1 KB  |  52 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!mcsun!julienas!irisa!ridoux
  3. From: ridoux@irisa.fr (Olivier Ridoux)
  4. Subject: Unification of rational terms
  5. Message-ID: <1992Dec23.100438.20247@irisa.fr>
  6. Sender: news@irisa.fr
  7. Organization: IRISA, Rennes (Fr)
  8. Date: Wed, 23 Dec 92 10:04:38 GMT
  9. Lines: 41
  10.  
  11. Bart Demoen writes:
  12. > Supporting rational tree unification (and conservation of sharing during
  13. > some built-in predicates - which is a consequence of fully supporting cyclic
  14.                                         ^^^^^^^^^^^
  15. > terms) can actually speed up some programs quite a lot.
  16.  
  17. WEll, Well, well.  I like to be shightly more precise and show that
  18. rational term unification and conservation of sharing are rather
  19. independent.
  20.  
  21. The minimum that rational tree unification must do is to remember
  22. every pair of equivalent terms in the current branch of the current
  23. unification problem.  It will not buy you much conservation of
  24. sharing.  The maximum it can do is to remember every pair of
  25. equivalent terms in the current branch of the search-tree.  This will
  26. buy you the maximum conservation of sharing.
  27.  
  28. In this context, "equivalent" means "made equivalent by unification".
  29. Those terms that are equivalent without the help of unification may
  30. well never be recognised as equivalent.
  31.  
  32. One might want to stick to the minimum for avoiding special trailing
  33. and backtracking operations for handling the storing and unstoring of
  34. equivalent pairs, and to benefit from the recursive control of
  35. unification.  However, modern Prolog implementations already have
  36. these special operations (for handling contraints, term rewriting or
  37. whatever ...).  It would be rather mean of these implementations not
  38. to give the maximum.
  39.  
  40. Note also, that remembering pairs of equivalent terms in the current
  41. branch of the search-tree is also feasible and usefull for finite term
  42. unification.  It improves memory representation and unification (if it
  43. is smart enough to detect physically equal terms).
  44.  
  45. Moral: rational term unification and conservation of sharing are
  46. rather independent issues.  Even if they use similar techniques.
  47.  
  48. Hoping it helps,
  49.  
  50. Olivier Ridoux
  51.  
  52.