Function composition (computer science)

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 the composed function is passed to the composing one via a parameter. Because of this similarity, the syntax in program code tends to closely follow that in mathematics. As a subroutine, the feature appears in most programming languages.

For example, suppose we have two arithmetic functions $f$ and $g$, as in $z=f(y)$ and $y=g(x)$. One way of composing these two functions would be to first compute $y$, and then to compute $z$ from $y$, as in $y=g(x)$ followed by $z=f(y)$. In a programming context, the only obvious difference from mathematics involves notation. Here is the same example but implemented in the C programming language:

float foo (float x){ float y, z; y=g(x); z=f(y); return z; }

One could get the same result with the one line composition in mathematics $f(g(x))$, by the corresponding one line function in C:

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

Despite differences in length, these two implementations compute the same result (providing their data types are the same). The longer first implementation is known as the "single-assignment" form of function composition. This form is useful in the areas of parallel programming and embedding logic onto field programmable gate array devices (see Hammes, et. al). The shorter second example is known as "sequential composition" (Abadi and Lamport pg 96), since the result of the second function depends on the result of the first. Another type of functional composition known as "parallel composition" (Pierce and Turner pg 2) (Abadi and Lamport pg 96), enables a developer to compose two or more functions so that each runs in parallel on its own separate computer.

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, say, seven (see Miller) or more functions may have the opposite effect, making the code less maintainable.

A related issue is the dilemma of whether to compose (put together) or "factor" (break apart) functions for maintainability and code reuse.

In a functional programming language, such as Haskell, function composition can be expressed rather naturally. The example given above becomes: f . g using the composition operator (.) :: (b -> c) -> (a -> b) -> a -> c, 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 as: f . g = x -> f (g x)

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

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

References

* Henry Korn and Albert Liberi, "An Elementary Approach to Functions", New York, McGraw-Hill, 1974, ISBN 0-07-035339-5.
* Hal Daume III, "Yet another Haskell Tutorial", available at http://www.isi.edu/~hdaume/htut/tutorial.pdf.
* 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.
* Jeffrey Hammes, Bruce Draper, and Willem Böhm, "Sassy: A Language and Optimizing Compiler for Image Processing on Reconfigurable Computing Systems", "Proceedings of the International Conference on Vision Systems", Las Palmas de Gran Canaria, Spain, Jan 11-13, 1999.
* Martín Abadi and Leslie Lamport, "Composing Specifications", "ACM Transactions on Programming Languages and Systems", Vol 15. No. 1, January 1993. Pages 73-132.
* 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