for review: big rats

[Bert Thompson]

Fergus Henderson <fjh at cs.mu.OZ.AU> writes:

Fergus,

Thanks for the suggestions. I've made the changes, with one remark below.

|The way to defining equality for a type is with `where equality is <blah>'
|in the type declaration, rather than by defining an =/2 predicate.
|It's probably a bug if the compiler does not at least warn you
|if you try to do that.

|In this case, the builtin unification will do the correct thing, so you
|can just delete this predicate.  However, a comment next to the type
|definition about the type's invariant and why it is needed (to ensure
|that the builtin equality gives correct results) would be a good idea.

I've done this, but I think adding the `where equality is <blah>'
approach may be preferable since it makes the code blindingly obvious:
it does what it says not what the comments say.
(Who has any faith in comments?)

Anyway, here's the diff...

------------------------------------------------------------
*** 1.4	1998/04/08 07:36:14
--- rational.m	1998/04/09 06:02:59
***************
*** 68,73 ****
--- 68,89 ----
  
  :- import_module require.
  
+ 	% The normal form of a rational number has the following
+ 	% properties:
+ 	%	- numerator and denominator have no common factors.
+ 	%	- denominator is positive.
+ 	%	- denominator is not zero.
+ 	%	- if numerator is zero, then denominator is one.
+ 	%
+ 	% These invariants must be preserved by any rational number
+ 	% constructed using this module since the equality predicate
+ 	% on rationals is simply Mercury's default unification
+ 	% predicate =/2. If the invariants were not maintained,
+ 	% we would have pathologies like r(-1,2) \= r(1,-2).
+ 	%
+ 	% The rational_norm/2 predicate generates rationals in this
+ 	% normal form.
+ 	%
  :- type rational
  	--->	r(integer, integer).
  
***************
*** 79,99 ****
  
  rational:'=<'(R1, R2) :-
  	Cmp = cmp(R1, R2),
! 	(Cmp = lessthan; Cmp = equal).
  
  rational:'>='(R1, R2) :-
  	Cmp = cmp(R1, R2),
! 	(Cmp = greaterthan; Cmp = equal).
! 
! rational(Num, Den) = rational_norm(r(integer(Num), integer(Den))).
  
! rational_from_integers(Num, Den) = rational_norm(r(Num, Den)).
  
! 	% We needn't call rational_norm since rationals can be
! 	% created only by the rational constructors or by rational
! 	% operations, the results of which must be normalised.
! rational:'='(r(An, Ad), r(Bn, Bd)) :-
! 	An = Bn, Ad = Bd.
  
  %% XXX: There are ways to do this in some cases even if the
  %% float conversions would overflow.
--- 95,109 ----
  
  rational:'=<'(R1, R2) :-
  	Cmp = cmp(R1, R2),
! 	(Cmp = lessthan ; Cmp = equal).
  
  rational:'>='(R1, R2) :-
  	Cmp = cmp(R1, R2),
! 	(Cmp = greaterthan ; Cmp = equal).
  
! rational(Num, Den) = rational_norm(integer(Num), integer(Den)).
  
! rational_from_integers(Num, Den) = rational_norm(Num, Den).
  
  %% XXX: There are ways to do this in some cases even if the
  %% float conversions would overflow.
***************
*** 109,116 ****
  rational:'-'(r(Num, Den)) = r(-Num, Den).
  
  rational:'+'(r(An, Ad), r(Bn, Bd)) =
! 	rational_norm(r(An*CA + Bn*CB, M)) :-
! 	M = lcm(Ad,Bd),
  	CA = M / Ad,
  	CB = M / Bd.
  
--- 119,126 ----
  rational:'-'(r(Num, Den)) = r(-Num, Den).
  
  rational:'+'(r(An, Ad), r(Bn, Bd)) =
! 	rational_norm(An*CA + Bn*CB, M) :-
! 	M = lcm(Ad, Bd),
  	CA = M / Ad,
  	CB = M / Bd.
  
***************
*** 119,127 ****
  
  rational:'*'(r(An, Ad), r(Bn, Bd)) =
  	% XXX: need we call rational_norm here?
! 	rational_norm(r((An//G1)*(Bn//G2), (Ad//G2)*(Bd//G1))) :-
! 	G1 = gcd(An,Bd),
! 	G2 = gcd(Ad,Bn).
  
  rational:'/'(R1, R2) =
  	R1 * inverse(R2).
--- 129,137 ----
  
  rational:'*'(r(An, Ad), r(Bn, Bd)) =
  	% XXX: need we call rational_norm here?
! 	rational_norm((An//G1)*(Bn//G2), (Ad//G2)*(Bd//G1)) :-
! 	G1 = gcd(An, Bd),
! 	G2 = gcd(Ad, Bn).
  
  rational:'/'(R1, R2) =
  	R1 * inverse(R2).
***************
*** 128,137 ****
  
  :- func inverse(rational) = rational.
  inverse(r(Num, Den)) = Rat :-
! 	(Num = izero ->
  		error("rational:inverse: division by zero")
  	;
! 		Rat = r(signum(Num)*Den,abs(Num))
  	).
  
  rational:numer(r(Num, _)) = Num.
--- 138,147 ----
  
  :- func inverse(rational) = rational.
  inverse(r(Num, Den)) = Rat :-
! 	( Num = izero ->
  		error("rational:inverse: division by zero")
  	;
! 		Rat = r(signum(Num)*Den, abs(Num))
  	).
  
  rational:numer(r(Num, _)) = Num.
***************
*** 138,162 ****
  
  rational:denom(r(_, Den)) = Den.
  
! rational:abs(r(Num,Den)) = r(abs(Num),Den).
  
! 	% The normal form of a rational number has the following
! 	% properties:
! 	%	- numerator and denominator have no common factors.
! 	%	- denominator is positive.
! 	%	- denominator is not zero.
! 	%	- if numerator is zero, then denominator is one.
! :- func rational_norm(rational) = rational.
! rational_norm(r(Num, Den)) = Rat :-
  	( Den = izero ->
! 		error("rational_norm: division by zero")
  	; Num = izero ->
! 		Rat = r(izero,ione)
  	;
  		Rat = r(Num2//G, Den2//G),
  		Num2 = Num * signum(Den),
  		Den2 = abs(Den),
! 		G = gcd(Num,Den)
  	).
  
  :- func gcd(integer, integer) = integer.
--- 148,166 ----
  
  rational:denom(r(_, Den)) = Den.
  
! rational:abs(r(Num, Den)) = r(abs(Num), Den).
  
! :- func rational_norm(integer, integer) = rational.
! rational_norm(Num, Den) = Rat :-
  	( Den = izero ->
! 		error("rational:rational_norm: division by zero")
  	; Num = izero ->
! 		Rat = r(izero, ione)
  	;
  		Rat = r(Num2//G, Den2//G),
  		Num2 = Num * signum(Den),
  		Den2 = abs(Den),
! 		G = gcd(Num, Den)
  	).
  
  :- func gcd(integer, integer) = integer.
***************
*** 207,217 ****
  
  :- pred is_zero(rational).
  :- mode is_zero(in) is semidet.
! is_zero(r(Num,_)) :-
  	Num = izero.
  
  :- pred is_negative(rational).
  :- mode is_negative(in) is semidet.
! is_negative(r(Num,_)) :-
  	Num < izero.
  
--- 211,221 ----
  
  :- pred is_zero(rational).
  :- mode is_zero(in) is semidet.
! is_zero(r(Num, _)) :-
  	Num = izero.
  
  :- pred is_negative(rational).
  :- mode is_negative(in) is semidet.
! is_negative(r(Num, _)) :-
  	Num < izero.