Passing subroutines/functions through parameters

I am just wondering what the advantages are to languages that allow functions to be passed through parameters? 开发者_运维技巧 And hopefully an couple examples to go with this.

What popular programming languages allow this?

---

Suppose I have a collection of objects, and I want to sort them based on some criteria.

If I can pass a function to a function, it's easy:

collection.sort((a, b) => a.SomeProperty.compareTo(b.SomeProperty));

If I can't, then in order to do something like this I basically have to reimplement the sorting algorithm each time I want to sort based on different criteria.

---

The advantage is that you can parametrize functions over things that aren't easily expressed as plain values.

For example if you want to find an item which satisfies a certain predicate in a collection, or you want to find out whether all items in a collection satisfy a predicate, the predicate is most naturally expressed as a function from the element type to bool.

Another really common example is a sorting function which takes a comparison function as its argument, so the elements of a collection can be sorted by a custom sort key.

Of course in languages that don't allow functions as arguments, but which do have an object system (read: in java), you can work around this by using an object which implements a certain interface to the sorting function.

What popular programming languages allow [passing functions as arguments]?

C, C++, C#, Objective C, Python, Ruby, Perl, PHP, Javascript, and basically all functional or functionalish languages.

It should be noted that C and C++ (before C++0x), unlike the other languages in the list, don't have closures.

---

The advantage of being able to pass functions to other functions is that it allows you to write cleaner, more general code. For instance, consider a reasonably realistic function which sums all the numbers in a list:

sum []     = 0
sum (x:xs) = x + sum xs

This is in Haskell syntax, which may be unfamiliar to you; the two lines define two different cases, depending on whether the input is an empty list, in which case the sum is zero, or it's x prepended to the list xs, in which case the sum is x plus the sum of xs. In a more traditional language (not any one in particular), you'd have

function sum(xs) {
  var total = 0
  for x in xs {
    total = x + total
  }
  return total
}

Now, suppose we want to find the product of the numbers in a list, instead:

product []     = 1
product (x:xs) = x * product xs

In a traditional language, it'd look more like

function product(xs) {
  var total = 1
  for x in xs {
    total = x * total
  }
  return total
}

Interestingly, these two functions look pretty much the same. The only difference is that 0 is replaced with 1, and + is replaced with *. And indeed, it turns out that we can generalize both sum and +:

foldr f i []     = i
foldr f i (x:xs) = f x (foldr f i xs)

Here, foldr takes three arguments: a two-argument function f, a constant i, and a list. If the list is empty, we return the constant (e.g., sum [] = 0); otherwise, we apply the function to (a) the first element of the list, and (b) the result of folding the rest of the list. In a more traditional language, this'd look something like

function foldr(f,i,xs)
  var result = i
  for x in xs {
    result = f(x, result)
  }
  return result
}

This means that we can simplify sum and product to simply

sum     = foldr (+) 0
product = foldr (*) 1

(Here, (+) and (*) are two-argument functions which add and multiply their arguments, respectively.) You can't do this without first-class functions. (The other thing I'm doing is leaving off the last argument; this is called currying, and is rather handy. The idea is that if I don't give foldr all its arguments, it returns a function which is expecting the rest of them. But if you find it confusing, imagine the definitions say sum xs = foldr (+) 0 xs.)

But here's where things can get more interesting. Suppose you have a list of numbers, and you want to compute the square of every number in the list:

squares []     = []
squares (x:xs) = (x^2) : squares xs

function squares(xs) {
  var result = []
  for x in xs {
    result = result ++ [x^2]
  }
  return result
}

But this is clearly abstractable: almost exactly the same code would work if you wanted to negate every element of your list, or if you had a list of emails and wanted to get the senders, or whatever. So, we abstract:

map f []     = []
map f (x:xs) = f x : map f xs

function map(f,xs) {
  var result = []
  for x in xs {
    result = result ++ [f(x)]
  }
  return result
}

squares      = map (^2) # (^2) is the function which squares its argument.
negations    = map negate
emailSenders = map getSender

But interestingly enough, we can also implement map in terms of our previous foldr. First, we need to define function composition, .:

f . g = \x -> f (g x)

This says the composition of f and g is a new anonymous function of one argument, which itself applies g to x and f to the result. And so now, we can define map:

map f = foldr ((:) . f) []

Here, (:) is the function which takes an element and a list, and returns that element prepended to the list. (:) . f is the same as \x -> (:) (f x), which (under the currying rule I mentioned) is the same as \x xs -> f x : xs. In other words, at each step of the fold, prepend f x to what we have so far. (This doesn't gives us the reverse of map because foldr works "inside-out", as it were.)

This definition of map uses the higher-order function . to construct the function it passes to foldr. So many functions are being passed as parameters! And this lets us do things like write

f &&& g = \x -> (f x, g x)

And then use that to write

sendersAndRecipients = map (getSender &&& getRecipient) . fetchEmails

You gain a lot of power by being able to treat functions as values. You can write generic procedures like map or &&&, which allow you to write concise but readable code later. Passing around functions also comes in handy for callbacks: sendMessage(theMessage,fn), where fn is a function to be run when a response is received. It's just a very natural way to work.

As for what languages support this: honestly, Wikipedia'd know better than I would. But I'll give it a shot. C and C++ do, sort of: you can't write functions in-line, but you can pass function pointers around. It's not terribly common in either language though (even less in C). Any OO language can, if you define a class which has a single method which is the function you want, but this is terribly clunky. Nevertheless, this is what Java does. C#, on the other hand, actually has functions which can be passed as parameters. Ruby (which also has "blocks", which are a special syntax for certain use cases), Python, Perl, and JavaScript all support passing functions around, as does every functional programming language: the Lisps (Scheme, Common Lisp, Clojure, …); the ML family (SML, OCaml, …); Haskell (which could be lumped in with the ML family); Scala; and others. It's a useful feature, so it's not surprising to see it so wide-spread.