Friday, August 6, 2010

How to create function polymorphism in C

Why should we try for polymorphism in c?
There are already many high-level, easy-to-use languages out there with full object-oriented capabilities, including polymorphism. Why insist on doing this in C?
I am working on a communications systems simulator that is used, among other things, to estimate the complexity of different communication algorithms. It is able to do so at quite a low-level, keeping count of every operation required.
At one point, I found myself needing to execute the same algorithm, but with different data types. For instance, I wanted to compare performance when using floating-point versus fixed-point numbers. I hated the idea of maintaining several, almost identical versions of the different algorithms. We're talking a few thousand lines of code here.
This is the point where, in many situations, one switches to a language that is able to run the same code on several different data types — in other words, a language that supports polymorphism.
I had one main reason to do persist in using C, though: execution speed. It is not unusual for the simulator to take a few days to complete a test case, on modern hardware. I didn't want to think about extending this time any further. In my experience, C produces the fastest code of any language (excepting, maybe, carefully optimized assembler).
Another reason was just the plain challenge of doing it. It was an opportunity to learn more about C. For example, I had never needed to use function pointers before. Also, I believe that the ultimate test of whether you understand a high-level programming concept is to implement it in C.

How to do?
OK, on to the technical details.
My main objective was to be able to tell the program which data type to use, without having to recompile. This type is selected once, when the program is invoked. I don't need to change the type once the program has started.
This simplifies the problem a bit, but more general polymorphism is easy to create with one or two simple additions to the main idea I'll describe.
I'll show how to create a polymorphic function to add two numbers. The numbers can both be either int or double. We start by creating a new data type that can hold either an integer or a double.
Example: Composite data type
typedef union
{
double floatpt;
int integer;
} number;
A union is just like a struct, except that it can hold only one element at a time. The memory required by the union is that of the largest data type it can hold.
Now we create two functions to add numbers. Both operate on variables of type number, but one uses the int part and the other the double part.
Example: Two add functions
number add_floatpt(number x, number y)
{
number result;

result.floatpt = x.floatpt + y.floatpt;
return result;
}

number add_integer(number x, number y)
{
number result;

result.integer = x.integer + y.integer;
return result;
}
As can be seen, both functions take and return arguments of type number. Internally, one of them assumes the union contains an int, and the other assumes it contains a double. In each function, we use the built-in overloading of the + operator.
Now we're ready to create our polymorphic add function. What we'll do is create a function pointer, that points to add_floatpt or to add_integer.
Example: Function pointer
/* pointer to function
* function "add" will show polymorphism */

number (* add)(number, number) = NULL;

if( sel == 1 ) {
add = &add_floatpt;
}
else {
add = &add_integer;
}
Here we use a variable named sel to decide whether add will point to add_floatpt or to add_integer. In this example, this is done once when the program starts. It can just as easily be done each time add is called, although it is a bit messier.
Now, the rest of the program can happily go about its way, calling add whenever it needs to perform an addition, completely oblivious to the underlying data types.
Below I present a full example, with comments.
Example: Full source code

/* This program shows how to create a form of function polymorphism
 * using the C language
 *
 * The technique shown is nowhere near as powerful as what C++ or other OO
 * languages provide, but is useful for some applications.
 *
 * Compilation:
 * First, save the program as poly.c; then
 * compile with: gcc -o poly poly.c
 *
 * Usage:
 * The program takes three arguments:
 * poly TYPE X Y
 *
 * TYPE: if equal to 1, then X and Y are taken as floating point numbers,
 * otherwise, X and Y are taken as integers
 *
 * X, Y : two numbers of the type specified by TYPE
 *
 * The program will output the addition of X and Y.
 *
 * Examples:
 *
 * $ ./poly 1 2.0 3.0
 * Result = 5.00000
 *
 * $ ./poly 2 2 3
 * Result = 5
 *
 * */

#include <stdlib.h>

/* all quantities used by the program will be of type "number"
 * (a union is used to save memory) */
typedef union
{
double floatpt;
int integer;
} number;

/* the next two functions are used to add numbers. Each function knows how to
 * add a different type */
number add_floatpt(number x, number y)
{
number result;

result.floatpt = x.floatpt + y.floatpt;
return result;
}

number add_integer(number x, number y)
{
number result;

result.integer = x.integer + y.integer;
return result;
}

/* the next two functions are used to print the result. Each function knows how
 * to print a different type */
void print_floatpt( number x )
{
printf( "Result = %1.5f\n", x.floatpt );
}

void print_integer( number x )
{
printf( "Result = %d\n", x.integer );
}

int main( int argc, char *argv[] )
{
int sel;
number x, y, result;

/* pointers to functions.
         * functions "add" and "print" will show polymorphism */
number (* add)(number, number) = NULL;
void (* print)(number) = NULL;

sel = atoi( argv[1] );

/* make "add" and "print" point to the function of the correct type.
         * note that the option to use integers or floating-point values
         * is set at run time; there is no need to recompile. */
if( sel == 1 ) {
add = &add_floatpt;
print = &print_floatpt;
x.floatpt = atof( argv[2] );
y.floatpt = atof( argv[3] );

}
else {
add = &add_integer;
print = &print_integer;
x.integer = atoi( argv[2] );
y.integer = atoi( argv[3] );
}

/* from this point forward, "add" and "print" can be used as
         * polymorphic functions. As long as the program does all its
         * calculations using the "number" type, it doesn't care about
         * whether the underlying types are integers or floating point
         * numbers */
result = add( x, y );
print( result );

return 0;
}

No comments:

Post a Comment