An Example: The Implementation of Monomials

The domain of monomials  over a field can be defined as the cartesian product of the field domain and the domain of power products. Multiplication of two monomials can be described as ``componentwise multiplication''. This definition of the product of two monomials is valid for any field of coefficients and any monoid of power products.

However, if we want to implement the algorithm, we must know, which particular field is used as the coefficient domain  and which particular monoid is used as the power product domain  in order to call the appropriate multiplication algorithms. This would result in different implementations of the multiplication algorithm for all combinations of subdomains.

Suppose all algorithm names have suffixes depending on the domain, for which they can be applied, such as rn for rational numbers, ff for finite fields, iel for integer exponent lists, and ge for Gödel exponents, which is another simple representation of power products. An Implementation of multiplication of monomials with rational number coefficients and integer exponent lists as representation for power products would look as follows:

 
product_mon_rn_iel(   ,   ) \+

  c =  product_rn(   ,   )

  pp =  product_iel(   ,   )

  return (c,pp) 

In contrast, an implementation for monomials with finite field coefficients and Gödel exponents as representation for power products would look as follows:

 
product_mon_ff_ge(   ,   ) \+

  c =  product_ff(   ,   )

  pp =  product_ge(   ,   )

  return (c,pp) 

In order to avoid this duplication of code, we introduce two virtual subdomains  named coefficient (suffix coef) and power_product (suffix pp). In the implementation of the multiplication algorithm for monomials we only use the multiplication of these subdomains resulting in one implementation:

 
product_mon(   ,   ) \+

  c =  product_coef(   ,   )

  pp =  product_pp(   ,   )

  return (c,pp) 

By an appropriate renaming of these calls in the preprocessing phase we establish the connection to the desired function. In C this can be done for instance by renaming product_coef to product_rn by #define  instructions to the C-preprocessor .

The general concept of virtual domains, virtual operations, and virtual data types is presented in more detail in the following sections.