Module proposal [long]

[rauen@brokaw.LCS.MIT.EDU (James R. Rauen)]

Slipping away from the #f .EQ. '() brouhaha momentarily, here is a
module proposal for R5RS.  The proposal is based on a design by Pavel
Curtis and myself, currently being implemented at Xerox PARC.

Two prefatory comments:

1. Modules are not first class.  In essence, they are statically
checkable binding forms; in this respect they are similar to
definitions.

2. Sections 4 and 5 of the proposal, which deal with syntax, are a bit
dated given the "painting" algorithm that supersedes syntactic
closures.  However, I don't see any fundamental problems with updating
this.

		Jim Rauen
		545 Technology Square, Room NE43-440
		Cambridge, MA 02139    
		(617) 253-0884
		rauen@brokaw.lcs.mit.edu

======================================================================


			Module System Proposal
			----------------------

0. Design Goals

Our principal design goal is to support very large scale programming
in Scheme.  This goal affects several fundamental design decisions,
such as not having first-class modules.  Other major goals are:

* The semantics must be static; they should not require any notion
of state or mutation.  However, the semantics must accomodate such
tools as separate compilation, read-eval-print loops, and dynamic
loading.

* Static checks (for example, checking unbound variables,
unimplemented or multiply implemented interfaces, and incorrect
inter-module references) must be possible.

* Syntactic extension must be accomodated and well-specified,
especially given separate compilation.


1. Overview

The foundation of the module system is the Scheme language as (will
be) defined in the Revised^4 Report.  R4RS defines a Scheme program as
a sequence of definitions and expressions.

The module system adds several new kinds of program components:
interfaces, modules, syntax definitions, and meta-modules. 


2. Interfaces

An interface is a collection of specifications of variables.  The
specification of a variable includes an identifier that names the
variable, and (optionally) other information about the variable, such
as its type.  Each variable should be accompanied by a comment that
informally describes the variable.

Example:

	(INTERFACE hash-table	; Mutable hash tables.
	  (VALUE create)	; (create) returns a new, empty table
	  (VALUE insert!)       ; (insert! tab key val) associates key
				;   with val in tab.
	  (VALUE lookup)	; (lookup tab key) returns associated
	  			;   value for key in tab, or #f if 
	  )			;   there is none


3. Modules

A module is an isolated scope that contains a complete program.  The
program inside the module can only communicate outside the module by
explicitly exporting and importing variables.

[More correctly, modules share value bindings.  However, since there
is a one-to-one correspondence between the shared variables and the
shared value bindings, I will generally use the phrase "shared
variable".]


3.1 Exports

A module provides a variable to other modules by exporting the
variable.  The variable must have a specification in some interface
that is lexically visible to the exporting module.  The module
includes an EXPORTS clause that lists the names of the
interface and the exported variable.

The program inside the exporting module must either contain
a definition of the variable or contain a module that itself exports
the variable.  

For brevity's sake, the export clauses (EXPORTS e1), ..., (EXPORTS en)
may be combined into (EXPORTS e1 ... en).  If a module exports all the
variables specified in an interface, without any renaming, then the
module may simply (EXPORTS interface-name).  Also, if a module exports
more than one frob from an interface, there is the syntax (EXPORTS
(interface-name frob1 frob2 ...)).

Example:
	(MODULE ((EXPORTS (hash-table create insert! lookup)))
	  (DEFINE create (LAMBDA () ...))
	  (DEFINE insert! (LAMBDA (tab key val) ...))
	  (DEFINE lookup (LAMBDA (tab key) ...)))


3.2 Imports

A module gains access to variables in other modules by importing the
variables.  An imported variable must have a specification in an
interface, and there must be a module at the appropriate scoping level
(3.6, below) that exports the variable.  The importing module
contains an import clause of the form (IMPORTS (interface-name
identifier)), where the interface-name and identifier indicate which
variable is desired.

Like exports, the import clauses (IMPORTS i1), ..., (IMPORTS in) may
be combined into (IMPORTS i1 ... in), and if a module imports
everything specified in an interface, then the module may simply
(IMPORTS interface-name).  Also, if a module imports more than one
frob from an interface, there is the syntax (IMPORTS (i-name frob1
frob2 ...)).

The program inside a module uses an ACCESS form to obtain the value of
an imported variable.  The access form may either be written (ACCESS
ifcname varname) or ifcname#varname.  The reader transforms the latter
syntax into the former.

An imported variable may not be assigned to.  Side-effects are always
restricted to the module where the variable is defined.  However, a
module can certainly export procedures that modify its variables.

Example:
	(MODULE ((IMPORTS hash-table))
	  (DEFINE ht (hash-table#create))
	  (hash-table#insert! ht 'foo 3)
	  (hash-table#lookup ht 'foo)		; => 3
	  )


3.3 Opening imported variables

To avoid the nuisance of having to qualify imported variable names
with their interfaces, a module can "open" any binding it imports.  By
opening the binding, the module introduces a new name, local to the
module, by which the imported binding can be referred to.

The new name defaults to the imported variable name.  To obtain this
behavior, the module contains an open clause of the form
(OPEN (interface-name identifier)).  To use a different name, the
module should contain a clause of the form (OPEN (i-name
(id-in-module id-in-interface))).  Open clauses may be abbreviated in
the same way as import and export clauses.

Example:
	(MODULE ((IMPORTS hash-table) (OPEN hash-table))
	  (DEFINE ht (create))
	  (insert! ht 'foo 3)
	  (lookup ht 'foo)		; => 3
	  )


3.4 Tree structure of programs

Because programs contain modules, and each module itself contains a
program, programs have a tree structure.  At the root of the tree is
the outermost (``closed'') program.  Its children are the closed
program's components, which include definitions, expressions,
interfaces, and modules.  Each module has a child of its own, the
program that the module contains.  


3.5 Scope of interfaces

An interface defined in a program P is visible to all the programs
that are descendants of P, unless shadowed by another interface
definition of the same name.


3.6 Scope of shared variables

The scope of a shared variable is the set of programs that have access
to the binding that implements the variable.  Three rules determine
the scope of a shared variable:

1. A shared variable is available in the program where it is defined.
(This is the only program that can mutate the variable.)

2. A shared variable is available in any program containing a module
that exports the variable.

3. A shared variable is available in any program inside a module that
imports the variable.  The importing module must either occur within
the same program as the exporting module, or nested inside another
module that imports the binding.

These rules allow there to be more than one shared variable
corresponding to a particular value specification in an interface.
For example, consider the following program.  The labels on the left
identify each program (P#) and each module (M#) for identification
purposes and to depict the tree structure.

[P0]                 (INTERFACE foo (VALUE bar))
[P0]
[P0][M1]             (MODULE ((EXPORTS foo))	
[P0][M1][P1][M2]       (MODULE ((EXPORTS foo))
[P0][M1][P1][M2][P2]     (DEFINE bar 1)))
[P0]
[P0][M3]             (MODULE ((IMPORTS foo))
[P0][M3][P3]           foo#bar)
[P0]
[P0][M4]             (MODULE ()
[P0][M4][P4][M5]       (MODULE ((EXPORTS foo))
[P0][M4][P4][M5][P5]	 (DEFINE bar 2))
[P0][M4][P4][M6]       (MODULE ((IMPORTS foo))
[P0][M4][P4][M6][P6]     foo#bar))

The above program contains two shared variables corresponding to the
specification of bar in interface foo.  The first variable, defined in
program P2, is available to programs P0, P1, P2, and P3.  The second
variable, defined in program P5, is available to programs P4, P5, and
P6.


4. Syntactic extension

Syntactic extensions (macros) are how new kinds of expressions are
defined.  The semantics of a syntactic extension are given by a
procedure that transforms instances of the new syntax into other
forms.


4.1 Syntax definitions

The syntax definition (DEFINE-SYNTAX identifier meta-expression)
introduces a syntactic extension whose scope is the program where the
syntax definition occurs.  

The meta-expression is interpreted in the initial environment and
store.  It should evaluate to a transformation procedure.  The
meta-expression may close over variables and perhaps mutate these
variables.  The semantics of syntax invocation takes this into
account.


4.2 Syntax invocation

A syntactic extension is invoked by a list form whose first element is
an identifier that has a syntax definition.  

When syntax is invoked, something equivalent to the following happens.
The meta-expression for the syntax is evaluated in an initial
environment and store.  The resulting procedure is applied an
arbitrary number of times to arbitrary forms, registering any
side-effects in the store.  Finally, the transformation procedure is
applied to the list form; the result is used in place of the original
list form.


4.3 Shared syntax

Modules can share syntactic extensions.  Shared syntax obeys the same
scoping rules that shared variables do.  Interfaces may contain syntax
specifications analogous to variable specifications.  Modules may
import, export, and open syntactic extensions in the same way as they
do variables.


4.4 Syntactic environments

A syntactic environment associates identifiers with their static
meanings.  An identifier may be mapped to any of:
	* An interface
	* A syntactic extension
	* A primitive syntax description
	* A variable

Syntactic environments can be used to control the scoping of names by
transformation procedures, as described by Bawden and Rees ("Syntactic
Closures", Lisp and Functional Programming 1988).


5. Meta-modules

A meta-module is an isolated scope containing a program called a
meta-program.  The meta-module can export some of the meta-program's
variables to be used as syntax transformation procedures.

Meta-modules are used to implement syntactic extensions that cannot be
handled easily with DEFINE-SYNTAX.  Two situations where this is
likely are (1) when a syntactic extension is so complicated that it is
best implemented with an entire program, and (2) when several
syntactic extensions wish to share auxiliary procedures.


5.1 Exports

The exports of a meta-module must have syntax specifications.  Within
the meta-program, however, they are treated as regular variables.
Each exported syntactic extension must either be implemented by a
top-level variable definition in the meta-program, or be exported by
some module in the meta-program.

Example:
	(INTERFACE stackish-ops (SYNTAX push))
	(META-MODULE ((EXPORTS (stackish-ops push)))
	  (DEFINE push (LAMBDA (form env) ...)))


5.2 Imports and Opens

The imports and opens of a meta-module establish a syntactic
environment.  This syntactic environment is an extension of the
initial syntactic environment, with additional entries for the items
that the meta-module imports and opens.  This syntactic environment is
considered to be the "environment of definition" of syntax exported by
the meta-module.


5.3 Invocation of meta-module syntax

When syntax defined by a meta-module is invoked, something equivalent
to the following happens.  The meta-program is evaluated in the
initial environment and store.  The resulting transformation
procedures are applied, in arbitrary order, an arbitrary number of
times to arbitrary forms.  All side-effects from the evaluation and
applications are registered in the store.  Finally, the appropriate
transformation procedure is applied to the form invoking the syntax,
and the resulting form is used in place of the original.

Invocation of syntax defined by a meta-module follows essentially the
same rules as those given in 4.2, above.  However, in the stage of
arbitrary applications, any transformation procedure in the
meta-module may be applied.


6. Initial environments

Every program implicitly imports and opens the SCHEME interface.  The
SCHEME interface specifies the primitive procedures and syntax defined
in the Scheme report.  It also specifies the module system syntax
itself (ACCESS, INTERFACE, MODULE, etc.) and several other useful
procedures (MAKE-SYNTACTIC-CLOSURE, etc.).  A module may forego this
default for its body program by including WITHOUT-OPENING-SCHEME in
its externals.


7. Grammar

 p: Program	::=	(d | e | i | m | mm)*
 d: Definition	::=	(DEFINE id e)
		 |	(DEFINE-SYNTAX id me)
 e: Expression	::=	usual Scheme expressions
		 |	(ACCESS in id)
		 |	(id q*)			; syntactic extension
		 |	((ACCESS in id) q*)	; syntactic extension
 i: Interface	::=	(INTERFACE in s*)
 s: Spec	::=	(VALUE id at*) 
		 |	(SYNTAX id at*)
at: Attribute					; not specified 
 m: Module	::=	(MODULE (x*) p)
 x: External	::=	(EXPORTS {in | (in {id | (id id)}*)}*)
		 |	(IMPORTS {in | (in id*)}*)
		 |	(OPEN {in | (in {id | (id id)}*)}*)
		 |      WITHOUT-OPENING-SCHEME
mm: MetaModule	::=	(META-MODULE (x*) mp)
me: MetaExpr	::=	e
mp: MetaProgram	::=	p
in: IfcName	::=	id
id: Identifier
 q: Datum


The grammar does not reflect the following:
	* syntactic sugar for DEFINE forms
	* the shorthand in#id for (ACCESS in id)