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