Function composition (computer science)

The concept underlying functional composition was borrowed from mathematics, more specifically, from the theory of functions (see Korn and Liberi). As such, it is a direct adaptation of function composition to computers.

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

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

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

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

These two implementations tell us that compositions may look very different, yet compute the same result. It furnishes insight into why there are so many programs that do exactly the same thing. The second implementation requires only one line of code and is colloquially refered to as a "highly composed" form. Readability and hence maintainability is one advantage of highly composed forms, since they require fewer lines of code. In other words, they minimize a program's "surface area". CAVEAT: It is possible to get carried away with highly composed forms to the point that a nesting of, say, seven (see Miller) or more functions has the opposite effect, making the code less maintainable. Some have attributed this compositional depth to why the otherwise elegant programming language LISP had not been more widely adopted.

The first form, the one having more surface area, is also known as a "single-assignment" form of functional composition. This form is useful in an area of parallel programming known as pipelining, and in embedding logic onto field programmable gate array devices (see Hammes, et. al). The example above illustrates a type of functional composition known as "sequential composition", since the result of the second function depends on the result of the first. Another type of functional composition known as "parallel composition", enables a developer to compose two or more functions so that each runs in parallel on its own separate computer.

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 paragraph is a sampling of the kind of research in which the notion of composition is central.

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.

References

Henry Korn and Albert Liberi, An Elementary Approach to Functions, New York, McGraw-Hill, 1974, pp. 223-227.
George 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.
Bertrand Meyer, Object-oriented Software Construction, New York, Prentice Hall, 1988, pp 13-15.
Martin Abadi and Leslie Lamport, "Composing Specifications", ACM Transactions on Programming Languages and Systems, Vol 15. No. 1, January 1993. Pages 73-132.
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", Procedings of COORDINATION 2002, LNCS 2315, Farhad Arbab and Carolyn Talcott (Eds.), 2002 Springer-Verlag Berlin-Heidelberg, pp. 167-173.

Research Survey

References

See also