From: Jeff Dalton
Subject: Re: What ``first-class'' means in comp.lang.misc
Date: 
Message-ID: <4021@skye.ed.ac.uk>
In article <···@smds.UUCP> ··@smds.UUCP (Stephen E. Witham) writes:

>Bravo.  If this means that the standard of "first-class" has been raised,
>then let it be raised.  Someone (sorry, forget who) asked sarcastically
>whether Scheme introduced the concept of "first-class".  The answer is,
>in many ways, yes.  Any lesser definition is, well, second-class.

I think it's unlikely that the concept was introduced by Scheme.  It
occurred as early as 1968 in the Pop literature, and the importance
of first-class functions was already recognized.  (See one of the
early volumes of Donald Michie's _Machine Intelligence_ literature.)
I once asked Robin Popplestone (one of the inventors of Pop) where the
idea had come from, and he thought it had been "in the air" at the
time.  He remembered someone (Burstall?)  going around quoting Quine's
"to be is to be the value of a variable".

I have also heard the suggestion that the idea came from Strachey's
group at Oxford.  It certainly appears in the literature on denotational 
semantics, in particular in Stoy's book (MIT Press).  I suspect that
the work on denotational semantics led to an increased emphasis on the
lambda calculus at places such as MIT and hence to Scheme as an
"extended lambda calculus".

Once Scheme was off the ground, it became necessary to distinguish
it from other dialects of Lisp and also from the languages in the
Algol family.  Two important ideas for this purpose were referential
transparency and the first-class status of functions.

Some of the issues raised under the topic "first class" are often
raised under the topic "orthogonality" when discussing the Algol
languages.  Orthogonality is usually considered a matter of syntax,
while "first class" concerns values, but I think we can see some
of the language of orthogonality in Norman Graham's

   the language must allow the value to appear in any syntactic
   construct in which other values may occur.

Norman Graham and Dave Berry (and others) are surely right in making
"first class" be, to some extent, relative to the language.  It wouldn't
do to require first class values to be subject to assignment in a
language that didn't have assignment, for example.  

However, there is also a pragmatic component to "first class".  We
don't actually require that the value can appear in _any_ construct
in which other values can occur, nor do we require that _all_
non-domain-specific operations be applicable if we take Dave Berry's
definition:

   I would say that entities of a language L are first-class if all
   generic operations (i.e. not domain-specific operations) that can
   be applied to other entities of L can also be applied to the
   entities in question.

In particular, we do not require that first class values all have a
printed representation so that they can be input and output -- and
there are languages in which i/o is a syntactic context (eg, a print
statement in Basic) or a non-domain-specific operation (eg, write in
Scheme).  This point might also be made about Dave Berry's suggestion
that 

   for entities in C to be first-class, it must be possible to
   allocate them dynamically.

So, when we want to state what we actually do require it often makes
sense to make an explicit list, a "bill of rights".  However, the
usual aim of such is list is to give the reader the right idea rather
than to make a precise definition.  This may account for some of the
glaring omissions from some of the lists as cited in Dan Bernstein's
message:

   All the other definitions disagree with each other on some
   particular.  Must it be possible to return first-class objects
   from functions?  Not if you believe Dybvig (as quoted by Dickey).
   Must it be possible to pass them as arguments? Not if you believe
   Clinger (as quoted by Ozan). Are C's integers first-class? Only
   if you believe Lennart.

One more thing.  When we talk about "first class functions" and
whether a language has them (and similarly for objects other than
functions), it isn't _just_ a matter of relative status within a
language.  Suppose, for example, we had a language in which no
values could be passed to procedures.  All values would have the
same status in this respect, but would any of them be first-class?
I think it makes sense to say "no", even though there may be 
contexts where, strictly speaking, and given a certain meaning
of "first class", the answer would have to be "yes".

Of course, when I say "a certain meaning" there are surely some who
think "what about the (one) right meaning?"  In my opinion, we will
not be able to pin it down to One True Meaning without doing too
much violence to how the term has been used.  A technical, language-
relative definition of the sort suggested by Dave Berry will be
right for some purposes; but even then the pragmatic component may
be difficult to make precise.  In other cases, a partly language-
independent "bill of rights" may be more appropriate; and then we
may have to make exceptions for particular languages.  However, this
is not to say that all definitions are equally good, nor that we
can never answer such questions as whether functions in C are first
class.  Such questions are part of our attempt to make the concept
more precise.

(I think that was two more things.)

N.B. This is followup-to comp.lang.misc.  You may want something else.

- jd