Using modules and classes recursively

Using modules and classes recursively

[Markus Mottl]

Hello - Bonjour,

Even though I have tried hard, I couldn't solve the following problem:

I want to have a class that is able to return a set of objects of
its type, but I have no idea, how I have to formulate this (if it is
possible).

E.g.:

---------------------------------------------------------------------------
class foo =
object
  method bar = FooSet.singleton (new foo)
end
---------------------------------------------------------------------------

An object of this class would return a set containing itself if its
member function "bar" is called.
Before the definition of this class, the module "FooSet" has to be
created. But it seems impossible to do so.

E.g.:

---------------------------------------------------------------------------
module FooSet =
  Set.Make (struct type t = <bar : FooSet.t> let compare = compare end)
---------------------------------------------------------------------------

This does not work, because the type constructor "FooSet.t" cannot be
bound before "FooSet" exists - but that's what are defining!

Is it impossible to have modules and classes combined recursively?
If yes, what would be a good workaround?

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: Using modules and classes recursively

[Xavier Leroy]

> Is it impossible to have modules and classes combined recursively?

Currently, yes.  A module definition cannot be mutually recursive with
any other definition (type, class, or another module).  This raises a
number of difficult typechecking and compilation problems that are
still largely open.  I agree this is probably the most irritating
restriction of ML modules.

> If yes, what would be a good workaround?

I'm afraid you just have to define your own "set" type, without using
the Set.Make functor.  E.g.

        type 'a myset = Empty | Node of myset * 'a * myset

        (* an efficient implementation of myset can easily be
           lifted from the sources of the "Set" standard library
           module *)

        class foo =
          object
            method bar = (... : foo myset)
            ...
          end

This isn't very satisfactory, but I'm afraid we can't do better until
recursive modules are better understood.

Regards,

- Xavier Leroy

Re: Using modules and classes recursively

[Brian Rogoff]

On Tue, 12 Jan 1999, Xavier Leroy wrote:
> > Is it impossible to have modules and classes combined recursively?
> 
> Currently, yes.  A module definition cannot be mutually recursive with
> any other definition (type, class, or another module).  This raises a
> number of difficult typechecking and compilation problems that are
> still largely open.  I agree this is probably the most irritating
> restriction of ML modules.

A similar restriction also exists in Ada, i.e., two package specifications
cannot "with" (open) each other. One workaround for the case where you
have mutually dependant tagged types (classes) in separate package specs
is to break the cycle by creating a dummy parent type for each of the 
dependant tagged types and using those in place of the type which would 
cause the problem, in this case a "foo_dummy_parent set" would replace foo
in the problem spots, foo would inherit from foo_dummy_parent and the
foos that go into the set would have to be coerced to foo_dummy_parent.

I think this trick will work in OCaml too, but I haven't tried.

-- Brian

PS: For the Ada aware Camlists (Camlers?),

	http://www.bluemarble.net/~jvolan/WithingProblem/FAQ.html

    is a long discussion of the problem in Ada.

Re: Using modules and classes recursively

[Markus Mottl]

> On Tue, 12 Jan 1999, Xavier Leroy wrote:
> > > Is it impossible to have modules and classes combined recursively?
> > 
> > Currently, yes.  A module definition cannot be mutually recursive with
> > any other definition (type, class, or another module).  This raises a
> > number of difficult typechecking and compilation problems that are
> > still largely open.  I agree this is probably the most irritating
> > restriction of ML modules.
> 
> A similar restriction also exists in Ada, i.e., two package specifications
> cannot "with" (open) each other. One workaround for the case where you
> have mutually dependant tagged types (classes) in separate package specs
> is to break the cycle by creating a dummy parent type for each of the 
> dependant tagged types and using those in place of the type which would 
> cause the problem, in this case a "foo_dummy_parent set" would replace foo
> in the problem spots, foo would inherit from foo_dummy_parent and the
> foos that go into the set would have to be coerced to foo_dummy_parent.
> 
> I think this trick will work in OCaml too, but I haven't tried.
> 
> -- Brian

That would generally be a fine idea - I am sure it would work (I
have also not tried yet)! But unfortunately this won't work with my
classes, because they cannot be subtypes of their ancestor: they all
inherit from another class that has a method with the "'self"-type in
its signature. This "'self"-type is automatically redefined in every
(sub-)class, so the signature of the child class does not match the one
of its dummy parent class. It would only do so if this method didn't
exist in the dummy parent, but unfortunately, I have to access this
method for all objects in the set, so I cannot leave it away...

My last posting about "subtypes and inheritance" dealt with this problem.
Has already someone found a solution to this? - To me this is really
a big shortcoming, because it does not allow me to build larger class
hierarchies, where things like the "'self"-type or otherwise redefined
signatures of methods are very likely to occur.

Regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl