Package Proposal (moby message)

[Scott E. Fahlman <Fahlman@CMU-CS-C>]

This is a retry of an earlier mailing that apparently never made it
through SU-AI.

It has been generally agreed that it is important to have a
workable Package system specified in the white pages, since packages
play such a large role in the production of portable code.  However, all
of our past attempts to agree upon a package system have failed for one
reason or another.  Since the manual is to be finalized very soon, I
thought that it might be worthwhile to make one last attempt to propose
something that, maybe, we can all agree upon.

Some amount of hill climbing on this proposal is certainly possible (if
we climb quickly enough), but if we don't agree on something very soon,
the first edition of the white pages will simply have to say that ":" is
reserved for some future package system, ":symbol" is a self-evaluating
keyword, and everything else is left unbound.  That would be tragic.  So
if you feel compelled to raise objections, it would be very helpful if
you could accompany such objections with a specific counter-proposal
whenever possible.  It would also be useful if people could refrain from
trying to think up the most perverse and convoluted cases that might
ever occur, and just concentrate on what you need to get useful work
done.  We can patch this chapter in later editions if need be, but right
now the choices are to go for something simple and workable or to have
nothing at all.  Obviously, work cannot begin on a yellow-pages library
until this has been resolved.

Moon and Weinreb have persuaded me that we really do want some sort of
runtime inheritance from one package to another -- a sort of deep
binding -- and that our earlier attempt to fudge this issue by proposing
a copying paradigm was misguided.  So this proposal features
inheritance, plus the concept of internal and external symbols that was
introduced (in the context of Common Lisp) by Dave Dill.  Also, I have
come around to the view that a package name should be a string, not a
symbol.  This eliminates the issue of where the package name is
interned.

One final point: the system proposed here is intended only to solve the
problem of developing and running code with modules written by many
people.  It is not intended to solve version-control problems, to ensure
system integrity, or to provide Ada-like modules for separate
compilation.  All of those issues are important to the future of Lisp as
a tool for building large systems -- worthy thesis topics -- but if we
try to solve them here and now we will end up with no package system at
all.

Here it is, then:

***************************************************************************

One problem with most Lisp systems is the use of a single name space for
all symbols.  In large Lisp systems, with modules written by many
different programmers, accidental name collisions become a serious
problem.  In the past, this problem has been addressed by the use of a
prefix on each symbol name in a module or by some sort of clumsy ``obarray''
switching to keep the names separated.

Common Lisp addresses this problem through the @i[package system],
derived from an earlier package system developed for Lisp Machine Lisp.
The Common Lisp package system provides an @i[export] mechanism for
easily dividing the symbols in a package into @i[external symbols],
which are part of the package's public interface to other packages, and
@[internal symbols], which are for internal use only and are normally
hidden from other packages.

A @i[package] is a data structure that establishes a mapping from print
names (strings) to symbols.  (The package thus replaces the ``oblist''
or ``obarray'' of earlier Lisp systems.)  A symbol may appear in many
packages, but will always have the same name.  On the other hand, the
same name may refer to different symbols in different packages.  No two
symbols in the same package may have the same name.

Some of the symbols in a package are external and some are internal.
The functions @b[export] and @b[unexport] move symbols from external to
internal status within a package, respectively.

Each package is named by a unique string.  There is a single name space
for packages.  The name is usually assigned when the package is created.
The function @b[find-package] translates a package-name into the
associated package.  The function @b[package-name] returns the name of a
package.  The package name may be changed with @b[setf] of
@b[package-name].  (This is occasionally useful when, for development
purposes, it is desirable to load two versions of a package into the
same Lisp.  We can load one, rename it, and then load the other, without
getting a lot of name conflicts.)

<< The LispM package system has a much more complicated system for
name-to-package translation, in effect providing a tree-structured
directory of names.  It seems to me that this much simpler scheme will
suffice for our present needs.  Does anyone have a counter-example that
is not too contrived?  I thought about adding some synonym machinery so
that a package could go by several names, but this also seems to be more
trouble than it is worth.  Opinions? >>

The value of the special variable @b[*package*] must always be a package
object (not a name).  This is referred to as the @i[current package].

When the Lisp reader has, by parsing, obtained a string of characters
thought to name a symbol, that name is looked up in the current package.
This lookup may involve looking in other packages whose external symbols
are inherited by the current package (see below).  If the name is found,
the corresponding symbol is returned.  If the name is not found, a new
symbol is created for it and is placed in the current package as an
internal symbol; if the name is seen again while this same package is
current, the same symbol will then be returned.  When a new symbol is
created, a pointer to the package in which it is initially placed is
stored in the @i[package cell] of that symbol; the package is said to be
the symbol's @i[home package], and is said to @i[own] the symbol.  (Some
symbols are not owned by any package; they are said to be
@i[uninterned].)

Often it is desirable, when typing an expression to be read by the Lisp
reader, to refer to a symbol in some package other than the current one.
This is done through the use of a @i[qualified name], which consists of
the package name, followed by a colon, followed by the print name of the
symbol.  This causes the symbol's name to be looked up in the specified
package, rather than in the current one.  For example,
``@b[editor:buffer]'' refers to the symbol named ``@b[buffer]'' in the
package named ``@b[editor]'', regardless of whether there is a symbol
named ``@f[buffer]'' in the current package.  If ``@b[buffer]'' does not
exist in package ``@b[editor]'', it is created there as a new internal
symbol.  (If, on the other hand, there is no package named
``@b[editor]'', an error is signalled.)

The package named @b[keyword] contains all keyword symbols used by the
Lisp system itself and by user-written code.  Such symbols must be
easily accessible from any package, and name conflicts are not an issue
since these symbols are used only to label arguments and never to carry
package-specific values or properties.  Because keyword symbols
are used so frequently, Common Lisp permits ``@b[keyword:foo]'' to be
abbreviated to simply ``@b[:foo]''.  The @b[keyword] package is also
treated specially in that whenever a symbol is added to the @b[keyword]
package, the symbol is automatically declared to be a constant and is
made to have itself as its value.  This is why every keyword evaluates
to itself.

All other uses of colons within names of symbols are not defined by
Common Lisp, but are reserved for implementation-dependent use; this
includes names that end in a colon, contain two or more colons, or
consist of just a colon.

Symbols from another package may be added to the current package in two
ways.  First, one or more individual symbols may be added to the current
package by use of the @b[import] function.  The form @b[(import
'editor:buffer)] takes the symbol named @b[buffer] in the @b[editor]
package (this symbol was located when the form was read by the Lisp
reader) and adds it to the current package as an internal symbol.  The
imported symbol is not automatically exported from the current package,
but if it is already present and external, that is not changed.  After
the call to @i[import] it is possible to refer to @b[buffer] in the
current package without any qualifier.  The status of @b[buffer] in the
package named @b[editor] is unchanged, and @b[editor] remains the home
package for this symbol.  If the imported symbol already exists in the
current package, this operation effectively does nothing.  If a distinct
symbol with the name @b[buffer] already exists in the current package, a
correctable error is signalled.  The user will be offered a choice of
whether or not the importation of this symbol is to go forward.  << Or
should we just let it happen? >>

The second mechanism, the @b[inherit-package] function, causes the
current package to inherit all of the @b[external] symbols of some other
package.  These symbols can then be referred to from the current package
without a qualifier, and they in effect become external symbols of the
current package, passed along to any other package that inherits the
current one.  There is no way to inherit the @i[internal] symbols in
another package; to refer to an internal symbol, you must either make that
symbol's home package current or use a qualifier.  When a package is
created, it is given an initial list of ancestors, usually including at
least the @b[lisp] package.  @b[Inherit-package] adds a new package to
the end of this list, if that package is not already present.
@b[Uninherit-package] removes a package from the list.  The
@b[package-ancestors] function returns this list for a given package.

<< No convenient way is provided to reorder the list of ancestors.  Can
anyone think of a good reason why this would be needed?  I can't. >>

When a name N is being looked up in package X, the system first searches
for N among the internal and external symbols of X itself.  Then, it
searches the ancestor packages of of X in the order they appear on the
ancestor-list of X, but this search only succeeds if X is found as an
@i[external] symbol.  The search is depth-first: if the first ancestor
of X is Y, then the search of Y will include a search of Y's ancestors,
and so on.  The first occurrence of N along this search path is the one
that is returned.  The system remembers which packages have been visited
in a given search and does not search them a second time.  In addition
to being more efficient, this makes it possible to have cycles in the
tree, as when two packages wish to inherit from one another; each would
see its own symbols first, and then its partner's.

<< That sounds more complicated than it is.  We need to be able to
declare multiple ancestors for a given package, and there has to be SOME
determinate order in which the search occurs.  It is probably better to
let the set of packages searched be determined at runtime, by following
chains of ancestors, than to wire it into each package for the same
reason that inheritance is better than copying semantics: something up
in the tree of superiors might change at runtime.  With a bit of care
and some back-pointers, the search path for a package can be pre-computed
once and can then be corrected if anything changes up in the tree of
superiors, but we don't need to explain this to the users.  I envision
the internal and external symbols as residing in two separate
hash-tables within each package structure. >>

Each symbol contains a package slot that is used to record the home
package of the symbol.  When the symbol is printed, if it is in the
keyword package then it is printed with a preceding colon; otherwise, if
it is present (directly or by inheritance) in the current package, it is
printed without any qualification; otherwise, it is printed with the
name of the home package as the qualifier.  A symbol that is uninterned
(has no home package) is printed preceded by ``@b[#:]''.  It is
possible, by the clever use of import and unintern, to create a symbol
that appears to be uninterned but that in fact is interned in some
package.  The system does not check for this.

@Section[Built-in Packages]

The following packages are built into the Common Lisp system:

@begin[description]
@b[lisp]@\The package named @b[lisp] contains the primitives of the
Common Lisp system.  Its external symbols include all of the
user-visible functions and global variables that are present in the
Common Lisp system, such as @b[car], @b[cdr], @b[*package*], etc.
Almost all other packages will want to inherit @b[lisp] so that these
symbols are available without qualification.

@b[user]@\The @b[user] package is, by default, the current package at the time
a Common Lisp system starts up.  This package inherits the @b[lisp] package.

@b[keyword]@\This package contains all of the keywords used by built-in
or user-defined Lisp functions.  Symbols that start with a colon are
treated as if they started with "keyword:" instead.  All symbols in this
package are treated as constants that evaluate to themselves, so the
user can type @b[:foo] instead of @b[':foo].

@b[si]@\This package name is reserved to the implementation.  (The name
is an abbreviation for ``system internals''.)  Normally this is used to
contain names of internal and implementation-dependent functions.
<< Note, however, that most of the things traditionally found in SI: are
now internal symbols in the LISP: package.  Is it worth preserving SI: ? >>
@end[description]

@Section[Package System Functions and Variables]

@Defvar[Var {package}]
The value of this variable must be either a package or a symbol
that names a package; this package is said to be the current package.
The initial value of @b[*package*] is the @b[user] package.

The @b[load] function rebinds @b[*package*] to its current value.  If
some form in the file changes the value of @b[*package*] during loading,
the old value will be restored when the loading is completed.
@Enddefvar

@Defun[Fun {make-package}, Args {@i[package-name] @optional @i[ancestor-list]}]
Creates and returns a new package with the specified package name.
The @i[package-name] must be a string that does not currently name a
package.  If a package of this name already exists, a correctable error
is signalled.

The @i[ancestors-list] argument is a list of packages or
package names whose external symbols are to be inherited by the new
package.  If not supplied, this defaults to one ancestor, the @b[lisp]
package.
@Enddefun

@Defun[Fun {in-package}, Args {@i[package-name] @optional @i[ancestor-list]}] 
The @b[in-package] function is intended to be placed at the start of a
file containing a subsystem that is to be loaded into some package other
than @b[user].  It is similar in function to @b[make-package], except
that after the new package is created, the @b[*package*] variable is
bound to it.  This binding will remain in force until changed by the
user (perhaps with another @b[in-package] call), or until the
@b[*package*] variable reverts to its old value at the completion of a
@b[load] operation.

If a package of the same name already exists, it is assumed that
@b[in-package] merely wants to augment the existing package.  That
package becomes the current one.  The new ancestor list is merged with
the old one (any new ancestors are added at the end) and any new shadow
symbols are interned in the current package.
@Enddefun

@Defun[Fun {find-package}, Args {@i[name]}]
The @b[name] must be a string.  Returns the corresponding package, or
NIL if no such package exists.
@Enddefun

@Defun[Fun {package-name}, Args {@i[package]}]
The argument must be a package.  This function returns the string that
names that package.  @b[Setf] may be used with @b[package-name] to
rename the package.  The new name must be a string that does not
currently name a package.
@Enddefun

@Defun[Fun {ancestors-list}, Args {@i[package]}]
The argument must be a package.  This function returns that package's
list of ancestor packages.
@Enddefun

@Defun[Fun {list-packages}, Args {}]
This function returns a list of all packages that currently exist.
@Enddefun

@Defun[Fun {intern}, Args {@i[string] @optional @i[package]}]
The @b[package] argument defaults to the current package.  It is
searched for a symbol with the name specified by the @b[string]
argument.  This search will include inherited symbols, as described
above.  If a symbol with the specified name is found, it is returned.
If no such symbol is found, one is created and is installed in the
current package as an internal symbol.  This symbol is returned.
@Enddefun

@Defun[Fun {find-symbol}, Args {@i[string] @optional @i[package]}]
This is identical to @b[intern], but it never creates a new symbol.  If
a symbol with the specified name is found in the current package,
directly or by inheritance, the symbol found is returned.  The second
return value is T, indicating that the symbol was found.  The third
value is T if the symbol is an external symbol in the specified package,
NIL otherwise.  If the symbol is not found in the specified package,
@b[find-symbol] returns NIL for all three values.
@Enddefun

@Defun[Fun {unintern}, Args {@i[symbol] @optional @i[package]}]
If the specified symbol is present in the specified package, it is
removed from this package.  Moreover, if @i[package] is the home
package for the symbol, the symbol is made to have no home package.
The @i[package] defaults to the current package.
@b[unintern] returns T if it actually removed a symbol, and NIL otherwise.
@Incompatibility{The equivalent of this in @maclisp is @f[remob].}
@Enddefun

@Defun[Fun {export}, Args {@i[symbols]}]
The argument should be a list of symbols, or possibly a single symbol.
These symbols become external symbols in the current package, and are
therefore visible to any other package that imports the current one.
If a specified symbol is already an external symbol in @i[package], it
is unaffected.  @f[export] returns @true.

By convention, a call to @f[export] listing all exported symbols is
placed near the start of a file to advertise which of the symbols used
mentioned the file are intended to be used by other programs.
@Enddefun

@Defun[Fun {unexport}, Args {@i[symbols]}]
The argument should be a list of symbols, or possibly a
single symbol.  Any specified symbols that is an external symbol in the
current package is made to be an internal symbol instead.  Otherwise, it
is unaffected.  @f[unexport] returns @true.
@Enddefun

@Defun[Fun {import}, Args {@i[symbols]}]
The argument should be a list of symbols, or possibly a
single symbol.  These symbols become internal symbols in the
current package, and can therefore be referred to without a colon
qualifier.  @f[import] returns @true.
@Enddefun

@Defun[Fun {shadow}, Args {@i[symbols]}]
The argument should be a list of strings, or possibly a single string.
For each specified name, the current package is examined.  If a symbol
with that name is present in this package (directly, not by inheritance)
then nothing is done.  Otherwise such a symbol is created and is
inserted in the current package as an internal symbol.  This shadows any
symbol of the same name that would otherwise be inherited by the current
package.  @f[shadow] returns @true.
@Enddefun

@Defun[Fun {inherit-package}, Args {@i[packages]}]
The argument should be a list of packages or package names, or possibly
a single package or package name.  These packages are added to the end
of the current package's list of ancestors if they are not already
present in this list.  This means that all external symbols in the
inherited packages effectively become external symbols in the current
package.  Returns T.
@enddefun

@Defun[Fun {uninherit-package}, Args {@i[packages]}]
The argument should be a list of packages or package names, or possibly
a single package or package name.  These packages are removed from the
current package's list of ancestors.  Returns T.
@enddefun

@Defmac[Fun {do-symbols}, Args {(@i[var] @Mopt<@i[package]> @Mopt<@i[result-form]>) @Mstar<@i[declaration]> @mstar<@i[tag] @mor @i[statement]>}]

@f[do-symbols] provides straightforward iteration over the symbols of a
package.  The body is performed once for each symbol visible in the
@i[package], in no particular order, with the variable @i[var] bound to
the symbol.  This includes internal symbols, external symbols, and
symbols inheritied by this package from it ancestors.  Then
@i[resultform] (a single form, @i[not] an implicit @f[progn]) is
evaluated, and the result is the value of the @f[do-symbols] form.
(When the @i[resultform] is evaluated, the control variable @i[var] is
still bound, and has the value @nil.)  If @i[resultform] is omitted, the
result is @false.  @Funref[return] may be used to terminate the
iteration prematurely.  If execution of the body affects which symbols
are contained in the @i[package], other than possibly to remove the
symbol currently the value of @i[var] by using @Funref[unintern], the
effects are unpredictable.
@Enddefmac

@Defmac[Fun {do-all-symbols}, Args {(@i[var] @Mopt<@i[result-form]>) @Mstar<@i[declaration]> @mstar<@i[tag] @mor @i[statement]>}]

This is similar to @f[do-symbols], but executes the body once for every
symbol contained in ``every'' package.  (This may not get all symbols
whatsoever, depending on the implementation.)  It is @i[not] in general
the case that each symbol is processed only once, since a symbol may
appear in many packages.
@Enddefmac