Introduction to Programming in ATS:
PrevChapter 7. ModularityNext

Example: A Package for Rationals

Let us represent a rational number as a pair of integers. If we declare a boxed abstract type rat for values representing rational numbers, then each value of the type rat is stored in heap-allocated memory, which can only be reclaimed through garbage collection (GC). Instead, we follow an alternative approach by declaring rat as an unboxed abstract type. Therefore, a declaration like the following one is expected: 

abst@ype rat

The problem with this declaration is that it is too abstract. As there is not information given about the size of the type rat, the ATS compiler does not even know how much memory is needed for storing a value of the type rat. However, the programmer should not assume that such a form of declaration is useless. There are realistic circumstances where a declaration of this form can be of great importance, and this is a topic I will cover elsewhere. For now, let us declare an unboxed abstract type as follows: 

abst@ype rat = (int, int)

This declaration simply informs the ATS compiler that the representation for values of the type rat is the same as the one for values of the type (int, int). However, this information is not made available to the typechecker of ATS. In particular, if a value of the type rat is treated as a pair of integers in a program, then a type-error will surely occur.

The following code is contained in a file named ratmod.sats, which is available on-line. 

exception Denominator
exception DivisionByZero

fun rat_make_int_int (p: int, q: int): rat

fun ratneg: (rat) -> rat // negation
fun ratadd: (rat, rat) -> rat // addition
fun ratsub: (rat, rat) -> rat // subtraction
fun ratmul: (rat, rat) -> rat // multiplication
fun ratdiv: (rat, rat) -> rat // division

The exception Denominator is for reporting an erroneous occasion where a rational number is to be formed with a denominator equal to zero. Given two integers representing the numerator and denominator of a rational number, the function rat_make_int_int returns a value representing the rational number. The following implementation of rat_make_int_int can be found in a file named ratmod.dats, which is also available on-line. 

implement
rat_make_int_int (p, q) = let
  fun make (
    p: int, q: int
  ) : rat = let
    val r = gcd (p, q) in (p / r, q / r)
  end // end of [make]
//
  val () = if q = 0 then $raise Denominator
//
in
  if q > 0 then make (p, q) else make (~p, ~q)
end // end of [rat_make_int_int]

Given a pair of integers p and q such that q is not zero, the function rat_make_int_int returns another pair of integers p1 and q1 such that q1 is positive, p1 and q1 are coprimes, that is, their greatest common divisor is 1, and p1/q1 equals p/q. With rat_make_int_int, it is straightforward to implement as follows the arithmetic operations on rational numbers: 

implement ratneg (x) = (~x.0, x.1)

implement
ratadd (x, y) =
  rat_make_int_int (x.0 * y.1 + x.1 * y.0, x.1 * y.1)
// end of [ratadd]

implement
ratsub (x, y) =
  rat_make_int_int (x.0 * y.1 - x.1 * y.0, x.1 * y.1)
// end of [ratsub]

implement
ratmul (x, y) = rat_make_int_int (x.0 * y.0, x.1 * y.1)

implement
ratdiv (x, y) = (
if y.0 > 0
  then rat_make_int_int (x.0 * y.1, x.1 * y.0) else $raise DivisionByZero()
// end of [if]
) (* end of [ratdiv] *)

There is also some testing code available on-line that makes use of some functions declared in ratmod.sats.

PrevHomeNext
Abstract TypesUpExample: A Functorial Package for Rationals