jeff@aiai.ed.ac.uk (Jeff Dalton) (01/29/91)
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.) N.B. This is followup-to comp.lang.misc. You may want something else. - jd