+ <sect2 id="mutual-recursion">
+ <title>How to compile mutually recursive modules</title>
+
+ <indexterm><primary>module system, recursion</primary></indexterm>
+ <indexterm><primary>recursion, between modules</primary></indexterm>
+
+ <para>GHC supports the compilation of mutually recursive modules.
+ This section explains how.</para>
+
+ <para>Every cycle in the module import graph must be broken by a <filename>hs-boot</filename> file.
+ Suppose that modules <filename>A.hs</filename> and <filename>B.hs</filename> are Haskell source files,
+ thus:
+<programlisting>
+module A where
+ import B( TB(..) )
+
+ newtype TA = MkTA Int
+
+ f :: TB -> TA
+ f (MkTB x) = MkTA x
+
+module B where
+ import {-# SOURCE #-} A( TA(..) )
+
+ data TB = MkTB !Int
+
+ g :: TA -> TB
+ g (MkTA x) = MkTB x
+</programlisting>
+<indexterm><primary><literal>hs-boot</literal>
+ files</primary></indexterm> <indexterm><primary>importing,
+ <literal>hi-boot</literal> files</primary></indexterm>
+Here <filename>A</filename> imports <filename>B</filename>, but <filename>B</filename> imports
+<filename>A</filename> with a <literal>{-# SOURCE #-}</literal> pragma, which breaks the
+circular dependency. For every module <filename>A.hs</filename> that is <literal>{-# SOURCE #-}</literal>-imported
+in this way there must exist a souce file <literal>A.hs-boot</literal>. This file contains an abbreviated
+version of <filename>A.hs</filename>, thus:
+<programlisting>
+module A where
+ newtype TA = MkTA Int
+</programlisting>
+</para>
+<para>To compile these three files, issue the following commands:
+<programlisting>
+ ghc -c A.hs-boot -- Poduces A.hi-boot, A.o-boot
+ ghc -c B.hs -- Consumes A.hi-boot, produces B.hi, B.o
+ ghc -c A.hs -- Consumes B.hi, produces A.hi, A.o
+ ghc -o foo A.o B.o -- Linking the program
+</programlisting>
+</para>
+<para>There are several points to note here:
+<itemizedlist>
+<listitem>
+ <para>The file <filename>A.hs-boot</filename> is a programmer-written source file.
+ It must live in the same directory as its parent source file <filename>A.hs</filename>.
+ Currently, if you use a literate source file <filename>A.lhs</filename> you must
+ also use a literate boot file, <filename>A.lhs-boot</filename>; and vice versa.
+ </para></listitem>
+
+<listitem><para>
+ A <filename>hs-boot</filename> file is compiled by GHC, just like a <filename>hs</filename> file:
+<programlisting>
+ ghc -c A.hs-boot
+</programlisting>
+When a hs-boot file <filename>A.hs-boot</filename>
+ is compiled, it is checked for scope and type errors.
+ When its parent module <filename>A.hs</filename> is compiled, the two are compared, and
+ an error is reported if the two are inconsistent.
+ </para></listitem>
+
+ <listitem>
+ <para> Just as compiling <filename>A.hs</filename> produces an
+ interface file <filename>A.hi</filename>, and an object file
+ <filename>A.o</filename>, so compiling
+ <filename>A.hs-boot</filename> produces an interface file
+ <filename>A.hi-boot</filename>, and an pseudo-object file
+ <filename>A.o-boot</filename>: </para>
+
+ <itemizedlist>
+ <listitem>
+ <para>The pseudo-object file <filename>A.o-boot</filename> is
+ empty (don't link it!), but it is very useful when using a
+ Makefile, to record when the <filename>A.hi-boot</filename> was
+ last brought up to date (see <xref
+ linkend="using-make"/>).</para>
+ </listitem>
+
+ <listitem>
+ <para>The <filename>hi-boot</filename> generated by compiling a
+ <filename>hs-boot</filename> file is in the same
+ machine-generated binary format as any other GHC-generated
+ interface file (e.g. <filename>B.hi</filename>). You can
+ display its contents with <command>ghc
+ --show-iface</command>. If you specify a directory for
+ interface files, the <option>-ohidir</option> flag, then that
+ affects <filename>hi-boot</filename> files
+ too.</para>
+ </listitem>
+ </itemizedlist>
+ </listitem>
+
+ <listitem><para> If hs-boot files are considered distinct from their parent source
+ files, and if a <literal>{-# SOURCE #-}</literal> import is considered to refer to the
+ hs-boot file, then the module import graph must have no cycles. The command
+ <command>ghc -M</command> will report an error if a cycle is found.
+ </para></listitem>
+
+ <listitem><para> A module <literal>M</literal> that is
+ <literal>{-# SOURCE #-}</literal>-imported in a program will usually also be
+ ordinarily imported elsewhere. If not, <command>ghc --make</command>
+ automatically adds <literal>M</literal> to the set of moudles it tries to
+ compile and link, to ensure that <literal>M</literal>'s implementation is included in
+ the final program.
+ </para></listitem>
+</itemizedlist>
+</para>
+<para>
+A hs-boot file need only contain the bare
+ minimum of information needed to get the bootstrapping process
+ started. For example, it doesn't need to contain declarations
+ for <emphasis>everything</emphasis> that module
+ <literal>A</literal> exports, only the things required by the
+ module(s) that import <literal>A</literal> recursively.</para>
+<para>A hs-boot file is written in a subset of Haskell:
+<itemizedlist>
+<listitem><para> The module header (including the export list), and import statements, are exactly as in
+Haskell, and so are the scoping rules.
+ Hence, to mention a non-Prelude type or class, you must import it.</para></listitem>
+
+<listitem><para> There must be no value declarations, but there can be type signatures for
+values. For example:
+<programlisting>
+ double :: Int -> Int
+</programlisting>
+</para></listitem>
+<listitem><para> Fixity declarations are exactly as in Haskell.</para></listitem>
+<listitem><para> Type synonym declarations are exactly as in Haskell.</para></listitem>
+<listitem><para> A data type declaration can either be given in full, exactly as in Haskell, or it
+can be given abstractly, by omitting the '=' sign and everything that follows. For example:
+<programlisting>
+ data T a b
+</programlisting>
+ In a <emphasis>source</emphasis> program
+ this would declare TA to have no constructors (a GHC extension: see <xref linkend="nullary-types"/>),
+ but in an hi-boot file it means "I don't know or care what the constructors are".
+ This is the most common form of data type declaration, because it's easy to get right.
+ You <emphasis>can</emphasis> also write out the constructors but, if you do so, you must write
+ it out precisely as in its real definition.</para>
+ <para>
+ If you do not write out the constructors, you may need to give a kind
+ annotation (<xref linkend="sec-kinding"/>), to tell
+ GHC the kind of the type variable, if it is not "*". (In source files, this is worked out
+ from the way the type variable is used in the constructors.) For example:
+<programlisting>
+ data R (x :: * -> *) y
+</programlisting>
+</para></listitem>
+<listitem><para> Class declarations is exactly as in Haskell, except that you may not put
+default method declarations. You can also omit all the class methods entirely.
+</para></listitem>
+<listitem><para> Do not include instance declarations. There is a complication to do with
+how the dictionary functions are named. It may well work, but it's not a well-tested feature.
+ </para></listitem>
+</itemizedlist>
+</para>
+ </sect2>
+
+