Modules, mutually-recursive importing

Interface and implementation modules solve the problem of mutually-recursive imports, just like function pre-definitions solve the problem of mutually-recursive functions.

It is normal, and often necessary, for one module to import another. This does not cause any difficulty if there are no circular (or mutually-recursive) imports (such as two modules, each importing the other).

When shared modules need to import each other, they can usually do so safely if they are organized in this order:

  1. exported record type pre-definitions,
  2. imports of modules that define record types required for all remaining exported pre-definitions,
  3. the remaining exported pre-definitions themselves: function pre-definitions, global variable and constant pre-definitions, and catch declarations
  4. imports of modules that are needed to define everything that was pre-defined above, and everything that is local to the module,
  5. the definitions for the exported pre-definitions, as well as any pre-definitions, definitions, and declarations that are local to the module.

This organization will work in most cases, but not all. In cases where it does not work, the module implementer may choose to break up each shared module into interface and implementation modules, or combine the mutually-referential modules into a single larger module.

Combining the modules may not be an option, if the ownership for all the modules involved is spread among several groups, or if the resulting module becomes too large and complex to be maintained easily.

Mutually-recursive module example

Consider the following scenario, where an application tracks words and sentences for each input document. Words and sentences are each represented by record types. Each sentence contains one or more words, and each word references all sentences that contain it.

This is the module that implements the word type, organized as recommended:

  module shared as com.stilo.documentation.word
  
  ; Pre-Definitions
  
  export record word     elsewhere
  
  import 'sentence.xmd' unprefixed
  
  export function add-reference
     for value word     w
     to  value sentence s
     elsewhere
  
  export word function create-word
     value string       t
     in value sentence  s optional
     elsewhere
  
  export function output-word
     value word         w
     elsewhere
  
  export function output-word-references
     value word         w
     elsewhere
  
  ; Definitions
  
  export record word
     field stream   text
     field sentence refs       variable
  
  export function add-reference
     for value word     w
     to  value sentence s
  as
     set new w:refs to s
  
  export word function create-word
     value string       t
     in value sentence  s optional
  as
     local word w
     set w:text to t
     add-reference for w to s when s is specified
     return w
  
  export function output-word
     value word         w
  as
     output w:text
  
  export function output-word-references
     value word         w
  as
     repeat over w:refs as ref
        output '    '
        output-sentence ref
     again

The sentence module would be implemented as follows:

  module shared as com.stilo.documentation.sentence
  
  ; Pre-Definitions
  
  export record sentence elsewhere
  
  import 'word.xmd' unprefixed
  
  export sentence function create-sentence
     read-only word word-list
  elsewhere
  
  export function output-sentence
     value sentence     s
  elsewhere
  
  ; Definitions
  
  export record sentence
     field word     words      variable
  
  export sentence function create-sentence
     read-only word word-list
  as
     local sentence s
     repeat over word-list
        set new s:words to word-list
        add-reference for s:words to s
     again
     return s
  
  export function output-sentence
     value sentence     s
  as
     repeat over s:words as w
        output ' ' when !#first
        output-word w
     again
     output '%n'

The problem occurs when the function bodies are encountered. If the main program imports "word.xmd" first, then things are encountered in this order:

  1. Import of "word.xmd"
  2. Record pre-definition for word
  3. Import of "sentence.xmd"
  4. Record pre-definition for sentence
  5. Import of "word.xmd". (Because "word.xmd" is shared, the module is not reread. Instead, all of the things known to be exported from "word.xmd" (which at this point is only the record pre-definition for word) are made available for use in the "sentence.xmd" module.)
  6. Function pre-definitions for "sentence.xmd" (create-sentence and output-sentence).
  7. Record type definition for sentence.
  8. Function definitions for "sentence.xmd" (create-sentence and output-sentence).

The function definition for create-sentence contains a call to the function add-reference, whose pre-definition has not yet been seen.

A similar situation occurs if "sentence.xmd" is imported first.

Mutually-recursive module interfaces

The mutual-recursion problem can be solved by separating the shared modules into separate interface and implementation modules.

The interface module "word.xif" would be:

  module interface shared as com.stilo.documentation.words
  
  export record word     elsewhere
  
  import 'sentence.xif' unprefixed
  
  export function add-reference
     for value word     w
     to  value sentence s
     elsewhere
  
  export word function create-word
     value string       t
     in value sentence  s optional
     elsewhere
  
  export function output-word
     value word         w
     elsewhere
  
  export function output-word-references
     value word         w
     elsewhere

The interface module "sentence.xif" would be:

  module interface shared as com.stilo.documentation.words
  
  export record word     elsewhere
  
  import 'sentence.xif' unprefixed
  
  export function add-reference
     for value word     w
     to  value sentence s
     elsewhere
  
  export word function create-word
     value string       t
     in value sentence  s optional
     elsewhere
  
  export function output-word
     value word         w
     elsewhere
  
  export function output-word-references
     value word         w
     elsewhere

This works because interface files do not contain function bodies, which is where the problem occurs when modules combine interfaces and implementations.

The implementation module can then have both interfaces available before any of the function definitions. The implementation module "word.xmp" is:

  module implements 'word.xif'
  
  import 'sentence.xif' unprefixed
  
  ; Definitions
  ...

The implementation module "sentence.xmp" would be similar:

  module implements 'sentence.xif'
  
  import 'word.xif' unprefixed
  
  ; Definitions
  ...

Related Topics