One of the most pressing problems in designing computer algebra systems is the problem of avoiding repetition of structurally similar code for similar algebraic structures. This problem is serious because, in systems with deeply nested hierarchies of algebraic structures, a few repetitions of code at each level of the hierarchy may, in fact, lead to exponentially many repetitions of code in the entire system. Such code is hard to write and even harder to maintain and expand.
``Polymorphism'' is a solution for this problem. Two essentially different implementation methods for polymorphism are reported in the literature: Replacement of an ``abstract'' function call by a ``concrete'' call at compile-time (see, for example, the AXIOM Computer Algebra System, ) or, alternatively, modification of the abstract call at run-time by analyzing the type of the arguments (see, for example, the experimental Gröbner bases implementation in the Mathematica system described in ). Realization of the first approach needs a complicated static type analysis system but yields fast code. Realization of the second approach is straightforward in languages, like Mathematica, that allow user-defined type tags for objects . However, this approach results in drastically slower code. In our variant of polymorphism for C programs (and programs in similar languages), we use ``virtual'' function calls and explicit replacement of these calls at compile time by an easy preprocessor. This mechanism is not as general as the first approach but both easy to implement and efficient.