/* An opaque rational number (fraction) type.				*/
/* Invariant: denominator > 0.						*/
/* [] Comments on language issues are set off by these pseudo-quads. [] */
type Rational = struct rep {
    int		numerator;
    unsigned	denominator;
};

Rational 0 = {0, 1};
Rational 1 = {1, 1};

/* Calculate the greatest common denominator of two numbers, the first	*/
/* of which may be negative.  It is used to reduce rationals.		*/

/* [] Note that this function would have to be non-static if the	*/
/* operations that use it are implemented as inline functions in a	*/
/* "<Rational.h>" header.  This is a name-space pollution problem. []	*/
static void gcd(long a, long unsigned b) {
    long r;
    if (a < 0) a = -a;
    r = a % b;			/* [] C++ "declare anywhere" style would be
				      nice to have. []	*/
    while (r) {			/* Euclid's algorithm.	*/
	a = b;
	b = r;
	r = a % b;
    };
    return b;
}

/* Constructor for rationals. */
Rational a_rational(int num, unsigned denom) {
    extern void abort(void);
    Rational result;
    int gcd;
    if (denom == 0) abort();
    if (denom < 0) {
	num = -num;
	denom = -denom;
	}
    gcd = gcd(num, denom);	/* [] Hairy overloading! []	*/

    /* [] GNU style structure literals would be nice to have, too. []	*/
    result.numerator = num/gcd;
    result.denominator = denom/gcd;
    return result;
}

/* Explicit conversions to and from Rational.  Rational fits into the	*/
/* arithmetic type hierarchy between int and float.  Its relationships	*/
/* to long, unsigned, and long unsigned are deliberately undefined.	*/

/* [] I need a naming convention so that polymorphic functions		*/
/* can require conversion functions in assertions.  Let's try "widen"	*/
/* and "narrow" for safe and unsafe conversions.  Somewhere in "Design	*/
/* and Evolution of C++" (I can't find it again) Stroustrup says that	*/
/* too much existing code uses those names, but Cforall's wilder and	*/
/* woolier overload resolution may be able to handle the problem. []	*/ 

/* Convert an int to a Rational.  This conversion also handles short,	*/
/* char, and integer bit fields, thanks to implicit conversions to int. */ 
Rational widen(int i) {
    Rational result = {i, 1};
    return result;
}

/* Convert Rationals to floating point types. */
float widen(Rational r) {
    return (float)r.numerator/(float)r.denominator;
}

double widen(Rational r) {
    return (double)r.numerator/(double)r.denominator;
}

long double widen(Rational r) {
    return (long double)r.numerator/(long double)r.denominator;
}
    
/* Usage:								*/
/*     Rational r;							*/
/*     double d;							*/
/*     r = widen(7);							*/
/*     d = widen(r) + 1.5;						*/
/* [] Note that the target type of a conversion does not appear in the	*/
/* conversion expression!  Overload resolution must select the correct	*/
/* converter.  Sometimes this will be impossible because "widen"	*/
/* functions do not have conversion costs.				*/
/*     void f(double);							*/
/*     void f(float);							*/
/*     f(7);		  -- unambiguous (converts to float)		*/
/*     f(widen(r));	  -- ambiguous					*/
/*     f((float)widen(r)) -- unambiguous				*/
/* [] */

/* [] It is tempting to generalize the three floating point wideners	*/
/* to a polymorphic widener.						*/
/*     spec widenable_from_rat(type T) {				*/
/*         T widen(int);						*/
/*         T widen(unsigned);						*/
/*         T ?/?(T, T);							*/
/*     }								*/
/*									*/
/*     forall(type T | widenable_from_rat(T))				*/
/*     T widen(Rational r) {						*/
/*         return widen(r.numerator)/widen(r.denominator);		*/
/*     }								*/
/* Alas, Cforall does not allow this, because it requires that the	*/
/* value of T be inferrable from the argument of widen.			*/
/*    Even if it did work, I would have to provide the floating point	*/
/* wideners above, because Cforall doesn't define "float widen(int)",	*/
/* etc.									*/   
/*    However, "Rational widen(int)" can be generalized to any type	*/
/* that can be widened to int. []					*/ 
spec widenable_to_int(type T) {
    int widen(T);
}

forall(type T | widenable_to_int(T))
Rational widen(T num) {
    Rational result = {widen(num), 1};
    return result;
}

/* Convert Rationals to integral types.  Converting a negative		*/
/* Rational to an unsigned type is like converting a negative int: it	*/
/* is not an error.	*/
short narrow(Rational r) {
    return r.numerator/r.denominator;
    }

int narrow(Rational r) {
    return r.numerator/r.denominator;
    }

unsigned short narrow(Rational r) {
    return r.numerator/r.denominator;
}

/* [] As an alternative to "widen" and "narrow", consider an extension	*/
/* providing an overloadable "cast" operator `()?'.			*/
/*     Rational ()?(int i) {...}					*/
/*     int      ()?(Rational r) {...}					*/
/*     spec s(type T) {							*/
/*         T ()?(int);							*/
/*         T ()?(unsigned);						*/
/*         T ?/?(T, T);							*/
/*     }								*/
/*     forall(type T | s(T)) T ()?(Rational r) {...}			*/
/*     Rational r = (Rational)7;					*/
/*     int      i = (int)r;						*/
/*     extern type SomeType | s(SomeType);				*/
/*     SomeType s = (SomeType)r;					*/
/* - No clash with existing code that uses "widen" or "narrow".		*/
/* - The target type appears in the expression.				*/
/* - The target type can be polymorphic (although type inference is	*/
/*   handled specially).						*/
/*									*/
/* Now consider								*/
/*     void f(Rational);						*/
/*     f(7);								*/
/* Should Cforall implicitly apply the int-to-Rational cast to f's	*/
/* argument?  It seems the answer should be "yes": Cforall implicitly	*/
/* casts argument expressions to parameter types when possible in	*/
/* other cases.  But that would mess up overload resolution, because	*/
/* user-defined casts do not have a defined conversion cost or a	*/
/* "safe/unsafe" attribute.						*/
/*    Consider the polymorphic cast from Rational above.  Its safety	*/
/* and its conversion cost probably should depend on the safety and	*/
/* cost of the inferred ()? arguments.					*/
/*    Casts from Rational to float, double, and long double should be	*/
/* safe with costs 1, 2, and 3.  But then you create a "Longest" type	*/
/* for extended precision integers, also with casts to the floating	*/
/* types with costs 1, 2, and 3.  Now, what should the cost of a	*/
/* Longest-to-Rational cast be? []					*/ 

/* A typical operator group: multiplication.	*/
Rational ?*=?(Rational* t, Rational m) {
    /* Use long multiplication and reduce the number immediately, to	*/
    /* stave off overflow.						*/
    /* [] Perhaps exception handlers could catch overflow and reduce	*/
    /* only if necessary.  But overflow might be an imprecise		*/
    /* interrupt... []	*/
    long new_num = (long)t->numerator * m.numerator;
    long new_denom = (long)t->denominator * m.denominator;
    long gcd = gcd(new_num, new_denom);
    t->numerator = new_num/gcd;
    t->denominator = new_denom/gcd;
    return *t;
}

Rational ?*?(Rational a, Rational b) {
    return a *= b;
}

/* [] The lack of implicit conversions leaves two choices for mixed	*/
/* mode arithmetic: require the user to insert "widen" and "narrow"	*/
/* calls, or provide extra operators.  Polymorphism helps.  Note that	*/
/* only safe "widen" conversions are used; the `()?' extension would	*/
/* run into trouble here. []	*/
spec widenable_to_rat(type T) {
    Rational widen(T);
}
forall(type T | widenable_to_rat(T))
    Rational ?*=?(Rational *r, T m) { return *r *= widen(m); }
forall(type T | widenable_to_rat(T))
    Rational ?*=?(volatile Rational *r, T m) { return *r *= widen(m); }
forall(type T | widenable_to_rat(T))
    Rational ?*?(Rational a, T b) { return a *= widen(b); }
forall(type T | widenable_to_rat(T))
    Rational ?*=?(T a, Rational b) { return b *= widen(a); }

spec widenable_from_rat(type T) {
    T widen(Rational);
}
forall(type T | widenable_from_rat(T))
    Rational ?*=?(T *t, Rational m) { return *t *= widen(m); }
forall(type T | widenable_from_rat(T))
    Rational ?*=?(volatile T *t, Rational m) { return *t *= widen(m); }
forall(type T | widenable_from_rat(T))
    Rational ?*?(Rational a, T b) { return b *= widen(a); }
forall(type T | widenable_from_rat(T))
    Rational ?*=?(T a, Rational b) { return a *= widen(b); }

/* Local Variables: */
/* comment-multi-line:nil */
/* fill-column:70 */
/* End: */