Loading ...
Sorry, an error occurred while loading the content.

Circular dependencies between modules

Expand Messages
  • Fabrice Marchant
    Hi ! I m ashamed not to have grasped this yet. Moreover it s pretty sure this subject was already discussed - but can t find again where. So, the basic
    Message 1 of 15 , Nov 30, 2007
    • 0 Attachment
      Hi !

      I'm ashamed not to have grasped this yet. Moreover it's pretty sure this subject was already discussed - but can't find again where.
      So, the basic question :

      In a Makefile - that uses OCamlMakefile in my case - the list of .ml sources was specified like this :

      SOURCES = zero.ml one.ml two.ml three.ml

      the order is meaningful and - forgetting .mli interface restrictions - one.ml can access 'Zero.' things but not 'Two.' neither 'Three.' file modules belongings.

      The problem that arises is :
      one.ml now needs to access a three.ml component.
      But three.ml depends on two.ml and
      two.ml depends on one.ml, thus I can't reorder the sources name.

      I believed that defining the .mli files could solve this kind of problem in some cases. ( I originally waited for having completed the small project before to generate/restrict/document the .mli interfaces. )
      However, I'm not able to solve this mutual dependencies question this way here.

      There are workarounds ( I've even written an ugly one in order not to let my build stuck ) but I hope to learn what would be a clean way to perform this.

      Thanks,

      Fabrice
    • Remi Vanicat
      ... Well, there are two kind of dependency: - a module may need a type that is defined in another module - a module may need a value (a let ) that is defined
      Message 2 of 15 , Dec 1, 2007
      • 0 Attachment
        Fabrice Marchant <fabrice.marchant@...> writes:

        > The problem that arises is : one.ml now needs to access a three.ml
        > component. But three.ml depends on two.ml and two.ml depends on
        > one.ml, thus I can't reorder the sources name.
        >
        > I believed that defining the .mli files could solve this kind of
        > problem in some cases. ( I originally waited for having completed the
        > small project before to generate/restrict/document the .mli
        > interfaces. ) However, I'm not able to solve this mutual dependencies
        > question this way here.

        Well, there are two kind of dependency:
        - a module may need a type that is defined in another module
        - a module may need a value (a "let") that is defined in another
        module

        There can be circular dependency in type only if they are defined in
        the same "type ... and ... and ..." declaration
        There can be circular dependency in value only if they are defined in
        the same "let rec ... and .. and" (but there, on can cheat by using
        reference or mutable field, that will be put to the correct value
        before been used).

        .ml / .mli separation can only help you in the case where the circular
        dependency come from two different kind of dependency: say the module
        One use a type defined in module Two when module Two use a value
        defined in module One : you do a one.ml, two.mli and a two.ml. As Two.mli
        define only type, it do not need one.ml to be defined to compile. As
        One depend only on a type of Two, one.ml only need two.mli to be
        compiled to compile. And then two.ml can compile: everything else is
        compiled.

        By the way, there exist recursive module, but I never used them. But
        to use them you need to put the recursive module in the same .ml (as
        submodule).
      • Jon Harrop
        ... Yes, you need to break the cyclic dependence by parameterizing one definition over another. Having big cyclic dependencies is a bad idea anyway... -- Dr
        Message 3 of 15 , Dec 1, 2007
        • 0 Attachment
          On Saturday 01 December 2007 07:03, Fabrice Marchant wrote:
          > There are workarounds ( I've even written an ugly one in order not to let
          > my build stuck ) but I hope to learn what would be a clean way to perform
          > this.

          Yes, you need to break the cyclic dependence by parameterizing one definition
          over another. Having big cyclic dependencies is a bad idea anyway...

          --
          Dr Jon D Harrop, Flying Frog Consultancy Ltd.
          http://www.ffconsultancy.com/products/?e
        • Fabrice Marchant
          Thanks Remi ! ... If two.ml uses several one.ml components, so they appear in this order : one.ml two.ml in the Makefile, a cheat to access a two.ml component
          Message 4 of 15 , Dec 1, 2007
          • 0 Attachment
            Thanks Remi !

            > Well, there are two kind of dependency:
            > - a module may need a type that is defined in another module
            > - a module may need a value (a "let") that is defined in another
            > module
            >
            > There can be circular dependency in type only if they are defined in
            > the same "type ... and ... and ..." declaration
            > There can be circular dependency in value only if they are defined in
            > the same "let rec ... and .. and" (but there, on can cheat by using
            > reference or mutable field, that will be put to the correct value
            > before been used).
            If two.ml uses several one.ml components, so they appear in this order :
            one.ml two.ml in the Makefile, a cheat to access a two.ml component
            inside one.ml would be :
            to define a reference to None inside one.ml,
            to reinitalize this reference, at runtime from two.ml, with Some copy of
            this wanted two.ml component.
            'option' use causes the things to be heavier but otherwise they would
            become not only ugly but even unsafe.
            But maybe I'm wrong and there is a better way...

            > .ml / .mli separation can only help you in the case where the circular
            > dependency come from two different kind of dependency: say the module
            > One use a type defined in module Two when module Two use a value
            > defined in module One : you do a one.ml, two.mli and a two.ml. As Two.mli
            > define only type, it do not need one.ml to be defined to compile. As
            > One depend only on a type of Two, one.ml only need two.mli to be
            > compiled to compile. And then two.ml can compile: everything else is
            > compiled.
            Thanks for these accurate explanations.

            Regards,

            Fabrice
          • Fabrice Marchant
            Thanks Jon ! ... Please Jon, could you develop a bit more on this ? I m unable to see what you mean here. ... Ah ! I wondered whether the need of such cyclic
            Message 5 of 15 , Dec 1, 2007
            • 0 Attachment
              Thanks Jon !

              > > There are workarounds ( I've even written an ugly one in order not to let
              > > my build stuck ) but I hope to learn what would be a clean way to perform
              > > this.
              >
              > Yes, you need to break the cyclic dependence by parameterizing one definition
              > over another.
              Please Jon, could you develop a bit more on this ?
              I'm unable to see what you mean here.

              > Having big cyclic dependencies is a bad idea anyway...
              Ah ! I wondered whether the need of such cyclic dependency didn't reveal some misconception.

              Regards,

              Fabrice
            • Richard Jones
              ... Jon s right. It d be interesting to know what code you think needs circular dependencies. I ve rarely come across any, and each time it turned out to be
              Message 6 of 15 , Dec 1, 2007
              • 0 Attachment
                On Sat, Dec 01, 2007 at 11:40:41AM +0100, Fabrice Marchant wrote:
                > > Having big cyclic dependencies is a bad idea anyway...
                > Ah ! I wondered whether the need of such cyclic dependency didn't reveal some misconception.

                Jon's right. It'd be interesting to know what code you think needs
                circular dependencies. I've rarely come across any, and each time it
                turned out to be my faulty thinking.

                Rich.

                --
                Richard Jones
                Red Hat
              • Remi Vanicat
                ... Well, as I forget this possibility in my late post, I will show you here: For type: you have in one.ml: type t1 = Foo of Two.t2 ... in two.ml type t2 =
                Message 7 of 15 , Dec 1, 2007
                • 0 Attachment
                  Fabrice Marchant <fabrice.marchant@...> writes:

                  > Thanks Jon !
                  >
                  >> > There are workarounds ( I've even written an ugly one in order not to let
                  >> > my build stuck ) but I hope to learn what would be a clean way to perform
                  >> > this.
                  >>
                  >> Yes, you need to break the cyclic dependence by parameterizing one definition
                  >> over another.
                  > Please Jon, could you develop a bit more on this ?
                  > I'm unable to see what you mean here.

                  Well, as I forget this possibility in my late post, I will show you
                  here:

                  For type:

                  you have in one.ml:

                  type t1 =
                  Foo of Two.t2
                  | Bar of int

                  in two.ml

                  type t2 =
                  Fooz of One.t1 * int

                  of course this wont work, but you can do :

                  you have in one.ml:

                  type 'a t1 =
                  Foo of 'a
                  | Bar of int

                  in two.ml

                  type t2 =
                  Fooz of One.t1 * int | Leaf


                  then one can use Foo(Fooz(Bar 10)) : we use parametrization of the
                  first type to break the cycle.

                  In the same way, you could add an argument to a function so instead to
                  depend on value at compile time, it will only need it when evaluated.




                  >
                  >> Having big cyclic dependencies is a bad idea anyway...
                  > Ah ! I wondered whether the need of such cyclic dependency didn't
                  > reveal some misconception.

                  It might. Note that I learn the ref trick wile reading Ocaml source:
                  cyclic dependency can come from misconception, but sometime, it is the
                  way to go.


                  --
                  Rémi Vanicat
                • Remi Vanicat
                  ... If the reference is a function, you can also use this : in one.ml: let f : (int - string - string) ref = ref(fun _ _ _ - failwith not implemented yet )
                  Message 8 of 15 , Dec 1, 2007
                  • 0 Attachment
                    Fabrice Marchant <fabrice.marchant@...> writes:

                    > If two.ml uses several one.ml components, so they appear in this order :
                    > one.ml two.ml in the Makefile, a cheat to access a two.ml component
                    > inside one.ml would be :
                    > to define a reference to None inside one.ml,
                    > to reinitalize this reference, at runtime from two.ml, with Some copy of
                    > this wanted two.ml component.
                    > 'option' use causes the things to be heavier but otherwise they would
                    > become not only ugly but even unsafe.
                    > But maybe I'm wrong and there is a better way...

                    If the reference is a function, you can also use this :

                    in one.ml:
                    let f : (int -> string -> string) ref =
                    ref(fun _ _ _ -> failwith "not implemented yet")

                    in two.ml

                    let f x y z = "do the real stuff"

                    One.f := f

                    There is several problem with this:
                    - you need to explicitly give the type of f in one.ml,
                    - this type must not be polymorphic.
                    - this will only work with function.

                    --
                    Rémi Vanicat
                  • Jon Harrop
                    ... Sure. Consider a pair of mutually recursive functions: # let rec even ?(xs=[]) ?(ys=[]) = function ... and odd ?(xs=[]) ?(ys=[]) = function ... # even
                    Message 9 of 15 , Dec 1, 2007
                    • 0 Attachment
                      On Saturday 01 December 2007 10:40, Fabrice Marchant wrote:
                      > Thanks Jon !
                      >
                      > > > There are workarounds ( I've even written an ugly one in order not to
                      > > > let my build stuck ) but I hope to learn what would be a clean way to
                      > > > perform this.
                      > >
                      > > Yes, you need to break the cyclic dependence by parameterizing one
                      > > definition over another.
                      >
                      > Please Jon, could you develop a bit more on this ?
                      > I'm unable to see what you mean here.

                      Sure. Consider a pair of mutually recursive functions:

                      # let rec even ?(xs=[]) ?(ys=[]) = function
                      | [] -> xs, ys
                      | h::t -> odd ~xs:(h::xs) ~ys t
                      and odd ?(xs=[]) ?(ys=[]) = function
                      | [] -> xs, ys
                      | h::t -> even ~xs ~ys:(h::ys) t;;
                      # even [0;1;2;3;4;5];;
                      - : int list * int list = ([4; 2; 0], [5; 3; 1])

                      We want to keep them in separate modules and, consequently, we must break
                      their cyclic dependency. To do this, you just parameterize "even" over "odd"
                      and vice-versa:

                      # let rec even odd xs ys = function
                      | [] -> xs, ys
                      | h::t -> odd (h::xs) ys t;;
                      val even :
                      ('a list -> 'b -> 'a list -> 'a list * 'b) ->
                      'a list -> 'b -> 'a list -> 'a list * 'b = <fun>
                      # let odd even xs ys = function
                      | [] -> xs, ys
                      | h::t -> even xs (h::ys) t;;
                      val odd :
                      ('a -> 'b list -> 'b list -> 'a * 'b list) ->
                      'a -> 'b list -> 'b list -> 'a * 'b list = <fun>

                      Some people refer to this as "untying the recursive knot". Now, how do we use
                      these? Well, we just tie the knot again in a module that depends upon both:

                      # let rec even' xs = even odd' xs and odd' xs = odd even' xs in
                      even' [] [] [0;1;2;3;4;5];;
                      - : int list * int list = ([4; 2; 0], [5; 3; 1])

                      You can do exactly the same thing with types:

                      type a = A of b
                      and b = B of a;;

                      becomes:

                      type 'b a = A of 'b;;
                      type 'a b = B of 'a;;

                      and so on.

                      --
                      Dr Jon D Harrop, Flying Frog Consultancy Ltd.
                      http://www.ffconsultancy.com/products/?e
                    • Richard Jones
                      ... For an example of this in real code, take a look at how other modules are linked in to virt-top:
                      Message 10 of 15 , Dec 1, 2007
                      • 0 Attachment
                        On Sat, Dec 01, 2007 at 05:20:26PM +0100, Remi Vanicat wrote:
                        > If the reference is a function, you can also use this :
                        >
                        > in one.ml:
                        > let f : (int -> string -> string) ref =
                        > ref(fun _ _ _ -> failwith "not implemented yet")
                        >
                        > in two.ml
                        >
                        > let f x y z = "do the real stuff"
                        >
                        > One.f := f

                        For an example of this in real code, take a look at how other modules
                        are linked in to virt-top:

                        http://hg.et.redhat.com/virt/applications/virt-top--devel?f=e100f86fdf28;file=virt-top/virt_top.ml

                        (search for 'Hook')

                        Rich.

                        --
                        Richard Jones
                        Red Hat
                      • Fabrice Marchant
                        Thanks for your answer, ... There is a viewer file module in this project : it is a movable an zoomable window on a universe computed by another file
                        Message 11 of 15 , Dec 1, 2007
                        • 0 Attachment
                          Thanks for your answer,

                          > > > - Jon : Having big cyclic dependencies is a bad idea anyway...
                          > > Ah ! I wondered whether the need of such cyclic dependency didn't reveal some misconception.
                          >
                          > Jon's right. It'd be interesting to know what code you think needs
                          > circular dependencies.
                          There is a "viewer" file module in this project : it is a movable an "zoomable" window on a universe computed by another file
                          module called "automaton". This automaton is responsible of any modification of the universe. Another file module "controller" allow the user to control the automaton actions and the parameters of the viewer.
                          Due to their relative dependencies, the file modules ( among others ) appear in this order :
                          automaton.ml viewer.ml controller.ml
                          Up to now, no problem.

                          But here comes a trial to add a new possibility :
                          The user can decide via the controller to restrict existing universe, cutting it to objects that belong to the current visible view.
                          This request must be sent to the automaton - that now needs information about the zone of the universe that is currently viewed.
                          But the automaton cannot access to the viewer internals.

                          As in Jon's method, it would be possible to do the job with a module that depends on automaton and viewer : for example the controller. However this controller wasn't intended to access such kind of data and I would feel odd to add another module that would retrieve info from viewer to give them to the automaton.
                          I would prefer that the automaton simply fetch what it needs inside the viewer.

                          > I've rarely come across any, and each time it
                          > turned out to be my faulty thinking.
                          It's up to you to say whether if this above case is completely faulty or if it has a chance to fall in Rémi Vanicat possible "way to go".

                          Regards,

                          Fabrice
                        • Fabrice Marchant
                          Thanks a lot Rémi ! ... Thanks for this nice illustration of the interesting method Jon spoke about. Regards, Fabrice
                          Message 12 of 15 , Dec 1, 2007
                          • 0 Attachment
                            Thanks a lot Rémi !

                            > Well, as I forget this possibility in my late post, I will show you
                            > here:
                            >
                            > For type:
                            >
                            > you have in one.ml:
                            >
                            > type t1 =
                            > Foo of Two.t2
                            > | Bar of int
                            >
                            > in two.ml
                            >
                            > type t2 =
                            > Fooz of One.t1 * int
                            >
                            > of course this wont work, but you can do :
                            >
                            > you have in one.ml:
                            >
                            > type 'a t1 =
                            > Foo of 'a
                            > | Bar of int
                            >
                            > in two.ml
                            >
                            > type t2 =
                            > Fooz of One.t1 * int | Leaf
                            >
                            >
                            > then one can use Foo(Fooz(Bar 10)) : we use parametrization of the
                            > first type to break the cycle.
                            >
                            > In the same way, you could add an argument to a function so instead to
                            > depend on value at compile time, it will only need it when evaluated.
                            Thanks for this nice illustration of the interesting method Jon spoke about.

                            Regards,

                            Fabrice
                          • Fabrice Marchant
                            ... That is interesting, thanks ! But It makes me think to this now : even forgetting these circular dependencies, IMHO any initialization of a reference that
                            Message 13 of 15 , Dec 1, 2007
                            • 0 Attachment
                              > If the reference is a function, you can also use this :
                              >
                              > in one.ml:
                              > let f : (int -> string -> string) ref =
                              > ref(fun _ _ _ -> failwith "not implemented yet")
                              >
                              > in two.ml
                              >
                              > let f x y z = "do the real stuff"
                              >
                              > One.f := f
                              >
                              > There is several problem with this:
                              > - you need to explicitly give the type of f in one.ml,
                              > - this type must not be polymorphic.
                              > - this will only work with function.

                              That is interesting, thanks !

                              But It makes me think to this now :
                              even forgetting these circular dependencies, IMHO any initialization of a reference that isn't available at compile time seems to be a problem.

                              Regards,

                              Fabrice
                            • Fabrice Marchant
                              ... Thanks a lot ! ... That is absolutely cool ! ... Thanks for this interesting method I just discover here. Regards, Fabrice
                              Message 14 of 15 , Dec 1, 2007
                              • 0 Attachment
                                > > Please Jon, could you develop a bit more on this ?
                                > > I'm unable to see what you mean here.
                                >
                                > Sure.
                                Thanks a lot !

                                > Consider a pair of mutually recursive functions:
                                >
                                > # let rec even ?(xs=[]) ?(ys=[]) = function
                                > | [] -> xs, ys
                                > | h::t -> odd ~xs:(h::xs) ~ys t
                                > and odd ?(xs=[]) ?(ys=[]) = function
                                > | [] -> xs, ys
                                > | h::t -> even ~xs ~ys:(h::ys) t;;
                                > # even [0;1;2;3;4;5];;
                                > - : int list * int list = ([4; 2; 0], [5; 3; 1])
                                >
                                > We want to keep them in separate modules and, consequently, we must break
                                > their cyclic dependency. To do this, you just parameterize "even" over "odd"
                                > and vice-versa:
                                >
                                > # let rec even odd xs ys = function
                                > | [] -> xs, ys
                                > | h::t -> odd (h::xs) ys t;;
                                > val even :
                                > ('a list -> 'b -> 'a list -> 'a list * 'b) ->
                                > 'a list -> 'b -> 'a list -> 'a list * 'b = <fun>
                                > # let odd even xs ys = function
                                > | [] -> xs, ys
                                > | h::t -> even xs (h::ys) t;;
                                > val odd :
                                > ('a -> 'b list -> 'b list -> 'a * 'b list) ->
                                > 'a -> 'b list -> 'b list -> 'a * 'b list = <fun>
                                >
                                > Some people refer to this as "untying the recursive knot". Now, how do we use
                                > these? Well, we just tie the knot again in a module that depends upon both:
                                That is absolutely cool !

                                >
                                > # let rec even' xs = even odd' xs and odd' xs = odd even' xs in
                                > even' [] [] [0;1;2;3;4;5];;
                                > - : int list * int list = ([4; 2; 0], [5; 3; 1])
                                >
                                > You can do exactly the same thing with types:
                                >
                                > type a = A of b
                                > and b = B of a;;
                                >
                                > becomes:
                                >
                                > type 'b a = A of 'b;;
                                > type 'a b = B of 'a;;
                                >
                                > and so on.

                                Thanks for this interesting method I just discover here.

                                Regards,

                                Fabrice
                              • Fabrice Marchant
                                ... Thanks, Regards, Fabrice Nothing to do with the subject : The listing paper is nice. IMHO it would be even cooler with pale green strips instead of grey
                                Message 15 of 15 , Dec 1, 2007
                                • 0 Attachment
                                  > On Sat, Dec 01, 2007 at 05:20:26PM +0100, Remi Vanicat wrote:
                                  > > If the reference is a function, you can also use this :
                                  > >
                                  > > in one.ml:
                                  > > let f : (int -> string -> string) ref =
                                  > > ref(fun _ _ _ -> failwith "not implemented yet")
                                  > >
                                  > > in two.ml
                                  > >
                                  > > let f x y z = "do the real stuff"
                                  > >
                                  > > One.f := f
                                  >
                                  > For an example of this in real code, take a look at how other modules
                                  > are linked in to virt-top:
                                  >
                                  > http://hg.et.redhat.com/virt/applications/virt-top--devel?f=e100f86fdf28;file=virt-top/virt_top.ml
                                  >
                                  > (search for 'Hook')

                                  Thanks,

                                  Regards,

                                  Fabrice

                                  Nothing to do with the subject :
                                  The listing paper is nice. IMHO it would be even cooler with pale green strips instead of grey ones.
                                Your message has been successfully submitted and would be delivered to recipients shortly.