[Caml-list] Circular module dependencies

[Caml-list] Circular module dependencies

[Tony Edgin]

Hi all.

Recently, there was a thread which talked about how difficult module 
dependencies were to resolve for linking in Ocaml.  I'm guessing this is 
because of cycles in the dependency graph.

My thought is that maybe Ocaml shouldn't allow this to happen.  Wouldn't 
cyclical module dependencies be a symptom of bad design?  If a cyclic 
dependency occurs I can think of two ways of removing.  

First, if the dependency is among modules which are closely related, the code 
in each module in the cycle which interacts, should be extracted into its own 
module.   The cycle indicates code which is semantically related and would 
probably be easier to understand if it were all contained in the same file 
anyway.

Second, if the cycle contains modules which aren't closely related, a new 
module should be created to encapsulate this dependency.  This could be done 
using the Bridge pattern.  Since mutual dependencies make code brittle, 
explicitly revealing the cycle in a module makes the cycle more visible to 
the programmers and thus easier to deal with safely.

Are there any examples of cyclic dependencies which shouldn't be handled by 
either of these cases?

-- 
Tony Edgin

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Circular module dependencies

[Jacques GARRIGUE]

From: Tony Edgin <edgin@slingshot.co.nz>

> Recently, there was a thread which talked about how difficult module 
> dependencies were to resolve for linking in Ocaml.  I'm guessing this is 
> because of cycles in the dependency graph.
> 
> My thought is that maybe Ocaml shouldn't allow this to happen.  Wouldn't 
> cyclical module dependencies be a symptom of bad design?

Bingo. Ocaml does not allow it. It just happens that you can cheat the
compiler into accepting two different acyclic dependency graphs: one
for the types (compilation order of the .mli's) and one for the values
(compilation order of the .ml's). This was never intended, but there
is no specific reason to go to great length to defeat that trick, as
it is still safe.

At least that's my take on the question.

> If a cyclic dependency occurs I can think of two ways of removing.  

Indeed, this is the reasonable approach.

---------------------------------------------------------------------------
Jacques Garrigue      Kyoto University     garrigue at kurims.kyoto-u.ac.jp
		<A HREF=http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/>JG</A>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Circular module dependencies

[Christopher Dutchyn]

But what about (self- or mutually-) recursive modules?  By definition, 
they are cyclic, and neither suggested solution may work.  I use them to 
structure language semantics, and it's really convenient to have open 
recursion to different procedures and types.  I could restructure it into 
a single module, but then I couldn't mix-and-match.

I also appreciate the -rectypes option to Ocaml too; two-level types (a la 
Sheard and Pasalic) are elegant, and recursive types let me remove the 
superfluous tagging that Haskell needs.

So I think circularity is valuable, but I need to be careful to show my 
recursions are well-founded.

--
Christopher Dutchyn
UBC Computer Science

On Tue, 7 Sep 2004, Jacques GARRIGUE wrote:

> From: Tony Edgin <edgin@slingshot.co.nz>
>
>> Recently, there was a thread which talked about how difficult module
>> dependencies were to resolve for linking in Ocaml.  I'm guessing this is
>> because of cycles in the dependency graph.
>>
>> My thought is that maybe Ocaml shouldn't allow this to happen.  Wouldn't
>> cyclical module dependencies be a symptom of bad design?
>
> Bingo. Ocaml does not allow it. It just happens that you can cheat the
> compiler into accepting two different acyclic dependency graphs: one
> for the types (compilation order of the .mli's) and one for the values
> (compilation order of the .ml's). This was never intended, but there
> is no specific reason to go to great length to defeat that trick, as
> it is still safe.
>
> At least that's my take on the question.
>
>> If a cyclic dependency occurs I can think of two ways of removing.
>
> Indeed, this is the reasonable approach.
>
> ---------------------------------------------------------------------------
> Jacques Garrigue      Kyoto University     garrigue at kurims.kyoto-u.ac.jp
> 		<A HREF=http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/>JG</A>
>
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Circular module dependencies

[brogoff]

On Tue, 7 Sep 2004, Tony Edgin wrote:

> Hi all.
>
> Recently, there was a thread which talked about how difficult module
> dependencies were to resolve for linking in Ocaml.  I'm guessing this is
> because of cycles in the dependency graph.
>
> My thought is that maybe Ocaml shouldn't allow this to happen.  Wouldn't
> cyclical module dependencies be a symptom of bad design?  If a cyclic
> dependency occurs I can think of two ways of removing.
>
> First, if the dependency is among modules which are closely related, the code
> in each module in the cycle which interacts, should be extracted into its own
> module.   The cycle indicates code which is semantically related and would
> probably be easier to understand if it were all contained in the same file
> anyway.

In a discussion on this topic a while back, Fergus Henderson cited as an
example the Mercury compiler, where removing the dependencies by making one
big file of the dependent parts would lead to a pretty large file. I thought
that was a decent argument in favor of allowing mutually recursive functions
to cross module boundaries.

Another good example is when you have programs written in functorized style
(eg the Set module in OCaml) and you want to define a type which is in a
recursive relationship with the functor instantiation.

There are workarounds for those cases, but I think it's fair to say that
the desire for some recursive module capability is not always on account of
bad design.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Circular module dependencies

[Erik de Castro Lopo]

On Mon, 6 Sep 2004 21:39:21 -0700 (PDT)
brogoff <brogoff@speakeasy.net> wrote:

> In a discussion on this topic a while back, Fergus Henderson cited as an
> example the Mercury compiler, where removing the dependencies by making one
> big file of the dependent parts would lead to a pretty large file. I thought
> that was a decent argument in favor of allowing mutually recursive functions
> to cross module boundaries.

I was the initiator of a discussion much like this just recently.

The good advice I got was to refactor and move the common stuff
own the module hiearchy. So if you have two modules A and B
which SEEM to need each other, create a new module C containing
the required commong code and use the functionality of C in
both A and B.

I tried this for my situation and it not only worked like a charm,
in hindsight it made a whole lot more sense this way.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"Perl : this is a blue collar language" - Angus Lees

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Circular module dependencies

[brogoff]

On Tue, 7 Sep 2004, Erik de Castro Lopo wrote:
> On Mon, 6 Sep 2004 21:39:21 -0700 (PDT)
> brogoff <brogoff@speakeasy.net> wrote:
>
> > In a discussion on this topic a while back, Fergus Henderson cited as an
> > example the Mercury compiler, where removing the dependencies by making one
> > big file of the dependent parts would lead to a pretty large file. I thought
> > that was a decent argument in favor of allowing mutually recursive functions
> > to cross module boundaries.
>
> I was the initiator of a discussion much like this just recently.
>
> The good advice I got was to refactor and move the common stuff
> own the module hiearchy. So if you have two modules A and B
> which SEEM to need each other, create a new module C containing
> the required commong code and use the functionality of C in
> both A and B.
>
> I tried this for my situation and it not only worked like a charm,
> in hindsight it made a whole lot more sense this way.

Over two decades of experience with Ada (a different language, sure, but
similar enough for the purpose of this discussion) lead to the conclusion
that being able to spread types across modules (more than what the Mercury
implementors desired!) was desirable enough to be included in the language.
I haven't followed Ada 200X for a while, but that was practically at the top of
the change list last time I did, and GNAT even had an experimental extension to
support it.

In general, I agree that this can be a design error, but refactorings that
are reasonable for toy code posted during an internet email discussion may not
make sense when we're talking about files that are tens of thousands of lines
long even in very high level languages. Scale changes everything.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Circular module dependencies

[Christopher A. Watford]

On Tue, 7 Sep 2004 05:36:18 -0700 (PDT), brogoff <brogoff@speakeasy.net> wrote:
>>>SNIP>>>
> In general, I agree that this can be a design error, but refactorings that
> are reasonable for toy code posted during an internet email discussion may not
> make sense when we're talking about files that are tens of thousands of lines
> long even in very high level languages. Scale changes everything.
> 
> -- Brian

I run across this problem all the time at work with C/C++ header
files. The difference here is C/C++ allows forward declarations which
remove the need for cyclic includes. However, it adds on maintenance
requirements for renaming structures and classes and their
declarations all over the place if things get messy.

I'm glad OCaml atleast 'seems' to have a more well defined approach to
cyclic dependencies.

-- 
Christopher A. Watford
christopher.watford@gmail.com
http://dorm.tunkeymicket.com

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Circular module dependencies

[Erik de Castro Lopo]

On Tue, 7 Sep 2004 05:36:18 -0700 (PDT)
brogoff <brogoff@speakeasy.net> wrote:

> In general, I agree that this can be a design error, but refactorings that
> are reasonable for toy code posted during an internet email discussion may not
> make sense when we're talking about files that are tens of thousands of lines
> long even in very high level languages. Scale changes everything.

Well my particular problem was definitely not "toy code posted 
during an internet email discussion" but a serious piece of
that has already grown to about 3000 lines. Yes its still 
small but in this case refactoring was definitely the best
solution.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"Ever since GNOME development began, I have urged people to aim
to make it as good as the Macintosh. To try to be like Windows
is to try for second-best." - Richard Stallman

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Circular module dependencies

[Nicolas Cannasse]

> Recently, there was a thread which talked about how difficult module
> dependencies were to resolve for linking in Ocaml.  I'm guessing this is
> because of cycles in the dependency graph.
>
> My thought is that maybe Ocaml shouldn't allow this to happen.  Wouldn't
> cyclical module dependencies be a symptom of bad design?  If a cyclic
> dependency occurs I can think of two ways of removing.
>
> First, if the dependency is among modules which are closely related, the
code
> in each module in the cycle which interacts, should be extracted into its
own
> module.   The cycle indicates code which is semantically related and would
> probably be easier to understand if it were all contained in the same file
> anyway.
>
> Second, if the cycle contains modules which aren't closely related, a new
> module should be created to encapsulate this dependency.  This could be
done
> using the Bridge pattern.  Since mutual dependencies make code brittle,
> explicitly revealing the cycle in a module makes the cycle more visible to
> the programmers and thus easier to deal with safely.
>
> Are there any examples of cyclic dependencies which shouldn't be handled
by
> either of these cases?

The theoric aspect of this approach are correct.
However in practice you end up sometimes with very big modules that you
would like to split into several files for the maintenance sake. This is
very difficult to do since you have to analyse the non-recursive parts of
your module, and you can't really split it in a logical way because you have
to care about the specific implementation you made which could create a
cycle. Think for instance someone programming in OO, where objects are
naturally recursive (structural subtyping helps to break cycles here, but
some can still remains). However in functionnal style this happen rarely,
but is still IMHO a needed feature, the possibility of having such following
wrong recursion being more rare and possible to detect at linking time :

--- module A
let x = A.x
--- module B
let x = B.x

Nicolas Cannasse


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners