wmesard@oracle.com (Wayne Mesard) (09/14/90)
I seem to remember losing an argument a few years ago regarding whether or not Common Lisp functions were first class objects. The outcome was that they are not, but I can't remember why. Anyone? Thanks in advance. I will summarize any replies by email. Wayne();
jeff@aiai.ed.ac.uk (Jeff Dalton) (09/22/90)
In article <1990Sep13.202219.21047@oracle.com> wmesard@oracle.com (Wayne Mesard) writes: >I seem to remember losing an argument a few years ago regarding whether >or not Common Lisp functions were first class objects. The outcome was >that they are not, but I can't remember why. Common Lisp functions are first class. There are reasons why some people think otherwise, such as: * Functions aren't (now it's weren't) a distinct data type. Symbols and certain lists counted as fucntions. (That works just about as well to show that CL doesn't have 1st-class symbols or lists.) * Functions don't have components; there aren't any accessors. (That would show that Scheme didn't have 1st-class fns either, which indeed some people used to claim. Really.) * There are two namespaces with special binding forms (FLET, LABLES) and defining forms (DEFUN) for functions. (That's true, but CL could be used without them. The worst consequence is that calls would all have to use FUNCALL (which we'd have to regard as a special form). That's not a very nice syntax, but I don't see why it would make functions 2nd-class. But to show functions in CL aren't 1st-class you need a definition of "1st-class" that wasn't devised just to attack Common Lisp. And if you look at such lists, they're something like this: - All objects can be the arguments of procedures. - All objects can be returned as the results of procedures. - All objects can be the subject of assignment statements. - All objects can be tested for equality. This list is the modern form o"Pop design philosophy" list (1986) taken from Jonathan Laventhol's book "Programming in Pop-11" (written in 1987). Other such lists are similar. However, talk of equality does suggest one way in which Common Lisp might fall a bit short. It turns out that (flet ((f () 't)) (eq #'f #'f)) might return false. Of course, (let ((f #'(lambda () 't))) (eq f f)) always returns true. And that's good enough for me. -- Jeff
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (09/24/90)
In article <3437@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: > - All objects can be the arguments of procedures. > - All objects can be returned as the results of procedures. > - All objects can be the subject of assignment statements. > - All objects can be tested for equality. As far as I'm aware, "modern" "functional" languages like ML and Haskell do not define equality for functions (or for data types that contain functions as elements). I think that the Haskell people would be very upset if you told them functions weren't 1st class in Haskell. However, there is something clearly wrong with this list, because C can satisfy it, and functions aren't first-class in C. In C, a pointer to a function can be passed to a procedure, returned from a procedure, assigned to a variable, or compared for equality to another pointer of the same type. What's C missing? The ability to create (possibly) new functions at run time. From another perspective, *closures* as 1st-class values. In T I can (define (o f g) (lambda (x) (f (g x)) )) and then ((o car cdr) '(1 2 3)) ==> 2 In C, I cannot do this. Seems like an important difference to me. -- Heuer's Law: Any feature is a bug unless it can be turned off.
cowan@marob.masa.com (John Cowan) (09/25/90)
In article <3806@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <3437@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: >> - All objects can be the arguments of procedures. >> - All objects can be returned as the results of procedures. >> - All objects can be the subject of assignment statements. >> - All objects can be tested for equality. > >[T]here is something clearly wrong with this list, because C can >satisfy it, and functions aren't first-class in C. In C, a pointer to >a function can be passed to a procedure, returned from a procedure, >assigned to a variable, or compared for equality to another pointer of >the same type. This blurs the rigid distinction C makes between functions and pointers-to- functions. A pointer-to-function is a first-class C object; a function is not. >What's C missing? The ability to create (possibly) new functions at run time. That's not enough. There is no ability in Lisp to create "new" integers at run time; conceptually all the integers already exist. Ditto with all the characters. You cannot have a function in C that accepts a function as an argument or returns a function as a value. Nor can you assign functions. ANSI C relaxes the rules a little so that you can use the same syntax to call a function specified by name or by a pointer-to-function, but the two things are still different, and functions are very much 2nd-class. -- cowan@marob.masa.com (aka ...!hombre!marob!cowan) e'osai ko sarji la lojban
jeff@aiai.ed.ac.uk (Jeff Dalton) (09/25/90)
In article <3437@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: >But to show functions in CL aren't 1st-class you need a definition >of "1st-class" that wasn't devised just to attack Common Lisp. And >if you look at such lists, they're something like this: > > - All objects can be the arguments of procedures. > - All objects can be returned as the results of procedures. > - All objects can be the subject of assignment statements. > - All objects can be tested for equality. > >This list is the modern form o"Pop design philosophy" list (1986) Should be some other year, probably 1968. It's in one of the early volumes of the "machine Intelligence" series edited by Donald Michie. Sorry about that. -- Jeff
markf@zurich.ai.mit.edu (Mark Friedman) (09/25/90)
In article <3806@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: In article <3437@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: > - All objects can be the arguments of procedures. > - All objects can be returned as the results of procedures. > - All objects can be the subject of assignment statements. > - All objects can be tested for equality. However, there is something clearly wrong with this list, because C can satisfy it, and functions aren't first-class in C. In C, a pointer to a function can be passed to a procedure, returned from a procedure, assigned to a variable, or compared for equality to another pointer of the same type. What's C missing? The ability to create (possibly) new functions at run time. From another perspective, *closures* as 1st-class values. In T I can (define (o f g) (lambda (x) (f (g x)) )) and then ((o car cdr) '(1 2 3)) ==> 2 In C, I cannot do this. Seems like an important difference to me. I hate to say it, but C does have closures of a sort. The environment of a C procedure is the union of the bindings of the visible external variables and the bindings of the static internal variables declared in that procedure. What C does not have is general lexical scoping, therefore C closures do not have all the properties that we might like. -Mark -- Mark Friedman MIT Artificial Intelligence Lab 545 Technology Sq. Cambridge, Ma. 02139 markf@zurich.ai.mit.edu
jeff@aiai.ed.ac.uk (Jeff Dalton) (09/26/90)
In article <3806@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <3437@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: >> - All objects can be the arguments of procedures. >> - All objects can be returned as the results of procedures. >> - All objects can be the subject of assignment statements. >> - All objects can be tested for equality. >As far as I'm aware, "modern" "functional" languages like ML and Haskell >do not define equality for functions (or for data types that contain >functions as elements). I think that the Haskell people would be very >upset if you told them functions weren't 1st class in Haskell. And no doubt they wouldn't be very happy with the assignment clause either. To some extent, different languages have different notions of "first class". If there's no assignment, for example, it doesn't make much sense to say 1st-class values have to be subject to it. However, I'm not trying to find the One True Definition of "1st-class", just noting that functions in Common Lisp do satisfy a number of definitions that were not cooked up just to discredit Common Lisp and that any definition that does show Common Lisp not to have 1st-class functions needs some independent justification. Indeed, let's try another one. A somewhat different definition of "1st-class" was given by Will Clinger in his "Semantics of Scheme" article in the February 1988 issue of Byte: All Scheme objects are endowed with certain inalienable rights: - Objects have the right to remain anonymous. - Objects have an identity that is independent of any names by which they may be known. - Objects can be stored in variables and data structures without losing their identity. - Objects may be returned as the result of a procedure call. - Objects never die. This too is true of functions in Common Lisp (with a possible quibble on identity as in the FLET and EQ example in my previous article). >However, there is something clearly wrong with this list, because C can >satisfy it, and functions aren't first-class in C. In C, a pointer to >a function can be passed to a procedure, returned from a procedure, >assigned to a variable, or compared for equality to another pointer of >the same type. This argument concerns pointers to functions rather than functions, but I think that's fair because in Lisp, after all, everything is essentially a "pointer to". It's just that, since this is true of everything, we get to factor it out. >What's C missing? The ability to create (possibly) new functions at >run time. From another perspective, *closures* as 1st-class values. I think you are right. However, someone in a later message says: That's not enough. There is no ability in Lisp to create "new" integers at run time; conceptually all the integers already exist. Ditto with all the characters. Perhaps that is the right way to think of integers and characters, but there is still a difference between a language in which the number of functions is known at compile time and a language where that is not the case. When related issues have come up in the past, some people have argued that new functions aren't created in Lisp: all of the code was always there (modulo EVAL, LOAD, and friends) even when "different" closures are created. This seems a somewhat strange way to look at it, at least to me, because you can certainly return functions that give different values for the same arguments, and if those aren't different functions I don't know what is. Anyway, I don't feel up to arguing about this right now, except to say that, somewhere in there, we can find a significant difference between languages such as Scheme, Common Lisp, ML, etc. and languages such as C. -- Jeff
peter@ficc.ferranti.com (Peter da Silva) (09/29/90)
In article <3450@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: > - Objects have the right to remain anonymous. > - Objects have an identity that is independent of any > names by which they may be known. > - Objects can be stored in variables and data structures > without losing their identity. > - Objects may be returned as the result of a procedure call. > - Objects never die. > This too is true of functions in Common Lisp (with a possible quibble > on identity as in the FLET and EQ example in my previous article). It appears that this is true of functions in C, and I wouldn't want to argue that C has first-class functions. (the anonymity clause can be satisfied by packing the object away in a file, making it static, and having it returned by a function of known name that's global within that file) -- Peter da Silva. `-_-' +1 713 274 5180. 'U` peter@ferranti.com
jeff@aiai.ed.ac.uk (Jeff Dalton) (10/03/90)
In article <SR26X59@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes: >In article <3450@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: >> - Objects have the right to remain anonymous. >> - Objects have an identity that is independent of any >> names by which they may be known. >> - Objects can be stored in variables and data structures >> without losing their identity. >> - Objects may be returned as the result of a procedure call. >> - Objects never die. >> This too is true of functions in Common Lisp (with a possible quibble >> on identity as in the FLET and EQ example in my previous article). >It appears that this is true of functions in C, and I wouldn't want to >argue that C has first-class functions. If you look in the IEEE Scheme standard, you'll see a definition of "first class" that has only two clauses, both satisfied by (pointers to) functions in C. (I forget the details, and it was a draft I was reading, not the final standard. Anyway, it was probably something like: can be the value of a variable and can be returned as a result. Passed as a parameter probably comes under the value of a variable clause.) In any case, I'm not sure what point you're trying to make. If what you're thinking is that the above isn't really a good definition of "first-class", then I would, of course, be interested in a better one. Both the list above and the previous list I posted (from the Pop Design Philosophy) received the same complaint (this time from you, last time from Richard O'Keefe), namely that it would be true of functions in C. Nonetheless, they are typical of the lists one finds in the literature. So what is wrong? I can think of several possibilities: 1. The people who wrote these lists got it wrong. 2. The people applying the lists to C have got it wrong. For example, perhaps the lists aren't really true of functions in C but only of pointers to functions. 3. "First-class" doesn't imply all that we sometimes think it does. I think there's something to be said for all of these, but right now I'll just talk about (1). Another source for claims about "first class" is Stoy's book on denotational semantics. He says something about what "first class" means, and gives some examples, but does not (if I recall correctly) try to condense the definition into a neat little list or "bill of rights". One of the examples is a function that returns a function. It may have been a definition of composition, but I'm not sure. In any case, compose can be written in Scheme or Common Lisp; it cannot be written in (portable) C. I suspect that the lists of rights have this sort of thing in mind when they talk about objects being "returned as results". That would mean that the lists are basically right but haven't quite managed to express this particular idea. Of course, there's still a problem here, because compose (and similar functions) can be written in old-fashioned Lisp, the sort that supposedly doesn't have first class functions. I can see two ways to deal with this objection. (1) These definitions cheat in some way. (2) Those Lisps don't really have *functions* (or procedures) let along first-class ones. Of these, I think more can be said for the first. >(the anonymity clause can be satisfied by packing the object away in a file, >making it static, and having it returned by a function of known name that's >global within that file) Can you really pack the function (as opposed to the pointer to it) away in a file? But why go to such lengths? Why not just stick it in an array or something? Anyway, in C all functions are defined as named, even though they can (in a sense) be separated from their names later one. Not so in Scheme where functions might originate as anonymous lambda- expressions. I don't know if this is really the right difference, but at least it's a difference. -- Jeff
sfk@otter.hpl.hp.com (Steve Knight) (10/03/90)
Jeff Dalton writes (slightly abbreviated by me) on first-classness: > Both the list above and the previous list I posted (from the Pop > Design Philosophy) received the same complaint (this time from you, > last time from Richard O'Keefe), namely that it would be true of > functions in C. So what is wrong? > 1. The people who wrote these lists got it wrong. > 2. The people applying the lists to C have got it wrong. > For example, perhaps the lists aren't really true of > functions in C but only of pointers to functions. > 3. "First-class" doesn't imply all that we sometimes think > it does. Of these suggestions, I am inclined to think that the best answer is (3). It seems unreasonable (to me) to insist that having first-class functions entails lexical binding and/or closure construction. For example, old-style Pop11 used not to have lexical binding but only (shallow) dynamic binding and partial application. However, the designers of Pop11 thought it was reasonable to believe their functions had first-classness. The idea of first-class procedures was a move away from the profound division between data and procedure in programs. It suggests that procedures can participate in all the activities of ordinary data, such as numbers or strings. It seems fair to state that (pointers to) functions in C can partipate in all the operations that numbers, strings, and pointers *share*. As far as I am concerned, this was also true of old-style Lisp lambda-objects, too. Just being first-class is only part of the story. There are two other ideas that are closely associated with being a first-class datatype. In fact, they are so closely connected that some folks argue that they are included in the notion of first-classness. Firstly, there is the idea that objects of different data-types are not confusible i.e. they are tagged with disjoint types. This would exclude lambda-objects that are lists of symbols since they are confusible with lists (they are lists!) and are subject to the operations of lists. Secondly, there is the idea that there is a collection of "natural" operators, or algebra, on the datatype, or carrier. This would exclude C functions, since they lack the typical operations that might be associated with functions, such as composition, partial application, and so on. (Of course, you have to be careful here -- it would be easy to add domain, codomain, inverse, etc ... :-) I think it's the unwritten expectation of these latter two ideas, "disjointness" and "algebra-ness", that causes the surprises. Steve
aarons@syma.sussex.ac.uk (Aaron Sloman) (10/04/90)
jeff@aiai.ed.ac.uk (Jeff Dalton) writes: > Another source for claims about "first class" is Stoy's book on > denotational semantics. He says something about what "first class" > means, and gives some examples, but does not (if I recall correctly) > try to condense the definition into a neat little list or "bill of > rights". > > One of the examples is a function that returns a function. It may > have been a definition of composition, but I'm not sure. In any > case, compose can be written in Scheme or Common Lisp; it cannot > be written in (portable) C. I suspect that the lists of rights > have this sort of thing in mind when they talk about objects > being "returned as results". > Yes I think you have hit the nail on the head: whatever the people who made such lists (of features of first class objects) might have had in mind, I suspect that this is perhaps the most important, or one of the most important features of languages that are thought of as treating functions as "first class" objects. What I assume you are talking about is the ability to create new functions at run-time, as opposed simply to the ability to return them as results, store them in data-structures, etc. Run time function creation adds enormously to the expressive power of a language, especially if you already have functions that can take functions as arguments and then apply them. Being able to create new functions that can then be handed as arguments to old ones enormously increases the re-usability of functions, allowing many decisions to be left to the program at run-time instead of all possibilities having to be anticipated by the programmer and explicitly coded in advance. Function composition is just one example. Another is being able to provide a general function that can be instantiated to different specific forms in different contexts. (Function composition is an instance of this.) There are several different techniques for run-time function creation that I can think of off the top of my head: 1. Create a function data-structure that can be interpreted. Easy in any language that normally provides an interpreter and a rich collection of data structuring facilities. Many languages make it possible to write interpreters for new languages. E.g. in C one can write an interpreter for Lisp. 2. Create compiled functions at run time, e.g. from a list or other structure defining the function. I have the impression that having an incremental compiler is more powerful than being able simply to (a) create object files, (b) dynamically link in object files. For many purposes (a) and (b) would be too slow. 3. Partial application: freezing values into a pre-existing procedure by binding some of its formal parameters to actual instances. The Pop family makes very heavy and frequent use of this (e.g. a function that takes a character repeater and creates an item repeater uses partial application to produce new instances of a general function.) 4. Lexical closures Less efficient (??) but more general. E.g. allows you to define a function that returns a family of functions sharing some environment. (You can do this with partial application too but it's more clumsy.) (Using partial application and lexical closures is generally far more efficient than incrementally compiling new procedures, though it may be better to compile a new procedure when it is complex and likely to be used repeatedly. However, the ability to create a new definition and compile it is more general. It doesn't require that a suitably general schema already exist.) 5. Create a function object by combining a function that has dynamically scoped free variables with a binding environment. I believe this was available in several lisp systems prior to Common Lisp. But I don't know if anyone ever uses it now that lexical closures are available. It's possible, but tortuous, in Pop-11, but as far as I can see has no advantages over partial application or lexical closures. I've probably missed something important? Should the creation of a process that can be run and suspended and re-run and remembers its environment in-between, be another example? (Some lisps and Pop-11 provide this. Simlua-67 had a simplified version.). Not many languages that I am aware of can do all these things. In fact, apart from Common Lisp and Pop-11 are there any others? (T perhaps? I can't remember enough about it.) Prolog seems to provide a similar kind of power to function creation in a totally different way, insofar as it allows new rules to be added to the database by programs (interpreted or compiled, depending on the implementation.) Allowing a new class to inherit a method from its superclass is in some ways like partial application or creation of lexical closures. (The latter can be used as an implementation technique for OOP.) Scheme and ML provide lexical closures, which probably give most of the generality. An ML implementation may permit incremental compilation, but as far as I know it is not part of the definition of the language. Ditto Scheme? I suspect there are ways in C of creating new structures and putting machine instructions into them, then running them. But this is not so much a principled feature of the language, as an indication of how low level it is? Aaron
jeff@aiai.ed.ac.uk (Jeff Dalton) (10/08/90)
In article <3563@syma.sussex.ac.uk> aarons@syma.sussex.ac.uk (Aaron Sloman) writes: >5. Create a function object by combining a function that has > dynamically scoped free variables with a binding > environment. I believe this was available in several lisp > systems prior to Common Lisp. E.g., Lisp 1.5.