why first-class functions

I am thinking about a design for a new programming language, and I can't decide whether to include first-class functions.

I understand (I think) how they work and when they might be used, but I can't think of any programming problem where the solution requires them. Can anyone give such an example?

Thanks, Mark.

There is no programming

There is no programming problem that "requires" anything but assembly language. ;)

By Andreas Rossberg at Tue, 2012-02-28 09:52 | login or register to post comments

Assembly

Andreas: There's no programming problem that even requires assembly. Just use your brain, augmented with pencil and paper if you must.

Absurd, of course: the point is efficiency. Computers can't do things we can't already do, they just do them faster. So given a need for programming at all, the requirement for high level languages follows from the performance requirement (since time taken writing code counts in as part of the overall problem solution time).

By skaller at Wed, 2012-02-29 22:17 | login or register to post comments

Unless...

Well, unless the problem description includes anything like illuminating certain pixels on my screen in certain patterns. ;)

By Andreas Rossberg at Thu, 2012-03-01 07:57 | login or register to post comments

Exactly.

Yes, exactly, I found the assertion that computers can't do anything that humans can't to be silly. While it may be true in some academic algorithmic sense, very often performance is a fundamental aspect of the problem. We use computers not only to execute algorithms, but also to manipulate and influence the world around us in real time (e.g. drawing pixels on a screen) in ways that humans simply cannot.

Also, computers can store and recall petabytes of data within an epsilon of 100% accuracy. Humans cannot do that.

By Leon P Smith at Thu, 2012-03-01 16:54 | login or register to post comments

Agreed

"Quantity has a quality all its own." On the other hand:

Also, computers can store and recall petabytes of data within an epsilon of 100% accuracy. Humans cannot do that.

Sure I can: with a computer!

By Matt Hellige at Thu, 2012-03-01 23:30 | login or register to post comments

RE: why inheritence in OOP?

this was an error... I intended to create an new topic, but instead created a reply to my first topic.

Mark.

By ad1mt at Tue, 2012-02-28 10:02 | login or register to post comments

from the perspective of a language like C

Languages that initially left some kind of first-class function out (I'm thinking of Ada and Eiffel) added them later despite the fact that Ada supported a very powerful notion of genericity while Eiffel supported polymorphism. Part of the problem was Ada and Eiffel had to interface with languages and libraries that relied on function pointers for call backs.

Functions like fold, map, reduce, which you see frequently in functional languages, where you want to write all the boiler plate associated with those once and then pass in an appropriate action. This is awkward to simulate with polymorphism because rather than being per-object it is per-context so you end up with situations where either a type belongs to a single parent in more than one way or you end up artificially splitting types depending on how you are going to use them.

By Robb Nebbe at Tue, 2012-02-28 16:12 | login or register to post comments

First class or higher order?

The two are not necessarily the same. I can imagine a language with map, filter, fold etc but without the ability to return functions or store functions in data structures, for example. Whether such a language is interesting I don't know. SQL springs to mind (limited set of aggregate functions).

By Neil Madden at Tue, 2012-02-28 21:34 | login or register to post comments

This is a very important

This is a very important point. I have long believed that the marginal benefit of HOFs is much greater than the marginal benefit of first-class functions. (Analogously, I believe that the marginal benefit of typeclasses is much greater than the marginal benefit of first-class objects.)

In particular, I can't remember the last time I needed to use first-class functions to express anything succinctly. At most, I've needed typeclasses + existential types.

By Chris King at Thu, 2012-03-01 19:59 | login or register to post comments

Existential Types

Can you show me an example where existential types are not strictly a superset of typed first-class functions?

By dmbarbour at Thu, 2012-03-01 20:05 | login or register to post comments

if you are designing a language

(which seems to be the context) I would have trouble arguing that some half-way solution would make sense. My point was that eliminating first-class functions hasn't really turned out as well as expected (by some very smart people) in languages that have actually tried to restrict them. So far it has mostly been a false economy.

By Robb Nebbe at Thu, 2012-03-01 21:49 | login or register to post comments

User-defined SQL aggregates

SQL springs to mind (limited set of aggregate functions)

Actually, most SQL database engines have some mechanism for user-defined aggregate functions, and interestingly (but not surprisingly) these must typically be expressed a left fold, or something close. (This is true of Oracle and PostgreSQL at least, I'm not sure about others. I glanced at SQL Server's documentation but didn't immediately understand what was going on.)

By Leon P Smith at Fri, 2012-03-02 03:24 | login or register to post comments

Fine-grained reuse

IMO, first-class functions are indispensable for fine-grained reuse of code. Whereas objects might be better for code reuse in the mid-size, encapsulating state and a collection of related logic, and modules might be better for code reuse in the large, encapsulating many types and related interfaces, first-class functions are really useful for cases where, e.g.:

A type or value has a single associated operation, e.g. print(), or draw(), or compare(), and you have collection of many of those values which you would like apply this operation to many elements, such as printing all the values, sorting an array of the values, finding a value, etc.

If you're considering leaving first-class functions out, I would encourage you to not do so :)

By Ben L. Titzer at Tue, 2012-02-28 17:26 | login or register to post comments

You could do away with

You could do away with first-class functions and have only objects, as long as you have a concise syntax for declaring anonymous objects. Single-method anonymous objects could also be just as concise as lambdas.

By naasking at Tue, 2012-02-28 20:12 | login or register to post comments

Objects and closures are equivalent

Reminds me of

The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures."
Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.
On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.

From here.

But actually I don't agree. I find first-class functions to be more terse and readable.

By Ben L. Titzer at Wed, 2012-02-29 00:20 | login or register to post comments

But actually I don't agree.

But actually I don't agree. I find first-class functions to be more terse and readable.

But that's just a syntactic artifact. See for instance first-class messages with match-functions, where objects are simply pattern-matching functions and messages are simply polymorphic sums. The syntactic parsimony of lambdas is preserved, but we have objects too.

Closures really are objects there, so your parable is apt. ;-)

By naasking at Wed, 2012-02-29 00:24 | login or register to post comments

Christian Queinnec meets Norman Adams

Re: â€œvenerable Master Qc Naâ€.

Shouldn't it be Master Cq Na?

Anton, what sayeth you?

By el-vadimo at Fri, 2012-03-02 13:33 | login or register to post comments

Missing the point

I think the point is being missed. C has first class functions already, they're formally closures .. already.

What's missing is the ability to nest them and form a closure over the enclosing (sic) context: in C the enclosing context is the global scope and that *is* closed over by C function pointers.

Whether or not you support object closures or just function closures, you have to bind to the subsequence of the execution frame stack consisting of the top most instance of each static object or function scope. Combined with the fact objects support multiple methods, they clearly provide a richer and more complex system.

Unfortunately a wealth of alternatives isn't always the best thing. Furthermore, closure over too deep or broad a scope is also evil.

It's a YMMV. Felix provides function closures (no OO), but they're implemented by "one method C++ class instances". Actually, there are a several methods (call, clone ..) but they're not user defined. After all you can always store a closure in another if you want to emulate multiple methods.

By skaller at Wed, 2012-02-29 22:58 | login or register to post comments

Second-class functions

True, they are closures in the sense you describe, but they are not first class. That would include the ability to define a function anywhere I can define any other value, i.e., also in nested scopes.

By Andreas Rossberg at Thu, 2012-03-01 08:01 | login or register to post comments

Custom control flow

The fucntion when done right, allows to implent custom control flow constructs and rich set of DSLs.

For example, I had firstly implemented asynchrnous control flow in the project AsyncObjects for Java using inner classes, and the result was barely usable. On other side both Groovy and Scala (AsyncScala) versions of the same idea were quick to implement and they were quite usable.

By const at Wed, 2012-02-29 09:19 | login or register to post comments

Parametrization is the fundamental redundancy-hunting tool

I like to present the lambda-calculus in this way : when you have redundancy in a piece of code, abstraction/parametrization is the fundamental tool to make it go away by "factorizing" over the (small) differences in the repeated pattern.

Imagine you have a complex piece of code repeated with small changes. For examples `norm12 = sqrt(1*1+2*2); norm23 = sqrt(2*2+3*3)`. It is natural to define a fuction `norm(x,y) = sqrt(x*x+y*y)` to factorize over those changes.

Now if the "variability point" of this piece of code happens to be a function call, you need higher-order functions: `ssn = succ(succ(n)); cddrli = cdr(cdr(li))` naturally calls for `twice(f,x) = f(f(x))`.

(More generally, I think a language is incomplete when users are tempted to write textual macros that cannot be represented as first-class values of the language. Most languages are incomplete in this regard; it's often just a quirk, but sometimes an acceptable compromise, as for example statically typing such parametrizations can be daunting.)

Some comments above have noted that higher-order functions may not be necessary if you have higher-order objects; well, of course, and I'd count that as having higher-order functions.

It is also possible to use defunctionalization to work around the lack of higher-order functions; you would write the previous example as `twice(f,x) := call(f, call(f,x))` with `call` a function taking the name -- symbol, string... -- of a function and applying its behavior:

  call(f,x) := switch(f) {
    "succ": return(x+1);
    "tl": return(cdr(x));
  }

The problem with defunctionalization is that it is usually a global, whole-program transformation: you need to define a `call` function that is aware of all functions possibly passed as arguments. In essence you are asking the programmer to compile higher-order-functions-using code by hand, and that breaks the modularity/maintainability properties of the program. People have been working on open/extensible data types that could be used for modular approaches to defunctionalization, but so far I haven't heard of any really satisfying solution to this problem.

PS: I have learned about defunctionalization in the paper Polymorphic Typed Defunctionalization and Concretization, by FranÃ§ois Pottier and Nadji Gauthir, 2006, which also discusses the modularity issues by relegates them to future work -- that never happened, as far as I know.

By gasche at Thu, 2012-03-01 09:51 | login or register to post comments

Parameterization

Parameterization fundamental? I suppose it is in lambda calculus. But there are other tools for redundancy elimination. If you pursue point-free, generative grammars, blackboard metaphor, concurrent constraint, and other programming styles you'll find many other mechanisms for controlling redundancy.

I've a renewed interest in reducing use of parameters, e.g. constraining to static parameters or staged programming at runtime.

By dmbarbour at Thu, 2012-03-01 16:58 | login or register to post comments

I don't think point-free is

I don't think point-free is contradictory to my argument here; though the name "parametrization" could be a little awkward here as it suggests the presence of an explicit parameter. Call it "abstraction" (which is actually the standard name, but I tried to avoid due to the wordplay with abstraction as encapsulation) or "context carving" if you like. The last one is particularly relevant in case of point-free styles: you'll still remove redundancies by factoring out the repeated patterns into, for example, definitions; if your language is expressive enough those patterns are contexts of the language, and you can represent those contexts either as lambda-terms or, if your combinator library is expressive enough, point-free terms.

When I say that abstraction/parametrization is fundamental, this is not a formal statement, but rather a gut feeling: the redundancy I am able to detect in code is characterized by textual patterns -- or rather "structural", if you want to scale to other code representations -- and it is natural to remove it by factoring it out by a definition. At this level of thought there is no attempt to make a conceptual difference between macros, functions, Prolog-like clauses, concurrent messaging processes... Those are semantically very different, but the main way they remove redundancy is by allowing one to represent the fixed part of a slightly varying pattern.

By gasche at Fri, 2012-03-02 07:29 | login or register to post comments

I use structures holding closures all the time

Maybe not as often as I use map, fold, etc., but they're far from uncommon in my code. Especially maps of closures. This makes a lot more sense once you start thinking in terms of arrows instead of functions. Arrows are just everything which is kinda of like a function (simplifying enormously here, I'll grant)- so arrows are the class of things that include functions and maps (as well as other things). So a nice way to create a function whose behavior is different depending upon the value of the first argument is to make a map of values to closures (which "back-end" to execute). This is especially convenient if the map is in some sense dynamic. Yeah, you can fake it without having closures stored in a map, but it's not nearly as clean (welcome to the Turing tarpit, in other words).

By Brian Hurt at Thu, 2012-03-01 16:24 | login or register to post comments

Lambda the Ultimate

User login

Navigation