Re: First-class data types

Here are a couple of articles from the January 1991 first-class debate in
comp.lang.misc. I think they're lucid accounts of the first-class
principle (after all, I _did_ write one of them :-).


I hope the lack of context for these articles does not detract too much
from the points they're trying to make. The general debate centered around
the question of the first-class status (or lack thereof) of functions,
function pointers, and structures in C.


--- Begin included messages ---
Newsgroups: comp.lang.misc
Reply-To: norman@d.cs.okstate.edu (Norman Graham)
Subject: Re: What ``first-class'' means in comp.lang.misc
Date: Wed, 9 Jan 91 06:13:40 GMT


>From article <25449:Jan823:00:2991@kramden.acf.nyu.edu>, by Dan Bernstein:
> There is certainly some confusion here over what ``first-class'' means.
> Here's a summary of what several people have said about first-class
> objects in recent discussions here.


Thanks for the nice summary Dan: I had missed part of the discussion.


> Three people---Dave Gudeman, Norman Graham, and I---seem to agree on a
> single definition of first-class. Among other things, the definition
> implies that function pointers in C and structures in ANSI C are
> first-class, and that structures in pre-ANSI C are not first-class.


Since Dan has tried to determine my definition of 'first-class' by reading
between the lines of my previous postings, I think it's prudent for me to
state my position clearly.


First, note that the following is IMHO only; I realize there are other
viewpoints that may or may not have merit. Bear in mind that these are off
the cuff remarks, not a publication quality position paper.


Now, this is how I define the concept of 'first-class' (as it applies to
values in programming languages): We may call a value (or a range of
values represented by a data type) a 'first-class citizen' of a language
iff the language in question does not in any way _discriminate_ against
the value (or any value in the range of values). By the phrase 'does not
discriminate against' I mean the language must allow the value to appear
in any syntactic construct in which other values may occur. Now this is a
fairly general definition--we rely on typechecking to flag nonsensical
constructs. Note that this definition does not rely on a particular
feature set: The 'first-class' feature set will vary from language to
language.


For example, if the language allows values to be passed to funcitons, yet
it does not allow a certain value to be passed to functions, then that
value is not first-class. If it allows values to be named, yet it does not
allow a certain value to be named, then the language discriminates against
the value and the value is a second-class citizen of the language (that
is, the value does not have all the 'rights' that a first-class value
has). If a language allows values to be used directly (i.e. without being
named), then any value that the language requires to be named cannot be
called a first-class value. I believe most will agree with these examples.


One of the benifits of giving 'first-class' status to all the values
representable in a language is that you get a clean set of rules governing
how you can manipulate values in the language. When a language retreats
from this position (by incorporating second-class values) the set of value
manipulation rules becomes more complicated as more and more special cases
are added to restrict the areas where the second-class values may be used.


> In <1991Jan7.154111.5166@d.cs.okstate.edu>, Norman Graham says that C
> has first-class function pointers. He distinguishes between first-class
> functions and first-class function pointers.


That's my opinion. As far as I know, C does not discriminate against
function pointers in any way. On the other hand, in C, functions can
hardly be called values at all: The only operations you can perform on
them is to take their address (which some compilers will do implicitly for
you in some situations) and to call them with their formal parameters (if
any) instantiated to the actual arguments. In particular, in C, the
function value itself cannot be stored in a variable, cannot be passed to
or from functions, cannot be given a name other than its name of
definition, and cannot be used directly (without a name). Since C allows
these operations on other values, I can only conclude that C gives
functions a second-class status.


There are good, practical reasons for not conferring upon some values the
status of 'first-class'. For example, efficiency springs to mind. But
language definitions are more simple (hence easier to learn and use) when
the addition of second-class values is kept to a minimum.
-- Norman Graham


<norman@a.cs.okstate.edu> {cbosgd,rutgers}!okstate!norman


----------------------------------------------------------------------


Reply-To: jeff@aiai.ed.ac.uk (Jeff Dalton)
Newsgroups: comp.lang.misc,comp.lang.scheme,comp.lang.lisp
Subject: Re: What ``first-class'' means in comp.lang.misc
Date: 28 Jan 91 19:14:13 GMT
Organization: AIAI, University of Edinburgh, Scotland


In article <292@smds.UUCP> sw@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.)


- jd
--- End of included messages ---
--

Return to the comp.compilers page.
Search the comp.compilers archives again.