etymology of "list comprehension"?

[David C. Ullrich]

In article <7xej1o8i12.fsf at ruckus.brouhaha.com>,
 Paul Rubin <http://phr.cx@NOSPAM.invalid> wrote:

> mh at pixar.com writes:
> > Ah, thanks... and does "comprehension" have any special computer
> > science meaning?
> 
> It is from mathematical set theory.  If you write something like
> 
>    { p | [some logical expression indicating that p is prime] }
> 
> then that denotes a set (the set of all prime numbers).  That every
> such formula names a set is called the axiom of comprehension.  The
> above notation is sometimes called set-builder notation.
> 
> Frege's original system of logic (late 19th century), now called
> "naive set theory" had "unrestricted comprehension" which meant
> you could say anything at all where the logical expression went.
> This made the system inconsistent, because of Russell's paradox
> ("c is the class of all classes that are not members of themselves.
> So is c a member of itself?").  
> 
> Axiomatic set theory has a restricted axiom of comprehension that
> requires the logical expression to be a first order formula with
> a certain syntax, to avoid such paradoxes.

Not that it matters, but the fix is not by using a first-order
formula with a certain syntax. The comprehension itself is
not 

           {p | p satisfies some condition}, 

it's

           {p in S | p satisfies some condition},

where S is some set. You're not allowed to ask for _everything_
satisfying a certain condition, just for the elements of
some given set satisfying the condition.

The paradox doesn't come from being allowed to say anything
at all. If you write

(*)          c = {x | ~(x e x)}

(where ~ means "not" and "a e b" means "a is an element of b")
you get Russell's paradox: if c is an element of c then it follows
that c is not an element of c, while if c is not an element of c
then it follows that c is an element of c. The problem is not
with the formula ~(x e x); given a set S, there's no problem
with the set {x in S | ~(x e x)}, for example. "restricted"
versus "unrestricted" does not refer to some restriction on
that formula - the "restriction" in restricted comprehension
is the "x in S" part - we're restricting things to elements
of a given set S.

Writing informally people often omit the "in S" part when the
S in clear from the context. For example, your original
{p | p is prime} should officially be {p in N | p is prime},
where N is the set of natural numbers - the first form is 
often written because the "in N" is implicit in "prime".

> Anyway, list comprehensions in programming languages got their
> name because of their resemblance to set-builder notation that
> invoked the axiom of comprehension.

-- 
David C. Ullrich