Theoretical foundation of polymorphism
From Wikipedia, the free encyclopedia.
| Missing image Merge_articles.png | It has been proposed that this article or section be merged with polymorphism (computer science).
This request may be discussed on the article's talk page. |
One could say that the beginnings of polymorphism are in the beginnings of the lambda calculus. The computational notion underlying polymorphism is simple: computations need not be static with respect to the data they use. Fluidity is attained by packaging computations into the famed "black boxes" and defining interfaces. A "polymorphic computation" is characterized by an external component that operates through an interface, or a convention. The designer of the outer computation (sometimes called a client - see Component Object Model) uses external information, which he mandates, to execute an arbitrary computation inside. The interface here, actual (tangible; mathematically substantial) or conditional, agreed upon by the designer of the outer and inner computations, is the pivot.
Consider a simple computation. Suppose we have a function, <math>f(x)<math>. We would like to approximate its derivative, given that we can - and can only - compute its value at any real number <math>x<math>. How to go about it?
We know that the expression
- <math>[f(x + dx) - f(x - dx)]/2(dx)<math>
for a small value <math>dx<math> - the smaller, the better - is an approximation to the limit which gives us the "exact" derivative. We also know that this expression applies to any continuous function <math>f(x)<math>.
Now suppose we wanted to define a computation that produced a function from the real numbers to the real numbers that approximates the derivative of f at x. In general, we are describing a class of computations - in any event one of the founding principles of program design. But this is an unusual class: it ranges not over some canonical, static (at least from the point of view of the user of a programming language) - simple - data, but over a dynamic class; in particular, continuous functions from the real numbers to the real numbers. What's more, we want for our result, not simple data, but another function yet - the function that approximates the derivative of a continuous function at a real value <math>x<math>.
Polymorphism is the name for the paradigm that allows us to agree that, if <math>f(x)<math> is really a continuous function from the real numbers to the real numbers, and we know how to compute it, then we can embed it inside a computation without concerning ourselves over how it is computed; and, altogether by analogy, that the user of our computation can apply its result without concerning himself with how it's computed, so that, if derivatives suddenly become integrals, he'll be able to grin and lean back in his hammock. What makes polymorphic code different from your ordinary modular program is that we are now talking not about single, disparate functions, but about an entire class of functions satisfying our definition (i.e., the interface). The interface is the agreement, both about f and about the function that our hypothetical derivative computation produces. This is the simple, elegant foundation for polymorphism; the entire abstract class paradigm in C++ can be reformulated in terms of it.
If we agree that the expression <math>deriv<math> is the above definition verbatim (with every symbol in place), then our polymorphic function can be defined like this:
- deriv-f(x) = D(f)|f:f(x)|x a real number; f continuous; deriv-f(x) a function from a real number to a real number
== deriv
Now, substituting exactly, instantiating D with f is equivalent to replacing each f in deriv with the body of a specific f; inside this f, the expression - umodified - is substituted for the argument in f. (This can become a little muddly, so let's say f is defined <math>f(y)<math>):
D(<math>y^2<math>) = <math>[(x + dx)^2 - (x - dx)^2]/2(dx)<math>
which is, of course, a function taking a parameter x and returning an approximation for the derivative of <math>y^2<math> == <math>x^2<math>.
