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) { return f(g(x)); } (the long form with intermediates would work 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. An evaluation of an arbitrary composition of predefined functions, however, is possible: #include <stdio.h> typedef int FXN(int); int f(int x) { return x+1; } int g(int x) { return x*2; } int h(int x) { return x-3; } int eval(FXN *fs[], int size, int x) { for (int i=0; i<size; i++) x = (*fs[i])(x); return x; } int main() { // ((6+1)*2)-3 = 11 FXN *arr[] = {f,g,h}; printf("%d\n", eval(arr, 3, 6)); // ((6-3)*2)+1 = 7 arr[2] = f; arr[0] = h; printf("%d\n", eval(arr, 3, 6)); } 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, 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, the interchangeability of code and data together with the treatment of functions lend themselves extremely well for a recursive definition