First-class function

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (January 2008)

It has been suggested that Anonymous function be merged into this article or section. (Discuss)

In computer science, a programming language is said to support first-class functions (also called function literals, function types or exponential types^[1]) if it treats functions as first-class objects. Specifically, this means that the language supports constructing new functions during the execution of a program, storing them in data structures, passing them as arguments to other functions, and returning them as the values of other functions. This concept doesn't cover any means external to the language and program (metaprogramming), such as invoking a compiler or an eval function to create a new function.

These features are a necessity for the functional programming style, in which (for instance) the use of higher-order functions is a standard practice. A simple example of a higher-ordered function is the map or mapcar function, which takes as its arguments a function and a list, and returns the list formed by applying the function to each member of the list. For a language to support map, it must support passing a function as an argument.

There are certain implementation difficulties in passing functions as arguments and returning them as results. Historically, these were termed the funarg problems, the name coming from "function argument".

In type theory, the type of functions accepting values of type A and returning values of type B may be written as A → B or B^A. In the Curry-Howard correspondence, function types are related to logical implication; lambda abstraction corresponds to discharging hypothetical assumptions and function application corresponds to the modus ponens inference rule. Besides the usual case of programming functions, type theory also uses first-class functions to model associative arrays and similar data structures.

In category-theoretical accounts of programming, the availability of first-class functions corresponds to the closed category assumption. For instance, the simply-typed lambda calculus corresponds to the internal language of cartesian closed categories.

Availability

Languages which are strongly associated with functional programming, such as Lisp, Scheme, ML, and Haskell, all support first-class functions. Other languages which also support them include Perl, Python, PHP, Lua, Tcl/Tk, ECMAScript (JavaScript, ActionScript), Ruby, Io, Scala, and Nemerle.

Most modern, natively compiled programming languages (e.g. C, C++, C#, and Pascal) support function pointers, which can be stored in data structures and passed as arguments to other functions. Nevertheless, they are not considered to support first-class functions since, in general, functions cannot be created dynamically during the execution of a program without using reflection, which has an enormous performance impact. This could be mitigated by caching in some cases. The closest analog would be a dynamically compiled function created by a just-in-time compiler, which is compiled as an array of machine language instructions in memory and then cast to a function pointer, such as in C#. However, this technique is specific to the underlying managed framework architecture and is therefore not portable. But if using Windows, C# has a delegate type which is a type-safe function pointer. The C++ programming language supports user-defined operators, including the '()' operator, which allows first-class objects to be treated as functions. Those objects can be manipulated just like any other first-class object in C++, but such manipulations do not include changing the function itself at runtime. Additionally, real Lambdas (see Lambda Calculus) have no language support in the latest C++ standard (although they are included in the working draft of C++0x). C# supports lambdas in many uses, including anonymous methods. C# Version 3 adds a lamdba expression lexer and parser which run at compile-time and then a lambda code-generation portion of the compiler which executes at run-time.[1]

Examples

D

alias real delegate(real x) Delegate;
 
Delegate makeDerivative(Delegate f, real deltaX)
{
    return delegate real (real x)
    {
       return (f(x + deltaX) - f(x)) / deltaX;
    };
}
 
void main()
{
    real mySin(real s)
    {
        return std.math.sin(s);
    }
 
    Delegate cos = makeDerivative(&mySin, 0.000001);
    writefln(cos(0));
}

Erlang

-module(calculus).
-export([derivate/2]).
 
% F: function that takes a number and returns a number
% DeltaX: small positive number
% Returns a function that is an approximate derivative of F
 
derivative(F, DeltaX) ->
  fun(X) ->
    (F(X + DeltaX) - F(X)) / DeltaX
  end.

Scheme

(define square (lambda (x) (* x x))) ;assigning a function literal to a variable
(define fns (list + sin square)) ;functions as elements of a list
(define (compose f g) (lambda (x) (f (g x)))) ;a function that takes two functions as arguments and returns a composite function
((compose sqrt square) -3) ;function as return value of another function, applied to the argument -3
;the result is: 3
(define fns-squared (map (lambda (fn) (compose square fn)) fns)) ;compose the list of function with the square function -> list of functions
(map (lambda(fn) (fn 3)) fns-squared) ;apply each function to the argument 3
;the result is the list: (9 0.01991485667481699 81)

Lisp

(lambda (a b) (* a b)) ; function literal
((lambda (a b) (* a b)) 4 5) ; function is passed 4 and 5

ALGOL 68

PROC newton = (REAL x, error, PROC (REAL) REAL f, f prime) REAL:
# Newton's method #
  IF f(x) <= error
  THEN x
  ELSE newton (x - f(x) / f prime (x), error, f, f prime)
  FI;

print((
  newton(0.5, 0.001, (REAL x) REAL: x**3 - 2*x**2 + 6, (REAL x) REAL: 3*x**2 - 4**x),
  newline
));

ECMAScript

function(message) { print(message); } // function literal
SomeObject.SomeCallBack=function(message) { print(message); } // function literal assigned to callback

Note that the callee keyword in ECMAScript makes it possible to write recursive functions without naming them.

Python

Python creates functions by the def statement or the lambda expression. Although lambda expressions cannot create functions that use statements in their definition as they are confined to be just expressions, they are flexible enough to show that they create first class functions as well as if the more powerful def statement were used:

>>> #some built in functions and their inverses
>>> from math import sin, cos, acos, asin
>>> # Add a user defined function and its inverse
>>> cube = lambda x: x * x * x
>>> croot = lambda x: x ** (1/3.0)
>>> # First class functions allow run-time creation of functions from functions
>>> # return function compose(f,g)(x) == f(g(x))
>>> compose = lambda f1, f2: ( lambda x: f1(f2(x)) )
>>> # first class functions should be able to be members of collection types
>>> funclist = [sin, cos, cube]
>>> funclisti = [asin, acos, croot]
>>> # Apply functions from lists as easily as integers
>>> [compose(inversef, f)(.5) for f, inversef in zip(funclist, funclisti)]
[0.5, 0.49999999999999989, 0.5]
>>>

JavaScript

JavaScript supports both first class functions and lexical scope.

// f: function that takes a number and returns a number
// deltaX: small positive number
// returns a function that is an approximate derivative of f
function makeDerivative ( f, deltaX ) {
    return function (x) { 
       return ( f(x + deltaX) - f(x) )/ deltaX;
    };
}
var cos = makeDerivative( Math.sin, 0.000001);
// cos(0)     ~> 1
// cos(pi/2)  ~> 0

C#

C#, since version 3, supports anonymous functions and lambda expressions.

using System;
class Program
{
  // f: function that takes a double and returns a double
  // deltaX: small positive number
  // returns a function that is an approximate derivative of f
  static Func<double, double> MakeDerivative(Func<double, double> f, double deltaX)
  {
    return (x) => (f(x + deltaX) - f(x - deltaX)) / (2 * deltaX);
  }
  static void Main()
  {
    var cos = MakeDerivative(Math.Sin, 0.00000001);
    Console.WriteLine(cos(0));            // 1
    Console.WriteLine(cos(Math.PI / 2));  // 0
  }
}

Ruby 1.9

def deriv(f, dx)
  ->(x){ f[x + dx] - f[x] }
end
 
sin = ->(x){ Math.sin(x) }
 
cos = deriv(sin, 0.00000001)
 
puts sin[Math::PI / 2]
puts cos[Math::PI / 2]

Scala

 import Math._
 
 def deriv(f:Double => Double, dx:Double) = (x:Double) => f(x + dx) - f(x)
 
 val cos = deriv(sin, 0.00000001)
 
 Console.println(sin(Pi / 2))
 Console.println(cos(Pi / 2))

Haskell

 derivative f delta = \x -> (f (x+delta) - f x) / delta
 
 main = do
 	let sin' = derivative sin 0.00000001
 	let x = pi / 3
 	print (sin x)
 	print (sin' x)

See also

• Anonymous function
• Closure
• Function object
• First-class object

References

1. ^ Erik Meijer and Graham Hutton (1995). Bananas in Space: Extending Fold and Unfold to Exponential Types. ACM Press. pp. 324--333.