home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / prolog / 1452 < prev    next >
Encoding:
Text File  |  1992-07-26  |  4.5 KB  |  117 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: Unsafe variables
  5. Message-ID: <1992Jul27.065551.3053@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: Mon, 27 Jul 1992 06:55:51 GMT
  10. Lines: 105
  11.  
  12. Tim Lindholm writes:
  13.  
  14. > ... to get rid of unsafe variables (by immediately globalizing
  15. > them -- I hope that's what we are talking about!).
  16.  
  17. That is indeed what I meant: put_yvar doesn't store an UNDEF in the
  18. environment, but a REF to the heap where an UNDEF is stored.
  19.  
  20. I try to list the advantages and the disadvantages + possible remedies:
  21.  
  22.     + trail test is cheaper (1): one comparison
  23.     + no put_unsafe_yval: it is replaced by a put_yval
  24.     + no overhead in unify_yval to avoid pointers from heap to local stack
  25.     + possibly less trailing (2)
  26.  
  27.     - more heap usage (3)
  28.     - reference chains become longer (4)
  29.  
  30.  
  31. (1) some people would say this is no advantage: it is sometimes claimed
  32.     that ALWAYS trailing (without testing) is the best ...
  33.  
  34.  
  35. (2) Perhaps you will find the following a somewhat contrived example, but here it is:
  36.  
  37.     a :- b , c(Y) , d(Y) .
  38.  
  39.     b .
  40.     b .
  41.  
  42.     c(1) .
  43.  
  44.     With unsafe variables, Y is in an old part of the local stack when it is bound to 1,
  45.     so that this binding is trailed. (Mind you: this is true for WAM not for VAM)
  46.     Without unsafe variables, Y is in the most recent part of the heap (it is created
  47.     on the heap after the choicepoint for B was created), so that the binding
  48.     of Y to 1 is not trailed.
  49.  
  50.     Since most Prolog programs are deterministic (sic), and since the extra trailing
  51.     requires the choicepoint, you can make your conclusions yourself.
  52.  
  53.  
  54. (3) At the time we got rid of unsafe vars, we worried little about higher heap
  55.     consumption because BIMprolog was probably the only commercial Prolog with
  56.     a garbage collector (maybe M-Prolog had one as well ?). Still, I put an option
  57.     in the compiler which would count the number of permanent variables in the program
  58.     and the number of put_yvar instructions generated, so that I could have an idea
  59.     of the relative importance of unsafe variables. And the figures looked ok.
  60.     Now I think that these figures don't give much information, because
  61.     environments are deallocated on forward execution, and heap is not.
  62.     I observed extra heap usage in the order of 50% for typical programs - but here
  63.     is a program that needs no gc in SICStus (which has unsafe vars) and
  64.     repeatly for BIM:
  65.  
  66.     a :- b(X) , c(X) , a .
  67.     b(1) .
  68.     c(_) .
  69.     ?- a .
  70.  
  71.     We have the same experience as in VAM that by doing something about builtin
  72.     predicates, the extra heap cost becomes lower.
  73.  
  74.  
  75. (4) This can be easily remedied by the introduction of some new instructions, e.g.
  76.  
  77.     a :- b(Y) , c(Y) . is compiled in WAM to
  78.  
  79.     allocate
  80.     put_yvar Y,1
  81.     call b/1
  82.     put_unsafe_yval Y,1 (*)
  83.     deallocate
  84.     execute c/1
  85.  
  86.     the instruction with the (*) is replaced by put_deref_yval Y,1 which does
  87.     something like:
  88.     
  89.         ArgReg[1] := *E[Y]  % this is safe because E[Y] always contains
  90.                     % a ref after a put_yvar of Y
  91.  
  92.     Without this, refchains might become longer and the introduction of these
  93.     instructions was good for performance. (sorry, I have currently no figures,
  94.     perhaps once later).
  95.  
  96. I used to like not having unsafe variables - recently I am not so sure any more.
  97. What were Aquarius reasons for choosing not to have them ? I guess that with its
  98. global analysis, they occur very infrequent, so the heap penalty is neglectable.
  99.  
  100. Two more remarks: I want to make a link with BinProlog (by the way, the
  101. relation between BinProlog and BIMProlog as not the same as between Nu-Prolog
  102. and Mu-Prolog !) or a continuation based implementation of Prolog:
  103. continuations on the heap actually means also environments on the heap, so that
  104. it in fact puts uninitialized 'permanent' variables on the heap. Still, it trails as
  105. much as a WAM implementation with unsafe variables. And it is difficult to get rid
  106. of the extra dereference every time the variable is accessed.
  107.  
  108. Finally, the unsafe variables fall in the category of variables that are called
  109. 'unnecessary' variables by Proietti&Pettorossi and in a PLILP'91 paper they
  110. describe how eliminate them (in logic programs, but their approach can be
  111. applied to Prolog as well). Hoorah, unsafe is unnecessary at last :-)
  112. No kidding, I think the work by Proietti&Pettorossi is very important for anybody
  113. interested in program transformation and compilation.
  114.  
  115. Bart Demoen
  116.  
  117.