Re: [Caml-list] Type Inference and Overloading

[Brian Hurt <bhurt@spnz.org>]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset=X-UNKNOWN; format=flowed, Size: 3753 bytes --]



On Mon, 10 Apr 2006, Tom Primo¾iè wrote:

> Does anyone have any idea what kind of algorithm and structures would the
> compiler need to deploy to correctly infer the types for these functions:
>
> a : int -> float -> int
> a : float -> int -> int

I'm not sure there is one- in fact, I don't think there is.  Consider if I 
have the following case as above, and then I type:

let g = a;;

what's the type of g?  Is it int -> float -> int or float -> int -> int?

What if I type:

let g x y = a y x;;

?  What happens if I define two functions:
val c: int -> float -> int
val c: int -> int -> int

and then say:
let h x = c 3 x;;

What type does h have?

As a more general rule, how I deal with overloading in Ocaml is to use 
modules and functors.  Say I want to implement Newton's method.  In other 
languages, I'd depend upon overloading (possibly even operator 
overloading).  In Ocaml, I'd do something like:

module type Req =
 	type t (* the type of the number system *)
 	val sub : t -> t -> t (* subtraction *)
 	val div: t -> t -> t (* division *)
 	val within_epsilon: t -> t -> bool
end

module Newtons(Alg: Req) = struct
 	let meth f df x =
 		let rec loop x =
 			let x' = Alg.sub x (Alg.div (f x) (df x)) in
 			if (Alg.within_epsilon x x') then
 				x'
 			else
 				loop x'
 		in
 		loop x
end;;

Of course, a real implementation would be more complicated than this, but 
this gets the idea across.  I could then create "overloaded" versions of 
my Newtons method just by calling the functor with the right modules, for 
example:

module Float = struct
 	type t = float
 	let sub = ( -. );;
 	let div = ( /. );;
 	let within_epsilon x y = (abs_float (x -. y)) < 1e-14;;
end;;

module FloatNewtons = Newtons(Float);;

Similiar code bits can give me Newton's method for integers (use an 
epsilon of 1), complexes, quaternions, even vectors/matricies.

Note that the performance overhead of using a functor is not signifigantly 
larger than the performance overhead of using virtual or overloaded 
functions- you're calling the sub, div, and within_epsilon functions via a 
function pointer either way.  And if you were to use ocamldefun, you could 
eliminate even that cost.

Another advantage of Ocaml's funtors over overloaded functions/operators 
is in documentation.  You can see, right up front, in the .mli file, what 
operations the algorithm needs.  And the compiler checks to make sure you 
are providing them.

The other important point to make here is that the operations provided to 
a module are not implicitly "part of" the object itself.  This is 
especially important with comparison functions (such as within_epsilon 
above)- I have come to the conclusion that comparison can *NOT* be a 
member function:
http://enfranchisedmind.com/blog/archive/2006/01/30/62
http://enfranchisedmind.com/blog/archive/2006/03/28/123

As an example of this problem in action (and how functors solve it), 
consider the above case except that sometimes I want to use a run-time 
defined value for epsilon, instead of the hardcoded 1e-14.  I could then 
do:

module FloatE = struct
 	(* floating point with variable epsilon *)
 	type t = float
 	let sub = ( -. );;
 	let div = ( /. );;
 	let epsilon = ref 1e-14;;
 	let within_epsilon x y = (abs_float (x -. y)) < !epsilon;;
end;;

module FloatENewtons = Newtons(FloatE);;


Now I have two different Newton's methods on floats: one that uses the 
fixed epsilon of 1e-14, and one that uses a variable epsilon.  Note that 
both FloatNewtons.meth and FloatENewtons.meth have the same type!  If the 
comparison method was built in, I'd need two different "types" of floats.

Brian