First Class, Higher Order Functions, Closures and Lambdas. What's What?
When first learning about functional programming the terms first-class function, higher-order function, closure and lambda are sure to come up. Those terms and concepts can be somewhat confusing to a functional programming novice. In this article I will try to shed some light on what each term means and how they are related.
First-class function
Programming languages that support first-class functions allow functions to be passed as arguments to other functions and returned as values from them. First-class functions can also be assigned to variables. In essence, a language supports first-class functions if it treats functions as regular values. That’s really all there is to first-class functions. Pretty simple right?
Here are some examples of what you can do in languages that support first-class functions:
//Declare a function that takes a variable of type `Function` as a parameter
function myFunction(b: Function)
//Return a function return value from another function
function myFunction() {
…
return function(){
…
}
}
//Assign a function to a variable
var f = function () {…}
The most common example of the usefulness of first-class functions is the map()
function. The map()
function takes some collection c
and a function f
as parameters. The function f in turn takes an element of the same type as the elements contained in the collection c
(It can also take an index and other arguments in some cases). The map()
function then returns a new collection d
which is simply the result of applying the function f
to every element of the original collection c
. Other common examples for first class functions are reduce()
and filter()
.
Higher-order function
Higher-order functions are simply functions that take one or more functions as arguments or return a function as a result (the function has to do at least one of those things to be considered a higher-order function). A function that does neither of those things is called a first-order function (not to be confused with first-class function!).
The concept of a higher-order function also exists in Mathematics, where the differential operator is a higher-order function, as it accepts a function and returns it's derivative, which is also a function.
function higherOrderFunction(a: Function) {
…
return function() {…}
Closures
A Closure is a type of first-class function. It is a function that captures or closes over its enclosing lexical scope. What does that mean? It means, that if you define a function and use variables inside that function that you have declared somewhere outside of that function, a closure will hold on to the references that point to those values, so that they still exist and can accessed even when the enclosing scope in which they where first declared no longer exists. Variables declared within the scope of the nested function are also called bound variables, while variables declared outside of the scope are free variables.
What's the point?
This can be useful when you define a nested function within a function and return that nested function as return value of the outer function assigning it to a variable. Once the outer function has returned, it will be gone along with all its declared variables. But what about the returned nested function that was assigned to a variable? That function will still have access to the values of the variables declared in the outer function, even though the outer function is gone. This is referred to as capturing those variables or closing over them, hence the name.
But how?
The way you can picture a closure in memory, is as a struct or an object holding references over which it closed and also including a function or a pointer to the function code. Wikipedia puts it well by stating that a closure is a ‘function together with an environment’.
When a closure is created, it stores references to all the free variables of its enclosing scope which it needs; sort of like a snapshot. This kind of makes sense for global variables which aren't declared in functions, but what about variables inside functions, which live on the stack. Shouldn't they cease to exist as soon as the enclosing function returns and its frame is popped from the stack? Well, languages with support for closures don't (usually) implement the call stack with an actual stack data structure. Instead, the call stack is implemented as a linked list on the heap (go figure). When a function returns, its node is removed from the list. If a closure has any references to variables on any frame, it simply keeps a reference to the node in question.
To make everything clearer, let’s look at an example:
function outer(a) {
return function increment() {
++a;
}
}
The outer function takes one argument and simply returns an inner function. The only thing the inner function does is to increment the value of the outer functions only parameter a. As soon as the outer function is called and its return value is assigned to incrementFromTen a closure is created, capturing a reference to the outer functions argument, which in this case happens to have a value of 10. Repeatedly calling incrementFromTen() will increment the captured value of a which has been captured by the closure, even though outer() has long returned.
Lambdas
A lambda is simply a function an anonymous function. Lambdas are often used as one off function arguments for higher-order functions.