home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1360 < prev    next >
Encoding:
Text File  |  1992-11-12  |  2.6 KB  |  79 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!snorkelwacker.mit.edu!ai-lab!cs.tu-berlin.de!wg
  3. From: wg@opal.cs.tu-berlin.de (Wolfgang Grieskamp)
  4. Subject: Re: Is efficient backtracking feasible in functional languages?
  5. Message-ID: <1992Nov12.220621.14143@cs.tu-berlin.de>
  6. Followup-To: comp.lang.functional
  7. Sender: news@cs.tu-berlin.de
  8. Reply-To: wg@cs.tu-berlin.de
  9. Organization: Technical University of Berlin
  10. References: <1992Nov11.171742.18783@eua.ericsson.se> <lg3071INN8m1@exodus.Eng.Sun.COM>
  11. Date: Thu, 12 Nov 1992 22:06:21 GMT
  12. Lines: 65
  13.  
  14.  
  15. >   strangesucc n =    hd [x|x<-[0..];x>n];
  16. >   ...
  17. >   [Major collection... 21% used (3397260/15733684), 1920 msec]
  18. >   ...
  19. >   GC Stack Overflow !
  20.  
  21. Whats funny with this example that the stream (lazy list) in the list
  22. comprehension can be seen as an imperative counter which is
  23. communicated to the consumer (hd):
  24.  
  25.     x := 0;
  26.     while (1){
  27.       if (x > n) output(x);
  28.       x++;
  29.     }
  30.  
  31. We have prototyped a scheme for the compilation of streams which
  32. (nearly) essentially result in such an imperative counter. (Its not
  33. published, but believe, its fairly easy). Its embedded in the approach
  34. of mixed compile-time and run-time garbage collection via the
  35. reference counting model described in [SG91] [Sch92].
  36.  
  37. It would use constant space for the example, i.e. one cell for the
  38. current "head" of the stream. The head becomes reused if the next
  39. element is demanded by the consument. A stupid straight-forward
  40. compilation would generate a run-time test for the reference counter
  41. of the cell to prove this reusability; a simple sharing analysis would
  42. even eliminate the test at all in the given example (it can easy
  43. detect that their is no context which can share the stream).
  44.  
  45. Well, we have never implemented the scheme, since streams have been
  46. dropped from the language design we consider ([Pep91]).
  47.  
  48.  
  49. @InProceedings{SG92,
  50.   author =      {Wolfram Schulte and Wolfgang Grieskamp},
  51.   title =       {Generating {E}fficient {P}ortable {C}ode for a
  52.                  {S}trict {A}pplicative {L}anguage},
  53.   booktitle =   {Phoenix Seminar and Workshop on Declarative Programming},
  54.   year =        {1992},
  55.   publisher =   {Springer-Verlag}
  56. }
  57.  
  58. @PhDThesis{Sch92,
  59.   author =      {Wolfram Schulte},
  60.   title =       {Zur {\"U}bersetzung strikter applikativer
  61.                  {P}rogrammiersprachen},
  62.   school =      {Techincal University of Berlin},
  63.   year =        {1992}
  64. }
  65.  
  66. @TechReport{Pep91a,
  67.   author =      {P. Pepper},
  68.   title =       {The Programming Language OPAL},
  69.   institution = {Technical University of Berlin},
  70.   year =        {1991},
  71.   type =        {},
  72.   number =      {91-04},
  73.   month =       {Apr},
  74. }
  75.  
  76. --
  77. Wolfgang Grieskamp  
  78. wg@cs.tu-berlin.de 
  79.