🚀 go-pugleaf

In article <9910@uqcspe.cs.uq.oz.au>, michaeln@cs.uq.oz.au (Michael Norris) writes:
> A quick question.
> 
> Where can I find good definitions of the words relating to
> functional programming? ...
> 
> Specifically,
> 	...
> 	list comprehension
> 	...


You may be interested in the note, attached below, which I wrote recently.

Regards,

Nikhil
------------------------------------------------------------
NAME:      Rishiyur S. Nikhil
EMAIL:     nikhil@crl.dec.com
TELEPHONE: (617) 621 6639        FAX : (617) 621 6650
ADDRESS:   Digital Equipment Corporation,
           Cambridge Research Laboratory,
           One Kendall Square, Bldg. 700, Cambridge, MA 02139, USA
================================================================

	NOTES ON THE ORIGIN OF THE TERM ``LIST COMPREHENSION''
			   Rishiyur Nikhil
			    September 1991
		 (revised January 1992, August 1992)

Recently, I did a little research into the origins of the term ``list
comprehension'' (since I wanted to attribute it correctly in a book
that I am writing).  I corresponded with several people, including
Phil Wadler, Rod Burstall and John Darlington.  This is what I learned
(of course, I'd be happy to receive comments/corrections to this
account).

The term itself seems to have been coined by Phil Wadler circa
1983-1985, although the programming construct itself goes back much
further (most likely Jack Schwartz and the SETL language).

The earliest reference to the notation that I have is in the following
paper:

    ``Program Transformation and Synthesis: Present Capabilities''
    John Darlington
    Research Report No. 77/43, Dept. of Computing and Control, Imperial
    College of Science and Technology, London (also appears as
    Report No. 48, Dept. of Artificial Intelligence, U. of Edinburgh)
    September 1977

which describes a functional language called NPL, designed by Rod
Burstall and John Darlington.  The report contains the following
passage:

    ``In addition, NPL allows certain sets and logic constructs to appear
    on the right hand side, for example

        setofeven(X) <= <:x: x in X & even(x) :>

    ...

    ... NPL allows certain sets and logic constructs on the right hand side
    of equations.  The concrete syntax of these constructs is:

        setexpression ::= <:expression: generator* :>
        ...
        generator     ::= variable IN expression (range) * expression (condition)

    The NPL interpreter evaluates the list of generators in a left to right
    fashion so conditions can mention any bound variables that occur to
    their left.''

and, amusingly:

    ``The interpreter is able to run many programs written
    using these facilities, but some program written are horrendously
    inefficient while others are not runnable as they stand.''

In that report, Darlington also goes on to show how to implement these
expressions by transformation (similar to the translation shown by
Wadler in Peyton Jones' book [Ch. 7, The Implementation of Functional
Languages, Simon L. Peyton Jones, Prentice Hall 1987]).

The following contemporary paper also discusses the set expression
notation in NPL:

    "Design Considerations for a Functional Programming Language",
    Burstall, Rod M.,
    in "Infotech State of the Art Conference: The Software Revolution,
        Copenhagen"
    October 1977

The paper contains the following passage, where Burstall attributes
the notation originally to Schwarz and SETL (he also mentioned this to
me in a personal communication).  The concrete syntax seems to have
changed slightly:

  ``To make it easier to work with sets, we permit a notation very similar
    to mathematical usage (following Schwarz in his SETL language).
    Suppose for example that we already have constants s and t denoting
    sets of numbers, then a typical set expression would be

        {i + j : i in s, j in union (s,t) & i < j}

    The general form is:

        {EXPRESSION : VARIABLE in EXPRESSION & EXPRESSION, ...,
                      VARIABLE in EXPRESSION & EXPRESSION}

    We also allow explict sets like {1,2,3}.  So

        {i+j : i in {1,2,3}, j in {1,2,3} & i = j}   is  {2,4,6}''

John Darlington says that he and Rod Burstall introduced the notation
into NPL to make up for the lack of higher-order capability in NPL.
This was shortly after Darlington came to Edinburgh for his Ph.D.
straight after a degree at the London School of Economics which
included a fair bit of logic and in particular ZF (Zermelo-Frankel)
set theory.

Darlington also says that at the same time Richard Waldinger at SRI
was using the same constructs as specification lannguage for his
program synthesis work.

David Turner subsequently adopted this notation in his languages SASL,
KRC and Miranda*, where he has called them ``zf expressions'' (in his
1981 FPCA paper [The Semantic Elegance of Applicative Languages])
set-abstractions and list-abstractions (in his 1985 FPCA paper
[Miranda: A Non-Strict Functional Language with Polymorphic Types]).

Phil Wadler says he believes he originated the term ``list
comprehension'' after a conversation with John Hughes, where he
bemoaned the current nomenclature and Hughes reminded him of the
existing term ``set comprehension''.  The term ``list comprehension''
appears in the following:

    ``The OL Manual''
    Philip Wadler, Quentin Miller and Martin Raskovsky
    Probably 1983-1985 (my copy is undated)

The term ``list comprehension'' also appears in quotation marks in
Wadler's 1985 FPCA paper:

    ``How to Replace Failure by a List of Successes''
    FPCA September 1985, Nancy, France, pp 113-146

Interestingly, I have a pre-publication version of this paper dated
January 1985 where the term used in exactly the same place (last
sentence of para 2) is ``list abstraction'', i.e., it seems to have
been substituted by ``list comprehension'' in the intervening months
before publication.

----------------------------------------------------------------
* ``Miranda'' is a trademark of Research Software, Ltd.