home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / function / 1022 < prev    next >
Encoding:
Text File  |  1992-08-20  |  6.3 KB  |  168 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!decwrl!deccrl!news.crl.dec.com!nikhil
  3. From: nikhil@crl.dec.com (R.S. Nikhil)
  4. Subject: Re: Definitions
  5. Message-ID: <1992Aug20.162659.10144@crl.dec.com>
  6. Sender: news@crl.dec.com (USENET News System)
  7. Organization: DEC Cambridge Research Lab
  8. References:  <9910@uqcspe.cs.uq.oz.au>
  9. Date: Thu, 20 Aug 1992 16:26:59 GMT
  10. Lines: 156
  11.  
  12. In article <9910@uqcspe.cs.uq.oz.au>, michaeln@cs.uq.oz.au (Michael Norris) writes:
  13. > A quick question.
  14. > 
  15. > Where can I find good definitions of the words relating to
  16. > functional programming? ...
  17. > 
  18. > Specifically,
  19. >     ...
  20. >     list comprehension
  21. >     ...
  22.  
  23.  
  24. You may be interested in the note, attached below, which I wrote recently.
  25.  
  26. Regards,
  27.  
  28. Nikhil
  29. ------------------------------------------------------------
  30. NAME:      Rishiyur S. Nikhil
  31. EMAIL:     nikhil@crl.dec.com
  32. TELEPHONE: (617) 621 6639        FAX : (617) 621 6650
  33. ADDRESS:   Digital Equipment Corporation,
  34.            Cambridge Research Laboratory,
  35.            One Kendall Square, Bldg. 700, Cambridge, MA 02139, USA
  36. ================================================================
  37.  
  38.     NOTES ON THE ORIGIN OF THE TERM ``LIST COMPREHENSION''
  39.                Rishiyur Nikhil
  40.                 September 1991
  41.          (revised January 1992, August 1992)
  42.  
  43. Recently, I did a little research into the origins of the term ``list
  44. comprehension'' (since I wanted to attribute it correctly in a book
  45. that I am writing).  I corresponded with several people, including
  46. Phil Wadler, Rod Burstall and John Darlington.  This is what I learned
  47. (of course, I'd be happy to receive comments/corrections to this
  48. account).
  49.  
  50. The term itself seems to have been coined by Phil Wadler circa
  51. 1983-1985, although the programming construct itself goes back much
  52. further (most likely Jack Schwartz and the SETL language).
  53.  
  54. The earliest reference to the notation that I have is in the following
  55. paper:
  56.  
  57.     ``Program Transformation and Synthesis: Present Capabilities''
  58.     John Darlington
  59.     Research Report No. 77/43, Dept. of Computing and Control, Imperial
  60.     College of Science and Technology, London (also appears as
  61.     Report No. 48, Dept. of Artificial Intelligence, U. of Edinburgh)
  62.     September 1977
  63.  
  64. which describes a functional language called NPL, designed by Rod
  65. Burstall and John Darlington.  The report contains the following
  66. passage:
  67.  
  68.     ``In addition, NPL allows certain sets and logic constructs to appear
  69.     on the right hand side, for example
  70.  
  71.         setofeven(X) <= <:x: x in X & even(x) :>
  72.  
  73.     ...
  74.  
  75.     ... NPL allows certain sets and logic constructs on the right hand side
  76.     of equations.  The concrete syntax of these constructs is:
  77.  
  78.         setexpression ::= <:expression: generator* :>
  79.         ...
  80.         generator     ::= variable IN expression (range) * expression (condition)
  81.  
  82.     The NPL interpreter evaluates the list of generators in a left to right
  83.     fashion so conditions can mention any bound variables that occur to
  84.     their left.''
  85.  
  86. and, amusingly:
  87.  
  88.     ``The interpreter is able to run many programs written
  89.     using these facilities, but some program written are horrendously
  90.     inefficient while others are not runnable as they stand.''
  91.  
  92. In that report, Darlington also goes on to show how to implement these
  93. expressions by transformation (similar to the translation shown by
  94. Wadler in Peyton Jones' book [Ch. 7, The Implementation of Functional
  95. Languages, Simon L. Peyton Jones, Prentice Hall 1987]).
  96.  
  97. The following contemporary paper also discusses the set expression
  98. notation in NPL:
  99.  
  100.     "Design Considerations for a Functional Programming Language",
  101.     Burstall, Rod M.,
  102.     in "Infotech State of the Art Conference: The Software Revolution,
  103.         Copenhagen"
  104.     October 1977
  105.  
  106. The paper contains the following passage, where Burstall attributes
  107. the notation originally to Schwarz and SETL (he also mentioned this to
  108. me in a personal communication).  The concrete syntax seems to have
  109. changed slightly:
  110.  
  111.   ``To make it easier to work with sets, we permit a notation very similar
  112.     to mathematical usage (following Schwarz in his SETL language).
  113.     Suppose for example that we already have constants s and t denoting
  114.     sets of numbers, then a typical set expression would be
  115.  
  116.         {i + j : i in s, j in union (s,t) & i < j}
  117.  
  118.     The general form is:
  119.  
  120.         {EXPRESSION : VARIABLE in EXPRESSION & EXPRESSION, ...,
  121.                       VARIABLE in EXPRESSION & EXPRESSION}
  122.  
  123.     We also allow explict sets like {1,2,3}.  So
  124.  
  125.         {i+j : i in {1,2,3}, j in {1,2,3} & i = j}   is  {2,4,6}''
  126.  
  127. John Darlington says that he and Rod Burstall introduced the notation
  128. into NPL to make up for the lack of higher-order capability in NPL.
  129. This was shortly after Darlington came to Edinburgh for his Ph.D.
  130. straight after a degree at the London School of Economics which
  131. included a fair bit of logic and in particular ZF (Zermelo-Frankel)
  132. set theory.
  133.  
  134. Darlington also says that at the same time Richard Waldinger at SRI
  135. was using the same constructs as specification lannguage for his
  136. program synthesis work.
  137.  
  138. David Turner subsequently adopted this notation in his languages SASL,
  139. KRC and Miranda*, where he has called them ``zf expressions'' (in his
  140. 1981 FPCA paper [The Semantic Elegance of Applicative Languages])
  141. set-abstractions and list-abstractions (in his 1985 FPCA paper
  142. [Miranda: A Non-Strict Functional Language with Polymorphic Types]).
  143.  
  144. Phil Wadler says he believes he originated the term ``list
  145. comprehension'' after a conversation with John Hughes, where he
  146. bemoaned the current nomenclature and Hughes reminded him of the
  147. existing term ``set comprehension''.  The term ``list comprehension''
  148. appears in the following:
  149.  
  150.     ``The OL Manual''
  151.     Philip Wadler, Quentin Miller and Martin Raskovsky
  152.     Probably 1983-1985 (my copy is undated)
  153.  
  154. The term ``list comprehension'' also appears in quotation marks in
  155. Wadler's 1985 FPCA paper:
  156.  
  157.     ``How to Replace Failure by a List of Successes''
  158.     FPCA September 1985, Nancy, France, pp 113-146
  159.  
  160. Interestingly, I have a pre-publication version of this paper dated
  161. January 1985 where the term used in exactly the same place (last
  162. sentence of para 2) is ``list abstraction'', i.e., it seems to have
  163. been substituted by ``list comprehension'' in the intervening months
  164. before publication.
  165.  
  166. ----------------------------------------------------------------
  167. * ``Miranda'' is a trademark of Research Software, Ltd.
  168.