Introduction to Programming in ATS:
Prev	Chapter 7. 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 I employ 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). Let us 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 operation
, 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, let us 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, 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, let us 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"

val ratmod_int = let
//
val intmod_int = '{
  ofint= lam (i) => i
, fprint= lam (out, x) => $extfcall (void, "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]
//
in
  ratmod_make_intmod<int> (intmod_int)
end // end of [val]

val ratmod_dbl = let
//
val intmod_dbl = '{
  ofint= lam (i) => g0i2f(i)
, fprint= lam (out, x) => $extfcall (void, "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) // truncation
, mod= lam (x, y) => $M.fmod (x, y)
, cmp= lam (x, y) => compare (x, y)
} : intmod (double) // end of [val]
//
in
  ratmod_make_intmod<double> (intmod_dbl)
end // end of [ratmod_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.

Prev	Home	Next
Example: A Package for Rationals	Up	Interaction with C