As an example of generic programming, a generic quotient field (or field of fractions) construction algorithm is discussed.

The first step in representing these ideas in software is to devise an interface that describes the rings. Suppose that the rings are equipped with the basic ring operations, as well as several methods that implement desired computations.

`type/Ring` := '`module`(
    `+`::procedure,
    `*`::procedure,
    `-`::procedure,
    iszero::procedure,
    isone::procedure,
    zero, one
)':

This interface corresponds naturally with a formal mathematical characterization of the ring as a tuple

that satisfies a number of properties, and to which some computational capabilities have been added. Given the way operator overrides work in Maple, unary negation (-) is added. (In a more tightly integrated system, you specify the number and types of arguments to each of the procedures.)

For these computations, you need a slightly richer structure.

`type/GcdRing` := '`module`(
    `+`::procedure,
    `*`::procedure,
    `-`::procedure,
    quo::procedure,
    rem::procedure,
    gcd::procedure,
    unormal::procedure,
    iszero::procedure,
    isone::procedure,
    zero, one
)':

This interface extends the Ring interface defined previously. Note that nothing in the signature enforces any ring-theoretic properties (such as being an integral domain, or having unique factorization). It merely specifies the admissible operations. To compute with infinite rings (and even large finite ones), you do not require an enumeration of the elements of the ring. You can focus entirely on the effectively computable operations that the ring must support.

One of the simplest examples of a ring that supports the computations is the ring of integers $\mathbb{Z}$ in its native Maple representation.

MapleIntegers := module()
    description "the ring of integers";
    export `+`, `*`, `-`,
           gcd, unormal, iszero,
           isone, zero, one, rem, quo;
    `+` := ( a, b ) -> a + b;
    `*` := ( a, b ) -> a * b;
    `-` := i -> -i;
    quo := ( a, b ) -> :-iquo( a, b );
    rem := ( a, b ) -> :-irem( a, b );
    gcd := ( a, b ) -> :-igcd( a, b );
    unormal := proc( i::integer )
        if i < 0 then
            -1, -i;
        else
            1, i; # includes 0
        end if;
    end proc;
    iszero := i -> evalb( i = 0 );
    isone := i -> evalb( i = 1 );
    zero := 0;
    one := 1;
end module:

This is a software representation of the ring of integers. The unit normal mapping is represented by the exported procedure unormal. It returns an expression sequence of length two, whose first member is a unit, and whose second member is the unit normal form of its argument. The product of the output values yields the input ring element. The other methods only invoke the corresponding built-in Maple operations.

type( MapleIntegers, 'Ring' );

$\mathrm{true}$

type( MapleIntegers, 'GcdRing' );

$\mathrm{true}$

The quotient field constructor produces a field. An interface that describes fields differs from the one for integral domains by the absence of a gcd method (since they are trivial) and the addition of the (unary) / operator that computes inverses. The methods rem and quo are also not included in the signature for fields, because they are trivial in a field. Two new methods are included:

make for constructing field elements from their numerators and denominators

embed, the natural embedding of the integral domain D into its field k of fractions.

Additionally, the two methods numer and denom allow the user to extract the components of a fraction.

`type/Field` := '`module`(
    `+`::procedure,
    `*`::procedure,
    `-`::procedure,
    `/`::procedure,
    normal::procedure,
    iszero::procedure,
    isone::procedure,
    zero, one,
    make::procedure,
    embed::procedure,
    numer::procedure,
    denom::procedure
)':

Naturally, the ring $\mathbb{Z}$ of integers is not a field.

type( MapleIntegers, 'Field' );

$\mathrm{false}$

Fields produced by the quotient field constructor satisfy this interface.

Here is the generic constructor for quotient fields.

QuotientField := proc( R::GcdRing )
    description "quotient field functor";

    module()
        description "a quotient field";
        export `+`, `*`, `-`, `/`,
               zero, one,
               iszero, isone,
               make,
               numer, denom,
               normal, embed;
        make := proc( n, d )
            local u, nd;
            if R:-iszero( d ) then
                error "division by zero";
            end if;
            u, nd := R:-unormal( d );
            'FRACTION'( u*n, nd );
        end proc;
        embed := d -> make( d, R:-one );
        numer := f -> op( 1, f );
        denom := f -> op( 2, f );
        zero := embed( R:-zero );
        one := embed( R:-one );
        iszero := f -> evalb( normal( f ) = zero );
        isone := f -> evalb( normal( f ) = one );
        normal := proc( f )
            local g, a, b;
            g := R:-gcd( numer( f ), denom( f ) );
            if R:-isone( g ) then
                f;
            else
                a := R:-quo( numer( f ), g );
                b := R:-quo( denom( f ), g );
                make( a, b );
            end if;
        end proc;
        `-` := f -> normal( R:-`-`( numer( f ) ), denom( f ) );
        `/` := f -> normal( make( denom( f ), numer( f ) ) );
        `+` := proc( a, b );
            use `+` = R:-`+`, `*` = R:-`*` in
                normal( make( numer( a ) * denom( b )
                                 + denom( a ) * numer( b ),
                              denom( a ) * denom( b ) ) );
            end use;
        end proc;
        `*` := proc( a, b )
            use `*` = R:-`*` in
                normal( make( numer( a ) * numer( b ),
                              denom( a ) * denom( b ) ) );
            end use;
        end proc;
    end module;
end proc:

Note: The source code for QuotientField.mpl is available in the samples/ProgrammingGuide directory of your Maple installation.

Most of the exported routines are straightforward. The fraction constructor make accepts two members of the ring R as arguments and returns the constructed fraction, which is represented by an unevaluated function call of the form

The exported procedure embed is the canonical embedding $\mathrm{\eta }$ of the integral domain into its quotient field, described previously. This makes the constructor functorial. The arithmetic operators are simple implementations of the familiar rules for fraction arithmetic:

After applying these simple formulae, the result is normalized by using a call to the local routine normal (not the top-level routine :-normal). The normal routine does most of the interesting work in the ring generated by this constructor. It uses the manifestation of the division algorithm in the ring R via the exported procedures quo and gcd to reduce each fraction to the lowest terms. The fraction constructor make and the method normal represent field elements by the normal form representative of the appropriate equivalence class. The make routine prevents division by zero, and forces denominators to be unit normal representatives. The normal routine ensures that fractions are reduced to lowest terms.

The most important property of the QuotientField functor is that it is generic. It relies solely on the GcdRing interface. No knowledge of the concrete representation of the input integral domain R (other than that it is a module that satisfies the required interface) is used in the construction. Therefore, it works with any implementation of the GcdRing interface that:

Implements the correct semantics for its public operations

Satisfies the abstract constraint that it be a software representation of an integral domain. (This constraint is required to ensure that the arithmetic operations are well defined.)

To construct the quotient ring of the ring MapleIntegers defined previously, proceed as follows.

FF := QuotientField( MapleIntegers );

$\mathrm{FF}≔\mathbf{module}\left(\right)...\mathbf{end\; module}$

type( FF, 'Field' );

$\mathrm{true}$

a := FF:-make( 2, 3 );

$a≔\mathrm{FRACTION}\left(2\&comma;3\right)$

b := FF:-make( 2, 4 );

$b≔\mathrm{FRACTION}\left(2\&comma;4\right)$

use FF in
    a + b;
    a * b;
    a / b;
end use;

$\mathrm{FRACTION}\left(7\&comma;6\right)$

$\mathrm{FRACTION}\left(1\&comma;3\right)$

$\mathrm{FRACTION}\left(4\&comma;3\right)$

Note: This is a complex representation of the field of rational numbers.

To illustrate the generic quality of this constructor, construct the field $\mathbb{Q}$[T] of rational functions in a single indeterminate T from a concrete representation of Maple rational polynomials.

MaplePoly := module()
      description "the ring of rational polynomials";
      export `+`, `*`, `-`,
             zero, one,
             iszero, isone,
             gcd, unormal,
             quo, rem;
      `+` := ( a, b ) -> expand( a + b );
      `*` := ( a, b ) -> expand( a * b );
      `-` := p -> -p;
      gcd := ( a, b ) -> :-gcd( a, b );
      unormal := proc( p )
          local lc;
          if iszero( p ) then
              one, zero;
          else
              use lc = lcoeff( p ) in
                  lc, :-normal( p / lc );
              end use;
          end if;
      end proc;
      iszero := p -> Testzero( p );
      isone := p -> Testzero( p - 1 );
      zero := 0;
      one := 1;
      rem := proc( a, b )
          local vars;
          vars := indets( {a,b}, 'name' );
          if nops( vars ) > 1 then
              error "expecting univariate polynomials, but received %1 and %2", a, b;
          end if;
          :-rem( a, b, op( vars ) );
      end proc;
      quo := proc( a, b )
          local vars;
          vars := indets( {a,b}, 'name' );
          if nops( vars ) > 1 then
              error "expecting univariate polynomials, but received %1 and %2", a, b;
          end if;
          :-quo( a, b, op( vars ) );
      end proc;
end module:

The unormal method produces the leading coefficient and monic associate of a given polynomial in $\mathbb{Q}$[T]. The remaining exports simply capture built-in Maple operations on univariate rational polynomials.

RR := QuotientField( MaplePoly );

$\mathrm{RR}≔\mathbf{module}\left(\right)...\mathbf{end\; module}$

type( RR, 'Field' );

$\mathrm{true}$

To make printed fractions more readable, introduce the following extension to the print command.

`print/FRACTION` := ( n, d ) -> sort( n ) / sort( d ):

Finally, construct a few examples, and test the arithmetic.

a := RR:-make( randpoly( 'T', 'degree' = 4, 'terms' = 3 ),
               randpoly( 'T', 'degree' = 4, 'terms' = 3 ) );
b := RR:-make( randpoly( 'T', 'degree' = 4, 'terms' = 3 ),
               randpoly( 'T', 'degree' = 4, 'terms' = 3 ) );
use RR in
    a + b;
    a * b;
    a / b;
end use;

$a≔\frac{4015T^4+6862T^2-6351T}{T^4+\frac{4}{73}{T}^3+\frac{83}{73}{T}^2}$

$b≔\frac{-620T^4+820T^2-800T}{T^3+\frac{7}{10}T+4}$

$\frac{-620T^7+\frac{290615}{73}{T}^6+\frac{8400}{73}{T}^5+\frac{1301945}{146}{T}^4+\frac{773617}{73}{T}^3+\frac{1421241}{365}{T}^2+\frac{230023}{10}T-25404}{T^6+\frac{4}{73}{T}^5+\frac{1341}{730}{T}^4+\frac{1474}{365}{T}^3+\frac{741}{730}{T}^2+\frac{332}{73}T}$

$\frac{-2489300T^6-962140T^4+725620T^3+5626840T^2-10697420T+5080800}{T^5+\frac{4}{73}{T}^4+\frac{1341}{730}{T}^3+\frac{1474}{365}{T}^2+\frac{741}{730}T+\frac{332}{73}}$

$\frac{-2489300T^6-5996950T^4-6019580T^3-2978108T^2-14261426T+15750480}{T^7+\frac{4}{73}{T}^6-\frac{420}{2263}{T}^5+\frac{2756}{2263}{T}^4-\frac{3243}{2263}{T}^3+\frac{3320}{2263}{T}^2}$