Lambda the Ultimate

There isn't a definition offered in that thread -- just a bunch of implication, and that's what I'm to trying to get away from.

I think the best way to think about it is to remember that this is an intuitive concept, and a formal definition will depend on the semantics of each language, which makes cross language comparisons difficult. Since the intuitive concept is useful precisely for this sort of comparison looking for a formal definition is the wrong approach.

Intuitively the idea is that a first class object is a native citizen, and can be used like other basic values, without special restrictions. A first class value will in general be (1) passable as a parameter (2) returnable from functions, with no restrictions and (3) storable in data structures.

There is, I should add, a notion of second-class value as well.

It seems that wikipedia has a pretty decent discussion on the notion of first class objects.

Now I'm back where I started.

I hoped there was a formal definition lurking under all the confusion -- the Talk Page for that article ends with:

I would really like to see more citations in this article. It seems to me that the text here is really just hypothesis and conjecture rather than hard facts.

There's wide spread uncertainty about whether or not C has first class functions -- both on Wikipedia and in other forums. If that's the state of the art, though, then I guess I'll never really be able to resolve for sure whether Ruby has first class functions or not :)

Contrary to popular opinion this is really not an interesting question, so you shouldn't worry about it. The question that you should be interested in is whether certain things can be done in C or not. The restrictions on C functions are quite obvious, so if you want to use them in ways that are possible in some other languages you are stuck, or have to use problematic workarounds (global variables etc.). Call them first class or not, it really doesn't matter (but since anyone who appreciates the meaning of the term would say they aren't I really don't see why people debate this. The goal when choosing a language is not to tick feature boxes) .

(Of course, the C case is clear, so arguing about it in general is rather a waste of time anyway).

The question that you should be interested in is whether certain things can be done in C or not.

We all know it can be done in C. The question is whether certain things can be done in C with a reasonable amount of effort.

I meant whether certain coding patterns can be used (I think I even used this phrase at some point).

There's wide spread uncertainty about whether or not C has first class functions

I can't help making the sarcastic comment that this uncertainty exists only among people who have never used a language with real first-class functions. It's also a consequence of language evangelists tending to claim that their favorite language has all kinds of features somehow deemed important (see my attempt of a definition of first-classness in the thread mentioned above, which addresses C; also see my other post there for an argument why the syntactic class of the introduction form does not matter).

I just added a comment to the wikipedia talk page pointing out that being able to construct new values at run-time is a pretty much hard and fast requirement[1] as any turing complete language has to be able to encode the construction of new natural numbers.

I think continuations are something of a special case regarding introduction forms, but those aside it's all just syntax.

[1] It's mildly debatable for type with a finite number of values, but only if you're being obnoxious

I just added a comment to the wikipedia talk page pointing out that being able to construct new values at run-time is a pretty much hard and fast requirement...

I think that distinction is less than helpful in C's case. We can construct as many function pointers as we want at runtime... I've made a note of this on the talk page.

This was something of a stumbling block in the life of the first class functions page -- it was troublesome to distinguish constructing and defining a function at runtime. In languages without partial evaluation or closures, the difference between a function and the binding of the free variables in it doesn't make much sense, so people were arguing that you needed eval and dynamicism in order to have a functional language.

In languages without partial evaluation or closures, the difference between a function and the binding of the free variables in it doesn't make much sense

I'm not sure I get your point. Languages without closures don't have first-class functions (usually), because closures are nothing but an implementation technique for first-class functions.

Also, your comment in Wikipedia seems to miss the distinction between structure types and structure values. First-classness is about what you can do with values. Structs have been first-class in C since ANSI C.

[In C] We can construct as many function pointers as we want at runtime...

Yes, function pointers are first-class -- but they aren't functions.

[Edit: Also made some comments to this end in Wikipedia talk page.]

In languages without partial evaluation or closures, the difference between a function and the binding of the free variables in it doesn't make much sense

I'm not sure I get your point. Languages without closures don't have first-class functions (usually), because closures are nothing but an implementation technique for first-class functions.

I was suggesting a cause for the confusion on the "First class functions" page on Wikipedia -- people thought a "new function" meant code generation.

...your comment in Wikipedia seems to miss the distinction between structure types and structure values.

On the Wikipedia page, I drew a distinction between defining and creating structures -- I felt that was easier for the uninitiated.

I was suggesting a cause for the confusion on the "First class functions" page on Wikipedia -- people thought a "new function" meant code generation.

Closures can be compiled via code generation, it's just probably not worth it.

Talking of which, I'm amused to note that we're currently both effectively arguing for intentionally second-class facilities rather than tolerably-encoded first-class ones elsenet.

...I would very much like to see first-class modules become more wide-spread. :-)

In an ideal world, I would even have records and modules, and functions and functors, be the same thing. But a lot of typing problems have to solved before that can happen in a reasonable manner.

Yep. But in an ideal world we'd also be able to supply separate termination proofs!

What are the typing difficulties of first-class modules? First-Class Modules for Haskell argues that dependent types aren't needed, and they were used simply as a convenience due to the dependencies involved in opening existentials; they instead use existential quantification directly, and introduce a new open construct to handle those dependencies.

I've been reading up on module and record systems, and Extensible Records with Scoped Labels looks promising, though it depends on MLF. Their first-class modules are similar to the system described in Using Parameterized Signatures to Express Modular Structure.

Also, Moscow ML has first-class modules, so clearly the problem is solvable in current systems.

That was the point of the first half of my posting: first-class modules a la Moscow ML basically are a solved problem -- with the caveat that you have to inject them into values explicitly (which is why Harper & Co insist on calling this approach "modules as first-class values" as opposed to "first-class modules"). In the second half however, I was referring to actually merging module and core language, which is a much harder problem.

Note also that the encoding approaches you mention do not give you the full power of ML-style modules, because they do not really deal with type abstraction and translucency.

There's wide spread uncertainty about whether or not C has first class functions...

...this uncertainty exists only among people who have never used a language with real first-class functions. It's also a consequence of language evangelists tending to claim that their favorite language has all kinds of features...

It is ultimately discussion with a language pundit that drove me to start this thread :) I argued that a certain style of wrapped functions was definitely second class; but it was hard to find any real documentation on the matter, and it doesn't help that the Wikipedia page is a shambles, the result (I'm sure) of acquiescence to language pundits.

The style of "first class" functions I inveighed against are apparently wide spread. If my arguments were taken seriously, then apparently the pundit's favorite language could be said not to have first class functions! He told me that many PhDs disagreed with me, came up with some names and then couldn't find any actual quotes. He's promised to get an audio quote on the matter from Phil Wadler when he comes to speak at BayFP in January -- though I doubt the good professor would go in for on demand language advocacy.

So which was the language in question?

I have hidden it in the message above. It's not Ruby -- it's more recent than that.

When the discussion turned to the pundit's language, I punted: I've never used it and know nothing about it.

It's tempting to try to settle questions like this in a binary way, but when you're comparing features across languages it's just not that simple. That's also the reason there's no formal definition that applies here: to have a formal definition, you'd first need a formal framework that encompasses all programming languages. Derek's answer from category theory is the only suggestion along these lines so far.

To answer Philippa's question, the language provoking all this intrigue appears to be Ruby. To me, it seems fairly clear that Ruby's functions are not quite as first class as those in most functional languages, because you have to jump through some hoops to use them as values. But the fact that it's possible to do that at all makes Ruby's functions much more first class than those of many other languages.

So I'm going to settle this once and for all by saying that Ruby has 1.4999...th-class functions. Now the argument can turn to the question of whether that should be rounded up to 1 or down to 2, which at least has a definitive answer. ;)

That's a generous attitude, but in common usage, classes are sets. I appreciate where Ehud is coming from when he suggests that whether or not a language has first class functions is not going to get you too far, because even if it doesn't, it might still have a lot.

The reason I'd like a clear definition, I have to confess, is to battle punditry. Were there a plain and simple -- if exclusive -- definition, then we could separate the Brahmans from the other castes once and for all. I hate to see the widespread dilution of "Functional Programming" that results in people telling me C has first functions, so what does functional programming offer, anyway? There is no document I can refer them to which makes a clear case against C, at least not in any respected forum. Wikipedia, so commendable for its coverage of The Golden Compass, is unfortunately no help in this matter.

By the way, though Ruby was the language I was harping on, it's not the language of the pundit.

It also works the other way: If there are useful coding patterns that can't be used, than I don't really care if according to some definition the language does have first class functions.

My usual test is pretty simple: can you code an easy to use and useful "foreach" function in the language? If the result is not easy to use, it's is a good clue that there must be a problem somewhere... (note that the criterion isn't just to write foreach, but that it will be easy enough to use it productively).

but in common usage, classes are sets.

I'm not sure what you mean here. Assuming you mean the "class" in "first-class", you can easily partition all PL entities in a given language into three sets: first-class, second-class, and intermediary-class. This is essentially what Anton has done, with a bit more tongue in cheek. ;-)

Were there a plain and simple -- if exclusive -- definition, then we could separate the Brahmans from the other castes once and for all.

Ah, this is the dream of Brahmans everywhere and for all time. Unfortunately, as with all such dichotomies, there are usually way too many edge cases to make this stick. (Not to mention too many disparate groups that consider themselves the indisputable in-crowd.)

If the faithful of the church of some particular PL want to believe that they qualify as Brahmans (i.e. their language has first-class X), why not let them? There probably isn't any criterion, no matter how well defined, by which you can convince them that their language is second best to any other on any feature that they care about.

Meanwhile, to be an LtU Brahman (at least according the 6785 page LtU reference book on my shelf), you have to accept that some PL concepts are useful but not definitively defined. ;-)

Assuming you mean the "class" in "first-class", you can easily partition all PL entities in a given language into three sets: first-class, second-class, and intermediary-class. This is essentially what Anton has done, with a bit more tongue in cheek. ;-)

I'm looking into having surgery to get that resolved. ;-P

Actually the class division I had in mind is a little different. I'm assuming quite ambitiously that if we refer to a feature as "first class", we mean that it belongs to the class of all language features, across all languages, that have certain properties which have been discussed in this thread, such as that instances of the feature "can be passed as an argument".

This class is indeed a set, so I'll talk in those terms. A point in this set is a feature in a particular language. There are multiple relevant properties that are used to describe a point in this set. The n-tuple of properties describing points in the set can be interpreted conventionally as the dimensions of the set. For an example of this, consider Barendregt's Lambda Cube which classifies the set of typed lambda calculi in three dimensions.

In the case at hand, the dimensionality of the set may be anywhere from about 3 to 12 (the latter number based on the number of properties specified by Wikipedia.) But since we refer to this set by the name "first class", and its sibling by the name "second class", and because humans consistently prefer to classify things along as few dimensions as possible, I'm suggesting that it is useful to map the n-tuple which describes a point in this set to a real number between 1 and 2, the purpose of which is to identify where a feature fits on a single dimension which ranges from 1 meaning "as first class as possible" to 2 meaning "entirely second-class".

The exact nature of the mapping function is yet to be determined. It's not inconceivable that the use of Hausdorff dimensions might be appropriate here — a generous NSF grant may be needed to determine this, since the topological properties of the set of all language features has not yet been sufficiently explored. At present, we can only estimate the number in individual cases, an admittedly unfortunate state of affairs which leads to unnecessary disagreement amongst otherwise reasonable language advocates.

Like the infamous "one-drop rule", I'm also suggesting that any hint of first-classness be considered sufficient to elevate a feature to first class membership, albeit with a high number such as > 1.9 for C functions. The reasons for this are as much social as technical, to avoid causing unnecessary emotional distress for users of languages that are missing important first-class features.

There were at least two claims at providing an explicit definition, there was Andreas' which he mentioned. I also provided an fairly objective one here.

I liked your rule about the expressibility of curry/uncurry operators (although it's very indirect, so I would rather consider it a criterium than a definition). A caveat is that it relies on the existence of first-class tuples, so you need a definition for those first. And you have to make precise that you mean currying with respect to those. For example, you can write higher-order curry/uncurry functors in ML, but with respect to structures, which are second-class themselves.

They're second-class within the ML language as a whole, but presumably first-class within the module language, no? Sometimes that distinction proves useful :-) I think it's at least clear that we're talking about currying with respect to an existing product in the category in question, you can't define the isomorphism without it.

Aside from that, I'm wondering if anyone has given a description of (suitably generalised) church encoding in terms of currying and cocurrying (for lack of a better name - the dual on sums).

The function pointers of C would count under this rule, if I understand it correctly.

Which? Andreas gave reasons why he didn't think so (or at least, why they don't lead to first-class functions; if you want to say C has first class function pointers, well then uh, sure.) I asserted without proof that C doesn't have first class functions by my definition; what you need to do to prove me wrong is quite clear.

Oops.

Your definition may be too specific. What's your working definition for "constructible at runtime?" How does it apply to Haskell e.g.?

Also, from your blog link:

First it can’t be an l-value like any of the fundamental types: you can’t assign a function to another function, you can only assign references. Second you can’t create functions dynamically, you can only reference functions which have been declared in the source code."

Which of your three bullets does not being an l-value contradict?
Are Objects in Java not first class because you can only store them by reference?

Your definition may be too specific.

You are probably correct. It's a first attempt.

What's your working definition for "constructible at runtime?"

You can dynamically construct any of the possible valid values for the given type at runtime.

How does it apply to Haskell e.g.?

To be honest I'm not sure.

Which of your three bullets does not being an l-value contradict?

None AFAICT, perhaps it should be a bullet? In general if you can't construct arbitrary instances of the type (e.g. it has some restriction determined at compile-time) then I wouldn't consider the type to be first-class.

Are Objects in Java not first class because you can only store them by reference?

I believe so. You also can't construct arbitrary objects at run-time, only instances of a specific predefined set of classes. This is very different than the behaviour of ints, chars, and other built-in types. The problem of creating a definition at this point, becomes a bit circular: should a correct definition of first-class include Java objects, or is the question of whether Java objects are first-class dependent on the definition.

Are Objects in Java not first class because you can only store them by reference?

I believe so. You also can't construct arbitrary objects at run-time, only instances of a specific predefined set of classes. This is very different than the behaviour of ints, chars, and other built-in types.

This seems to mix levels. Ints are a particular type, analogous to a particular class. You can create arbitrary instances of 'int' at runtime (although often out of a fixed set of e.g. 2^32 or 2^64 elements), and similarly it's possible to define a class Foo and create arbitrary instances of it at runtime.

The only sense in which "you also can't construct arbitrary objects at run-time" is the same sense in which "you can't construct arbitrary built-in types at runtime" (i.e. you're stuck with a "specific predefined set" of built-in types). And in fact, since you can dynamically load previously unknown new classes at runtime in Java, they're actually "more first class" than the built-in types in this respect.

I see your point, and you could make a definition based on whether or not you can write a program that enumerates all possible functions. What I was really getting at with the first questions is that I think this really just boils down to having function values with bound parameters, and needn't depend on a concept of runtime.

I agree with Anton that built-ins in Java seem less first class than objects - mainly because you can't treat them as objects (e.g. put them in containers). So they end up feeling second class when you try to use them.

Also, I think the distinction between functions and function pointers mentioned elsewhere in the thread is a red-herring. If C let you easily create new function closure pointers, I think they'd seem first class. Interestingly, Ehud's "foreach" test doesn't even seem to require closures - all C seems to be missing is the ability to nest function definitions?

Anyway, I'm going to side with the people who think this term isn't worth defining formally and bow out :)

I simply can't agree with the assertion:

You also can't construct arbitrary objects at run-time, only instances of a specific predefined set of classes. This is very different than the behaviour of ints, chars, and other built-in types.

You can't create arbitrary byte values at run-time either, you can only select one of 256 predefined values. While the cardinalities of other types, e.g. int or char, are larger, they're still finite and predefined.

The cardinality of type PairOfByte (an ad hoc example, each instance of which contains two byte fields) is larger than the cardinality of the (primitive, built-in) type byte. I'm not trying to be snarky or pedantic, but trying to understand your real point.

Isn't it true that any program/language makes some kinds of variability easier than others (without implying that some kinds of variability are made impossible)?

In other words, by defining and using PairOfByte, I'm implicitly stating that I think it's unlikely that I'll need a concept represented by three byte values (unless I also define TripleOfByte in the same context). On the other hand, if I define and use TupleOfByte (with varying size), then I'm implicitly stating that I expect to have cases needing two, three, etc. component values.

Then there's the question of what kinds of mutability my TupleOfByte class allows: none--immutable size and values--or more--immutable size but mutable content, or completely dynamic size and content. (Of course, by the time I've worked up my courage to define and use DynamicTupleOfObject, I've left the barn door wide open! ;-)

All of that is before we talk about the fact that I can use class loader tricks in Java to create and instantiate classes at run-time that didn't exist in source code. Of course, it's not trivial to do so, but it is done all the time (in commercial products).

And, to be fair to the C crowd, I could write code in C that:

1. writes a text file containing C source
2. invokes the compiler on that file
3. does various other incantations to turn the compiler's output into a dynamically-linked library
4. loads the resulting library, and
5. invokes its behavior.

although I must point out that the probability of my doing so is vanishingly small! ;-)

That last idea likely involves some platform-specific bits, which the Java bytecode- and classloader-games version doesn't. But when I try to contrast that with e.g. macros in LISP, I find myself asking (seriously) exactly where to draw the line between qualitative and quantitative. To be sure, I'll use higher-order functions in Haskell or macros in LISP well before dynamic bytecode in Java, and nearly infinitely well before "dynamic C", but is that an issue of required effort, rather than theoretical possibility?

I'm probably (almost) as impatient as anyone when--during a discussion of e.g. higher-order-functions in Haskell--a C programmer interjects, "But I could do that in C!". However, instead of saying, "No, you can't!", I'm likely to respond, "Perhaps so, but why would you ever want to?"

Even if you would succeed with what you described for C you would have stepped far outside what's provided by the language itself, so this counter example is easily dismissed.

The Java example, when applied to creating functions at runtime, is more interesting. I would dismiss it as providing true first-class functions on the grounds that you still cannot use the standard mechanism for creating functions in all places, nor can you access/close over all kinds of entities from the local scope when you use the workaround. So there still exist significant restrictions.

(Just to clarify: I agree with you that the difference between objects and primitive types like Christopher described is immaterial.)

From the comments, first-classness seems to be a purely syntactic criterion, where X is first-class if one can create an X anywhere one can create any other value. In C, one cannot create a function where one creates an int, even though one can pass a function reference [1].

In functional languages, one can create functions inline in other function bodies, curry function applications essentially creating new functions, etc. Modules tend to be second-class because they have restrictions on their definitions. Classes in C# are also second-class by this criterion, but first-class in Java due to anonymous classes.

[1] well, it's possible by code generating into an inline array and casting the array to a function pointer, but all unsafe languages are equivalent in this regards, so let's assume a memory-safe subset of C.

Quite the contrary: as I tried to argue earlier, syntax is largely irrelevant.

More specifically, where and how you can create something is only half of the story. For example, several ML implementations allow local module definitions - but that does not make them first class! Much more important is what you can do with them, and that is mostly a semantic issue. You still cannot pass local modules around like other values. The same goes for anonymous classes in Java.

For example, several ML implementations allow local module definitions

I was considering that very situation when I wrote my post actually, but I was under the impression that such definitions could not be manipulated like ordinary values, ie. returned from a function, and so would fail my criterion regardless.

Now I'm confused about what criterion you were actually suggesting. Sure, you cannot return a local module, but neither can you return a Java class, anonymous or not. But you said those would be first class?

I was confused myself. I'll have to think about it some more. :-)

The statement (fragment):

...neither can you return a Java class, anonymous or not.

is simply incorrect. A Java Class is an object, and can be returned as the result of a method. The most obvious example is that every Java object has a getClass() method, whose result is the Class object for the object on which getClass() was invoked.

And, of course, such Class objects are first-class (whatever that means! ;-) objects. You can put them into structures and collections, and call methods on them.

That is an interesting case. But let's look a bit closer: what you are doing is not actually returning the class - you are returning a descriptor object for the class. The difference being that you can no longer use it like a regular class (and also loose all static knowledge about it). There is not even a way to coerce it back into a regular class (unlike with the "modules as first-class values" in some MLs). So I stand by my statement that you cannot return a class (as such).

In fact, I'd say something stronger: I'd suggest this as another rule-of-thumb definition of "first-class": If you need to use reflection to mention x, x is not first-class in your language.

In Java, this categorizes class, constructor, field, and method as non-first-class entities, which seems about right to me. (I'd almost argue that function pointers in C can be understood as a simple kind of reflective mechanism, but I don't really want to make that case here.)

Foo foo = new Foo; // OK
Class classOfFoo = foo.getClass(); // OK
classOfFoo foo = new ClassOfFoo; // Oops.  This doesn't work.
Foo foo = new classOfFoo; // Oops.  This doesn't work.
Object foo = new classOfFoo; // This doesn't work either

Certain structures in Java require their argument to be of kind "type", such as variable declarations, which have to be of the form

[declspecs] [type] [name] ( = [value] )?

and new invokations, which need to look like

new [type] ( [arguments] )?

In both places where you see "[type]", one can only put a type literal, or a generic instance which returns a type. As class objects are values; there is no way to take the result of getClass() and plug it into either form.

Now, if Java had a "typeof" operator like C++ is getting, one might get closer; if it had an operator which took in Class objects (value) and output (at the syntax level) type literals, then maybe you could argue that types were first-class in Java. Of course, there's the issue of proving type correctness--taking the result of a "typeof" and running it through a lossy function like "getClass()" (which erases all compile-time type info) means that some run-time typechecking (and possible failure) is probably an issue.

[extra sentence fragment accidentally left in the post deleted by author]

It's possible [in C] by code generating into an inline array and casting the array to a function pointer.

In fact, ISO C does not allow data pointers to be converted to function pointers. (Gcc has to be coerced into producing a message for this infraction, say by using the -pedantic flag. But that's a flaw in Stallman, not C.)

Well, I wouldn't have necessarily considered it a flaw since it allows projects like GNU Lightning, except that it may also allow buffer overflow exploits.

I think that our conclusions in specific cases would be more similar than my previous rant might lead one to believe, but there was a purpose for the rant, which you've helped me distill.

I agree with you that C and Java do not provide what I would consider first-class functions. I think my reasons for doing so are imprecise, as explained below.

By way of background, while I write this I'm still "under the influence" of listening to the OOPSLA2007 keynote by Gregor Kiczales. The podcast is available at http://www.oopsla.org/oopsla2007/index.php?page=podcasts/ and the slides are available under his "talks" link at http://www.cs.ubc.ca/~gregor/ . (Obviously Kiczales isn't to blame for the ditch I ended up in...)

I cannot so easily dismiss my horrible C-based scenario as being "far outside what's provided by the language itself" because doing so requires that one take a crisp view of the boundary of the language. I think most programmers would disagree with the assertion that e.g. output formatting is outside the C language, simply because it is done via library and not hard-wired into the syntax of C. But in the same sense, the C function system(...) is just a library function. If a LISP programmer considers the interpreter part of the language, and makes use of that fact, isn't it also fair for the C programmer to consider the compiler a part of the language, and make use of that fact (even if it is harder to do so)?

Further quibbling aside, I think of "object orientation", "first-class functions", etc. as descriptive of a style of programming and so regard a language as e.g. "object oriented" if the language encourages me to program in that style. I believe it is very valuable to have deep, precise discussions about mechanisms, but am cautious about higher-level pronouncements that "Language L IS a P language because it has features X, Y, Z, ...

For example, do we require that a language's feature-set be isomorphic to Smalltalk in order to qualify as "object oriented"? What about Self, NewtonScript, IO, Lua, etc. which clearly "want" the programmer to design in terms of interacting objects, but which don't implement quite the same feature set in quite the same way (e.g. consider inheritance)?

AFAIK, Haskell takes the extreme position among "functional languages" WRT not mixing pure and impure code, but must a language do Monad in a Haskell-like style to be functional?

I think I prefer saying that "programming with first-class functions" means ___ (insert some of the excellent remarks about style from elsewhere in this thread). Then I can talk in very precise ways about what features a language (or implementation of a language!) provides to help/encourage me to think that way, or what aspects of the language get in the way of thinking that way.

We can compare/contrast the doing of analogous thing in different languages, but instead of a binary (yes I can, no you can't) discussion, we can take a hard look at how much support the language provides (vs. how much convention the programmer must remember), the amount of code required to express the idea, the fragility/robustness of that code, etc.

My C example was horrible because the language didn't offer me ANY support for what I was describing, it would take huge amounts of fragile code, etc.

While I can use Java to implement function-like objects, I agree that it doesn't feel sufficiently first-class, because I must rely on so much convention. It really doesn't take too much code (in absolute line count), and it's fairly robust (thanks to Java's static typing), but the programmer has to impose the idea on the code, rather than the code helping the programmer think of doing it that way.

I certainly agree that it is more important to talk about what you can do. But to talk at all you need some agreed-on language. If we allow to keep terminolgy far in the vague then inevitably everybody will interpret it in her/his own way, being a failsafe recipe for talking past each other. I had way too many technical discussions that went nowhere because of incompatible interpretations of central terminolgy involved, and the inability to sort it out (for technical, social or psychological reasons). The notion of "type" is a perfect example. :-)

Matt M: Are Objects in Java not first class because you can only store them by reference?

Java has no notion of reference, so this question is meaningless. Objects are simply mutable values, and as such first-class. Whether you implement them by passing pointers, or by some other means (you might well envision some form of copying with propagation of mutations), is merely an implementation detail.

Sun's docs for Java talk about "reference types", and fields of a reference type behave like references to objects etc rather than the objects themselves. The relationship to actual objects is much the same as that between references and cells in ML, only the cell allocation mechanism will only accept a constructor call rather than a general value as the initial value.

You are right, I should have been more careful: Java has no separate notion of reference. There are so-called reference types, but this is basically just a name for the class of (potentially) mutable types. There is no distinction between such a type and a reference to it (what operation could tell a reference from "the object itself"?). So I don't think it makes sense to distinguish them when we discuss s.th like first-classness.

Same with ML. There is no notion of reference separable from mutable values: references are the mutable values.

It's true that in formal semantics you usually introduce this indirection of references (addresses) to memory slots (cells). But IMO that is merely a technical artifact, a device to encode the graph structure of a "real" program into something tree-like that is expressible as terms. IOW, an implementation technique. On a higher level of abstraction, it is valid - and seems preferable - to think of actual objects being passed around, not addresses.

In addition to Philippa's comment re "reference", I must also point out that Java objects can be immutable. The canonical examples are String, the primitives, and the "primitive wrappers" (e.g. Integer). An object whose fields are all immutable, final, and initialized by the constructor will also be final, IIRC.

Your definition may be too specific. What's your working definition for "constructible at runtime?" How does it apply to Haskell e.g.?

I think following this "constructible at runtime" idea leads to an important insight. Compare C function pointers to closures. They are both values that you can call as functions, pass them around as arguments to other functions, and return them as values of functions. However:

• In C, for all practical purposes, the domain of distinct values over which variables of function pointer type can range is fixed at a finite number at compile-time. Functions are things that the compiler spits out in some finite number, and your function pointers must point to one of these functions or another.
• In a language with closures, the domain of distinct values that an identifier of function type can be bound to is not fixed to a finite number at compile-time in the general case. Compilation does fix some properties of that set (because your closures must all share some finite set of code routines), but since the value of a function type expression can depend on the captured values of free variables in your function definitions, there are potentially infinitely many functions that could exist at runtime.

Of course, the difficulty now is that this condition cannot be applied as a criterion of "first class" types in general, because fixed-size integer types also can only take on values from a finite domain.

Bools only have two values, "true" and "false". Nobody would suggest that they aren't first class in any modern language.

Those three rules may (partly!) capture a particular colloquial use of "first class". However, the term is also used more broadly than that, which I suspect is what the Wikipedia definition is getting at.

For example, imagine a language in which all types are serializable, except for say function types. In that context, it could make sense to call functions second-class. Certainly, they'd be second class with respect to serialization. The point is the term is relative to the language and even the specific context within a language.

...imagine a language in which all types are serializable...

It's more specific to say all values, not all types, are serializable. If the types are in fact values, they could be serialized, too. An exception for values of function type would make them second class, I agree. However, I suspect those function 'values' would not be values at all in a language that offered otherwise uniform serializability -- the functions would actually be statements.

I meant to say something more like "all types of value" - I didn't intend to drag first-class types into this.

However, I suspect those function 'values' would not be values at all in a language that offered otherwise uniform serializability -- the functions would actually be statements.

I don't know what you mean by "statements" here [edit: or why functions would be statements]. Are you saying something about what would happen in the presence of first-class types?

Otherwise, it's easy enough to serialize function values in a properly designed language implementation. In an eager functional language, this typically involves serializing the function's environment along with some sort of representation of the code, possibly just a relative pointer. This typically involves some restrictions related to e.g. transient values like open file handles, and dependence on a particular version or image of the code, but that wouldn't seem to disqualify such functions as first-class w.r.t. serialization.

Otherwise, it's easy enough to serialize function values in a properly designed language implementation. In an eager functional language, this typically involves serializing the function's environment along with some sort of representation of the code, possibly just a relative pointer.

Having worked on a language with higher-order pickling I partially disagree. Most existing languages indeed make functions second-class citizens with respect to serialisation. Merely externalising a code pointer, like many do, does not really count IMO, because it does not produce a self-contained representation of the function - in particular, it will be meaningless in another program (or even a different version). On the other hand, getting code pickling right may require a few somewhat non-standard design decisions in the language implementation.

Assuming that object/binding identity/mutability isn't an issue (or is treated by the serialiser already anyway), what is the issue with serializing an environment + lambda-lifted source (+ UUID on the source for optimisation purposes)? Having implemented such a hack for CL, I'm interested in the other issues I may have missed.

That should work, but keeping the source code of all functions around, and having a full compiler in the runtime system to recompile it on the target site, isn't something you would want to do in most systems.

If you are dealing with compiled code instead then issues arise regarding safety and security (even for dynamically checked languages). And you want to be able to serialise and garbage collect code for individual functions, something which you cannot do with the usual monolithic approach to code generation (the paper discusses other issues and requirements we tried to address).

Merely externalising a code pointer, like many do, does not really count IMO, because it does not produce a self-contained representation of the function - in particular, it will be meaningless in another program (or even a different version).

I mentioned this in my comment. These issues and the others you mention are inherent in the issue of serializing functions, so in keeping with the relative nature of the term "first-class", I don't see that they should be held against an implementation that provides serialization of function values that are not self-contained and that depend on a particular program and version.

Many ordinary serialized values are not self-contained anyway — for example, they may contain identifiers that relate to an external database. A function pointer that relates to an external program isn't that different. Similarly, other kinds of serialized values also inherently have version dependency issues.

I've found that serialized functions and continuations can be enormously useful even with the limitations inherent in simple implementation strategies like the one I alluded to. In many applications, it is not at all problematic to refuse to run functions or continuations which have a version mismatch: the response to the user in many such cases would be the moral equivalent of a "session expired" message in a web application, except it would typically happen much less often.

These issues and the others you mention are inherent in the issue of serializing functions

If by "inherent" you mean "unavoidable" then I disagree. If not then I'm not sure what you mean. It seems clear that objects whose serialised representation is incomplete or has restricted functionality -- in contrast to basic serialised values like integers -- are not first-class (wrt serialisation). It's the same criterium we have been discussing for other applications of the term. "No restrictions" in the context of serialisation can only imply having a self-contained representation.

(AFAICS, the situation is analogous to functions in C: if you argue that functions are still first-class entities for a serialiser that only serialises function pointers, then you'll have a hard time arguing that C does not have first-class functions although you can pass around function pointers.)

But please note that I am not saying that a second-class (or "semi first-class") treatment of functions is necessarily bad and first-classness a must-have. I fully agree that serialised function pointers are still very useful, and sufficient for many interesting applications. I just don't think it's correct to call functions first-class citizens in this respect.

Many ordinary serialized values are not self-contained anyway — for example, they may contain identifiers that relate to an external database.

Yes - the identifier is first-class, but that's not the database, and the latter certainly isn't first-class at all (again somewhat similar to the function pointer vs. function situation in C). Likewise with all other kinds of external references.

If by "inherent" you mean "unavoidable" then I disagree. If not then I'm not sure what you mean.

I mean that more or less the same difficulties apply across many languages. This is in contrast to the situation with, say, ordinary first-class functions as values, where the decision not to implement them or to implement them in some restricted form is often largely arbitrary, not related to some inherent difficulties of first class functions (except perhaps in the mind of the implementor ;)

It seems clear that objects whose serialised representation is incomplete or has restricted functionality -- in contrast to basic serialised values like integers -- are not first-class (wrt serialisation). It's the same criterium we have been discussing for other applications of the term. "No restrictions" in the context of serialisation can only imply having a self-contained representation.

Right, and I've been arguing that such a binary definition of "first-class" isn't very useful, because (a) you can argue it to the point where almost nothing is first-class (we've already seen "Java objects are not first class"), and (b) it tends to end up excluding many things that seem first-class enough in a given context but not in some broader or more absolute context.

In this particular case, compared to the integer example we could say that structures of any kind cannot be first-class wrt serialization if they contain values that reference e.g. an external database. Although you make the point that those references themselves are first-class, they nevertheless introduce a dependency which can create restrictions on what can be done with the serialized value. These restrictions don't exist in the integer case.

Unless you have some definition in mind which accounts for such issues, using a type such as integer as a benchmark for first-classness can be misleadingly strict.

I mean that more or less the same difficulties apply across many languages. This is in contrast to the situation with, say, ordinary first-class functions as values, where the decision not to implement them or to implement them in some restricted form is often largely arbitrary, not related to some inherent difficulties of first class functions (except perhaps in the mind of the implementor ;)

Why would that be in the mind of the implementor only? Supporting first-class functions has a huge impact on language design and implementation - in particular, you are practically forced to use garbage collection, which certainly is a significant difficulty in some settings. There are valid reasons to avoid this complication.

Almost the same story with higher-order serialisation, just one level up.

Although you make the point that those references themselves are first-class, they nevertheless introduce a dependency which can create restrictions on what can be done with the serialized value. These restrictions don't exist in the integer case.

Those dependencies and restrictions already exist within the original process (e.g., the external resource might suddenly become inaccessible for some reason). Serialisation does not add any new ones, which is the criterium I am suggesting.

Supporting first-class functions has a huge impact on language design and implementation - in particular, you are practically forced to use garbage collection, which certainly is a significant difficulty in some settings. There are valid reasons to avoid this complication.

Yes, true. My comment was aimed at a particular category of languages, but I didn't make that clear. I was thinking of languages which already have garbage collection, and some restricted notion of first-class functions -- the 1.nth-class functions that have been discussed in this thread. In these cases, the restrictions imposed on first-class functions typically don't actually have to do with any inherent difficulty in implementing first-class functions: they're things like syntactic or semantic restrictions on what anonymous functions can contain (e.g. no statements), errors in handling of lexical scope in nested functions, or complications in gaining access to or using a function value.

These restrictions usually have some sort of justification in the context of the language they're implemented in, but those reasons usually don't apply to first-class functions in general, and aren't an impediment to implementing them more generally in some other language.

Almost the same story with higher-order serialisation, just one level up.

So to clarify the difference I was getting at, any language that implements higher-order serialization is going to face the issue of how to deal with serializing actual code, and the other issues you've mentioned. These issues don't really have easy solutions, as you originally pointed out. A reasonable choice in the face of these difficulties is to compromise, e.g. by serializing some sort of code pointer. In light of the nature of these difficulties, something less than perfection could still reasonably be considered first-class, even if you're taking a fairly strict view of what it means to be first class.

Those dependencies and restrictions already exist within the original process (e.g., the external resource might suddenly become inaccessible for some reason). Serialisation does not add any new ones, which is the criterium I am suggesting.

You could say the same about a running program. Even serializing absolute memory pointers to code will work fine as long as the program continues running - but if it crashes or terminates, those pointers naturally become invalid. So serialization of function values containing code pointers doesn't add any new restrictions...?

In these cases, the restrictions imposed on first-class functions typically don't actually have to do with any inherent difficulty in implementing first-class functions

OK, I agree.

In light of the nature of these difficulties, something less than perfection could still reasonably be considered first-class, even if you're taking a fairly strict view of what it means to be first class.

Frankly, for my taste this comes too close to bending terminology for the sake of making something "look better" (whatever that means). But we probably have to agree to disagree.

Even serializing absolute memory pointers to code will work fine as long as the program continues running - but if it crashes or terminates, those pointers naturally become invalid.Even serializing absolute memory pointers to code will work fine as long as the program continues running - but if it crashes or terminates, those pointers naturally become invalid.

I don't follow. When you serialise a code pointer you are turning an internal "dependency" into an external one. That is a fundamental difference. The mentioned problems only exist for external references, internal dependencies are not an issue because a well-behaved language should always ensure their consistency.

To reiterate my point, I consider something fully first-class with respect to serialisation if and only if serialising it in process A and then deserialising it in process B produces an equivalent value that has no restrictions that did not exist (in principle) for the original. I think this is a relatively clear and useful definition. Of course, there will always be corner cases.

I agree that nailing down a specific definition is hard given the infinite possibilities of languages. Looking at a representative subset of popular languages, does give us some ideas for how to construct a good working definition.

Now as for your particular example, I would argue that it is a bit contrived. If I said language X doesn't have first-class functions, you would probably assume that one of the three bullets was violated, not that you couldn't serialize functions.

Saying "language X doesn't have first-class functions" is a particular statement that's interpreted according to its context. My point is that your definition relates to one such context, but that the term is also usefully used in other ways, and that its meaning is relative. For example, in this thread Philippa wrote in connection with ML structures and functors that "They're second-class within the ML language as a whole, but presumably first-class within the module language, no?" Similarly, the term can be and is used relative to the criteria listed on the Wikipedia page, quite naturally and without being contrived.

I feel the definition is on the right path but not specific enough (e.g. what does it mean to be "part of the world of expressions").

The "world of expressions" is terminology from John Backus (see his Turing Award Lecture for an example). He was a member of the group that defined FORTRAN, and later was a major supporter of FP. The "world of expressions" is the world of values defined by their relations, whereas the "world of statements" is the world of values defined by a sequence of operations. As the "world of expressions" grows, we have to deal with more relations; but the existing ones do not change. As the "world of statements" grows, the relations change (and grow) in ways that are difficult to predict.

Don't know about the others, but I've been working on a SICP translation to CAT. I kind of use chapter #1 of SICP to get a read on whether functions are first class. For example, section 1.1.8 defines the sqrt function in a couple of different ways. CAT easily manipulates top level functions:

define good_enough(guess x) {
   guess square x - abs_double 0.001 <
}
define improve(guess x) {
   guess x guess / average
}
define sqrt_iter(guess x) {
   guess x good_enough
      [guess]
      [guess x improve x sqrt_iter]
   if
}
define sqrt(x) {
   1.0 x sqrt_iter
}

However, CAT does not currently have the capacity to define functions within the scope of another function. So the following is not valid CAT code:

// invalid CAT
define sqrt(x) {
   define good_enough(guess x) {
      guess square x - abs_dbl 0.001 <
   }
   define improve(guess x) {
      guess x guess / average
   }
   define sqrt_iter(guess, x) {
      guess x good_enough
         [guess]
         [guess x improve x sqrt_iter]
      if
   }
   1.0 x sqrt_iter
}

CAT does have the ability to define anonymous lambda functions in scope. But there is a disconnect between top level function definitions, and functions which are defined in scope. Of course, it's probably unfair to single out CAT in this respect. Erlang and Ruby also have a disconnect between functions defined at module scope and those defined within another function.

[Edit Note: My own belief is that CAT, Erlang, Ruby and Python do not have a syntax that has functions being first class. But I don't think it to be fatal as each has the ability to do Higher Order Functions.]

But there is a disconnect between top level function definitions, and functions which are defined in scope.

Specifically there is a lack of local function names. I'll add that soon, since it is mostly syntactic sugar.

I don't believe lack of names makes the functions second class. In Cat, nothing else has a name so lacking names doesn't make local functions second-class to some other type of value AFAICS. I'm assuming here that not being first-class means "lacking some property of other values which can be intuitively understood as being first-class".

[Edit: removed earlier broken example]

Using my notion (curry/uncurry), I suspect the answer to all of these is yes (I haven't looked at Cat.) This is one of the benefits of it, it is independent of scoping, but it also leads to one of the drawbacks. My definition does not require any construct that is able to "capture" variables. I.e. nested or anonymous functions are sufficient but not necessary according to my "definition."

Since all these terms have well known definitions in the field, what is the motivation to come up with your own definitions?