First Class Functions

Question

I started seriously taking a look at Lisp this weekend (by which I mean I have only been learning Lisp and not reverting back to projects in C#) and must say I love it. I have dabbled with other functional languages (F#, Haskell, Erlang) but haven't felt the draw that Lisp has given me.

Now as I continue to learn Lisp, I have started wondering why non-functional languages don't support first-class functions. I know that languages such as C# can do similar things with delegates and to an extent you can use pointers to functions in C/C++ but is there a reason why this would never become a feature in those languages? Is there a drawback to making functions first-class? To me, it is extremely useful, so I am lost as to why more languages (outside the functional paradigm) don't implement it.

[Edit]I appreciate the responses so far. Since I have been shown that many languages now support first-class functions now, I'll re-phrase the question to be why would it take so long for languages to implement them? [/Edit]

Answer 1

C#, VB.NET, Python, JavaScript, now even C++0x provides first-class functions.

Update:

An implementation of closures requires lambda-lifting - a technique originally quite alien for the imperative programmers. Proper first-class functions (which includes closures) requires at least some support from the runtime and VM. It also took some time to adopt the old functional techniques into the imperative world.

And, the most important part - first-class functions are barely usable if there is no garbage collection present. It was introduced into a mass programming only recently, with Java and, consequently, .NET. And the original Java approach was to oversimplify the language in order to keep it comprehandable by the average coders. .NET first followed, and only recently parted from that (IMHO, quite justified and appropriate) direction.

All such concepts takes time to be digested by the industry.

Answer 2

First-class functions are a lot less interesting without closures.

Closures aren't really possible without some kind of dynamic management of scope (garbage collection). One of the things that makes C/C++ so highly performant is the fact that it's a lot easier to compile a language where you manage memory manually, so that kinda takes C/C++ out of the equation.

And then yes, there is the matter of OOP impact. You no longer have a separation of methods and properties. Methods are themselves properties that accept functions as values. In that context, what does it really mean to overload methods since you can just swap the silly things out at any time. Can you really add that to Java, for instance, without introducing a major paradigm shift to the entire language? Where's the contract or that sense of (IMO false) security people get from knowing the construct guarantees it will always work the same way every time? It might make sense to treat functions tied to objects as methods as a different organism in languages that allowed functions to exist independently in the first place but in Java that's not really an option.

In JavaScript, OOP and functional are very much intertwined and I would personally find it hard to see first-class funcs as anything but bolted-on in languages where they weren't. But that requires a number of other paradigm-shifting changes including high levels of mutability in objects and their methods themselves as well as being able to call functions as if they were members of any object on the fly.

Languages aren't just tool-sets full of do-hickeys for getting things done for the most part. They're paradigms. Bundles of ideas, strategies, and opinions that all kind of go together in a way that's connected (or seem connected). In a lot of cases functions as noun and verb really just don't fit the paradigm at all or at best are an imperfect fit.

That said, I feel like I'm missing an arm when forced to code without them.

Answer 3

It's not really impossible. But it's yet another feature, and the complexity budget is limited. It may be considered unnecessary by (or not even occur to) the language designer - "why the heck would we need to pass functions around? This language is for programming an OS!". It may also take significant effort to merge with the rest of the language. For instance, a function type may require serious additions to the type system (e.g. in Java), even more if you have overloading (thanks @Renesis for pointing that out). You also need to provide some library code to make use of the viable - nobody wants to define map themselves.

It could also make other goals of the language harder to achive:

• It becomes "harder" to optimize (not actually harder in many cases, but requires different approaches than the ones you're used to). For instance, if global functions may be reassigned, you have to prove that f is never reassigned before you inline it.
• In a similar vein, if you make functions fully-featured objects, you need a smart compiler and JIT to remove the overhead associated with that and make calling as efficient (speed- and space-wise) as pushing arguments and return address and jumping to some address.
• As already mentioned, it's another full feature and the first steps towards supporting yet another paradigm - if you want a simple language, perhaps you can't afford to add first-class functions without throwing other stuff (which you may consider much more important) out.
• Perhaps it simply doesn't blend well with the rest of the language. If you design the language to e.g. be the best incarnation of OOP since Smalltalk, you may want to focus on that instead of offering another, very different, paradigm. Especially if it is hard to integrate the two (see above). N paradigms done well is more pleasant to program in than N+1 paradigms done badly.

In the same vein, one can ask why any programming language L1 doesn't have feature F of the very different language L2.

Answer 4

I think the first problem is a misunderstanding that Object-Oriented and Functional cannot be mixed. A quick list of languages described, at least by Wikipedia, as both: JavaScript, ActionScript, Python, C#, F#.

The second problem seems to be a definition of first-class functions - why do you not consider C# to have them, for example?

I'm not a functional language expert, so please correct me in the comments if I'm wrong, but my understanding is that the inclusion of first-class functions itself more or less defines whether a language supports a functional paradigm.

What's the real question?

So, understanding that object-oriented languages can also be functional, and these languages contain first-class functions, it sounds like the question you are looking for is why do some object-oriented languages not contain first-class functions?

Function overloading

One of the primary reasons for this is the difficulty of defining first class functions when the language has also chosen to support function overloading (example in Java):

public int dispatchEvent(Event event);
public int dispatchEvent(String event, Object data);

Which dispatchEvent function would a variable refer to?

Class-based programming

Class-based programming doesn't prevent a languages from supporting first-class objects, but it can make it more confusing or add questions to be answered.

ActionScript, for example, as an ECMAScript language started out in a much more functional paradigm like JavaScript. Functions weren't inherently bound to objects, they could essentially be called with any object as it's scope at the time of execution.

When you add (non-dynamic) classes, you have functions that are inherently bound to an instance, not just the class itself. This throws a few wrinkles into the specification of Function.apply that I honestly haven't dug in to find out how they have dealt with it.

Answer 5

I have wondered the same thing myself. Once I am in a language with lambdas I use them a LOT. Even PHP gets better when you realize that you can do a closure with php 5.3 (its not as nice as lisp, but still better)