Re: [Caml-list] stl?

[Jon Harrop <jon@ffconsultancy.com>]

On Wednesday 04 March 2009 06:11:18 Brian Hurt wrote:
> On Wed, 4 Mar 2009, Jon Harrop wrote:
> > Efficiency is only important in the context of functors when abstracting
> > very fast and common functions like arithmetic without defunctorizing
> > your code. I don't think that is why people avoid functors in OCaml.
>
> Arithmetic operators that are themselves very cheap.  The cost of
> functorization is large compared to, say, floating point addition- but
> small compared to the cost of, say, vector addition.

Depends how big your vectors are.

> And it's expensive only because Ocaml lacks an obvious optimization
> (defunctorization). 

If you neglect the enormous disadvantages: whole program analysis => no 
incremental compilation and no DLLs.

You can resolve the abstraction as soon as possible, as Haskell, does but then 
you're on the slippery slope to wildly unpredictable performance that renders 
the language too risky for a lot of real work.

> And yet this whole discussion is simply proving my point- we're comparing
> clock cycles here.

A circular argument: you brought up clock cycles.

> Yes, if you're writing the inner loops of a numeric 
> computation that'll take days to run, maybe, *MAYBE*, the cost difference
> of calling via a functor is worthwhile to worry about.

Definitely, not "maybe". The cost is over an order of magnitude for the 
fastest operations. Therefore, many forms of arithmetic including 
low-dimensional vector/matrix and interval arithmetic will suffer significant 
performance degradation.

> But that's the 
> point where I start being really tempted to drop down to C, or even
> assembly (for SSE Vectorization).

If you want to drop to anything, drop to LLVM because it is faster than C and 
easier than assembler.

> But for the vast bulk of people 
> programming, performance (at least on the clock cycle level) simply isn't
> that important

For some definition of "programming" that includes website design, maybe.

> - as demonstrated by all the "real work" being done in hideously slow
> languages like Ruby, Python, etc... 

Real work is done mostly in C++, Java and C# and proven predictable efficiency 
is a huge part of that.

> > I think that is a reflection of what the communities desire rather than
> > what they already have. OCaml is already fast (particularly on amd64) but
> > OCamlers always want even better performance. Haskell's development
> > experience is a real sore point and they want to address that. However, I
> > would also say that both communities are moving very slowly toward these
> > goals.
>
> Both languages have their annoyances.  Adjusting for the fact that I'm
> significantly more familiar with and comfortable with Ocaml, I don't find
> Haskell that much more difficult to work in.

F# can be much easier to work with than both OCaml and Haskell.

> >> The type classes comparison isn't even an analogy- it's a precise
> >> relationship. Anywhere you might be thinking, in Ocaml, "this would be a
> >> nice place to use a type class", use a functor.  You want operator
> >> overloading in Ocaml?  You got it: use a functor.
> >
> > Functors do not facilitate operator overloading. You still end up with a
> > combinatorial explosion in the number of operator names.
>
> Bwuh?
>
> Try this.  Let's reimplement Haskell's Fractional class, in Ocaml, and
> then do Newton's method using this new Fractional class.  Then I'll
> provide implementations that use both floats and ratios (arbitrary
> precision fractions).  First, we need to define Fractional.  That's just:
>
> module type Fractional = sig
>  	type t
>  	val ( +. ) : t -> t -> t
>  	val ( -. ) : t -> t -> t
>  	val ( *. ) : t -> t -> t
>  	val ( /. ) : t -> t -> t
>  	val fabs : t -> t
>  	(* other functions elided from brevity *)
> end;;
>
> Now we write our functorized Newton's method:
>
> module Make(F: Fractional) = struct
>
>  	open F;;
>
>  	let rec newtons epsilon f df x =
>  		let x' = x -. ((f x) /. (df x)) in
>  		if (fabs (x -. x')) < epsilon then
>  			x'
>  		else
>  			newtons epsilon f df x'
>  	;;
>
> end;;
>
> Now we provide an instance of Fractional for floats:
>
> module FloatFractional = struct
>  	type t = float
>  	let ( +. ) = ( +. );;
>  	let ( -. ) = ( -. );;
>  	let ( *. ) = ( *. );;
>  	let ( /. ) = ( /. );;
>  	let fabs x = abs_float x;;
> end;;
>
> module FloatNewtons = Make(FloatFractional);;
>
> Now we provide an instance for Ratios:
>
> module RatioFractional = struct
>  	type t = Ratio.ratio;;
>  	let ( +. ) = Ratio.add_ratio;;
>  	let ( -. ) = Ratio.sub_ratio;;
>  	let ( *. ) = Ratio.mult_ratio;;
>  	let ( /. ) = Ratio.div_ratio;;
>  	let fabs = Ratio.abs_ratio;;
> end;;
>
> module RatioNewtons = Make(RatioFractional);;
>
> Viola.  Operator overloading.  In Ocaml.

No, that is not overloading at all. You just replaced the functions wholesale.

Operator overloading is about being able to reuse an identifier to refer to 
different functions where the resolution depends upon the argument types. You 
have not accomplished that at all and your solution is uselessly fragile, 
which is precisely it is practically unheard of in real OCaml code in this 
context.

Look at another example, Knuth's algorithm for numerically robust variance:

  let f (m, s, k) x =
    let m' = m + (x - m) / float k
    m', s + (x - m) * (x - m'), k + 1

The "+" operator is used to mean both floating point addition and integer 
addition in the same expression. Functors cannot do that. You can replace "+" 
with float and int versions but only when they are in separate modules, so 
you not only end up breaking this simple expression into separate functions 
but even into separate modules. That's obviously crazy useless and, indeed, 
is precisely the motivation behind Christophe Troestlers's delimited 
overloading syntax extension.

So OCaml adopted + for int and +. for float. Sounds good but it scales really 
badly when you introduce 2D and 3D homogeneous vectors and matrices, 
arbitrary-dimensional vectors and matrices, quaternions, complex numbers and 
even a 32-bit float type. You need something closer to genuine overloading.

> >> If this causes you a
> >> knee jerk reaction about performance, ask yourself this: do you know how
> >> type classes are implemented in Haskell, and what their performance hit
> >> there is?  Now, imagine programming haskell where typeclasses are only
> >> used in a very places- Ord, Eq, Monad.  No Num.  No Monoid.  No Show.
> >> That's Ocaml.  Not that it has to be.
> >
> > I don't follow your breakdown. OCaml does not have Ord and Eq, it only
> > has a hack for structural equality. Same for Show. Few people care about
> > Monad, Num and Monoid.
>
> The turn you missed was that I'm say "what if Haskell programmers used
> type classes as rarely as Ocaml programmers use functors?"  Typeclasses
> are a huge win in Haskell, but primarily because they get *used*.

Right.

> > However, that is trivial to fix with run-time type information that can
> > convey per-type functions. Both F# and my HLVM already do that.
>
> I suppose we could sit around and whine that Ocaml doesn't have type
> classes, or reflection, or some other neat feature, that if it only had
> it, we could all these neat things with them.
>
> Or we could use the equivalently powerfull features Ocaml *already* has...

If you mean OCaml's objects, they also do not solve this problem.

IMHO, the only real solution is to build a new infrastructure for OCaml and 
its relatives that provides everything we want. Once you have something the 
community can contribute to efficiently, industry will back it and we can 
build something better using today's technology in a relatively short amount 
of time.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e