recursive modules in Haskell

Alastair Reid alastair@reid-consulting-uk.ltd.uk
Wed, 19 Mar 2003 15:18:47 +0000


Simon Peyton-Jones <simonpj@microsoft.com> writes:
> Nothing deep.  GHC is just a fairly big thing and one of its
> assumptions is that it is compiling one module at a time.  There'd
> be quite a bit of chuffing around to remove this assumption.
> Nothing fundamental, but real work.

The other big problem is that, in the worst case, you need to
typecheck the entire program (however many modules that may be) at
once.  If your program happens to be GHC, Lolita or one of the other
big Haskell programs, this might be prohibitively expensive.

A potentially lightweight alternative that Simon PJ and I talked about
some time ago (1998/9?) is to break the recursion between two modules
by using type signatures on top-level definitions.  The idea is to
generate the .hi-boot files that GHC currently uses automatically.
Suppose we have a pair of mutually recursive modules A and B, we can
generate A.hi-boot as follows:

- read all of A and B discarding all function bodies as we go.
  [It might be possible to avoid reading B - depending on
  how much checking is performed at this stage.]

- check all the type, class and instance definitions in A and B

- keep the type signatures for exported definitions from A, discard
  everything else

[At this point, GHC would normally start typechecking function bodies
and generating code but we can stop now because all we need to do
is generate the .hi-boot file.]

- write A.hi-boot

This approach gives most of what we need from recursive modules.

It has the advantage that it probably doesn't take too much effort to
add to a compiler that already uses interface files. 

The big disadvantage is that you have to provide type signatures for
any definitions involved in cyclic module dependency.  This may not be
too bad since Haskell style guides suggest that you should provide
type signatures for all exported top-level definitions.

--
Alastair Reid                 alastair@reid-consulting-uk.ltd.uk  
Reid Consulting (UK) Limited  http://www.reid-consulting-uk.ltd.uk/alastair/