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();
From: Richard A. O'Keefe
Subject: Re: Why aren't CL functions 1st class objects?
Date:
Message-ID: <3806@goanna.cs.rmit.oz.au>
In article <····@skye.ed.ac.uk>, ····@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.
From: John Cowan
Subject: Re: Why aren't CL functions 1st class objects?
Date:
Message-ID: <26FE4FEF.48AE@marob.masa.com>
In article <····@goanna.cs.rmit.oz.au>,
··@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
>In article <····@skye.ed.ac.uk>, ····@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.
--
·····@marob.masa.com (aka ...!hombre!marob!cowan)
e'osai ko sarji la lojban
In article <····@goanna.cs.rmit.oz.au> ··@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
In article <····@skye.ed.ac.uk>, ····@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
·····@zurich.ai.mit.edu
From: Jeff Dalton
Subject: Re: Why aren't CL functions 1st class objects?
Date:
Message-ID: <3450@skye.ed.ac.uk>
In article <····@goanna.cs.rmit.oz.au> ··@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
>In article <····@skye.ed.ac.uk>, ····@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
From: Peter da Silva
Subject: Re: Why aren't CL functions 1st class objects?
Date:
Message-ID: <SR26X59@xds13.ferranti.com>
In article <····@skye.ed.ac.uk> ····@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`
·····@ferranti.com
From: Jeff Dalton
Subject: Re: Why aren't CL functions 1st class objects?
Date:
Message-ID: <3477@skye.ed.ac.uk>
In article <·······@xds13.ferranti.com> ·····@ficc.ferranti.com (Peter da Silva) writes:
>In article <····@skye.ed.ac.uk> ····@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
····@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
From: Jeff Dalton
Subject: Re: Why aren't CL functions 1st class objects?
Date:
Message-ID: <3491@skye.ed.ac.uk>
In article <····@syma.sussex.ac.uk> ······@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.
From: Jeff Dalton
Subject: Re: Why aren't CL functions 1st class objects?
Date:
Message-ID: <3443@skye.ed.ac.uk>
In article <····@skye.ed.ac.uk> ····@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
From: Steve Knight
Subject: Re: Why aren't CL functions 1st class objects?
Date:
Message-ID: <1350033@otter.hpl.hp.com>
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