In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
and
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
, a function type (or arrow type or exponential) is the type of a
variable
Variable may refer to:
* Variable (computer science), a symbolic name associated with a value and whose associated value may be changed
* Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
or
parameter
A parameter (), generally, is any characteristic that can help in defining or classifying a particular system (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
to which a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
has or can be assigned, or an argument or result type of a
higher-order function taking or returning a function.
A function type depends on the type of the parameters and the result type of the function (it, or more accurately the unapplied
type constructor
In the area of mathematical logic and computer science known as type theory, a type constructor is a feature of a typed formal language that builds new types from old ones. Basic types are considered to be built using nullary type constructors. S ...
, is a
higher-kinded type). In theoretical settings and
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s where functions are defined in
curried form, such as the
simply typed lambda calculus
The simply typed lambda calculus (\lambda^\to), a form
of type theory, is a typed interpretation of the lambda calculus with only one type constructor (\to) that builds function types. It is the canonical and simplest example of a typed lambda c ...
, a function type depends on exactly two types, the
domain ''A'' and the
range
Range may refer to:
Geography
* Range (geographic), a chain of hills or mountains; a somewhat linear, complex mountainous or hilly area (cordillera, sierra)
** Mountain range, a group of mountains bordered by lowlands
* Range, a term used to i ...
''B''. Here a function type is often denoted , following mathematical convention, or , based on there existing exactly (exponentially many)
set-theoretic functions mappings ''A'' to ''B'' in the
category of sets
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition o ...
. The class of such maps or functions is called the
exponential object
In mathematics, specifically in category theory, an exponential object or map object is the categorical generalization of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed c ...
. The act of
currying makes the function type
adjoint
In mathematics, the term ''adjoint'' applies in several situations. Several of these share a similar formalism: if ''A'' is adjoint to ''B'', then there is typically some formula of the type
:(''Ax'', ''y'') = (''x'', ''By'').
Specifically, adjoin ...
to the
product type
In programming languages and type theory, a product of ''types'' is another, compounded, type in a structure. The "operands" of the product are types, and the structure of a product type is determined by the fixed order of the operands in the prod ...
; this is explored in detail in the article on currying.
The function type can be considered to be a special case of the
dependent product type, which among other properties, encompasses the idea of a
polymorphic function.
Programming languages
The syntax used for function types in several programming languages can be summarized, including an example type signature for the higher-order
function composition function:
When looking at the example type signature of, for example C#, the type of the function is actually
Func,Func<B,C>,Func>.
Due to
type erasure In programming languages, type erasure is the load-time process by which explicit type annotations are removed from a program, before it is executed at run-time. Operational semantics that do not require programs to be accompanied by types are c ...
in C++11's
std::function, it is more common to use
templates
Template may refer to:
Tools
* Die (manufacturing), used to cut or shape material
* Mold, in a molding process
* Stencil, a pattern or overlay used in graphic arts (drawing, painting, etc.) and sewing to replicate letters, shapes or designs
Co ...
for
higher order function parameters and
type inference
Type inference refers to the automatic detection of the type of an expression in a formal language. These include programming languages and mathematical type systems, but also natural languages in some branches of computer science and linguistic ...
(
auto) for
closures.
Denotational semantics
The function type in programming languages does not correspond to the space of all set-theoretic functions. Given the
countably infinite type of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s as the domain and the booleans as range, then there are an
uncountably infinite
In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal num ...
number (2
ℵ0 =
c) of set-theoretic functions between them. Clearly this space of functions is larger than the number of functions that can be defined in any programming language, as there exist only countably many programs (a program being a finite sequence of a finite number of symbols) and one of the set-theoretic functions effectively solves the
halting problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
.
Denotational semantics concerns itself with finding more appropriate models (called
domains) to model programming language concepts such as function types. It turns out that restricting expression to the set of
computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
s is not sufficient either if the programming language allows writing
non-terminating computations (which is the case if the programming language is
Turing complete
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...
). Expression must be restricted to the so-called ''
continuous functions
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in valu ...
'' (corresponding to continuity in the
Scott topology
Scott may refer to:
Places Canada
* Scott, Quebec, municipality in the Nouvelle-Beauce regional municipality in Quebec
* Scott, Saskatchewan, a town in the Rural Municipality of Tramping Lake No. 380
* Rural Municipality of Scott No. 98, Saskat ...
, not continuity in the real analytical sense). Even then, the set of continuous function contains the ''parallel-or'' function, which cannot be correctly defined in all programming languages.
See also
*
Cartesian closed category
In category theory, a category is Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in math ...
*
Currying
*
Exponential object
In mathematics, specifically in category theory, an exponential object or map object is the categorical generalization of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed c ...
, category-theoretic equivalent
*
First-class function
In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from ...
*
Function space, set-theoretic equivalent
References
*
*
*
''Homotopy Type Theory: Univalent Foundations of Mathematics'', The Univalent Foundations Program, Institute for Advanced Study ''See section 1.2''.
{{Data types
Data types
Subroutines
Type theory