\section{Our technique}

We suggest a \clos{}-based \emph{protocol} defining the set of
operations on a first-class environment.  This protocol contains
around $40$ generic functions.  The details of the proposed protocol
can be found in the appendix of this paper.  The protocol has been
implemented as part of the \sicl{} project.%
\footnote{See https://github.com/robert-strandh/SICL.}

Mainly, the protocol contains versions of \commonlisp{} environment
functions such as \texttt{fboundp}, \texttt{find-class}, etc. that
take an additional required \texttt{environment} argument.

For a simple example, consider the \sicl{} implementation of the
standard \commonlisp{} function \texttt{fboundp}:

{\small\begin{verbatim}
(defun fboundp (name)
  (sicl-genv:fboundp
    name
    (load-time-value (sicl-genv:global-environment))))
\end{verbatim}}

In this example \texttt{sicl-genv} is the nickname for the package
named \texttt{sicl-global-environment} which contains the symbols of
the protocol defined in this paper.  In each global environment, the
function \texttt{global-environment} in that package returns
the value of the environment itself.  When the definition in the
example above is \emph{loaded}, either as source or from a previously
compiled file, the value of the \texttt{load-time-value} form will
therefore be the global environment in which the definition is loaded,
thereby permanently \emph{linking} this definition to that global
environment.

In addition to these functions, the protocol contains a set of
functions for accessing \emph{cells} that in most implementations
would be stored elsewhere.  Thus, a binding of a function name to a
function object contains an indirection in the form of a
\emph{function cell}.  The same holds for the binding of a variable
name (a symbol) to its \emph{global value}.  In our implementation,
these cells are ordinary \texttt{cons} cells with the \texttt{car}
containing the value of the binding, and the \texttt{cdr} containing
\texttt{nil}.  The reason for using ordinary \texttt{cons} cells is
that they are already supported in any \commonlisp{} implementation.
The only possible reason for choosing a different representation for
cells would be to save one word in each cell, since the \texttt{cdr}
slot in each of our \texttt{cons} cells is wasted.  However, the saved
space would probably be more than consumed by the space occupied by
specialized inspector functionality for dealing with custom cell
representations.

These cells are created as needed.  The first time a reference to a
function is made, the corresponding cell is created.  Compiled code
that refers to a global function will have the corresponding cell in
its run-time environment.  The cost of accessing a function at
run-time is therefore no greater in our implementation than in an
implementation that accesses the function through the symbol naming
it, hence our claim that there is no performance penalty for accessing
this information at run-time.

The \sicl{} compiler translates a reference to a global function (say
\texttt{foo}) into something similar to this code:

{\small\begin{verbatim}
(car
  (load-time-value
    (sicl-genv:function-cell
      'foo
      (sicl-genv:global-environment+))))
\end{verbatim}}

except that what is shown as \texttt{car} is not the full
\commonlisp{} function, because the argument is known to be a
\texttt{cons} cell.  When the code containing this reference is
loaded, the resulting machine code will refer to a local variable
containing the \texttt{cons} cell of the current global environment
that is permanently assigned to holding the function definition of
\texttt{foo}.

Our technique does, however, incur a performance penalty for functions
such as \texttt{fdefinition} and \texttt{symbol-value} with an
argument that is computed at run-time%
\footnote{When the argument is a constant, a suitable
  \emph{compiler-macro} can turn the form into an access of the
  corresponding cell.}
compared to an implementation in which each symbol contains slots for
these objects.  However, even in a high-performance implementation such
as \sbcl{}, these values are \emph{not} contained in symbol slots.

The performance penalty incurred on these functions depends on the
exact representation of the environment.  The representation of the
environment is outside the scope of this paper, however.  Here, we
only consider the \emph{protocol} for accessing it.  However, it is
not hard to devise a reasonable implementation.  In SICL, we use a
hash table for each namespace with the keys being the corresponding
\emph{names}%
\footnote{Functions are named by symbols and lists; variables are
  named by symbols; packages are named by strings; classes are named
  by symbols; etc.}
of the entities in that namespace.

While it is \emph{possible} for the application programmer to create
new global environments, it would not be a common thing to do, at
least not for the applications of first-class global environments that
we have considered so far.  For that reason, we have not streamlined
any particular technique for doing so.  The difficulty is not in
\emph{creating} the environment per se, but rather in filling it with
useful objects.  For the purpose of bootstrapping, we currently fill
environments by loading code into it from files.
