There are mutually recursive programs that GHC can't compile

GHC currently does not have proper support support recursive programs and instead users to write .hs-boot files to break cycles in the module graph. This is finding a feedback arc set for your import graph. This process isn’t complete however.

Consider this set of modules:

module A where
import B
import C
data A
a :: A -> B -> C
a = b `seq` c `seq` undefined

module B where
import A
import C
data B
b :: A -> B -> C
b = a `seq` c `seq` undefined

module C where
import A
import B
data C
c :: A -> B -> C
c = a `seq` b `seq` undefined

This forms a complete directed graph for the definitions with this edge set: { (a, b), (a, c), (b, a), (b, c), (c, a), (c, b) }. A minimal feedback arc set for this would be { (b, a), (c, a), (c, b) }. This translate this Haskell would mean that b needs a {-# SOURCE #-} import of a and c needs a {-# SOURCE #-} import of both a and b. Here is what the hs-boot files defining aand b would look like:

-- hs-boot files
module A where
data A
a :: A -> B -> C

module B where
data B
b :: A -> B -> C

There’s a problem however. These type signatures contain types that aren’t defined. Here, the A and B .hs-boot files both need to import each other and .hs-boot files can’t contain cycles, so this program is impossible for GHC to compile.

Just for completeness, the .hs-boot files would form a graph with this edge set { (A, B), (A, C), (B, A), (B, C) } and a minimal feedback arc set for this would be { (B, A) }. This means that B needs a secondary .hs-boot file for A.

To give some context. I’m currently writing my own Haskell compiler that has very cyclical modules. I’ve run into this on occasion and I’ve had to work around it. Lastly, just to brag my compiler can currently compile this perfectly :grinning_face_with_smiling_eyes:, no .hs-boot files needed.

9 Likes

I skimmed this, but my general view is that if you’ve found yourself in a place where two modules are mutually referencing each other, you probably should be restructuring the layout of the code to move those definitions into the same module, and if you want the “nicer” separation then do the definition in a .Internal module and then re-export the definitions from the modules you want. I’m not sure it’s fair to say that “Haskell can’t compile” these programs, but “Haskell can’t compile these programs if you choose to separate them across files in an awkward way”.

I skimmed this, but my general view is that if you’ve found yourself in a place where two modules are mutually referencing each other, you probably should be restructuring the layout of the code to move those definitions into the same module…

That’s probably true for most programs that but doing that would ruin the structure of my compiler. I currently have 113 .hs-boot modules and a lot of my modules share constructor names and selector names. I started following Java style OOP and putting all my major types in their own file to avoid constructor and field conflicts and I’ve really grown to like it. Unfortunately doing this in a compiler, where everything is cyclical, means I have a lot mutually recursive modules.

I’m not sure it’s fair to say that “Haskell can’t compile” these programs, but “Haskell can’t compile these programs if you choose to separate them across files in an awkward way”.

So this is a semantics things, but the Haskell report says that Haskell implementations must support mutually recursive module in some manner. I can’t imagine that would mean “support a subset of all possible mutually recursive modules”. That code is Haskell 2010, if my compiler can handle it, why can’t GHC?

1 Like

You meant to say “GHC” instead of “Haskell”. It’s a GHC bug that it can’t compile those modules. They are legal Haskell.

3 Likes

Here is the modules chapter in the Haskell 2010 report:

1 Like