home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / prolog / 2296 < prev    next >
Encoding:
Text File  |  1992-12-22  |  4.1 KB  |  93 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!mcsun!ub4b!news.cs.kuleuven.ac.be!bimbart
  3. From: bimbart@cs.kuleuven.ac.be (Bart Demoen)
  4. Subject: Re: occurs check
  5. Message-ID: <1992Dec22.194530.21069@cs.kuleuven.ac.be>
  6. Sender: news@cs.kuleuven.ac.be
  7. Nntp-Posting-Host: hera.cs.kuleuven.ac.be
  8. Organization: Dept. Computerwetenschappen K.U.Leuven
  9. Date: Tue, 22 Dec 1992 19:45:30 GMT
  10. Lines: 81
  11.  
  12. Gert Smolka writes:
  13. > I seriously doubt that rational tree unification pays any significant
  14. > efficiency penalties in practise over Edinburgh-style unification
  15. > without occurs check.  As has been mentioned by Torkel before,
  16. > UNIFICATION IN SICSTUS IS RATIONAL TREE UNIFICATION, and Sicstus seems
  17. > to be rather efficient.
  18. to which Fernando Pereira replies:
  19. > I don't know what "rather efficient" means without actual numbers to
  20. > back it up. 
  21.  
  22. Fernando Pereira is too cautious: SICStus and ProLog by BIM have chosen to
  23. support unification of cyclic terms and they are more efficient than most
  24. other systems that have no support for unification of cyclic terms, neither
  25. - systematic - occurs check. If any Prolog system is worth being named "rather
  26. efficient", it is them.
  27. A Prolog system by Siemens has chosen for occurs check. Perhaps Christian
  28. Pichler can comment on that: last time I talked to him, he said that the
  29. overhead was quite small. Also the Siemens system is faster than the average
  30. Prolog system.
  31.  
  32. again Gert:
  33. > However, given the efficiency and
  34. > the clean *logical* status of rational tree unification, I would expect
  35. > that rational tree unification is taken as default and finite tree
  36. > unification is accommodated as a built-in predicate
  37. to which Fernando Pereira replies:
  38. > .he reason is that the efficiency issues mentioned above have not
  39. > been addressed to everyone's satisfaction.
  40.  
  41. I think rather the following: the reason why the forthcoming standard does not
  42. require either occurs check or rational tree unification, is partly that some
  43. implementors fear the implementation cost (they are right: the cost will not be
  44. paid back by costumers) and partly that choosing between rational trees and
  45. occurs check is next to impossible for the ISO committee (remember how long it
  46. took for deciding about the database update view).
  47. The nice thing about what the current draft of the standard now requires, is
  48. that in order to keep the property that 2 unifications commute, implementors
  49. should commit to rational trees or occurs check and never have undefined behaviour.
  50.  
  51. Supporting rational tree unification is easy. The tedious (and also fun) work
  52. comes when one tries to make the built-in predicates behave sensibly when they
  53. are called with cyclic terms. As far as I know, IBM Prolog did a good job at
  54. this. In ProLog by BIM, the bag returned by bagof/3 can contain cyclic terms
  55. (e.g. ?- bagof(X,X = f(X),L)) and the record predicates can store and retrieve
  56. cyclic terms; numbervars/3, ground/1, copy_term/2 etc deal sensibly with
  57. cyclic terms. And the others will follow (for some of them - like assert - it
  58. will depend on options set by the user what happens exactly). But we don't
  59. plan (at the moment) to have an external syntax for them like in IBM Prolog.
  60. Cyclic bindings are shown at the toplevel as follows:
  61.  
  62.     ?- X = f(X) .
  63.       X = f(X)
  64.  
  65. which is just the generalisation of showing the sharing even in the non cyclic
  66. case, as in
  67.  
  68.     ?- Y = [1,2,3] , X = f(Y,g(Y)) .
  69.       X = f(Y,g(Y))
  70.       Y = [1,2,3]
  71.  
  72. which is a bit more useful than
  73.  
  74.     ?- Y = [1,2,3] , X = f(Y,g(Y)) .
  75.       Y = [1,2,3]
  76.       X = f([1,2,3],g([1,2,3]))
  77.  
  78. Supporting rational tree unification (and conservation of sharing during
  79. some built-in predicates - which is a consequence of fully supporting cyclic
  80. terms) can actually speed up some programs quite a lot.
  81.  
  82. Fernando again:
  83. > I would be happy it it were shown *over a well-chosen mix of programs*
  84. > that the overhead in question is negligible. But I've not seen such
  85. > a demonstration. 
  86. Depending on what exactly one wants to accept as a well-chosen mix of programs,
  87. Peter Van Roy's thesis (or paper) on the Aquarius system, contains some useful
  88. figures:  he compares the Aquarius system with BIM (with rational trees) and
  89. Quintus (no rational trees, neither occurs check).
  90.  
  91. Bart Demoen
  92.  
  93.