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 Applied science, practical discipli ...
, function composition is an act or mechanism to combine simple
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 ...
s to build more complicated ones. Like the usual
composition of functions
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
in
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole.
Programmers frequently apply functions to results of other functions, and almost all programming languages allow it. In some cases, the composition of functions is interesting as a function in its own right, to be used later. Such a function can always be defined but languages with
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 ...
s make it easier.
The ability to easily compose functions encourages
factoring (breaking apart)
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 ...
s for maintainability and
code reuse
In software development (and computer programming in general), code reuse, also called software reuse, is the use of existing software, or software knowledge, to build new software, following the reusability principles.
Code reuse may be achie ...
. More generally, big systems might be built by composing whole programs.
Narrowly speaking, function composition applies to functions that operate on a finite amount of data, each step sequentially processing it before handing it to the next. Functions that operate on potentially infinite data (a
stream
A stream is a continuous body of water, body of surface water Current (stream), flowing within the stream bed, bed and bank (geography), banks of a channel (geography), channel. Depending on its location or certain characteristics, a stream ...
or other
codata) are known as
filter
Filter, filtering or filters may refer to:
Science and technology
Computing
* Filter (higher-order function), in functional programming
* Filter (software), a computer program to process a data stream
* Filter (video), a software component tha ...
s, and are instead connected in a
pipeline
Pipeline may refer to:
Electronics, computers and computing
* Pipeline (computing), a chain of data-processing stages or a CPU optimization found on
** Instruction pipelining, a technique for implementing instruction-level parallelism within a s ...
, which is analogous to function composition and can execute
concurrently.
Composing function calls
For example, suppose we have two
functions and , as in and . Composing them means we first compute , and then use to compute . Here is the example in the
C language
C (''pronounced like the letter c'') is a general-purpose computer programming language. It was created in the 1970s by Dennis Ritchie, and remains very widely used and influential. By design, C's features cleanly reflect the capabilities o ...
:
float x, y, z;
// ...
y = g(x);
z = f(y);
The steps can be combined if we don't give a name to the intermediate result:
z = f(g(x));
Despite differences in length, these two implementations compute the same result. The second implementation requires only one line of code and is colloquially referred to as a "highly composed" form. Readability and hence maintainability is one advantage of highly composed forms, since they require fewer lines of code, minimizing a program's "surface area". DeMarco and Lister empirically verify an inverse relationship between surface area and maintainability. On the other hand, it may be possible to overuse highly composed forms. A nesting of too many functions may have the opposite effect, making the code less maintainable.
In a
stack-based language, functional composition is even more natural: it is performed by
concatenation
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...
, and is usually the primary method of program design. The above example in
Forth
Forth or FORTH may refer to:
Arts and entertainment
* ''forth'' magazine, an Internet magazine
* ''Forth'' (album), by The Verve, 2008
* ''Forth'', a 2011 album by Proto-Kaw
* Radio Forth, a group of independent local radio stations in Scotla ...
:
g f
Which will take whatever was on the stack before, apply g, then f, and leave the result on the stack. See
postfix composition notation for the corresponding mathematical notation.
Naming the composition of functions
Now suppose that the combination of calling f() on the result of g() is frequently useful, and which we want to name foo() to be used as a function in its own right.
In most languages, we can define a new function implemented by composition. Example in
C:
float foo(float x)
(the long form with intermediates would work as well.) Example in
Forth
Forth or FORTH may refer to:
Arts and entertainment
* ''forth'' magazine, an Internet magazine
* ''Forth'' (album), by The Verve, 2008
* ''Forth'', a 2011 album by Proto-Kaw
* Radio Forth, a group of independent local radio stations in Scotla ...
:
: foo g f ;
In languages such as
C, the only way to create a new function is to define it in the program source, which means that functions can't be composed at
run time
Run(s) or RUN may refer to:
Places
* Run (island), one of the Banda Islands in Indonesia
* Run (stream), a stream in the Dutch province of North Brabant
People
* Run (rapper), Joseph Simmons, now known as "Reverend Run", from the hip-hop group ...
. An evaluation of an arbitrary composition of ''predefined'' functions, however, is possible:
#include
typedef int FXN(int);
int f(int x)
int g(int x)
int h(int x)
int eval(FXN *fs[], int size, int x)
int main()
First-class composition
In functional programming languages, function composition can be naturally expressed as a higher-order function or operator. In other programming languages you can write your own mechanisms to perform function composition.
Haskell
In
Haskell (programming language), Haskell, the example given above becomes:
foo = f . g
using the built-in composition operator (.) which can be read as ''f after g'' or ''g composed with f''.
The composition operator itself can be defined in Haskell using a
lambda expression:
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
The first line describes the type of (.) - it takes a pair of functions, and returns a function (the lambda expression on the second line).
Note that Haskell doesn't require specification of the exact input and output types of f and g; the a, b, c, and x are placeholders;
only the relation between matters (f must accept what g returns). This makes (.) a
polymorphic operator.
Lisp
Variants of
Lisp, especially
Scheme A scheme is a systematic plan for the implementation of a certain idea.
Scheme or schemer may refer to:
Arts and entertainment
* ''The Scheme'' (TV series), a BBC Scotland documentary series
* The Scheme (band), an English pop band
* ''The Schem ...
, the
interchangeability of code and data together with the treatment of functions lend themselves extremely well for a recursive definition of a
variadic In computer science, an operator or function is variadic if it can take a varying number of arguments; that is, if its arity is not fixed.
For specific articles, see:
* Variadic function
* Variadic macro in the C preprocessor
* Variadic template
...
compositional operator.
(define (compose . fs)
(if (null? fs) (lambda (x) x) ; if no argument is given, evaluates to the identity function
(lambda (x) ((car fs) ((apply compose (cdr fs)) x)))))
; examples
(define (add-a-bang str)
(string-append str "!"))
(define givebang
(compose string->symbol add-a-bang symbol->string))
(givebang 'set) ; > set!
; anonymous composition
((compose sqrt negate square) 5) ; > 0+5i
APL
Many dialects of
APL feature built in function composition using the symbol
∘
.
This higher-order function extends function composition to
dyadic application of the left side function such that
A f∘g B
is
A f g B
.
foo←f∘g
Additionally, you can define function composition:
o←
In dialect that does not support inline definition using braces, the traditional definition is available:
∇ r←(f o g)x
r←f g x
∇
Raku
Raku like
Haskell (programming language), Haskell has a built in function composition operator, the main difference is it is spelled as
∘
or
o
.
my &foo = &f ∘ &g;
Also like
Haskell (programming language), Haskell you could define the operator yourself. In fact the following is the Raku code used to define it in the
Rakudo
Rakudo is a Raku compiler targeting MoarVM, and the Java Virtual Machine, that implements the Raku specification. It is currently the only major Raku compiler in active development.
Originally developed within the Parrot project, the Rakudo sour ...
implementation.
# the implementation has a slightly different line here because it cheats
proto sub infix:<∘> (&?, &?) is equiv(& is assoc
multi sub infix:<∘> () # allows ` @array` to work when `@array` is empty
multi sub infix:<∘> (&f) # allows ` @array` to work when `@array` has one element
multi sub infix:<∘> (&f, &g --> Block)
# alias it to the "Texas" spelling ( everything is bigger, and ASCII in Texas )
my &infix: := &infix:<∘>;
Python
In
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
, a way to define the composition for any group of functions, is using
reduce
Reduction, reduced, or reduce may refer to:
Science and technology Chemistry
* Reduction (chemistry), part of a reduction-oxidation (redox) reaction in which atoms have their oxidation state changed.
** Organic redox reaction, a redox react ...
function (use functools.reduce in Python 3):
# Available since Python v2.6
from functools import reduce
def compose(*funcs) -> int:
"""Compose a group of functions (f(g(h(...)))) into a single composite func."""
return reduce(lambda f, g: lambda x: f(g(x)), funcs)
# Example
f = lambda x: x + 1
g = lambda x: x * 2
h = lambda x: x - 3
# Call the function x=10 : ((x-3)*2)+1 = 15
print(compose(f, g, h)(10))
JavaScript
In
JavaScript
JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
we can define it as a function which takes two functions f and g, and produces a function:
function o(f, g)
// Alternatively, using the rest operator and lambda expressions in ES2015
const compose = (...fs) => (x) => fs.reduceRight((acc, f) => f(acc), x)
C#
In
C# we can define it as a Func which takes two Funcs f and g, and produces a Func:
// Call example:
// var c = Compose(f, g);
//
// Func g = _ => ...
// Func f = _ => ...
Func Compose(params Func[] xs) => xs.Aggregate((accum, item) => x => accum(item(x)));
Ruby
Languages like Ruby (programming language), Ruby let you construct a binary operator yourself:
class Proc
def compose(other_fn)
->(*as)
end
alias_method :+, :compose
end
f = ->(x)
g = ->(x)
(f + g).call(12) # => 13824
However, a native function composition operator was introduced in Ruby 2.6:
f = proc
g = proc
(f << g).call(3) # -> 11; identical to f(g(3))
(f >> g).call(3) # -> 15; identical to g(f(3))
Research survey
Notions of composition, including the
principle of compositionality
In semantics, mathematical logic and related disciplines, the principle of compositionality is the principle that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them. ...
and
composability, are so ubiquitous that numerous strands of research have separately evolved. The following is a sampling of the kind of research in which the notion of composition is central.
* directly applied function composition to the assemblage of building blocks known as '
monads' in the
Haskell programming language
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming la ...
.
* addressed the
software reuse
In software development (and computer programming in general), code reuse, also called software reuse, is the use of existing software, or software knowledge, to build new software, following the reusability principles.
Code reuse may be achiev ...
problem in terms of composability.
* formally defined a proof rule for functional composition that assures a program's safety and liveness.
* identified a strengthened form of compositionality by placing it into a
semiotic
Semiotics (also called semiotic studies) is the systematic study of sign processes ( semiosis) and meaning making. Semiosis is any activity, conduct, or process that involves signs, where a sign is defined as anything that communicates something ...
system and applying it to the problem of structural
ambiguity frequently encountered in
computational linguistics.
* examined the role of compositionality in analog aspects of natural language processing.
*According to a review by , formal treatment of composition underlies validation of component assembly in visual programming languages like IBM's Visual Age for the
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
language.
Large-scale composition
Whole programs or systems can be treated as functions, which can be readily composed if their inputs and outputs are well-defined.
Pipelines allowing easy composition of
filters
Filter, filtering or filters may refer to:
Science and technology
Computing
* Filter (higher-order function), in functional programming
* Filter (software), a computer program to process a data stream
* Filter (video), a software component tha ...
were so successful that they became a
design pattern
A design pattern is the re-usable form of a solution to a design problem. The idea was introduced by the architect Christopher Alexander and has been adapted for various other disciplines, particularly software engineering. The " Gang of Four" b ...
of operating systems.
Imperative procedures with side effects violate
referential transparency
In computer science, referential transparency and referential opacity are properties of parts of computer programs. An expression is called ''referentially transparent'' if it can be replaced with its corresponding value (and vice-versa) withou ...
and therefore are not cleanly composable. However if one considers the "state of the world" before and after running the code as its input and output, one gets a clean function. Composition of such functions corresponds to running the procedures one after the other. The
monad
Monad may refer to:
Philosophy
* Monad (philosophy), a term meaning "unit"
**Monism, the concept of "one essence" in the metaphysical and theological theory
** Monad (Gnosticism), the most primal aspect of God in Gnosticism
* ''Great Monad'', a ...
formalism uses this idea to incorporate side effects and input/output (I/O) into functional languages.
See also
*
Currying
*
Functional decomposition
In mathematics, functional decomposition is the process of resolving a functional relationship into its constituent parts in such a way that the original function can be reconstructed (i.e., recomposed) from those parts by function composition.
...
*
Implementation inheritance
In object-oriented programming, inheritance is the mechanism of basing an object or class upon another object ( prototype-based inheritance) or class ( class-based inheritance), retaining similar implementation. Also defined as deriving new classe ...
*
Inheritance semantics In object-oriented programming, behavioral subtyping is the principle that subclasses should satisfy the expectations of clients accessing subclass objects through references of superclass type, not just as regards syntactic safety (such as the abs ...
*
Iteratee In functional programming, an iteratee is a composable abstraction for incrementally processing sequentially presented chunks of input data in a purely functional fashion. With iteratees, it is possible to lazily transform how a resource will emi ...
*
Pipeline (Unix)
In Unix-like computer operating systems, a pipeline is a mechanism for inter-process communication using message passing. A pipeline is a set of processes chained together by their standard streams, so that the output text of each process ('' std ...
*
Principle of compositionality
In semantics, mathematical logic and related disciplines, the principle of compositionality is the principle that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them. ...
*
Virtual inheritance
Virtual inheritance is a C++ technique that ensures only one copy of a base classs member variables are inherited by grandchild derived classes. Without virtual inheritance, if two classes B and C inherit from a class A, and a class D inherits fr ...
Notes
References
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*{{citation
, last = Steele , first = Guy L., Jr. , author-link = Guy L. Steele, Jr.
, contribution = Building interpreters by composing monads
, doi = 10.1145/174675.178068
, pages = 472–492
, title =
Proc. 21st ACM Symposium on Principles of Programming Languages
, contribution-url = http://groups.csail.mit.edu/mac/~dae/related-papers/steele.ps.Z
, year = 1994.
Programming language topics
Higher-order functions