Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
In computer science, object composition is a way to combine simple objects or data types into more complex ones...
) is an act or mechanism to combine simple function
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, 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 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 functions make it easier.
The ability to easily compose functions encourages factoring (breaking apart) functions
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
Code reuse, also called software reuse, is the use of existing software, or software knowledge, to build new software.-Overview:Ad hoc code reuse has been practiced from the earliest days of programming. Programmers have always reused sections of code, templates, functions, and procedures...
. More generally, big systems might be built by composing whole programs.
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
and , as in and . Composing them means we first compute , and then use to compute . Here is the example in the C language
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
:
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
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
, and is usually the primary method of program design. The above example in Forth:
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 we want to name foo and use it as a function in its own right.
In all languages, we can define a new function implemented by composition. Example in C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
:
float foo (float x) {
return f(g(x));
}
(the long form with intermediates would work as well.) Example in Forth:
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, 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.
First-class composition
In functional programming languages, function composition can be naturally expressed as a higher-order
Higher-order function
In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:*take one or more functions as an input*output a function...
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
, 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
Lambda expression
Lambda expression may refer to:*Anonymous function*Lambda calculus#Definition...
:
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
The first lines describes the type of (.) - it takes a pair of functions and returns a function.
Note that Haskell doesn't require specification of the exact input and output types of f and g,
only the relations between them (f must accept what g returns). This makes (.) a polymorphic operator.
Variants of Lisp, especially Scheme, the interchangeability of code and data together with the treatment of functions lend themselves extremely well for a recursive definition of a variadic
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 templates...
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)))))
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
we can define it as a function which takes two functions f and g, and produces a function:
function o(f, g) {
return function(x) {
return f(g(x));
}
}
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, a way to define the composition for any group of functions, is using reduce
Fold (higher-order function)
In functional programming, fold – also known variously as reduce, accumulate, compress, or inject – are a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its...
function (use functools.reduce in Python3):
def compose(*funcs, **kfuncs):
"""Compose a group of functions (f(g(h(..)))) into (fogoh...)(...)"""
return reduce(lambda f, g: lambda *args, **kaargs: f(g(*args, **kaargs)), funcs)
Example
f = lambda x: x+1
g = lambda x: x*2
h = lambda x: x-3
In mathematics, semantics, and philosophy of language, 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. This principle is also called Frege's Principle,...
Composability is a system design principle that deals with the inter-relationships of components. A highly composable system provides recombinant components that can be selected and assembled in various combinations to satisfy specific user requirements...
, 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 (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
Code reuse, also called software reuse, is the use of existing software, or software knowledge, to build new software.-Overview:Ad hoc code reuse has been practiced from the earliest days of programming. Programmers have always reused sections of code, templates, functions, and procedures...
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
Computational semiotics
Computational semiotics is an interdisciplinary field that applies, conducts, and draws on research in logic, mathematics, the theory and practice of computation, formal and natural language studies, the cognitive sciences generally, and semiotics proper...
system and applying it to the problem of structural ambiguity
Ambiguity
Ambiguity of words or phrases is the ability to express more than one interpretation. It is distinct from vagueness, which is a statement about the lack of precision contained or available in the information.Context may play a role in resolving ambiguity...
Computational linguistics is an interdisciplinary field dealing with the statistical or rule-based modeling of natural language from a computational perspective....
. 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 (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
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
Pipeline (Unix)
In Unix-like computer operating systems , a pipeline is the original software pipeline: a set of processes chained by their standard streams, so that the output of each process feeds directly as input to the next one. Each connection is implemented by an anonymous pipe...
In Unix and Unix-like operating systems, a filter is a program that gets most of its data from its standard input and writes its main results to its standard output . Unix filters are often used as elements of pipelines...
In software engineering, a pipeline consists of a chain of processing elements , arranged so that the output of each element is the input of the next. Usually some amount of buffering is provided between consecutive elements...
Referential transparency and referential opaqueness are properties of parts of computer programs. An expression is said to be referentially transparent if it can be replaced with its value without changing the behavior of a program...
and therefore are not cleanly composable. However if you consider the "state of the world" before and after running the code as its input and output, you get a clean function. Composition of such functions corresponds to running the procedures one after the other. The Monads formalism uses this idea to incorporate side effects and I/O into functional languages.
Functional decomposition refers broadly to the process of resolving a functional relationship into its constituent parts in such a way that the original function can be reconstructed from those parts by function composition...
In Unix-like computer operating systems , a pipeline is the original software pipeline: a set of processes chained by their standard streams, so that the output of each process feeds directly as input to the next one. Each connection is implemented by an anonymous pipe...
In mathematics, semantics, and philosophy of language, 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. This principle is also called Frege's Principle,...
Virtual inheritance is a topic of object-oriented programming. It is a kind of inheritance in which the part of the object that belongs to the virtual base class becomes common direct base for the derived class and any next class that derives from it...
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
and 
, as in 
and 
. Composing them means we first compute 
, and then use 
to compute 
. Here is the example in the C language