modules

[Jonathan A Rees <JAR@AI.AI.MIT.EDU>]

Here is my answer to Pavel's request "could you be more concrete about
the kind of system you envision?".

Rather than try to say what I think is the right thing (I don't know),
I'll simply try to describe my understanding of the essence of the ML
module system.  This has been the point of departure in my own recent
ponderage of the topic of modules.  This message does NOT constitute a
proposal or endorsement of its content.

The names have been changed to offend the innocent (MacQueen et al.),
and other accomodations made to a schemish worldview.  Equivalent ML
constructs are given at right.

    <exp> ::= (STRUCTURE <sig> <form>*)           ; struct ... end
	    | (STRUCTURE-REF <struct> <id>)	  ; .
	    | ... the usual ...

    <form> ::= <exp>
	     | <definition>
	     | (OPEN-STRUCTURE <exp> <sig>)       ; open
	     | (DEFINE-SIGNATURE <name> <sig>)    ; signature ... = ...

    <sig> ::= <name>
	    | (SIGNATURE <id>*)                   ; sig ... end

A signature is a list of variable names.  Signature definitions, like
macro definitions, must be known at compile time.  If Scheme had a way
to write types, a signature would give types for the variables; but then
so would any binding construct, including LAMBDA, LETREC, and DEFINE; so
this is an orthogonal design issue.

A STRUCTURE-expression evaluates to a structure, which is something you
can do STRUCTURE-REF on.  The values exported by a structure are given
by the signature.  (A signature is like an interface decsription, and a
structure is like an implementation of that interface.)  The body of a
STRUCTURE-expression looks like the top level of a file.  Simple
example:
   (structure-ref (structure (signature a) (define a 5))
		  a)
        =>  5

The contents of a file that participates in the module system is
typically a single STRUCTURE expression, or a LAMBDA whose body is a
STRUCTURE (in ML, a "functor").  LOAD then returns a structure (or a
procedure that returns a structure).  This being a common case, a file
syntax could be invented (analogous to T's or Pavel's HERALD) that
doesn't leave that extra parenthesis dangling until the end.  The
merits of this are debatable.

(OPEN-STRUCTURE struct sig) is equivalent to a series of DEFINE forms
that transfer values from the given structure to the current
environment.  E.g.
    (open-structure foo (signature a b))
is equivalent to
    (define a (structure-ref foo a))
    (define b (structure-ref foo b))

Of course, one doesn't generally write out (SIGNATURE ...) forms in
STRUCTURE and OPEN-STRUCTURE forms, but instead does a DEFINE-SIGNATURE:
    (define-signature foo-sig (signature a b))
    (define foo (structure foo-sig
		  (open-structure bar bar-sig)
		  (define a ...)
		  (define b ...)))

Multiple definitions in the same block are in error, so in particular,
if I do
    (open-structure foo foo-sig)
    (open-structure bar bar-sig)
within the same STRUCTURE body, and foo-sig and bar-sig both list
an identifier a, then you lose.  (For the same reason that
(lambda (x x) ...) is an error -- and by the way, the report needs to
say that it is.)

If importing is by value rather than by reference, then all of this
mechanism can be implemented using macros.  (Left as an exercise.  Hint:
signatures are macros.)  If importing is by reference, then it can be
done in terms of two new special forms, one for getting a variable's
location (like Zetalisp LOCF or T LOCATIVE) and another for doing an
"identity declaration" (DEFINE-LOCATION var exp), which would bind var
to the value of evaluating exp, which value must be something returned
by a LOCATIVE form.  Of course, more sophisticated implementations are
possible.

Features of the this module system (and ML's) that make me like it
better than Pavel's:

- It's simple: really only four new things.

- File syntax is completely equivalent to some existing expression
  syntax; the existence of files is an artifact.  A call to LOAD
  returns the value of the expression to which the file is equivalent.
  (Actually ML doesn't work quite like this, but it's close.)

- A file is considered to be an expression that yields a value, rather
  than a block of code that has a side-effect on some environment.  Thus
  LOAD is not generally a side-effect, and does not add new bindings to
  any pre-existing environment.  If a client wants to get at the values,
  it has to fetch them itself using STRUCTURE-REF or OPEN-STRUCTURE;
  that's not the file's business.

- Similarly, it is up to the loader of a file to decide in which
  environment the file is to be closed.

- It certainly does not preclude the existence of more general
  first-class environments, but it treats that (and meta-tools
  generally) as an orthogonal question.

- Interfaces (signatures) are described centrally, so that multiple
  implementations and the clients of those implementations can all share
  a single definition.  This makes code more concise and easier to change
  than otherwise.

Things I don't want to talk about now:
  - structures resemble records (concrete vs. abstract types?)
  - importing could be by reference instead of by value
  - inheritance among signatures and implementations
  - signatures could be first class (echoes of PROGV)
  - what about interactive development & debugging
  - performance questions (e.g. how to avoid lots of copying) (I think Appel
    has written a paper about this)
  - open-structure is too powerful
  - maybe allow open-structure in other contexts, or disallow it except at
    top of a structure form, or banish it altogether
  - multiple "views" on a structure
  - syntactic file sugar to avoid dangling parentheses
  - where do macros fit in (put them in signatures?)
  - system configurations
  - functors
  - Felleisen & Friedman '85
  - etc.

I didn't promise that I was going to give constructive criticism.  Maybe
if you wait a few months I'll be able to answer these concerns and
propose something I like.