circular types?

circular types?

[Chris Hecker]

How do I do this:

type foo = B of bar
type bar = F of foo

That is, I want two types to refer to each other.  I thought putting a 

type bar

above foo would do it, but that's an abstract type now, and when I redefine it I get a different type?

Chris

Re: circular types?

[Pierre Weis]

> How do I do this:
> 
> type foo = B of bar
> type bar = F of foo
> 
> That is, I want two types to refer to each other.

It's exactly similar to value definitions: put a ``and'' between the
two recursive definitions.

type foo = B of bar
and bar = F of foo

Then you can define recursively a f of type foo and a b of type bar as in:

let rec f = B b
and b = F f;;

val f : foo =
 B
  (F
    (B
      (F
        (B
          (F
            (B
              (F ...
)))))))
val b : bar =
  F
   (B
     (F
       (B
         (F
           (B
             (F
               (B
                 (F ...
))))))))

Hope this helps,
        
Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: circular types?

[Chris Hecker]

>It's exactly similar to value definitions: put a ``and'' between the
>two recursive definitions.
>type foo = B of bar
>and bar = F of foo

Ah, thanks!  Is there any way to do it without the "and"?  In other words, what if I want to do this but the types are defined "far away" from each other in the source.  The "and" solution works, but I'm looking for something like forward declarations from C++:

class foo;
class bar;
class foo { bar *Bar; };
// ...lots of stuff...
class bar { foo *Foo; };

Chris

Re: circular types?

[Pierre Weis]

> >It's exactly similar to value definitions: put a ``and'' between the
> >two recursive definitions.
> >type foo = B of bar
> >and bar = F of foo
> 
> Ah, thanks!  Is there any way to do it without the "and"?  In other
> words, what if I want to do this but the types are defined "far
> away" from each other in the source.  The "and" solution works, but
> I'm looking for something like forward declarations from C++: 
> 
> class foo;
> class bar;
> class foo { bar *Bar; };
> // ...lots of stuff...
> class bar { foo *Foo; };
> 
> Chris

There is no such construction in Caml. This problem is not very
important for a single compilation unit (or single file if you want),
since you just have to write the types at the beginning of the
file. By contrast if the recursivity has to spread over more than one
module, there is no solution in Caml. This is an active research area
to design a module system that supports this feature (the so-called
``mixins'').

Best regards,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: circular types?

[Chris Hecker]

> By contrast if the recursivity has to spread over more than one
> module, there is no solution in Caml. This is an active research area
> to design a module system that supports this feature (the so-called
> ``mixins'').

Could you explain how this helps with mixin?  My understanding of
mixin is that you compose types such that you can easily add
"printable" or "drawable" to an object in a lightweight way.  Is this
related in some way I don't see?  Or, does mixin mean something
different?

Templates somewhat obviate the need for mixin, since "printable" just
becomes a constraint that the type support the "print" function,
"sortable" means the type has "<", etc.  This is generic programming
in the Stepanov sense.  I still need to get my head around ocaml's
generic programming constructs, though.  It seems they're more
powerful in some ways and less in others (since you can't overload,
you can't write a single generic function that operates on any types
that satisfy the constraints like you can in C++).  I'm still trying
to figure this out, though, so I could be mistaken.

Chris

Re: circular types?

[Vitaly Lugovsky]

On Fri, 20 Oct 2000, Chris Hecker wrote:

> >It's exactly similar to value definitions: put a ``and'' between the
> >two recursive definitions.
> >type foo = B of bar
> >and bar = F of foo
> 
> Ah, thanks!  Is there any way to do it without the "and"?  In other words, what if I want to do this but the types are defined "far away" from each other in the source.  The "and" solution works, but I'm looking for something like forward declarations from C++:
> 
> class foo;
> class bar;
> class foo { bar *Bar; };
> // ...lots of stuff...
> class bar { foo *Foo; };

 It's just a C++ way. Sucks. "and" construction is much more informative.

--

   V.S.Lugovsky aka Mauhuur (http://ontil.ihep.su/~vsl) (UIN=45482254)

Re: circular types?

[Chris Hecker]

> > class foo;
> > class bar;
> > class foo { bar *Bar; };
> > // ...lots of stuff...
> > class bar { foo *Foo; };
>  It's just a C++ way. Sucks. "and" construction is much more informative.

Oh, and here I thought it was a flexible and yet still typesafe
programming construct useful for decoupling large projects.  I
obviously have a lot of learning to do.

:)

Chris

Re: circular types?

[Brian Rogoff]

On Fri, 20 Oct 2000, Chris Hecker wrote:
> >It's exactly similar to value definitions: put a ``and'' between the
> >two recursive definitions.
> >type foo = B of bar
> >and bar = F of foo
> Ah, thanks!  Is there any way to do it without the "and"?  In other
words, 
> what if I want to do this but the types are defined "far away" from each 
> other in the source.  The "and" solution works, but I'm looking for 
> something like forward declarations from C++:
> 
> class foo;
> class bar;
> class foo { bar *Bar; };
> // ...lots of stuff...
> class bar { foo *Foo; };

Nope, no forwards in Ocaml. At some point, you'll have to tie the recursive 
knot with an "and". If the problem you're having is that "far away" means 
"in different modules" then you bump into the lack of recursive modules, 
IMO the biggest PITA with ML style modules. This hurts most in a situation 
where you want something like the Composite pattern with modules  

type composite = { data : string ; children : CompositeSet.t }
and module CompositeSet = 
  Set.Make( struct 
              type t = composite 
              let compare c1 c2  = 
                Pervasives.compare (String.length c1.data) 
                                   (String.length c2.data) 
            end )

The first choice, which you don't like, is to put the mutually recursive
types into the same module. This would entail copying all of the source for
Set.Make into the module where you're defining the Composite, and using
"and" to tie the recursion together. I agree this is a poor workaround.

Another choice, which I saw on caml-list in a post from Benoit deBoursetty, 
is to make polymorphic versions of the Set functor by grab-and-hack on the
source of Set, and use the polymorphism to move the recursive dependence out 
of lift the module. So you make a 

module type PolyOrderedType =
  sig
    type 'a t
    val compare: 'a t -> 'a t -> int
  end;;

type 'a composite_fwd = { data : string ; forward : 'a };;

module OrderedComposites =
  struct
    type 'a t = 'a composite_fwd
    let compare cf1 cf2 = 
      Pervasives.compare (String.length cf1.data) (String.length cf2.data) 
  end;;

module CompositeSet = PolySet.Make(OrderedComposites);;

and given these polymorphic sets we can untie the mutual recursion with an 
"and" as follows 

type children = { children : composite CompositeSet.t }
and  composite = children composite_fwd;;

This is better, but involves an unpleasant extra level of indirection. You
can find the polymorphic sets at

http://www.stud.enst.fr/~debourse/caml.html

if this technique looks useful.

If the entities involved in the module spanning mutual recursion are
classes, and you *absolutely-don't-want-to-put-them-in-the-same-module*
you can create a dummy module in which the dependent classes are linked
and inherit from that. That moves the mutual recursion but doesn't break
it; there is no way I know of to break it short of doing a downcast or
narrowing-conversion on the classes, which is illegal in Ocaml. 

Here is a silly example; starting with these impossible signatures

module type DoctorType = 
  sig 
    class c : 
      object 
	method treat_patient : PatientType.c 
	method bill_patient : PatientType.c 
      end 
  end ;;

module type PatientType = 
  sig 
    class c : 
      object 
	method visit_doctor : DoctorType.c 
	method pay_doctor : DoctorType.c 
      end 
  end ;;

we add a parent module which expresses an interface dependency and write
the signatures in terms of that. 

module Forwards = 
  sig 
    class virtual patient_intf = 
      object 
	method virtual visit_doctor : doctor_intf  
	method virtual pay_doctor :   doctor_intf
      end 
    and virtual doctor_intf = 
      object 
	method virtual treat_patient : patient_intf
        method virtual bill_patient  : patient_intf
      end 
  end ;;

module type DoctorType = 
  sig 
    class c : 
      object 
	method treat_patient : Forwards.patient_intf
	method bill_patient : Forwards.patient_intf
      end 
  end ;;

module type PatientType = 
  sig 
    class c : 
      object 
	method visit_doctor : Forwards.doctor_intf
	method pay_doctor : Forwards.doctor_intf
      end 
  end ;;

-- Brian

Re: circular types?

[Anton Moscal]

On Fri, 20 Oct 2000, Chris Hecker wrote:

> 
> >It's exactly similar to value definitions: put a ``and'' between the
> >two recursive definitions.
> >type foo = B of bar
> >and bar = F of foo
> 
> Ah, thanks!  Is there any way to do it without the "and"?  In other words, what if I want to do this but the types are defined "far away" from each other in the source.  The "and" solution works, but I'm looking for something like forward declarations from C++:

There is no good solution. But may be the following can help you:

type 'bar foo = B of 'bar
...
type bar = F of bar foo

Regards, Anton

Re: circular types?

[Tom Hirschowitz]

> Nope, no forwards in Ocaml. At some point, you'll have to tie the recursive 
> knot with an "and". If the problem you're having is that "far away" means 
> "in different modules" then you bump into the lack of recursive modules, 
> IMO the biggest PITA with ML style modules.

Hi, 

I'm pleased to see I'm not working for nobody. 
Actually I'm not working exactly on recursive modules, but rather on 
mixin modules.
Instead of defining your two modules and then link them, you would 
create a new one with the holes filled.
For instance, for Brain's example, you would write something like : 

mixin A = 
  mix 
    deferred module CompositeSet : sig type t ... end
    type composite = { data : string ; children : CompositeSet.t }
  end;;

mixin B = 
  mix
    deferred type composite
    module CompositeSet = 
      struct
        type t = C of composite | D
      end
  end

mixin C = A + B

In fact, this one is too difficult for me right now, because it 
relies on a mutual dependency between a type and a module.
Since I'm just beginning this, I would really be pleased by any 
comments, suggestions or questions about it.

Ciao.

Tom

Re: circular types?

[Brian Rogoff]

On Mon, 23 Oct 2000, Tom Hirschowitz wrote:
> > Nope, no forwards in Ocaml. At some point, you'll have to tie the recursive 
> > knot with an "and". If the problem you're having is that "far away" means 
> > "in different modules" then you bump into the lack of recursive modules, 
> > IMO the biggest PITA with ML style modules.
> 
> Hi, 
> 
> I'm pleased to see I'm not working for nobody. 
> Actually I'm not working exactly on recursive modules, but rather on 
> mixin modules.
> Instead of defining your two modules and then link them, you would 
> create a new one with the holes filled.
> For instance, for Brain's example, you would write something like : 
> 
> mixin A = 
>   mix 
>     deferred module CompositeSet : sig type t ... end
>     type composite = { data : string ; children : CompositeSet.t }
>   end;;
> 
> mixin B = 
>   mix
>     deferred type composite
>     module CompositeSet = 
>       struct
>         type t = C of composite | D
>       end
>   end
> 
> mixin C = A + B
> 
> In fact, this one is too difficult for me right now, because it 
> relies on a mutual dependency between a type and a module.

I don't mind viewing modules as "the higher level" meaning that if you 
can have mutually recursive modules this is good enough since I just
encapsulate the type in a module. This is going to be a bit unnatural
sometimes because the Ocaml implemenation uses the top level module names 
specially but probably no big deal in practice. This is what Moscow ML
does; in OCamlized syntax the composite set looks like this I think 

module Composite = rec (Fwd : sig module ElemSet sig type t end end)
  struct 
    module Elem = 
      struct 
        type t = 
        { data : string
        ; children : Fwd.ElemSet.t
        } 
      end
   module ElemSet = 
     struct 
       type t = Elem.t Set.t
     end
  end

If you can support something similar that's fine with me, but if you think
you the direct type and module mutual recursion is workable that's even
better. And if you can do that then allowing mutual recursion between
classes and types also should be allowed. 

> Since I'm just beginning this, I would really be pleased by
> comments, suggestions or questions about it.

I also like that the syntax I show above consumed no more keywords. Just 
something to think about. 

-- Brian

Re: circular types?

[John Max Skaller]

Brian Rogoff wrote:

> And if you can do that then allowing mutual recursion between
> classes and types also should be allowed.

I think this can be done now. Here is the method: to have a type t
and a class c mutually dependent, for example:

	class type c = object x : t end
	and type  t = C c | Null

write

	class type c' ['t] = object x : 't end
	type t = C t c' | Null
	class type c = t c'

and you have it. In other words, abstract out the types from
the classes by making them type parameters, declare the types,
using appropriately instantiated class types, and then name the
required class instances.

As far as I can see, this always works, and thus shows
(constructively) that mutual recursion between classes and types
can be supported. 

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: circular types?

[Brian Rogoff]

On Thu, 26 Oct 2000, John Max Skaller wrote:
> Brian Rogoff wrote:
> > And if you can do that then allowing mutual recursion between
> > classes and types also should be allowed.
> 
> I think this can be done now. Here is the method: to have a type t
> and a class c mutually dependent, for example:
> 
> 	class type c = object x : t end
> 	and type  t = C c | Null
> 
> write
> 
> 	class type c' ['t] = object x : 't end
> 	type t = C t c' | Null
> 	class type c = t c'
> 
> and you have it. In other words, abstract out the types from
> the classes by making them type parameters, declare the types,
> using appropriately instantiated class types, and then name the
> required class instances.

Yes, it's the same trick that I pointed out for module/type recursions; as 
they say any problem can be solved by another level of indirection. I'd
like to be able to express this directly with an "and" of course.

Check your syntax too, it's really

class type ['a] c' = object method x : 'a end;;
type t = C of t c' | Null;;
class type c = object inherit [t] c' end;;

and note that this works with virtual classes as well as class types 

class virtual ['a] c' = object method virtual x : 'a end;;
type t = C of t c' | Null;;
class virtual c = object inherit [t] c' end;;
class foo a_t = object inherit c method x = a_t end;;
let f0 = new foo Null;;
let f1 = new foo (C f0);;

Before anyone complains about those horrid double semi-colons I point out
that those lines are all accepted by the top-level ;;-)

-- Brian

Re: circular types?

[Hendrik Tews]

Hi,

John Max Skaller writes:
   From: John Max Skaller <skaller@ozemail.com.au>
   Date: Thu, 26 Oct 2000 01:03:29 +1100
   Subject: Re: circular types?
   
   I think this can be done now. Here is the method: to have a type t
   and a class c mutually dependent, for example:
   
   	class type c = object x : t end
   	and type  t = C c | Null
   
   write
   
   	class type c' ['t] = object x : 't end
   	type t = C t c' | Null
   	class type c = t c'
   

Yes, this is the theoretical answer. But this just doesn't work
out in anything bigger than a tutorial example. I am involved in
programming a logic compiler. We have about 40 variant types and
at least 10 classes. If my design were not constraint by the
abilities of the ocaml compiler some of the classes were in
mutual recursion with the bigger halve of the variant types. So
you are not telling me seriously I should write classes with 10
type variables!

Just for curiosity: Does somebody use the above workaround in a
project with more than 10.000 lines of ocaml code? (We do, but
every typing error is a nightmare.)

Bye,

Hendrik

Re: circular types?

[John Max Skaller]

Hendrik Tews wrote:

> John Max Skaller writes:

>    I think this can be done now. Here is the method: to have a type t
>    and a class c mutually dependent, for example:
> 
>         class type c = object x : t end
>         and type  t = C c | Null
> 
>    write
> 
>         class type c' ['t] = object x : 't end
>         type t = C t c' | Null
>         class type c = t c'
> 
> 
> Yes, this is the theoretical answer. But this just doesn't work
> out in anything bigger than a tutorial example. I am involved in
> programming a logic compiler. We have about 40 variant types and
> at least 10 classes. 

	I have used this technique in Vyper (my implementation
of Python in Ocaml). While it is probably smaller than your logic
compiler:
there are 10 public class types, and about 20 variants --- the word
'and' occurs 33 times in the .mli file --- it would seem to be in the
same league. The interface file is 500 lines.

> If my design were not constraint by the
> abilities of the ocaml compiler some of the classes were in
> mutual recursion with the bigger halve of the variant types. So
> you are not telling me seriously I should write classes with 10
> type variables!

	Sure! 10 type variables adds one line to each class. 
(if you use very short names :-)

> Just for curiosity: Does somebody use the above workaround in a
> project with more than 10.000 lines of ocaml code? (We do, but
> every typing error is a nightmare.)

	Vyper consists of 25,000 lines of .ml files and
5000 lines of .mli files. 
	
-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: circular types?

[Hendrik Tews]

Hi,

Tom Hirschowitz writes:
   Date: Mon, 23 Oct 2000 09:43:19 +0200
   Subject: Re: circular types?
   
   Since I'm just beginning this, I would really be pleased by any 
   comments, suggestions or questions about it.
   

I would like to have recursive types spread over different files
like

========== file types.ml

type types =
  | Product of types list
  ...
  | Comprehension of formula

===================================

========== file expression.ml

type expression =
  | Abstraction of (string * types) list * expression
  ....
  | Formula of formula

===================================

========== file formula.ml

type formula = 
  | Forall of (string * types) list * formula
  ...
  | Expression of expression

===================================


It would be great if one could incorporate a class into the
recursion. But I guess as a first step one has to allow recursion
between classes and types in one module as in

    type t = ....

    and class c = ...

    and type t' = ...


Bye,

Hendrik

Re: circular types?

[John Max Skaller]

Hendrik Tews wrote:
> I would like to have recursive types spread over different files
> like
> 
> ========== file types.ml
> 
> type types =
>   | Product of types list
>   ...
>   | Comprehension of formula
> 
> ========== file expression.ml
> 
> type expression =
>   | Abstraction of (string * types) list * expression
>   ....
>   | Formula of formula

> ========== file formula.ml
> 
> type formula =
>   | Forall of (string * types) list * formula
>   ...
>   | Expression of expression

	You can't. Instead, create a single interface (.mli) file containing
all the type definitions. No ml file is required. Note that you must
define class _types_ not classes. Your actual classes should be defined
and constrained to these types, and client modules should only know
the class types (not the classes).

	This way, indirection (abstraction) is used to solve the problem.

> It would be great if one could incorporate a class into the
> recursion. But I guess as a first step one has to allow recursion
> between classes and types in one module as in
> 
>     type t = ....
>     and class c = ... 
>     and type t' = ...

	See previous post: you can do this now, by first abstracting
the classes over the types:

	class type c' ['t] = ... 
	type t = .... t c' ...
	class type c = t c'

Again, indirection (abstraction) is used to solve the problem.
It is slightly more effort to first give (otherwise useless) generic
class types, then instantiate them.

Considerably more effort is required to give a class type,
and then separately an implementation (since a whole lot of
method signatures need to be repeated).

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: circular types?

[Hendrik Tews]

Hi,

John Max Skaller writes:
   From: John Max Skaller <skaller@ozemail.com.au>
   Date: Thu, 26 Oct 2000 01:31:14 +1100
   Subject: Re: circular types?
   
   Hendrik Tews wrote:
   > I would like to have recursive types spread over different files
   > like

   	You can't. Instead, create a single interface (.mli) file containing

Sorry, John, I should have made more clearly that it was not a
beginners question but a reply to:

Tom Hirschowitz writes:
   Date: Mon, 23 Oct 2000 09:43:19 +0200
   Subject: Re: circular types?
   
   Since I'm just beginning this, I would really be pleased by any 
   comments, suggestions or questions about it.


Bye,

Hendrik

Re: circular types?

[Tom Hirschowitz]

Hendrik Tews writes :
I would like to have recursive types spread over different files
like ....

That should be possible, but again there will be a mixing step, 
creating
a new module, in which the different parts of your recursive types 
block
are linking together.

In your example, you would have :


========== file types.ml

? type formula

type types =
  | Product of types list
  ...
  | Comprehension of formula

===================================

========== file expression.ml

? type formula

type expression =
  | Abstraction of (string * types) list * expression
  ....
  | Formula of formula

===================================

========== file formula.ml

? type expression

type formula = 
  | Forall of (string * types) list * formula
  ...
  | Expression of expression

===================================

========== file next.ml

module MyTypes = Types + Expression + Formula;;

...

===================================

Is it enough?


> It would be great if one could incorporate a class into the
> recursion. But I guess as a first step one has to allow recursion
> between classes and types in one module as in

>     type t = ....

>     and class c = ...

>     and type t' = ...

I'm not here until now, since in the prototype, there are only 
recursive values. But probably O-people at Cristal could answer this 
point.

Bye,

Tom

Re: circular types?

[Hendrik Tews]

Hi,

Tom Hirschowitz writes:
   From: Tom Hirschowitz <hirschow@mouton.inria.fr>
   Date: Tue, 24 Oct 2000 10:48:06 +0200
   Subject: Re: circular types?
   
   [some of the pseudo code deleted]

   ========== file expression.ml
   
   ? type formula
   
   type expression =
     | Abstraction of (string * types) list * expression
     ....
     | Formula of formula
   
   ===================================
   
   ========== file formula.ml
   
   ? type expression
   
   type formula = 
     | Forall of (string * types) list * formula
     ...
     | Expression of expression
   
   ===================================
   
   ========== file next.ml
   
   module MyTypes = Types + Expression + Formula;;
   
   ...
   
   ===================================
   
   Is it enough?
   
I think yes, just a two question to make sure I get it right:

- If I want to program a function typecheck (which recursively
walks down formulas, expressions, and types) I separate it into
typecheck_formula, typecheck_expression, etc and put these
functions into the respective files. Will there be lightweight
syntax for the forward declaration of typecheck_expression in
file formula.ml similar to what you used for the types above? 

- Assume another module that uses typecheck_formula, does it have
to "open" Formula or Next? 

- How about link order? The mixin module is linked after all
modules it mixes and all modules that use something of file
formula or expression have to be linked after the mixing module?

- (Impatiently) In which ocaml release can I expect the mixing
modules?

Bye,

Hendrik

Re: circular types?

[Tom Hirschowitz]

Hendrik Tews <tews@tcs.inf.tu-dresden.de> :

> - If I want to program a function typecheck (which recursively
> walks down formulas, expressions, and types) I separate it into
> typecheck_formula, typecheck_expression, etc and put these
> functions into the respective files. Will there be lightweight
> syntax for the forward declaration of typecheck_expression in
> file formula.ml similar to what you used for the types above? 

Yes. You'll have to specify the type of deferred functions in each 
module.
For example,


   ========== file expression.ml
   
   ? type formula
   
   type expression =
     | Abstraction of (string * types) list * expression
     ....
     | Formula of formula

   ? val typecheck_formula : formula -> ...

   let rec typecheck_expression = ...
   
   ===================================
   
   ========== file formula.ml
   
   ? type expression
   
   type formula = 
     | Forall of (string * types) list * formula
     ...
     | Expression of expression
   
   
   ? val typecheck_expression : expression -> ...

   let rec typecheck_formula = ...

   ===================================
   
   ========== file next.ml
   
   module MyTypes = Types + Expression + Formula;;
   
   ...
   
   ===================================
 

should work.


> - Assume another module that uses typecheck_formula, does it have
> to "open" Formula or Next? 

Other modules using those functions have to open Next, 
because before the merging, none of those functions or types 
is really defined.
For instance, the type checker refuses "Formula.typecheck_expression".

> - How about link order? The mixin module is linked after all
> modules it mixes and all modules that use something of file
> formula or expression have to be linked after the mixing module?

I really don't know, haven't worked on it yet.
But one module should be able to be mixed with many others.
Assume you want to test two strategies for type-checking expressions, 
you would use the same Formula module for both. 
Does it fix any link order anyway?

> - (Impatiently) In which ocaml release can I expect the mixing
> modules?

Not yet for sure!
Ocaml v 24.12? 
Xavier?