home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / function / 1378 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  1.7 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!decwrl!sun-barr!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!mailgzrz.TU-Berlin.DE!cs.tu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!chalmers.se!cs.chalmers.se!augustss
  2. From: augustss@cs.chalmers.se (Lennart Augustsson)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Is efficient backtracking feasible in functional languages?
  5. Keywords: lazy backtracking Gofern
  6. Message-ID: <1992Nov17.042026.19290@cs.chalmers.se>
  7. Date: 17 Nov 92 04:20:26 GMT
  8. References: <TMB.92Nov12122350@arolla.idiap.ch> <1992Nov12.162725.25836@cs.yale.edu> <BxM80r.1Hu@dcs.glasgow.ac.uk>
  9. Sender: news@cs.chalmers.se (News administrator)
  10. Organization: Chalmers University of Technology
  11. Lines: 20
  12.  
  13. The Haskell program
  14.     ss n = head [ x | x<-[0..], x>n ]
  15. does indeed use linear space with hbc 0.998.5.  The reason for this is
  16. that all Prelude functions (in this case head) are compiled without
  17. overwriting the root redex.  If you define your own head function
  18. the program runs in constant space (416 bytes to be exact).  The reason for
  19. not overwriting the root redex has nothing todo with efficiency 
  20. consideration; "zapping" the redex only takes about 3% longer.
  21. The reason is that I wanted the Prelude functions to work with
  22. the interactive system.  Zapping (blackholing) does not work well with
  23. the interactive system because here you can interrupt computation with ^C
  24. (admittedly not entirely clean), and the graph should be in a consistent
  25. state if you do.  Having black holes around makes it inconsistent (or at least
  26. unusable).  
  27. I hope to have the Prelude compiled with zapping in the next release.
  28.  
  29. -- 
  30.  
  31.     -- Lennart Augustsson
  32. [This signature is intentionally left blank.]
  33.