Introduction to Programming in ATS:
PrevChapter 17. From Genericity to Late-BindingNext

Example: Generic Operations on Numbers

There are many types of numbers in ATS. With function templates, we can greatly enhance code sharing in numerical computation. For example, we can give a generic implementation of matrix multiplication of the following interface: 

fun
{a:t@ype}
matrix_mul
  {p,q,r:int}
(
  p: int(p)
, q: int(q)
, r: int(r)
, A: &matrix(a, p, q)
, B: &matrix(a, q, r)
, C: &matrix(a?, p, r) >> matrix(a, p, r)
) : void // end of [matrix_mul]

and then use it to immediately obtain implementations of matrix multiplication for matrices of integers, matrices of floating point numbers, matrices of floating point complex numbers, etc. This approach is clearly far superior to relying on error-prone macros in C.

Let us take a look at a concrete example involving generic operations on numbers. The following code gives a standard implementation of the factorial function: 

//
extern
fun fact(n: int): int
//
implement
fact(n) =
  if n > 0 then n * fact(n-1) else 1
// end of [fact]
//

When applied to 100, fact is likely to return 0. This can be easily understood as the true value of the factorial of 100 is a multiple of 232 and the multiplication operation on integers of the type int is probably modulo 232. Suppose that we want to replace this multiplication operation with the one on floating point numbers of double precision. This can be done by implementing a slight variant of fact as follows 

//
extern
fun factd(n: int): double
//
implement
factd(n) =
  if n > 0 then n * factd(n-1) else 1.0
// end of [factd]
//

When applied to 100, factd should return a large floating point number. Obviously, there is a great deal of code duplication between the implementations of fact and factd. We can readily eliminate this duplication by introducing a generic implementation of the factorial function as follows: 

//
extern
fun{a:t@ype} gfact(n: int): a
//
implement
{a}(*tmp*)
gfact(n) = (
//
if n > 0
then gmul_int_val<a>(n, gfact<a>(n-1))
else gnumber_int<a>(1)
//
) (* end of [gfact] *)
//

With a bit of help from the support for overloading in ATS, we can rewrite gfact as follows: 

implement
{a}(*tmp*)
gfact(n) = let
//
overload * with gmul_int_val
//
in
//
if n > 0
then n * gfact<a>(n-1) else gnumber_int<a>(1)
//
end (* end of [gfact] *)

We can now implement fact and factd as follows: 

//
implement fact(n) = gfact<int>(n)
implement factd(n) = gfact<double>(n)
//

There is support in ATS based on the GNU multiple precision arithmetic library (GMPLIB) for integers of unlimited precision. The following code presents a way to compute the true value of the factorial of 100: 

//
#define
HX_INTINF_targetloc
"$PATSHOME/contrib/atscntrb-hx-intinf"
//
(* ****** ****** *)
//
staload _(*T*) =
"{$HX_INTINF}/DATS/intinf_t.dats"
staload _(*VT*) =
"{$HX_INTINF}/DATS/intinf_vt.dats"
//
staload
GINTINF =
"{$HX_INTINF}/DATS/gintinf_t.dats"
//
(* ****** ****** *)
//
typedef intinf = $GINTINF.intinf
overload print with $GINTINF.print_intinf
//
val () =
println! ("gfact<intinf>(100) = ", gfact<intinf>(100))
//

I only list some leading digits of the result: 

gfact<intinf>(100) = 933262154439441526816992388562667[...omitted...]

Please find on-line the file gnumber.dats containing the entirety of the code presented in this section plus some testing code.

PrevHomeNext
From Genericity to Late-BindingUpTemplates as a Special Form of Functors