[Caml-list] classes vs modules

[Tom _ <tom7ca@yahoo.com>]

Sorry if this is a FAQ, but it doesn't seem
listed.

I have been converting some SML code to OCAML, and
came across the following issue when converting a
Treap (randomized binary tree) data structure (in
fact, the analogous issue exists in SML).

The obvious module definition for a Treap is a
module like

    (* module-style implementation *)
    module Treap (Elt: ORDERED) =
      struct
        let rec insert e t = ...
        ...
      end
    module IntTreap =
	Treap(struct type t = int
              let lt (x:int) y = x<y end)

However, I can represent the same datatype as a
class as follows

    (* object-style implementation *)
    type 'a treap = Empty | Node of 'a treenode and
...
    class ['a] treapobj (lt: 'a -> 'a -> bool) =
      object
        method insert e (t:'a treap) = ...
        ...
       end
    let int_lt (x:int) y = x<y
    let inttreap = new treapobj int_lt
    inttreap#insert ...

This is, of course, roughly the equivalent of:

    (* closure-style implementation *)
    type 'a treap = Empty | Node of 'a treenode 
	and ...
    type 'a treapops = 
	{insert:'a -> 'a treap -> 'a treap; ...}
    let make_treap_ops (lt: 'a -> 'a -> bool) =
	let insert (e:'a) (t:'a treap) = ... in ...
	{ insert=insert; ... }
    let int_lt (x:int) y = x<y
    let inttreap = make_treap_ops int_lt
    inttreap.insert ...

Now, what are the differences between the two
approaches?

 -- In principle, with the module-based 
    implementation, IntTreap could 
    be optimized by inlining the
    "lt" function.  The compiler can statically
    determine the complete set of applications of
    the Treap functor that will occur in a
    program.  However, good ML implementations
    deliberately avoid taking advantage of this
    because they want to avoid code bloat.

 -- treapobj can be converted into a module without
    code duplication and without additional
    overhead:

    module TreapFromTreapObj (Elt: ORDERED) =
      struct
        let tobj = new treapobj Elt.lt
        let insert e t = tobj#insert
	...
      end

 -- treapobj is considerably more useful and flexible
    because the comparison function can be
    computed dynamically; this means that the
    compiler cannot statically determine all the
    comparison functions that treapobj might be
    used with, but as noted above, ML compilers
    avoid taking advantage of that knowledge
    anyway.

 -- Note that the "object-style" implementation is
    not the same as an imperative implementation
    you might find in a language like Java: the
    data structure itself and all its operations
    are purely functional.  The object merely
    holds the parameterization of the functions
    involved.

Now, the issue is that I can't find a way of
converting "module Treap" into the equivalent of a
"treapobj" without introducing considerable
overhead.  It seems any way of trying to do the
conversion involves wrapping up every element in a
class object.  This seems to limit somewhat the
reuse and functionality I can get out of existing
OCaml libraries written in a module style.

So, my question is: am I overlooking something?
Is there some way of getting the generality of the
object-based implementation out of pre-existing
module-based code without incurring significant
overhead?

If there isn't, wouldn't it make more sense to
write more datatypes in an object or closure style
and base module-style implementations on those?

It seems that the object-style approach is
somewhat like a limited form of first-class
modules.  Is there any more information about the
relationship between these approaches?

Thanks,
Thomas.

__________________________________________________
Do You Yahoo!?
Yahoo! Auctions - buy the things you want at great prices
http://auctions.yahoo.com/
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr