Function composition (computer science)

For function composition in mathematics, see function composition.

In computer science, function composition (not to be confused with object composition) is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in 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 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 for maintainability and code reuse. More generally, big systems might be built by composing whole programs.

Composing function calls

For example, suppose we have two functions <math>f</math> and <math>g</math>, as in <math>z=f(y)</math> and <math>y=g(x)</math>. Composing them means we first compute <math>y=g(x)</math>, and then use <math>y</math> to compute <math>z=f(y)</math>. Here is the example in the C programming language:

    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" (Cox pp 15–17). DeMarco empirically verifies an inverse relationship between surface area and maintainability (DeMarco pp 133–135). 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, 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:

    float foo (float x) { 
        return f(g(x));
    }

(the long form with intermediates would work just as well.) Example in Forth:

   : 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.

First-class composition

In functional programming languages, function composition can be naturally expressed as a higher-order function or operator. In 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 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.

In Javascript 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));
  }
 }

In Python, a way to define the composition for any group of functions, is using reduce 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

# Call the function x=10 : ((x-3)*2)+1 = 15
print (compose(f, g, h))(10)

Research Survey

Notions of composition, including the principle of compositionality 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.

• Steele directly applied function composition to the assemblage of building blocks known as 'monads' in the Haskell programming language.
• Bertrand Meyer addressed the software reuse problem in terms of composability.
• Martín Abadi and Leslie Lamport formally defined a proof rule for functional composition that assures a program's safety and liveness.
• Marcus Kracht identified a strengthened form of compositionality by placing it into a semiotic system and applying it to the problem of structural ambiguity frequently encountered in computational linguistics.
• Timothy van Gelder and Robert Port examined the role of compositionality in analog aspects of natural language processing.
• According to a review by Jeremy Gibbons, formal treatment of composition underlies validation of component assembly in visual programming languages like IBM's Visual Age for the Java programming language.

Large-scale composition

Whole programs or systems can thought of as functions, which can be readily composed if their inputs and outputs are well-defined . pipelines allowing easy composition of filters were so successful that it become a design pattern of operating systems.

Imperative procedures with side effects violate referential transparency 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.

References

• Martín Abadi and Leslie Lamport, "Composing Specifications", ACM Transactions on Programming Languages and Systems, Vol 15. No. 1, January 1993. Pages 73–132.
• Henry Korn and Albert Liberi, An Elementary Approach to Functions, New York, McGraw-Hill, 1974, ISBN 0-07-035339-5.
• Hal Daume III and others, "Yet another Haskell Tutorial", available at http://en.wikibooks.org/wiki/Haskell/YAHT.
• Tom DeMarco and Tim Lister,"Software Development: State of the Art vs. State of the Practice", in Why Does Software Cost So Much, and other puzzles of the Information Age, Tom DeMarco (Ed.), 1995, New York City: Dorset House, ISBN 0-932633-34-X
• Brad Cox, Object-oriented Programming, an Evolutionary Approach, Reading Mass,:Addison-Wesley, 1986.
• George A. Miller, "The Magical Number Seven, Plus or Minus Two: Some Limits on Our Capacity for Processing Information",Psychological Review, 1956, vol. 63, pp. 81–97.
• Benjamin C. Pierce and David N. Turner. "Pict: A programming language based on the pi-calculus". Technical report, Computer Science Department, Indiana University, 1997
• Guy L. Steele, Jr. "Building interpreters by composing monads". In Proceedings of the Twenty-First Annual ACM Symposium on Principles of Programming Languages, Portland, Oregon, January 1994.
• Bertrand Meyer, Object-oriented Software Construction, New York, Prentice Hall, 1988, pp 13–15, ISBN 0-13-629049-3
• Marcus Kracht, "Strict Compositionality and Literal Movement Grammars", LNCS, vol. 2014, 2001, pp 126–143.
• Timothy van Gelder and Robert Port, "Beyond Symbolic: Prolegomena to a Kama-Sutra of Compositionality", Symbol Processing and Connectionist Models in Artificial Intelligence and Cognition: Steps Toward Integration, Vasant Honavar and Leonard Uhr (Eds.), Academic Press, 1993.
• Jeremy Gibbons, "Towards a Colimit-Based Semantics for Visual Programming", Proceedings of COORDINATION 2002, LNCS 2315, Farhad Arbab and Carolyn Talcott (Eds.), 2002 Springer-Verlag Berlin-Heidelberg, pp. 167–173.

See also

• Functional decomposition
• Implementation inheritance
• Inheritance semantics
• Pipeline (Unix)
• Principle of compositionality
• Virtual inheritance