Introduction to Programming in ATS:
<<< Previous	Modularity	Next >>>

Example: A Functorial Package for Rationals

The previous package for rational numbers contains a serious limitation: The type for the integers employed in the representation of rational numbers is fixed to be int. If we ever want to represent rational numbers based on integers of a different type (for instance, lint for long integers or llint for long long integers), then we need to implement another package for rationals based on such integers. It is clearly advantageous to avoid this style of programming as it involves code duplication to a great extent.

The approach we take in this section to implement a package for rational numbers that can address the aforementioned limitation follows the idea of functors in the programming language Standard ML (SML). We first introduce a type definition as follows:

typedef
intmod (a:t@ype) = '{
  ofint= int -> a
, fprint= (FILEref, a) -> void
, neg= (a) -> a // negation
, add= (a, a) -> a // addition
, sub= (a, a) -> a // subtraction
, mul= (a, a) -> a // multiplication
, div= (a, a) -> a // division
, mod= (a, a) -> a // modulo
, cmp= (a, a) -> int // comparison
} // end of [intmod]

Given a type T, intmod(T) is a boxed record type in which each field is a function type. A value of the type intmod(T) is supposed to represent a module of integer operations on integers represented by values of the type T. Similarly, we introduce another type definition as follows:

abst@ype rat (a:t@ype) = (a, a)

typedef
ratmod (a:t@ype) = '{
  make= (a, a) -<cloref1> rat a
, fprint= (FILEref, rat a) -<cloref1> void
, numer= rat a -> a // numerator
, denom= rat a -> a // denominator
, neg= (rat a) -<cloref1> rat a // negation
, add= (rat a, rat a) -<cloref1> rat a // addition
, sub= (rat a, rat a) -<cloref1> rat a // subtraction
, mul= (rat a, rat a) -<cloref1> rat a // multiplication
, div= (rat a, rat a) -<cloref1> rat a // division
, cmp= (rat a, rat a) -<cloref1> int // comparison
} // end of [ratmod]

Given a type T, a value of the type ratmod(T) is supposed to represent a module of rational operations on rationals represented by values of the type rat(T). The function we need to implement can now be given the following interface:

fun{a:t@ype} ratmod_make_intmod (int: intmod a): ratmod a

If applied to a given module of integer operations, the function ratmod_make_intmod returns a module of rational operations such that the integers in the former and the latter modules have the same representation. Therefore, ratmod_make_intmod behaves like a functor in SML. In the following code, we implement two modules ratmod_int and ratmod_dbl of rational operations in which integers are represented as values of the types int and double, respectively:

staload M = "libc/SATS/math.sats" // for [fmod]

val intmod_int = '{
  ofint= lam (i) => i
, fprint= lam (out, x) => fprintf (out, "%i", @(x))
, neg= lam (x) => ~x
, add= lam (x, y) => x + y
, sub= lam (x, y) => x - y
, mul= lam (x, y) => x * y
, div= lam (x, y) => x / y
, mod= lam (x, y) => op mod (x, y)
, cmp= lam (x, y) => compare (x, y)
} : intmod (int) // end of [val]

val ratmod_int = ratmod_make_intmod<int> (intmod_int)

val intmod_dbl = '{
  ofint= lam (i) => double_of (i)
, fprint= lam (out, x) => fprintf (out, "%0.f", @(x))
, neg= lam (x) => ~x
, add= lam (x, y) => x + y
, sub= lam (x, y) => x - y
, mul= lam (x, y) => x * y
, div= lam (x, y) => $M.trunc (x/y) // trunc: truncation
, mod= lam (x, y) => $M.fmod (x, y) // the modulo function
, cmp= lam (x, y) => compare (x, y)
} : intmod (double) // end of [val]

val ratmod_dbl = ratmod_make_intmod<double> (intmod_dbl)

An implementation of the function ratmod_make_intmod is available on-line and there is some related testing code available on-line as well.

<<< Previous	Home	Next >>>
Example: A Package for Rationals	Up	Specific Template Implementation