home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / prolog / 2278 < prev    next >
Encoding:
Text File  |  1992-12-21  |  2.1 KB  |  51 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!haven.umd.edu!decuac!pa.dec.com!decprl!decprl!dumant
  3. From: dumant@prl.dec.com (Bruno Dumant)
  4. Subject: Re: Occurs check
  5. Message-ID: <1992Dec21.104802.11246@prl.dec.com>
  6. Sender: news@prl.dec.com (USENET News System)
  7. Nntp-Posting-Host: prl304.prl.dec.com
  8. Organization: Digital Equipment Corporation - Paris Research Laboratory
  9. References: <1992Dec13.173016.8849@nntp.hut.fi> <1992Dec17.111142.24450@dcs.qmw.ac.uk> <24435@alice.att.com> <1992Dec17.185017.17766@cs.uoregon.edu>
  10. Date: Mon, 21 Dec 1992 10:48:02 GMT
  11. Lines: 38
  12.  
  13.  
  14.  Saumya Debray writes:
  15.  > 
  16.  > Fernando Pereira writes:
  17.  > > Nonetheless, the efficiency reasons that led to Prolog's
  18.  > > unification not having the check are pretty compelling, so I do not advocate
  19.  > > adding it to Prolog in all cases. 
  20.  > 
  21.  > While I believe this statement, it would be interesting to actually see some
  22.  > numbers (preferably for programs other than nrev) showing how much more
  23.  > expensive unification becomes with the occurs check.  Do the implementors
  24.  > of Sepia, NU-Prolog, and other systems that provide both kinds of
  25.  > unification have any numbers they'd care to post?
  26.  
  27.  Some benchmarks were published in a paper presenting an architecture design of
  28.  a RISC processor for Prolog, in which the occur-check is always performed if
  29.  necessary. They use the WAM, and take advantage of the fact that only
  30.  get_value instructions really need to call the occur-check routine. According
  31.  to their results, 5 % of the time is spent performing the occur-check... It's
  32.  not that much !! Their benchmark programs include quite large programs, up to
  33.  5600 lines. 
  34.  
  35.  With some analysis (even a simple groundness analysis can be useful, but there
  36.  are also some more sophisticated analysis schemes), I'm sure that on most
  37.  programs, the overhead of the occur-check on a compiled Prolog can be negligible.
  38.  
  39.  
  40.  Reference:
  41.  
  42.  @inproceedings{ DRSW-89,
  43.        author = "Peter Dreussen and Wolfgang Rosentiel and Klaus Erik Schauser and
  44.                  J{\"{o}}rg Wedeck",
  45.        Title  = "{Architecture Design of a RISC Processor for Prolog}", 
  46.        Booktitle = "Euromicro 89",
  47.        Year      =  1989 }
  48.  
  49.  
  50.  B. Dumant
  51.