brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/09/91)
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. 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. 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. Without further ado, here's the complete summary. I think the only statement we can all agree with is Lennart's claim that ``first-class'' has several definitions. In <304@coatimundi.cs.arizona.edu> Dave Gudeman defines ``first-class'' as follows: ``The type of the object in question can be passed as an argument to procedures and returned from procedures as a result. In procedural languages like C, it also means that you can assign the values to variables.'' He says that C's function pointers are first-class. (Just in case somebody's been asleep through this discussion: This is the same definition that I'm familiar with, and I agree with the conclusion.) In <1990Dec19.222059.6878@mathrt0.math.chalmers.se> Lennart Augustsson made a claim that, if read literally, implies that first-class functions must be composable. In <1990Dec29.101233.1894@mathrt0.math.chalmers.se> Lennart says that ``first-class'' has several definitions. One of them, he says, is this: ``For a type to be first class it should be possible to do the same things with its objects as with objects of other types, such as integers.'' He says that this includes not only argument passing but ``be expressible without giving it a name.'' He says that (ANSI) C's structures are not first-class, but that gcc's structures are, because gcc lets you write unnamed struct values. In <1991Jan7.185658.20240@basho.uucp> John Lacey says that ``first-class'' implies having ``the right to be anonymous.'' In <20021@yunexus.YorkU.CA> Ozan Yigit quotes William Clinger. Clinger doesn't actually claim to define ``first-class'' in the quoted material, but Ozan appears to believe that the properties listed form a definition: having the right to remain anonymous, having an identity independent of any names by which the object may be known, being storable in variables and in data structures without losing their identity, being returnable from a procedure, and never dying. 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. Finally, to complete this comedy of definitions, Ken Dickey claims in <442@data.UUCP> that first-class objects do not have to be named, and in <443@data.UUCP> quotes Guy Steele. According to Steele, ``full-fledged'' objects may be passed as arguments, returned as values, made part of composite data structures, and notated as independent, unnamed entities. He also quotes Kent Dybvig: ``Procedures are first-class data objects similar to strings or numbers; identifiers are bound to procedures in the same way they are bound to other objects.'' If we take this as a definition, then ``first-class'' means only the identity properties listed by Clinger, and does not include argument passing. ---Dan
db@cs.ed.ac.uk (Dave Berry) (01/09/91)
I don't believe it makes sense to define the attributes required for an entity to be first-class without parameterising the definition on a particular language. 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 functional languages, this is often (erroneously) summarised as being able to pass entities to functions and return them from functions. Lennart pointed out that this definition is inadequate; for entities to be first-class it must be possible to write them anonymously. IMO, the previous discussion clearly shows that for entities in C to be first-class, it must be possible to allocate them dynamically. This makes sense - if there were "first-class" entities in C that couldn't be so allocated, while all/most other entities could be so allocated, then to what class would the allocatable entities belong? Super executive club class with a champagne breakfast? :-) The list of attributes given for first-class entities in Scheme may well be an accurate definition of what "first-class" means in Scheme. It doesn't mean (IMO) that entities in another language should have to satisfy those requirements to be first-class with respect to that language. Since most languages include procedures, functions, or similar constructs that involve passing arguments and returning values, it follows that this is a pretty common requirement for entities to be firt-class. I can't think of any language in which it is sufficient (though there may be such languages). >He also quotes Kent Dybvig: ``Procedures are first-class data objects >similar to strings or numbers; identifiers are bound to procedures in >the same way they are bound to other objects.'' If we take this as a >definition, then ``first-class'' means only the identity properties >listed by Clinger, and does not include argument passing. In most languages, entities are bound to identifiers when passed as arguments. In some languages, argument passing can be defined as a particular way of binding values to identifiers (Tennent's Principle of Correspondence). Possibly this applies to the language in question here. -- Dave Berry, LFCS, Edinburgh Uni. db%lfcs.ed.ac.uk@nsfnet-relay.ac.uk "The Berlin Wall; the border between East and West Germany. It's very narrow." "*Was* very narrow. Get your tenses right." -- Douglas Adams, THHGTTG.
guido@cwi.nl (Guido van Rossum) (01/10/91)
Here's a different opinion. You are all fighting over the wrong issue. As I read them, all those "definitions" of first-class don't really define it, but merely use a convenient term to convey a somewhat vague but useful idea which is then explained more precisely. The real problem with C functions (compared to Scheme or Lisp functions, for instance) is that their "closure" only contains global variables. This can be remedied by explicit closure parameters, and wrapper functions, but it still is a real nuisance if your programming style needs it a lot. It is even worse if you are using a library provided in object form only (no source) and there are interfaces that require you to pass a function pointer but don't allow you to pass an extra parameter for the closure -- you are forced to use globals which defeats reentrancy. On the other hand, the problem is no worse than the lack of built-in dynamic data structures (such as variable-size arrays) in C -- everybody knows how to roll their own, and for some this possibility is essential because it means they aren't stuck with a built-in feature that may be too slow or inflexible for a particular application. -- Guido van Rossum, CWI, Amsterdam <guido@cwi.nl> "It's probably pining for the fiords"
bevan@cs.man.ac.uk (Stephen J Bevan) (01/10/91)
In <2772@charon.cwi.nl> guido@cwi.nl (Guido van Rossum) writes :- > As I read them, all those "definitions" of first-class don't really > define it, but merely use a convenient term to convey a somewhat vague > but useful idea which is then explained more precisely. I disagree. The definition given by Norman Graham (<1991Jan9.061340.21668@d.cs.okstate.edu>) seems to capture exactly what it means for an object to be first-class. I don't see anything vague in the idea at all. > On the other hand, the problem is no worse than the lack of built-in > dynamic data structures (such as variable-size arrays) in C -- everybody > knows how to roll their own, and for some this possibility is essential > because it means they aren't stuck with a built-in feature that may be > too slow or inflexible for a particular application. The efficiency argument (yet) again. There are a number of reasons for writing a whole application in a single language%. However, I don't think efficiency is one of them. I'm sure everybody knows the following steps :- Write in a high level language. Profile it. Identify the bottlenecks. Re-code or re-write in a lower level language. However, most seem to equate ``high level langauge'' with C and low level language with assembler. Why not try ``high level langauge'' = Scheme* and ``low level language'' = C. It works for me, your mileage may vary. Stephen J. Bevan bevan@cs.man.ac.uk % I'm currently in the middle of writing a medium sized C program (20,000 LOC). I would prefer to write in some other language (preferably Scheme/CommonLisp) , but I'm constrained by what compilers other people have. * Replace by your personal favourite e.g. Prolog, Smalltalk, CommonLisp, Self, Icon, ... etc.
gudeman@cs.arizona.edu (David Gudeman) (01/11/91)
In article <2772@charon.cwi.nl> Guido van Rossum writes:
]The real problem with C functions (compared to Scheme or Lisp functions,
]for instance) is that their "closure" only contains global variables.
I'd say this is one of the major parts of the disagreement over the
meaning of "first-class". Some people are trying to use the term to
compare C functions with Lisp functions, however the term is not
supposed to compare features of different languages, it is meant to
compare features of a single language.
Obviously C does not have the powerful functionals that Lisp has, but
I don't think the difference should be stated in terms of "first
class". A better characterization would be "C does not have
functionals" or "C does not have closures", or "You cannot dynamically
create functions in C". All of which are true (modulo a convenient
definition of "functional").
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemanoz@yunexus.yorku.ca (Ozan Yigit) (01/11/91)
In article <25449:Jan823:00:2991@kramden.acf.nyu.edu> Dan Bernstein writes: >Three people---Dave Gudeman, Norman Graham, and I---seem to agree >on a single definition of first-class. I think I missed that definition. Would you completely spell it out for me? Who's definition is it? Thnx. >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). I don't think the ones quoted from scheme literature differ at all, and the proof of the pudding is the language itself. On the other hand, your confusion is understandable. The quoted authors do not attempt to supply a pedantic enumeration of ``first-class-ness'', rather, they simply mention that which is typically omitted from some [only some] other languages. Neither Dybvig, nor Clinger imply what you presume they do. [take my word for it, or you can contact them via e-mail ;-)] Incidentally, those definitions were posted only to address your appearent disbelief in some particulars of ``first-class functions''. >I think the only statement we can all agree with is Lennart's claim that >``first-class'' has several definitions. I am not convinced that this is true. oz --- Yellow pages is evil. All traces of | Internet: oz@nexus.yorku.ca it must be vanguished from the face. | Uucp: utzoo/utai!yunexus!oz of the earth -- Eriks Rugelis | Phone: 1+ (416) 736 5257 ..
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