[Caml-list] classes vs modules

[Caml-list] classes vs modules

[Tom _]

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

Re: [Caml-list] classes vs modules

[Markus Mottl]

On Sun, 27 May 2001, Tom _ wrote:
>  -- 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.

You can also make use of "dynamic" comparison functions using local
modules, e.g.:

  let f lt1 lt2 =
     let module Int1Treap = Treap (struct let lt = lt1 end) in
     let module Int2Treap = Treap (struct let lt = lt2 end) in
     ...

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

Well, it depends on what you mean with "overhead". OCaml may spend ages
generating closures depending on the particular case of local modules.

This, however, is a one-time effort (per call to enclosing function):
later calls to module functions do not cost any additional overhead. If
such modules are heavily used after their creation, you'll hardly
notice any difference to "statically" (misleading - see below) created
modules. With objects, you'll have a noticable overhead for every method
call (and for parameterization anyway).

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

There is still a distinction between modules that are parameterized at
runtime and modules that can be passed to and from functions. In fact,
closures arising from functor applications are _always_ computed at
runtime even at the toplevel, because this could cause side effects
like I/O (though the latter can be considered bad practice). In the
toplevel case these closures are only generated once and for all, but
people usually don't notice the startup overhead of their programs.

In short: your object-style approach is not really so much different from
the local module approach with the exception that object method lookups
come with the usual overhead. The only bonus for objects is that they can
reside within a polymorphic function, staying polymorphic themselves. I
am not sure whether this is really such a useful thing to have.

Out of curiousity, would it be unsound to allow functions like the
following:

  let f (cmp : 'a -> 'a -> bool) =
    let module SomeSet =
      Set.Make (struct type t = 'a let compare = cmp end) in
    ()

The compiler complains with:

  File "foo.ml", line 2, characters 49-51:
  Unbound type parameter 'a

This, however, is not true (in any case): 'a is bound by the explicit
function annotation. I am currently too lazy trying to find an example
where the type system could get a hole when the upper function were
allowed. Is there any?

Regards,
Markus Mottl

P.S.:  Please correct me if I have misexplained things...

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] classes vs modules

[Brian Rogoff]

On Sun, 27 May 2001, Markus Mottl wrote:
> Out of curiousity, would it be unsound to allow functions like the
> following:
> 
>   let f (cmp : 'a -> 'a -> bool) =
>     let module SomeSet =
>       Set.Make (struct type t = 'a let compare = cmp end) in
>     ()

You can do this now if you make a PolySet module by copying the
"monomorphic" implementation from the stdlib, changing elt and t to 
'a elt and 'a t and, using that instead of Set, something like:

let f (cmp : 'a -> 'a -> bool) =
  let module SomeSet =
    PolySet.Make 
      (struct type 'a t = 'a let compare = Pervasives.compare end) in
  ()

I use something very much like that in a few places, for example a
"uniquify" function on lists which eliminates duplicates.

I ended up creating polymorphic modules for a few of the stdlib modules on 
account of that old issue about functor instantiations recursive with a
type definition, so as to perform the ugly parameterization hack to
sidestep this ML limitation, but they are useful elsewhere too.

> The compiler complains with:
> 
>   File "foo.ml", line 2, characters 49-51:
>   Unbound type parameter 'a
> 
> This, however, is not true (in any case): 'a is bound by the explicit
> function annotation.

I thought you could never have type variables on the right hand side if
they were'nt also on the left? Besides, currently ML type annotations are 
without teeth, as you are well aware; as a translator of Okasaki's
algorithms you surely miss polymorphic recursion.

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] classes vs modules

[Markus Mottl]

On Sun, 27 May 2001, Brian Rogoff wrote:
> On Sun, 27 May 2001, Markus Mottl wrote:
> > Out of curiousity, would it be unsound to allow functions like the
> > following:
> > 
> >   let f (cmp : 'a -> 'a -> bool) =
> >     let module SomeSet =
> >       Set.Make (struct type t = 'a let compare = cmp end) in
> >     ()
> 
> You can do this now if you make a PolySet module by copying the
> "monomorphic" implementation from the stdlib, changing elt and t to 
> 'a elt and 'a t and, using that instead of Set, something like:

One could certainly do this. Still, I am not sure whether this issue
isn't slightly different here: 'a has to be bound, of course, and
parameterized types let you create such bindings, making them explicit
across interfaces. If the binding didn't exist, you could accidently
mix sets with incompatible elements.

Here, however, the type variable is indeed bound, and there is no way
that we can escape this binding (if I am not mistaken): if you happen
to use set elements like e.g. integers somewhere in this function, all
"'a"s there would unify to this type. This makes it impossible that we
can accidently mix incompatible instances of sets, because there is only
one (since explicitly bound) version of "'a".

If we don't restrict the type of "'a" in the function body by using
values of this type in specific contexts, it seems we can't do evil things
either. Note that you cannot return values from functions if the type of
these values is defined in a local module only (again, because the type
couldn't be identified outside anymore). But returning values of types
bound outside (also ones of type 'a) should be perfectly ok, n'est-ce pas?

> I thought you could never have type variables on the right hand side if
> they were'nt also on the left?

Well, the requirement is that the type variable be bound so as not to
lose track about its true identity. I am not an expert in type systems
so maybe I just don't see other problems. At least it seems to me that
a relaxation (generalization?) of the typing rules here would work
fine. In any case, the current error message is obviously misleading,
because 'a is really bound.

> Besides, currently ML type annotations are without teeth, as you are
> well aware; as a translator of Okasaki's algorithms you surely miss
> polymorphic recursion.

Sure, but as I said, I think your argument concerning mandatory type
declarations is a different issue.

Regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] classes vs modules

[Tom _]

> You can do this now if you make a PolySet module by
> copying the
> "monomorphic" implementation from the stdlib,
> changing elt and t to 
> 'a elt and 'a t and, using that instead of Set,
> something like:
> 
> let f (cmp : 'a -> 'a -> bool) =
>   let module SomeSet =
>     PolySet.Make 
>       (struct type 'a t = 'a let compare =
> Pervasives.compare end) in
>   ()

Thanks; that's very useful to know, and it seems
to be working.  I think it might be useful to feature
the ability to have polymorphic types in modules
a little more prominently in the documentation.
Maybe some of the standard modules could take
advantage of this more (it would require some
changes to their interfaces, I suppose).

The type signatures I get out of my module after
converting it are a little odd looking:

    type 'a t = 'a
    type 'a tree = Empty | Node of ...
    val insert :
	('a t t t -> 'a t t -> bool) -> 
	'a t t t -> 'a t tree -> 'a tree
    ...

Is there any useful information in the different
number of t's?  They should all be equivalent, right?

BTW, I opted for just passing the "lt" function
as explicit arguments to all the functions in the
module that need them.  That seems like the most
general approach, although it means some extra
arguments and it doesn't guarantee consistency,
as people might pass incompatible versions of "lt"
to different calls; a more convenient interface can
then be wrapped around that, maybe in a different
module

Cheers,
Tom.


__________________________________________________
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

Re: [Caml-list] classes vs modules

[Brian Rogoff]

On Sun, 27 May 2001, Tom _ wrote:

> > You can do this now if you make a PolySet module by
> > copying the
> > "monomorphic" implementation from the stdlib,
> > changing elt and t to 
> > 'a elt and 'a t and, using that instead of Set,
> > something like:
> > 
> > let f (cmp : 'a -> 'a -> bool) =
> >   let module SomeSet =
> >     PolySet.Make 
> >       (struct type 'a t = 'a let compare =
> > Pervasives.compare end) in
> >   ()
> 
> Thanks; that's very useful to know, and it seems
> to be working.  I think it might be useful to feature
> the ability to have polymorphic types in modules
> a little more prominently in the documentation.

Yes, or you have to make a habit of reading lots of the posts from
yesteryear in the mailing list archive. There is a lot of good information
there, unfortunately it isn't so easy to find. 

> Maybe some of the standard modules could take
> advantage of this more (it would require some
> changes to their interfaces, I suppose).

Yes, the interfaces would have to change. I think it is better that the 
interfaces don't have type variables; really the most compelling (IMO of
course!) reason for making them polymorphic is to use the parameterization 
trick for recursive types, and I am hoping that a future OCaml (OCaml 4?) 
handles this nicely by stealing Moscow ML features or by adopting the
mixin modules described briefly here by Tom Hirschowitz a few months ago.

> The type signatures I get out of my module after
> converting it are a little odd looking:
> 
>     type 'a t = 'a
>     type 'a tree = Empty | Node of ...
>     val insert :
> 	('a t t t -> 'a t t -> bool) -> 
> 	'a t t t -> 'a t tree -> 'a tree
>     ...
> 
> Is there any useful information in the different
> number of t's?  They should all be equivalent, right?

Something looks wrong to me here. Could you post more of your code, or
provide a pointer to the original SML code? I don't see why you have a 
'a t t t. The OCaml code should look a lot like the SML code, and the
signatures should only differ a little.

> BTW, I opted for just passing the "lt" function
> as explicit arguments to all the functions in the
> module that need them. 

Why not just parameterize the module by the comparison function? 

> That seems like the most general approach, although it means some extra
> arguments and it doesn't guarantee consistency,
> as people might pass incompatible versions of "lt"
> to different calls;

Right, I think you should pull the comaprison out of the functions and 
parameterize the module for this reason. 

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] classes vs modules

[Andreas Rossberg]

Markus Mottl wrote:
> 
> Out of curiousity, would it be unsound to allow functions like the
> following:
> 
>   let f (cmp : 'a -> 'a -> bool) =
>     let module SomeSet =
>       Set.Make (struct type t = 'a let compare = cmp end) in
>     ()

It would be sound. Actually, Moscow ML allows it as an extension to SML.
(Though I am not completely sure whether OCaml's odd semantics of type
variables in annotations makes a difference. But I do not see how it
should.)

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids.
 If Pac Man affected us as kids, we would all be running around in
 darkened rooms, munching pills, and listening to repetitive music."
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] classes vs modules

[Andreas Rossberg]

Tom _ wrote:
> 
> BTW, I opted for just passing the "lt" function
> as explicit arguments to all the functions in the
> module that need them.  That seems like the most
> general approach, although it means some extra
> arguments and it doesn't guarantee consistency,
> as people might pass incompatible versions of "lt"
> to different calls;

You can avoid this by passing it to the creator
function only and store it inside the object:

	val make_treap : ('a -> 'a -> bool) -> 'a treap

The treap type would look like this:

	type 'a treap' = Empty | ...
	type 'a treap  = {treap' : treap'; lt : 'a -> 'a -> bool}

In most cases I would prefer the functor version, though.

Hope this helps,

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids.
 If Pac Man affected us as kids, we would all be running around in
 darkened rooms, munching pills, and listening to repetitive music."
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr