There is no reliable way to extract the interface from an implementation short of compiling the implementation. So the only "proper" way to handle mutually recursive module is to have hand-written interface files where there is a cycle. This is how Haskell used to be, but alas, hand written interface files fell out of fashion at some point. -- Lennart On Fri, 24 Sep 2004, Henning Thielemann wrote:

Date: Fri, 24 Sep 2004 16:17:24 +0200 (MESZ) From: Henning Thielemann Reply-To: Henning Thielemann To: Malcolm Wallace Cc: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] mutually recursive modules

On Fri, 24 Sep 2004, Malcolm Wallace wrote:

...

The main obstacle is that Haskell systems generally process one file/module at a time. To extract an interface from each module first, before further processing, would not only require a second pass over the source files, but to load all of them simultaneously, which can be rather space-hungry.

I don't see where it is necessary to load more modules than usually. Modula doesn't support cycles in the dependencies. Each implementation depends only on interfaces of other modules and the interfaces must not depend cyclicly. Haskell compilers can reduce the problem to the situation of Modula by extracting the interface from the implementation. Maybe it's better if the user explicitly allows mutually recursive modules with a command line option which will invoke an automatic interface generation. The generation of an interface file should depend only on the corresponding implementation file, as it is the case for manual .hiboot creation. For mutually recursive functions across modules the signature had to be specified by the user to avoid the simultaneous loading of all modules.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Lennart

One other thing while I think of it... I wrote:

At the risk of stating the obvious, there's no reason (apart from incompatibility with the current language, of course) why this has to be a separate file.

I should also have used the phrase "double maintenance problem".

Cheers, Andrew Bromage

Alastair:

A crude approach is to assume the type (\forall a. a) for any function with no prototype

Andreas:

Huh? How can that ever be sound?

You're right, it's not - my mistake. I guess that leaves two options: 1) Insist on a prototype for any exported function. 2) Insist on a prototype for any imported function which is used. The latter is more in keeping with Haskell's lazy checking of import clashes. (There's a third option where you assume a type which you don't know anything about like (\exists a. a) but I'd be surprised if this let you typecheck any more useful programs.) -- Alastair

On 24-Sep-2004, Jan-Willem Maessen wrote:

An anecdotal note -

hbcc (the front end to the pH and Eager Haskell compilers, and also of GRIN) contained several mutually recursive modules both in the compiler and in the prelude.

One of the best things we ever did was get rid of the mutual recursion. The resulting refactoring helped us to group related pieces which had (for historical reasons) ended up scattered. It also cut our rebuild time dramatically, and let us do cross-module inlining and optimization safely.

In short, using mutual recursion was probably a bad idea, and we found we were better off without it.

Here's another anecdotal note. When refactoring the Cryptol compiler, in particular when abstracting some interfaces to use type classes, I found that (1) In the intermediate stages of the refactoring, I needed to use mutual recursion in quite a few different places. This was a pain because it required manually writing .hi-boot files. This was also problematic because my colleagues were reluctant to have our sources depend on a rather poorly supported feature of Haskell, and were also reluctant to have implementation-specific files like .hi-boot files in our CVS repository. As a result, I did not check in the intermediate stages of the refactoring into our CVS repository. These factors made the development process more difficult, made the code review process more difficult, and increased the likelihood of a CVS conflict. (2) Although most of the mutual recursion occurred only in the intermediate stages of the refactoring, some of the mutual recursion remained at the end of the refactoring, forcing two modules with only the smallest degree of coupling to be combined into a single module. The two modules in question were (a) the module which defines the calling interface between the Cryptol front-end and the various Cryptol back-ends, and (b) the module which defines the structure which records the settings of command-line options. Here (a) depends on (b) because one of the parameters which is passed to the back-ends is the command-line option settings, and (b) depends on (a) because one of the option settings is the currently selected back-end (represented using an existentially quantified typeclass-constrained type). So while I agree that unrestrained use of mutual recursion can lead to poor structuring, I think that in many cases mutual recursion _is_ useful, either as an intermediate stage during refactoring or as a final stage. A compiler warning about mutual recursion (with some way to suppress it in individual cases) might be useful, but a compiler error or the requirement to manually write separate .hi-boot files is not helpful, IMHO. -- Fergus J. Henderson | "I have always known that the pursuit Galois Connections, Inc. | of excellence is a lethal habit" Phone: +1 503 626 6616 | -- the last words of T. S. Garp.

On Monday 27 Sep 2004 8:27 pm, Andrew Pimlott wrote:

On Mon, Sep 27, 2004 at 10:46:25AM -0700, Fergus Henderson wrote:

...

(2) Although most of the mutual recursion occurred only in the intermediate stages of the refactoring, some of the mutual recursion remained at the end of the refactoring, forcing two modules with only the smallest degree of coupling to be combined into a single module.

The two modules in question were (a) the module which defines the calling interface between the Cryptol front-end and the various Cryptol back-ends, and (b) the module which defines the structure which records the settings of command-line options. Here (a) depends on (b) because one of the parameters which is passed to the back-ends is the command-line option settings, and (b) depends on (a) because one of the option settings is the currently selected back-end (represented using an existentially quantified typeclass-constrained type).

As a programmer not necessarily speaking about Haskell, I also find that mutually dependent modules are often natural in practice, and that avoiding them requires excessive and awkward factoring.

This is a subject I'd been meaning to whine about, so now seems like a good time for a "me too" post. I agree with Henning,Fergus,Andrew. It's annoying when what should be a fairly straight forward exercise in adding a new function to a module turns out to far less straight forward because you've introduced circular dependency, forcing you to either refactor modules which have become "old and familiar friends" (you know where everything is) for no good reason or start mucking about with hiboot files. I don't agree with the view that mutual recursion between modules is symptomatic of a poor design which badly needs refactoring anyway. On the contrary, I think perfectly natural and useful for modules which are part of the same package. If anything this problem _makes_ me produce a poor design by putting some functions in the "wrong" module. OK, it doesn't really make me do this. There are alternatives, but I suspect that in reality most programmers will take the path of least resistance (certainly I will, given the opportunity :-) Regards -- Adrian Hey