English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
[Caml-list] classes vs modules
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2001-05-27 (13:31)
From: Tom _ <tom7ca@y...>
Subject: [Caml-list] classes vs modules
Sorry if this is a FAQ, but it doesn't seem

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) =
        let rec insert e t = ...
    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) =
        method insert e (t:'a treap) = ...
    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

 -- 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

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

 -- 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

 -- 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

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

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?


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