signature, datatype and module

The programming language ML allows us to specify an abstract data type in terms of its signature. The signature tells us what are the essential components of the data-type available to any program that uses the data-type. It is merely a specification of the type and a list of operations associated with an abstract data type. It specifies what the operations are, but not how they are implemented. Consider, for example, the following ML declaration of the signature of a rational number. 2Signature of rational signature Rational = sig type number; val makerat : int *int -> number; val plus : number * number -> number; val minus : number * number -> number; val mult : number * number -> number; val div : number * number -> number; val equalto : number * number -> bool; end; 3 The signature tells us that any implementation of the abstract data type Rational must define a data-type called number; a function called makerat for constructing a rational number given two integers, and the functions plus, minus, mult, div and equalto which allow us to manipulate rational numbers. Further, only these functions will be available as the interface of the abstract data type Rational for other programs to use.

In order to implement the data-type Rational we need a facility to glue two integers in to a compound value. We may do this in ML using the primitive declaration datatype and a constructor in the following way: 4datatype declaration datatype number = ratify of int*int; 5 The above declaration defines the data-type number to be a compound value created with the constructor ratify. Note that the choice of the name of the constructor is arbitrary and we could choose any name for the constructor. The constructor ratify accepts two input arguments and returns a compound value which is a pair with the two input arguments as parts. Thus, if the two input integers are a and b then the compound value is ratify(a,b). The compound value can be un-glued by a powerful ML concept called pattern matching. The ML declarations 6pattern matching fun numer(ratify(a,_)) = a; fun denom(ratify(_,b)) = b; 7 define numer and denom to be functions that accept compound items created with the constructor ratify as input and return the components a and b respectively as output. The mechanism for extracting the components a and b from the compound item is called pattern matching. The notation ratify(a,_) means that we do not care about the second argument in the pattern matching.

Armed with the above, we can now define an ML module called RAT1 which is our first implementation of the abstract data type Rational.

8Module RAT1 structure RAT1 : Rational = struct datatype number = ratify of int*int;

exception DenomIsZero;

fun gcd(a,b) = if b = 0 then a else gcd(b,a mod b);

fun makerat(n:int,d:int) : number = if d = 0 then raise DenomIsZero else let val pn = abs(n); val pd = abs(d); val sign = if n = 0 then 0 else (n div pn) * (d div pd); val g = gcd(pn,pd) in ratify(sign * pn div g,pd div g) end;

fun numer(ratify(x,_)) = x; fun denom(ratify(_,y)) = y;

fun plus(a,b) = let val x = numer(a)*denom(b) + numer(b)*denom(a); val y = denom(a)*denom(b); in makerat(x,y) end;

fun minus(a,b) = ... fun mult(a,b) = ... fun div(a,b) = ... fun equalto(a,b) = ... end; 9

Exercise 6.1   Complete the functions minus, mult, div and equalto in the above module definition.

The above ML module RAT1 is a particular implementation (a data structure) of the abstract data type Rational. The declaration 10structure declaration structure RAT1 : Rational = struct ... end; 11 specifies that the module RAT1 adheres to the signature Rational defined earlier. We can use the module RAT1 from the ML prompt in the following way. 12ML usage examples - val x = RAT1.makerat(2,4); val x = ratify (1,2) : RAT1.number - val y = RAT1.makerat(3, 6); val y = ratify ( 1,2) : RAT1.number - RAT1.plus(x,y); val it = ratify (0,1) : RAT1.number 13 In the above example DenomIsZero is declared to be an exception which is a standard data type in ML . The DenomIsZero exception is raised when the denominator is zero in makerat. A typical ML usage example is 14ML exception - RAT1.makerat(2,0); uncaught exception DenomIsZero raised at: rat.ml:23.13-23.24 15 We will illustrate later how to write code to catch and exception to facilitate a graceful exit.

Note that the ML module RAT1 uses the internal function gcd to reduce a rational number to its canonical form. It also uses functions numer and denom for the internal representation of the data type. However, since these functions are not a part of the signature Rational, they are not visible outside the module RAT1, and, consequently, an usage like RAT1.gcd(4,6) is illegal. Only those components of a module which are explicitly specified in the signature of the abstract data type are available for use from outside.

We have thus implemented the data-type for rational numbers using several abstraction barriers. At the lowest level is the pairing of integers using the primitive datatype and the constructor facility in ML . At the next higher level are our functions makerat, numer and denom. Using these functions we have defined, at a still higher level, our functions for manipulating rational numbers. Any user program at a higher level may now simply define variables of the type rational (RAT1.number), construct rational numbers using the function makerat and use the functions for carrying out arithmetic on rationals directly. The overall hierarchy is illustrated in Figure 6.2.

Figure 6.2: Abstraction barriers in the implementation of rational numbers

Thus, at the interface to the highest level of any program using rational numbers, only the functions RAT1.makerat, RAT1.plus, RAT1.minus, RAT1.mult, RAT1.div and RAT1.equalto need to be available. The rest of the detail of the implementation may be completely hidden from an user program. This is achieved through the signature declaration.

The above idea of hiding the details of the implementation of an abstract data type is key to modular programming. After all, in order to drive a car we need to know only the methods available - the use of the steering, the brake, the indicators ^6.1, the clutch and gear changing. We definitely do not want to know about the details of the transmission system, the viscocity of the brake fluid etc. These issues are relevant when we are designing a car, exactly in the same way the internal representation of the data type is relevant to the designer of the data-type module. This clear cut separations of concerns is key to succesful development of large programs.

We may even change the underlying representation of rational numbers without affecting any computation at the higher levels. For example, we may consider a totally different, though somewhat inefficient, implementation of our functions makerat, numer and denom. If we consider only positive rational numbers, we may define the function makerat as

$$makerat(n,d) = 2^{n/gcd(n,d)}*3^{d/gcd(n,d)}$$

The function $makerat$ then returns an integer as defined above. Using the unique prime factorization theorem which states that any positive integer can be uniquely expressed as a product of primes, we can define the functions $numer$ and $denom$ by simply counting the numbers or 2's and 3's, respectively, in the prime factorization of any integer returned by $makerat$. We may thus define these functions as

$$numer(r) = \left\{ \begin{array}{ll} 0 & \mbox{if $r\;mod\;2 \neq 0$} \\ numer(r\;div\;2) + 1 & \mbox{otherwise} \end{array}\right.$$

and

$$denom(r) = \left\{ \begin{array}{ll} 0 & \mbox{if $r\;mod\;3 \neq 0$} \\ denom(r\;div\;3) + 1 & \mbox{otherwise} \end{array}\right.$$

We can then implement an entirely different module (a different data structure) for the same abstract data-type Rational in the following way.

16Module RAT2 structure RAT2 : Rational = struct type number = int;

exception DenomIsZero;

fun gcd(a,b) = if b = 0 then a else gcd(b,a mod b);

fun power(x,n) = ...

fun makerat(n:int,d:int) : number = if d = 0 then raise DenomIsZero else let val pn = abs(n); val pd = abs(d); val sign = if n = 0 then 0 else (n div pn) * (d div pd); val g = gcd(pn,pd) in if sign = 0 then power(2,pn div g)*power(3,pd div g) else sign * power(2,pn div g)*power(3,pd div g) end;

fun numer(r : number) = let val sign = r div abs(r); fun niter(r,i) = if (r mod 2) <> 0 then i else niter(r div 2,i+1) in sign*niter(abs(r),0) end;

fun denom(r : number) = let fun niter(r,i) = if (r mod 3) <> 0 then i else niter(r div 3,i+1) in niter(abs(r),0) end;

fun plus(a,b) = let val x = numer(a)*denom(b) + numer(b)*denom(a); val y = denom(a)*denom(b); in makerat(x,y) end;

fun minus(a,b) = ... fun mult(a,b) = ... fun div(a,b) = ... fun equalto(a,b) = ... end; 17

Exercise 6.2   Verify that if we use the above definitions of the functions makerat, numer and denom, we do not need to modify any of the functions plus, minus, mult, div and equalto. Also verify that any top level program that was defined using the module RAT1 can be used unchanged with the module RAT2.

rat_java.nw01