Title

Portable Modules

Author

André van Tonder

Abstract

We propose a portable module system for Scheme with the following properties:

Rationale

Scheme currently lacks a standardized module system. This SRFI proposes and implements a portable module system. The proposal addresses the issues of incremental compilation and of predictable management of compile-time and runtime environments. It is fully integrated with the reflective tower of SRFI 72.

Specification

The following forms are provided: 
                        
         module   
         import
         import-for-all
         scheme



Reflective tower:
The begin-for-syntax form is used to specify bindings, imports and computations at arbitrary levels of the reflective tower. For a discussion of the latter, see SRFI 72. 

syntax: (MODULE name (export-name ...) form ...)
This form declares a module with name name. It may only occur at top-level, and module declarations may not be nested. The namespace of module names is separate from the namespace of toplevel locations and syntax transformers.

The forms form ... are considered top-level forms. During expansion of the module, these forms are expanded from left to right in a fresh environment containing all the standard bindings of the host Scheme at every level of the reflective tower.

Before the module is expanded, all identifiers in the body form ... that do not refer to standard Scheme bindings are in effect renamed, completely isolating the module from any existing bindings in the global environment. Because of this, a module has no access to global variables, and any bindings introduced by the module are invisible outside the module. 

      (define global 1)
 
      (module m () 
        (define x 1)
        (display global)) 

      (import m) ==> reference to undefined identifier: global
      x          ==> reference to undefined identifier: x
The list (export-name ...) declares the set of identifiers exported by the module. Only bindings at the ground level in the reflective tower are exported. 
  (module m (x y)
    (define x 1)
    (begin-for-syntax (define x 2))
    (begin-for-syntax (define y 3)))

  (import m)
  x                     ==> 1
  (begin-for-syntax y)  ==> reference to unidentified identifier: y
Unbound identifiers may be exported. This allows one to remove bindings from an environment. This mechanism is useful for defining restricted languages by overriding subsets of standard Scheme at the required level of the reflective tower. 
  (module remove-x (x))
  
  (define x 1)       ==> 1
  x
  (import remove-x)  
  x                  ==> reference to unidentified identifier: x
Macros may expand to modules, permitting a simple form of module parametrization. An example is included below. 


syntax: (IMPORT module-name)
        (IMPORT module-name exp)
Import declarations may only appear at the toplevel or module toplevel. The effect of an import declaration is to make the exported identifiers of module-name available in the code following the import, at the level of the reflective tower at which the import declaration appears.

Environments at different levels of the reflective tower are strictly separate. Different bindings for the same name may be imported at different reflective levels by enclosing the imports in nested begin-for-syntax forms, as the example shows: 

  (module m (x)
    (define x 1))

  (module n (x)
    (define x 2))

  (module o (x)
    (define x 3))

  (module p ()
    (import m)                                       ; imports x = 1 into ground level
    (begin-for-syntax (import n))                    ; imports x = 2 into meta-level
    (begin-for-syntax (begin-for-syntax (import o))) ; imports x = 3 into meta-meta-level
    
    (let-syntax ((foo (lambda (form)
                        (let-syntax ((bar (lambda (form)
                                            (quasisyntax
                                             (quasisyntax (list x ,x ,,x))))))
                          (bar)))))
      (display (foo))))
  
  (import p)  ==> (1 2 3)

Arbitrary computations may be performed on import symbols by providing as second argument to import an expression that should evaluate to a renaming procedure with signature 

           symbol -> (union symbol #f)
Symbols renamed to #f are not imported. For example, the following form will import only car and cdr from scheme, renaming them as indicated. 
     (import scheme (lambda (symbol)
                      (case symbol
                        ((car) 'scheme:car)
                        ((cdr) 'scheme:cdr)
                        (else #f))))

     (scheme:car '(1 2))   ==> 1
The expression exp is evaluated at one reflective level higher than the level at which the import form appears.

The scope of an imported name is from the point of importation to either the end of the module, the first subsequent import that shadows the same name, or the first define or define-syntax binding the same identifier. The forms define and define-syntax always bind a location local to the module, never an imported location. 

     (module m (x)
       (define x 1))

     (module n ()
       (define (f) x)
       (import m)
       (define (g) x)
       (define x 2)
       (define (h) x)
       (display (f))     ; refers to the local    x = 2
       (display (g))     ; refers to the imported x = 1
       (display (h)))    ; refers to the local    x = 2

     (import n)  ==> 2 1 2
Imported locations may be mutated by using set! 
     (module m (x)
       (define x 1))

     (module n ()
       (define (f) x)
       (import m)
       (define (g) x)
       (set! x 2)
       (define (h) x)
       ; (display (f))   ; would refer to the local x, which is unbound
       (display (g))     ; refers to the imported x = 2
       (display (h)))    ; refers to the imported x = 2

     (import n)  ==> 2 2



syntax: (IMPORT-FOR-ALL module-name)
        (IMPORT-FOR-ALL module-name exp)
Provides a mechanism for importing a module simultaneously into all phases and reflective levels. An occurrence of 
  (import-for-all m [exp])
is equivalent to the combination 
  (import m [exp])
  (begin-for-syntax (import m [exp]))
  (begin-for-syntax (begin-for-syntax (import m [exp])))
  ...
up to the maximum level of the reflective tower used in the body of the module. 


module: SCHEME
This module provides the standard bindings of the host Scheme environment. In addition, it provides the primitive bindings described in SRFI-72 and in this document.

Evaluation semantics:

When a module declaration is evaluated, the forms form ... in the module body are expanded and compiled, but not executed [8]. The module body is only executed later when an import form referring to the module is evaluated.

During expansion of the module, the sequence of forms in its body are expanded from left to right in a fresh environment containing all the standard bindings of the host Scheme at every level of the reflective tower.

Any code wrapped in begin-for-syntax is expanded and then immediately evaluated when encountered during expansion. The right hand sides of macro definitions are also immediately evaluated and bound to the macro name. The macro is then available for further expansion of code at the same reflective level at which the macro definition appeared. This is the standard practice of compiling Scheme code, refined to take into account the reflective tower.

In the following example, u is available during compilation at the meta-level for expanding the right hand side of v, while v is available during compilation at the ground level for expanding the argument of display. The display statement is compiled but not evaluated until the module is later imported: 

  (module m ()
    
    (begin-for-syntax
      (define-syntax u (lambda (form) (syntax 1))))

    (define-syntax v (lambda (form) (quasisyntax (list ,(u) 2))))

    (display (v)))

  (import m)   ==> (1 2)

When an import form is encountered during expansion, the imported module is instantiated for syntax as follows: Syntactic bindings in the imported module are initialized, any code in the imported module wrapped in begin-for-syntax is evaluated, and any modules imported by the importing module are in turn instantiated for syntax. Identifiers exported by the imported module are then available at the current level of the reflective tower of the importing module for further expansion of the latter.

An imported module is guaranteed to be instantiated for expansion only once during expansion of a given importing module or toplevel, even if it is imported indirectly via different import chains.

In the following example, the code wrapped in begin-for-syntax is evaluated when m is imported for syntax during expansion of n, which imports it directly, and during expansion of o, which imports it indirectly, and again when the toplevel import form is expanded. The expanded module bodies are not executed until the final toplevel import form is evaluated. 

  (module m ()
    (begin-for-syntax (display 'm-syntax))     ==> m-syntax
    (display 'm-execute))     
  
  (module n ()
    (import m))                                ==> m-syntax
  
  (module o ()
    (import n))                                ==> m-syntax
 
  (import o)                                   ==> m-syntax m-execute

When an import form is evaluated, the imported module m is instantiated for execution as follows: All forms in the module that are not macro definitions or begin-for-syntax forms are evaluated from left to right, (re-)initializing any locations bound by the module.

An imported module is guaranteed to be instantiated for execution at most once during expansion, and at most once during evaluation of a given importing module or toplevel, even if it is imported indirectly via different import chains. The former can happen if the import form is itself wrapped in begin-for-syntax. In that case, the imported module will be instantiated for expansion and for execution during expansion of the importing module.

In the following example, 'm is only displayed once, despite m being imported into o via two different import chains. 

  (module m ()
    (display 'm))   
    
  (module n ()  
    (import m)     
    (display 'n))   
      
  (module o ()    
    (import n)     
    (import m))            
    
  (import o)        ==> m n
In the following example, during compilation of n, the import wrapped in begin-for-syntax is first expanded, causing m to be instantiated for syntax. Since the form is wrapped in begin-for-syntax, it is immediately evaluated, causing m to be instantiated for execution. Finally, compilation of the second import form does not instantiate m again for syntax, as might have been expected, since it has already been instantiated for syntax. 
  (module m ()
    (begin-for-syntax (display 'm-syntax))  ==> m-syntax
    (display 'm-execute))

  (module n ()
    (begin-for-syntax (import m))           ==> m-syntax m-execute
    (import m))

Examples

Implementation

A portable reference implementation is provided for testing modules in the interpreter. It includes the hygienic macro system of SRFI 72 and should run out of the box, or with minimal modifications, on most host Schemes. It has been tested on Chez, Chicken, Gambit and MzScheme.

The reference implementation is available here.

Acknowledgements

I would like to thank Felix Winkelmann for extremely helpful discussions contributing significantly towards improving this proposal.

References

The following references were all extensively used during the preparation of the current proposal. 
[1] Matthew Flatt - Composable and Compilable Macros You Want it When?
    International Conference on Functional Programming (ICFP'2002). 2002.

    http://library.readscheme.org/page5.html

[2] Richard A. Kelsey and Jonathan A. Rees - Modules 
    (in 'The Incomplete Scheme48 Reference Manual for release 0.57'). 2001.
    
    http://s48.org/0.57/manual/s48manual_24.html

[3] Oscar Waddell and R. Kent Dybvig - Extending the Scope of Syntactic Abstraction. 
    Conference Record of POPL'99: The 26th ACM SIGPLAN-SIGACT
    Symposium on Principles of Programming Languages. January 1999.

    http://library.readscheme.org/page5.html
                        
[4] R. Kent Dybvig - Chez Scheme user's guide:

    http://www.scheme.com/csug/

[5] Christian Queinnec - 23 things I know about modules for Scheme
    Workshop on Scheme and Functional Programming (2002). October 2002.

    http://library.readscheme.org/page5.html

[6] Felix Winkelmann - The Chicken Scheme Compiler
   
    http://www.call-with-current-continuation.org/

[7] The R6RS Editors - The March 2005 R6RS Status Report

    http://www.schemers.org/Documents/Standards/Charter/

[8] The PLT MzScheme language manual: Modules.

    http://download.plt-scheme.org/doc/299.200/html/mzscheme/