\documentclass[a4paper]{article}
\usepackage{a4wide}
\title{Ensuring that function uses can be found}
\author{Richard A. O'Keefe\\
Computer Science, University of Otago}
\date{February 2000}
\def\arw{~$\rightarrow$ }
\def\imp{$\Rightarrow$}
\begin{document}
\maketitle
\begin{abstract}
I continue to seek minimal changes to Erlang that will make it
better for growing very large systems.
In this report I propose tightening up the module system so that
we can reliably find, in a given set of sources, all the places
where a given function is called or where a callback is defined.
The new directives needed are described in reasonable detail,
and revised versions of \verb|io.erl| and \verb|user.erl| are
attached to show how this works in real code.
\end{abstract}

\section{What is the problem?}

Suppose we need to change the interface of some function $m:f/n$.
Ideally, we would add a new function with a different name and/or
arity, perhaps changing the old function to call the new one.
For example, suppose we have a function
\begin{quote}
create\_file({\it FileName\/})\arw {\it Port}
\end{quote}
and discover that with the change to Unicode there are many different
ways the data might be encoded:  UCS4-BE, UCS4-LE, UCS2-BE, UCS-LE,
UTF-8, UTF-7, or the new ``standard compression scheme'' which I'll
call TR6 because that's the number of the report that defined it.
Then of course there's a range of characters set names like Latin-1,
KOI8R, MacRoman, and so on.  So we might want to change the interface
to
\begin{quote}
create\_file({\it FileName, Encoding\/})\arw {\it Port}
\end{quote}

That's the easy case.  We write the new definition, and then add the
{\it adapter} definition
\begin{quote}
create\_file({\it FileName\/})\arw open\_file({\it FileName}, native).
\end{quote}

However, it does not end there.  Now that the question of what encoding
should be used has arisen, we realise that some existing calls to the
old function should be changed to call the new one.  So we have to
{\em find} all the existing calls and check them.

We might find it advisable to keep the same name and arity but change
the argument order or interpretation.  For example, we might notice
that UNIX and Windows NT use the same character set (almost; Windows
replaces most of the C1 controls with useful printing characters) but
that UNIX uses LF for line termination and Windows uses CR-LF.  We
might even notice the existence of the C1 control ``NExt Line'' from
ECMA 48 and the Unicode characters Line Separator and Paragraph
Separator.  Clearly on input we should accept all of CR, LF, CRLF,
NEL, LS, and PS as line terminators (this is the recommendation of
UNicode report TR14 but has always been blindingly obvious), but on
output we should specify which one we want.  With shared file systems
around we cannot assume that the ``native'' convention is the right one.
So we might decide to replace the Encoding argument by OptionList:
\begin{quote}
create\_file({\it FileName, OptionList\/})\arw {\it Port}
\end{quote}
where {\it Option} can be {\it Encoding} or \{encoding,{\it Encoding\/}\}
or {\it LineEnd} or \{line\_end,{\it LineEnd\/}\} or whatever.

Now it is imperative to find all the existing calls of the form
\begin{quote}
create\_file|$(E_1, E_2)$
\end{quote}
so that they can be changed to
\begin{quote}
create\_file($E_1$, [\{encoding,$E_2$\}])
\end{quote}

One way to find the existing calls is to simply delete the old
export, relink the system, and see what complaints we get.  That will
work with C.  It will not work with Erlang.

There are two reasons why it will not work with Erlang.  One is
unavoidable, and modern dynamically linked C systems cannot avoid it
either.  That is that Erlang allows modules to be loaded dynamically.
Just because $m:f/n$ is not defined {\em now} doesn't mean it will not be
defined when the actual call happens.  Perhaps $m$ will be replaced.
More seriously, the {\em call} to $m:f/n$ might be in a module that not
only hasn't been loaded yet, it hasn't been compiled yet.

The other reason is avoidable:  Erlang simply doesn't know where all
the calls are in the code that is loaded or otherwise available for
inspection right now.

For a small Erlang program, it is feasible to find all the uses of a
function manually, using \verb|grep| and the like.  For medium sized
systems, it is already tedious.  Producing the attached examples was
more work than it should have been.  I would not like to have to rely on
such measures while maintaining the Erlang system itself.  Unfortunately,
we have to.  For large and very large systems, that's not tolerable; we
{\em must} have a reliable means of finding all the uses of any function in
all of the modules available to us, whether they are available in source
form, or compiled form, or already loaded.  I do not say that we have to
be able to {\em change} function uses in compiled or loaded modules,
only that we have to know they {\em exist} so that we know we have a
problem.

The purpose of my recent work has been to find a minimal set of changes
to Erlang which guarantee that we can find all function uses.  This
report describes those changes.

\section{Module interfaces}

The existing directives for declaring a module interface are
\begin{itemize}
\item -module({\it Module\/}).
\item -export({\it FunctorList\/}).
\item -import({\it Module, FunctorList\/}).
\end{itemize}

I have previously proposed several others, including
\begin{itemize}
\item -export\_to({\it Module, FunctorList\/}).
\item -use({\it Module, FunctorList\/}).
\end{itemize}
The ``Delenda Est Preprocessor'' report had -use\_only for what I now
call -use; that was because in that report I did not envisage requiring
such a directive for {\em every} cross-module call.  Now I do.

\subsection{module}

A -module directive is required as the first form in a module.
It specifies the name of the module.  This calls for no comment except
to note that in very large systems it will be hard to avoid collisions
in module names so that the space of module names will need some kind
of structure.

\subsection{import}

An -import declaration such as
\begin{quote}
-import($m$, $[f/n]$).
\end{quote}
provides the following pieces of information:
\begin{itemize}
\item there should be a module called $m$
\item it should export a function called $f/n$
\item this module intends to call $m:f/n$
\item when this module calls $m:f/n$ it may omit the $m:$ module prefix
\item this module may not contain a definition of $f/n$
\item this module may not -import $f/n$ from any other module.
\end{itemize}
This information is extremely valuable.  If we want to find out where
$m:f/n$ is used, one way is to trawl through the modules available to us
looking at their -import declarations.

It would be useful if Erlang compilers were emit error or at least warning
messages for modules that -import functions they do not call.  At present
they do not do so because they cannot be sure of detecting all the uses of
a function in a module.  For example, apply$(M, F, A)$ might call $m:f/n$
or it might not.  It would require very good, sometimes impossibly good,
data flow analysis to be sure.

There are some problems with the -import directive.
\begin{itemize}
\item The style guide for Erlang strongly warns against its use,
on the grounds that it is better to use an explicit module prefix
on the calls.
\item You can call any exported function in any module without
explicitly -importing it, so the only real effect of an -import
directive is to let you omit the module prefix, which the style
guide says not to do anyway.
\item A compiler cannot be sure whether you are using everything
you -import or not.
\end{itemize}

These problems are solved by the new -use directive and the constraints
to be discussed in the next section.

\subsection{export}

An -export directive such as
\begin{quote}
-export($[f/n]$).
\end{quote}
provides the following pieces of information:
\begin{itemize}
\item this module must define a function called $f/n$
\item any other module may call it
\end{itemize}

These directives are useful in themselves.  We {\em can} be sure that
any function that is {\em not} exported is only used in the current
module, and that every use of it is explicit.  Unexported functions
cannot be called indirectly by spawn/3 or apply/3 or anything like that.

However, there are several problems:
\begin{itemize}
\item if we wish to spawn a call to a function, that function must be
exported even if we have no intention whatsoever of making it available
to other modules
\item there are many ``applications'' in the Erlang/OTP system which
consist of a flotilla of modules.  A module in such a flotilla cannot
export it to another member or other members of the flotilla without
exporting it to absolutely every module.
\end{itemize}

These problems are fixed by the new -export\_to directive and the
changes to spawn discussed in subsection 3.1.

\subsection{use}

A -use directive has the form
\begin{quote}
-use({\it Module, FunctorList\/}).
\end{quote}.
It has much the same meaning as an -import declaration, but requires
that a module prefix be used.

To simplify maintenance, it is legal to both -use and -import a function.
Suppose
\begin{quote}
-import($m$, $[f/n]$).\\
-use($m$, $[f/n]$).
\end{quote}
both appear.  Then the -import directive says that this module must not
define $f/n$, and the -use directive says that any call to $m:f/n$ must use
the $m:$ prefix.  If you are converting from -import to -use, this means
that the compiler must report any calls of $m:f/n$ that do not have a
module prefix yet.  If you are converting from -use to -import, the
compiler will tell you if you have a clashing definition of $f/n$.

\subsection{export\_to}

An -export\_to directive looks like
\begin{quote}
-export\_to({\it ModuleOrModuleList, FunctorList\/}).
\end{quote}
We only need to consider
\begin{quote}
-export\_to({\it Module}, [{\it Name/Arity\/}]).
\end{quote}
where {\it Module} is an atom, {\it Name} is an atom,
and {\it Arity} is a non-negative integer, because
\begin{quote}
-export\_to($[m_1,\dots,m_m]$, $[f_11/n_1, \dots, f_n/n_n]$).
\end{quote}
is equivalent to $mn$ separate declarations
\begin{quote}
-export\_to($m_i$, $[f_i/n_i]$).
\end{quote}

Similarly, we can reduce
\begin{quote}
-export($[f_1/n_1, \dots, f_n/n_n]$).
\end{quote}
to $n$ separate declarations
\begin{quote}
-export($[f_i/n_i]$).
\end{quote}

Now the rule is simple:
\begin{itemize}
\item
function $m:f/n$ {\it is available to} module $x$
if and only if $x$ is $m$ or module $m$ contains a directive
(implying) -export([$f/n$]) or module $m$ contains
a directive (implying) -export\_to($x$, [$f/n$]).
\item
function $m:f/n$ may be {\it called without a prefix}
in module $x$ if and only if $x$ is $m$ or module $x$
contains a directive (implying) -import($m$, [$f/n$])
and does not contain any directive (implying)
-use($m$, [$f/n$]).
\item
function $m:f/n$ may be {\it called with a prefix}
in module $x$ if and only if $m:f/n$ may be called without
a prefix in module $x$ or module $x$ contains a directive
(implying) -use($m$, [$f/n$]).
\end{itemize}

It is just as important to notice what is not in these rules as what is.
There is no requirement in the definitions of callable with or without
a prefix that requires the function to be available.
\begin{itemize}
\item
when module $x$ is compiled, the compiler checks whether all functions
that are called with a prefix are callable with a prefix and all
functions that are called without a prefix are calllable without a
prefix.  It does not and in general cannot check whether they are
available.
\item
when module $m$ is compiled, the compiler gathers the information about
which functions are available to what modules and stores that as part
of a load module.
\item
when the modules comprising a flotilla are bound, the binder checks
that every -import or -use that refers within the flotilla has
indeed a function available to it.  This check is not foolproof,
because any module in the flotilla might be replaced at run time.
\item
in the run-time system, a ``constraint store'' should be maintained
listing both availability and requirement.  there are several cases
that can occur when module $x$ is loaded and thinks $m:f/n$ is callable:
\begin{itemize}
\item module $m$ is not loaded yet
\item module $m$ is loaded, but does not define any $f/n$
\item module $m$ is loaded and defines $f/n$ but does not export it
\item module $m$ is loaded, defines $f/n$, and exports it.
\end{itemize}
The two cases we expect are the last and the first.  In any case we want
the run-time system to maintain a dictionary of externally referenced
functions:  $\langle m,f,n \rangle$ will be in the dictionary if either
$m$ is loaded and exports $f/n$ or some loaded module tries to -import
or -use $m:f/n$. There is one normal case:  a call through a dictionary
entry to a loaded, defined, and exported function.  There are two error
cases:  a call to a module that is not loaded, and a call to a function
that is not exported (whether it exists inside the module or not is
private to the module.
\end{itemize}

Flotillas (collections of closely related modules typically making up
OTP ``applications'') are made easier to develop with the aid of
-export\_to and tighter control of module interfaces.  They can export
things to each other without vulnerability to other modules.

This report does not provide a complete solution to the flotilla problem;
but it is a big improvement.

\subsection{Run-time checking}

Just because the currently loaded modules do not satisfy all
function availability requirements does not mean that there is an
error that {\em must} be dealt with.  It may be that additional
or replacement modules will be loaded before the lack matters, or
that the missing functions will never be called.

However, it doesn't seem like a good idea for a module to start a
lengthy computation and crash half way through because of a missing
function.

I suggest that there be a standard way for a process to determine
whether a particular module is loaded and whether a particular
function is available.  My ideas on this are still somewhat fluid;
purely for the sake of discussion I propose
\begin{quote}
erlang:unavailable({\it SpecialClosureList})\arw {\it ModuleMissingList}
\end{quote}
where a special closure is a value that was originally constructed
as
\begin{tabbing}
MM\=\kill
\>{\bf fun} $[m:]f/n$
\end{tabbing}
in some module, not necessarily the current one, and a {\it ModuleMissing}
term has the form {\it Module} if the entire module is missing or
\{{\it Module,FunctorList\/}\} if the module is loaded and the listed
functions are missing from its exports, and a {\it Functor} in such a
term is a \{{\it Name,Arity\/\}} tuple.  A further requirement is that
all the tuples precede all the atoms in the result.  For example,
\begin{verbatim}
erlang:unavailable([fun m:f/1, fun m:g/2, fun n:h/2, fun n:h/3])
\end{verbatim}
might return
\begin{verbatim}
[{m,[{f,1},{g,2}]},n]
\end{verbatim}
to say that module m is loaded but doesn't provide f/1 or g/2,
while module n is not loaded at all.

The ideas behind this interface are
\begin{itemize}
\item ``all is well'' is represented by a constant ([]) that is
easy to test for
\item if there is at least one module missing, but the only problem
is modules not loaded, that is easy to test for too:
([M$|$\_] {\bf when} atom(M)).
\item a clear description of what is missing can be constructed from the
function result
\item in particular, the missing function names are available without
giving user code the ability to dig inside SpecialClosures.
\end{itemize}

For example, a module might contain
\begin{verbatim}
    -use(ou_logger, [start/1]).
    ...
	case erlang:unavailable([fun ou_logger:start/1]) of
	    [] -> begin()
	;   [ou_logger] ->
		ou_admiral(load, ou_logger),
		case erlang_unavailable([fun ou_logger:start/1]) of
		    [] -> begin()
		;   [ou_logger] -> error("load failed")
		;   _ -> error("ou_logger:start/1 not exported")
		end
	;    error("ou_logger:start/1 not exported")
	end
    ...
\end{verbatim}

In fact this pattern looks useful enough that one imagines that it
would be generalised:
\begin{verbatim}
    ou_admiral(ensure, SpecialClosure) ->
	case erlang:unavailable([SpecialClosure]) of
	    [] -> true
	;   [Module] when atom(Module) ->
	    ou_admiral(load, Module),
	    case erlang:unavailable([SpecialClosure]) of
		[] -> true
	    ;   [Module] when atom(Module) ->
		    error({could_not_load,Module})
	    ;   [Module,{Name,Arity}] ->
		    erorr({not_exported,{Module,Name,Arity}})
	    end
	;   [Module,{Name,Arity}] ->
	    error({not_exported,{Module,Name,Arity}})
	end.
\end{verbatim}

``Full Erlang'' needs some meta-level calls to ask about what loaded modules
export and import.

\subsection{Section summary}

In Erlang 4, a module can call any exported function from any module
without any warning in the directives.  Large Systems Erlang requires
{\em every} function called in a module to be explicitly listed, either
as a definition, or in an -import directive, or in a -use directive.
The -export\_to directive makes it possible to limit the number of modules
that could be affected by a change to the interface of a function.

\section{{\it Delenda est} spawn/3}

The previous section dealt with calls that were visible to the compiler.
That leaves a big problem:  computed calls.  Erlang has two kinds.

\subsection{Calls to closures}

A {\it special closure} is the value of a term of the form
\begin{tabbing}
MM\=MM\=\kill
\>{\bf fun} {\it [m:]f/n}
\end{tabbing}
where {\it m} (if present) is an atom, {\it f} is an atom,
{\it n} is a non-negative integer, and {\it [m:]f/n} names a
function that is callable in the current module.

A {\it general closure} is the value of a term of the form
\begin{tabbing}
MM\={\bf fun} \=\kill
\>{\bf fun}\>$(P_{11},\dots,P_{1n})$ [{\bf when} $G_1$]\arw $B_1$\\
\>{\bf ;}\>$(P_{k1},\dots,P_{kn})$ [{\bf when} $G_k$]\arw $B_k$\}\dots\\
\>{\bf end}
\end{tabbing}

A {\it closure} is either a special closure or a general closure.
Sometimes I will abuse the word ``closure'' to refer to a {\bf fun} term.

Clsoures may be included in data structures, picked out of data
structures, passed as or as part of a parameter, and even sent to
a process on the same node.  They may then be called.

At the calling site, we see $F(E_1,\dots,E_n)$ where $F$ is a variable.
Almost always, the compiler will not have the faintest idea what
function(s) $F$ might be bound to.

For my present purposes, that doesn't matter.  What matters is that
the reference to the function {\it [m:]f/n} of a special closure, or the references to the functions in the Body(s) of a general closure, are fully explicit in the {\bf fun} term the closure originated from.
If we are looking for all the uses of bloodnok:major/2, then we can
find the one inside
    lists:map(fun (X, Y) -> bloodnok:major([X,Y], 3) end, Xs, Ys)
without any difficulty at all.  If we want to change the interface
of bloodnok:major/2, then we have to change {\em this} expression.
We don't need to change lists:map/3.

Before Erlang had closures, it had apply/3 and spawn/3.  They have
the form
    apply(Module, Name, ArgumentList)
    spawn(Module, Name, ArgumentList)
In general, the compiler and other tools haven't the faintest idea
what Module is, what Name is, or what the length of ArgumentList
might be, so there is a function reference which cannot be determined
here (like a call to a closure) and which is not captured anywhere else
either (unlike a closure).

{\bf These functions must go!}

We don't need apply/3 any more.  It may be useful to retain
\begin{tabbing}
MM\=\kill
\>apply({\it Closure}, $[A_1,\dots,A_n]$)\arw
{\it Closure\/}$(A_1,\dots,A_n)$
\end{tabbing}
and as Erlang distinguishes between values and functions of no
arguments, it may be useful to include
\begin{tabbing}
MM\=\kill
\>apply({\it Closure})\arw apply|({\it Closure}, []).
\end{tabbing}

In the same way, we could have
\begin{quote}
spawn({\it Closure}, $[A_1,\dots,A_n]$)\arw
the PID of a new process running {\it Closure\/}$(A_1,\dots,A_n)$.\\
spawn({\it Closure})\arw
the PID of a new process running {\it Closure\/}().
\end{quote}

There is a subtle difference between
\begin{quote}
spawn$(F, As)$
\end{quote}
and
\begin{quote}
spawn({\bf fun} ()\arw apply$(F, As)$ {\bf end})
\end{quote}
when $F$ is not a closure or $As$ is not a list of the right length;
the former will raise the error in the old process and the latter
will raise the error in the new process.  I do not like multiplying
interfaces, but this difference makes it seem like a good idea to
keep spawn/2 much though I'd like to get rid of it.

The existing apply/3 and spawn/3 interfaces are relics of the time
before closures; it was probably felt that keeping them was harmless.
Large Systems Erlang cannot tolerate these anachronisms any longer.

Now we may want to spawn a process on the current node or on another
Node; we may want to link to the new process or not; we may want to
bind the new PID to a PidName or not; we may have a list of additional
parameters or not.  That makes 16 variants of `spawn', which is too
many.
\begin{itemize}
\item[0.]  Pid = spawn({\it Closure\/})
\item[1.]  Pid = spawn({\it Closure, Args\/})
\item[2.]  Pid = spawn\_link({\it Closure\/})
\item[3.]  Pid = spawn\_link({\it Closure, Args\/})
\item[4.]  Pid = pid\_name\_spawn({\it PidName, Closure\/})
\item[5.]  Pid = pid\_name\_spawn({\it PidName, Closure, Args\/})
\item[6.]  Pid = pid\_name\_spawn\_link({\it PidName, Closure\/})
\item[7.]  Pid = pid\_name\_spawn\_link({\it PidName, Closure, Args\/})
\item[ ]
\item[8.]  Pid = spawn({\it Closure, Node\/})
\item[9.]  Pid = spawn({\it Closure, Args, Node\/})
\item[A.]  Pid = spawn\_link({\it Closure, Node\/})
\item[B.]  Pid = spawn\_link({\it Closure, Args, Node\/})
\item[C.]  Pid = pid\_name\_spawn({\it PidName, Closure, Node\/})
\item[D.]  Pid = pid\_name\_spawn({\it PidName, Closure, Args, Node\/})
\item[E.]  Pid = pid\_name\_spawn\_link({\it PidName, Closure, Node\/})
\item[F.]  Pid = pid\_name\_spawn\_link({\it PidName, Closure, Args, Node\/})
\end{itemize}

We can eliminate some of these:  the PidName versions bind a new PID
to a module-local "registry" on the current node, so starting up the
new process at another node doesn't make a lot of sense, so we can
drop the C-F variants.  We can eliminate the confusion between
1/8 and 3/A in one of two ways:  note that if the second argument
is a Node it cannot be a List, and drop 8 and A entirely.  In the
interests of type checking, let's tentatively take the second
alternative.  That leaves us with
\begin{itemize}
\item[0.]  Pid = spawn({\it Closure\/})
\item[1.]  Pid = spawn({\it Closure, Args\/})
\item[9.]  Pid = spawn({\it Closure, Args, Node\/})
\item[ ]
\item[2.]  Pid = spawn\_link({\it Closure\/})
\item[3.]  Pid = spawn\_link({\it Closure, Args\/})
\item[B.]  Pid = spawn\_link({\it Closure, Args, Node\/})
\item[ ]
\item[4.]  Pid = pid\_name\_spawn({\it PidName, Closure\/})
\item[5.]  Pid = pid\_name\_spawn({\it PidName, Closure, Args\/})
\item[ ]
\item[6.]  Pid = pid\_name\_spawn\_link({\it PidName, Closure\/})
\item[7.]  Pid = pid\_name\_spawn\_link({\it PidName, Closure, Args\/})
\end{itemize}

Another approach replaces all of these with a single function:
\begin{quote}
Pid = spawn({\it Closure, Args, SpawnOptionList\/})
\end{quote}
where a SpawnOption is one of
\begin{verbatim}
    link
    {node,Node}
    {pid_name,PidName}
\end{verbatim}

For the purposes of this report, it does not matter how the problem
of too many spawns is solved, as long as the mechanism involves
calling a closure.

\subsection{Not a New Problem}

The changes in section 2 were syntactically more complex, but
semantically less complex than this.  spawn/4 let you do something
rather interesting:  you could name and call a function on another
node.  This was done by sending the arguments (plain data) and the
{\em name} of the function.

The reason I say this is not a new problem is that Erlang 4 already
has the problem of sending a closure from one node to another.

\begin{verbatim}
    -module(hairy).
    -export([start/0, seagoon/1]).
    -export([private/0]).

    start() ->
        Fun = fun hairy:seagoon/1,
        PID = spawn(hairy, private, [], eris),
        PID ! {call,self(),Fun}.

    private() ->
        receive {call,Sender,Closure} -> Sender!Closure(27) end.

    seagoon(X) -> X.
\end{verbatim}

This starts a new process on the node 'eris', then sends it a closure
in a message.  The new process receives the closure, calls it, and
sends the result back.  How is this supposed to work?

The simplest way I can see around this problem is to exploit the
existing two forms of closure.  More precisely, to exploit the
fact that special closures do not contain any code of their own.
There is nothing to know about a special closure except the
function name it contains.  Indeed, we might go so far as to rule
that
\begin{tabbing}
MM\=\kill
\>{\bf fun} $m_1:f_1/n_1$ = {\bf fun} $m_2:f_2/n_2$
\end{tabbing}
if and only if $m_1:f_1/n_1$ and $m_2:f_2/n_2$ must name the same
function whatever the state of the system.

Given a suitable transport
protocol, there is no real difference between sending $\{m,f,n\}$ to another
node and sending {\bf fun} $m:f/n$ to another node.  In particular, there is
no possiblity of a special closure referring to any private functions or to
any variable bindings.

There is one obvious question:  what if the function named in a special
closure is not exported?  Within the scope of a single node, does it make
sense for
\begin{tabbing}
MM\=\kill
\>{\bf fun} f/2\\
and\\
\>{\bf fun} (X, Y)\arw f(X, Y) {\bf end}
\end{tabbing}
to behave differently?.  If we remember that module called $M$ on
node $X$ is not necessarily the same as the module called $M$ on node $Y$,
because $X$ and $Y$ might be running unrelated applications, or different
versions or releases of Erlang, then we realise that the fact that
$M:f/n$ is (or is not) exported on this node is no guarantee that it is
(or is not) exported on the other node.  That is, we can't {\em tell}
whether it will be legal or not until we try it.

In many ways, the simplest model of special closures is that they
{\em are} $\{m,f,n\}$ triples with special syntax and a special tag,
so that we can be sure of finding them.  Their semantics should be
essentially the same as the semantics of such triples, with the model
\begin{verbatim}
    apply({Mod,Fun,Arity}, Args) when Arity = length(Args) ->
        apply(Mod, Fun, Args).
\end{verbatim}
so that the question in the previous paragraph has the answer yes,
there is a difference in the behaviour of
\begin{tabbing}
MM\=\kill
\>{\bf fun} f/2\\
and\\
\>{\bf fun} (X, Y)\arw f(X, Y) {\bf end}
\end{tabbing}
The former represents a {\em dynamically bound} closure whose reference
is not determined until it is invoked, and thus must name an exported
function, while the latter represents a {\em statically bound} closure
whose reference is determined at compiled time, and whose body may thus
call any functions visible in the module, exported or not.

Accordingly,
\begin{itemize}
\item special closures may only refer to exported functions;
\item special closures may be spawned on other nodes,
\item special closures may be passed as arguments to processes
about to be spawned on other nodes,
\item special closures may be included in messages sent to
processes on other nodes,
\item but general closures may not.
\end{itemize}

It is entirely possible to relax this restriction, as KaliScheme has
shown.  There are ways that it can be eased without going quite that
far.

What makes this restriction to special closures a good resting place
in the design is that it exploits an {\em existing} distinction in the
language and restores the {\em existing} power to name functions on
other nodes.

So we might write
\begin{verbatim}
    -module(hairy).
    -export([start/0, seagoon/1]).
    -export([private/0]).

    start() ->
        spawn(fun hairy:private/0, [], [{node,eris}])
        ! {call,self(),fun hairy:seagoon/1}.

    private() ->
        receive {call,Sender,Closure} -> Sender!Closure(27) end.

    seagoon(X) -> X.
\end{verbatim}

\subsection{Section Summary}

I propose replacing apply/3 by apply(Closure[, Arguments])
and the spawn family by spawn(Closure, Arguments, Options),
and implementing special closures as pure data which can be
sent safely to other nodes.

\section{Static {\it vs} Dynamic Binding}

In Erlang 4, functions defined in the current module can be called
either statically (by omitting the module prefix) or dynamically
(by writing the module prefix), while functions from other modules
can only be called dynamically, whether a module prefix is present or not.

There are several reasons why a module might want to call one of its
own functions dynamically:
\begin{itemize}
\item because it wants the function to be `apply'ed.
This usage is obsolete now that we have closures.
\item because it wants to spawn a call to that function.
This usage is obsolete now that we have closures.
\item because it wants to switch over to a new version of the
module gracefully, if there is one.
This usage remains important.
\end{itemize}

An example of the graceful switchover usage might be
\begin{verbatim}
    -export_to(?MODULE, loop/2).

    loop(9, V9State) ->
	?MODULE:loop(9, do_it(V9State));
    loop(8, V8State) ->
	loop(9, convert_v8_state_to_v9(V8State)).
\end{verbatim}

The dynamic call here means that if the module is replaced by
a new version reading
\begin{verbatim}
    loop(10, V10State) ->
	?MODULE:loop(10, do_it(V10State));
    loop(9, V9State) ->
	loop(10, convert_v9_state_to_v10(V9State)).
\end{verbatim}
then the tail call will switch over to the new module, the second
clause of the new definition of loop/2 will convert the state to
the new format, and the loop will resume with a converted state.

\subsection{An Anomaly Could Be Removed}

There is a curious anomaly in Erlang 4.  If $f/n$ is an -imported
function (from some module $m$), then all calls to it are dynamically
bound whether they have a module prefix or not.  But if $f/n$ is
defined in the current module, then calls to it are dynamically bound
if they have a module prefix and statically bound if they lack one.

The language would be simpler if the rule ``has module prefix
\imp dynamic, lacks module prefix \imp static'' were valid.
That is one of the reasons that the Erlang style guide recommends
against -import.

We could eliminate this anomaly by ruling that {\em direct} calls to
local functions are always are always statically bound, calls to
-imported or -used functions are always dynamically bound, and
special closures are (as we have already seen they need to be)
dynamically bound.  The example above could be written
\begin{verbatim}
    -export_to(?MODULE, loop/2).

    loop(9, V9State) ->
	(fun loop/2)(9, do_it(V9State));
    loop(8, V8State) ->
	loop(9, convert_v8_state_to_v9(V8State)).
\end{verbatim}

This is admittedly clumsy.  My point in exhibiting it is to demonstrate
that when special closures were added to Erlang 4, the use of module
prefixes to force dynamic calls to local functions became an obsolete
anomaly.

We must preserve the distinction between static and dynamic calls
for functions and patterns defined in the current module, but we do
not need to preserve the notation for it.

There is a particularly important reason why this reading ``module
prefix \imp dynamic'' must go:  we need static calls to functions
and patterns defined in other modules.  We need static cross-module
calls in order to get rid of the preprocessor.  This means that we shall
need to use a module prefix in a call to name a function, without thereby
implying that the call is dynamic.

\subsection{Static Importing}

We can add two more directives.

\begin{quote}
-import\_static({\it Module, FunctorList\/})\\
-use\_static({\it Moduile, FunctorList\/})
\end{quote}

A module $X$ may make both static and dynamic calls to a module $Y$;
this is after all necessary for graceful switchover when $X=Y$, so we
might as well extend it to all modules.  There is therefore no restriction
on the number of times or ways in which a module $Y$ may be imported into
module $X$.  However, we noted that both -importing and -using the same
function was a problem.  It is a worse problem to import a function both
statically and dynamically.  The attempt to do so must be reportd as an
error.

The graph with modules as nodes and ``there is a dynamic mention of some
function or pattern in this module from some function or module in that
one'' is unrestricted.  Not only may it be cyclic, it may even contain
self-loops.

The point of including
\begin{quote}
-import\_static($Y$, [\#$p/n$]).
\end{quote}
in module $X$ is to allow the Erlang compiler to know what $\#Y:p/n$
does when compiling module $X$.  For that to be so, module $Y$ must
have been compiled and/or loaded before module $X$ is compiled and/or
loaded, and if a new version of module $Y$ is loaded, module $X$ must
be updated before it can safely be used.

This tells us that the graph with modules as nodes and ``there is
an -import\_static or -use\_static for this module in that one'' should
be acyclic.

The fact that the present preprocessor based system completely fails to
keep track of the dependencies between .erl files and the .hrl files they
include is not an advantage; that is precisely one of the troubles I want
to free Erlang of.  {\em Any} revision of Erlang I suggest is going to
require some mechanism for keeping track of module dependencies so that
a change to $Y$ will inform the system that $X$ is now out of date as well.

This is not a burden on programmers, because existing modules already
satisfy this requirement.  You find .erl files -including .hrl files;
you do not find those .hrl files -including the .erl files again.  The
file inclusion graph must be acyclic, and that file inclusion graph will
become the static import graph in Large Systems Erlang.

The information a compiler has to record in an object file for
(static) cross-module inlining to work is different from the information
a compiler has to record for normal (dynamic) cross-module calls.
For this practical reason, and because too much static binding goes
against the spirit of Erlang, I propose another directive:
\begin{verbatim}
    -static.
\end{verbatim}
which has the direct effect of telling the compiler to record whatever
additional information (compressed abstract parse trees, maybe) it needs,
and the indirect effect of permitting -import\_static and -use\_static
to refer to this module.  The compiler should enforce the rule that
\begin{verbatim}
    -import_static(M, ...).
    -use_static(M, ...).
\end{verbatim}
are legal only if module \verb|M| contains a -static directive.

I'm in two minds about -static.  It isn't really {\em needed}, we could
just require compilers to allow static linkage to any module and keep around
all the information that might be needed.  So sometimes I think it is
pointless.  Other times I think it is a brilliant idea, that touch of
``{\em controlled} use of redundancy'' which marks Software Engineering.

The net effect is that
\begin{itemize}
\item existing .hrl files will become proper modules, with the
-static directive.
\item existing -include directives will become -import\_static
directives or perhaps even -use\_static directives.
\item a compiler {\em may} inline cross-module
static calls, getting the same performance effect as -inclusion of
macro definitions
\item a compiler {\em need not} do so, treating cross-module calls
as full calls (but perhaps a little more efficient than dynamic
calls)
\end{itemize}

This should make it easy to switch over to the new scheme without
major work on the compiler, followed by compiler improvements later.

\subsection{Marking dynamic calls}

Now we have five ways that a function may be known inside a module:
\begin{verbatim}
    f(P1,...,Pn) -> ...
    -import_static(m, [f/n]).
    -import(m, [f/n]).
    -use_static(m, [f/n]).
    -use(m, [f/n]).
\end{verbatim}
All of these {\em may} be called with a module prefix, and the
-use and -use\_static cases {\em must} be.  The -use and -import
cases correspond imply dynamic calls and the others imply static
calls.  Note that a call to a function declared -use\_static must
have a module prefix but is nevertheless a static call, not a
dynamic one.

Therefore, we adopt the rule that whether a function call is static
or dynamic depends on its declaration:  -use and -import and
special closures imply dynamic calls, the others imply static calls.
The presence or absence of a module prefix should have {\em no}
effect.

That leaves us with the problem of notating dynamic calls to locally
declared functions (and of course to statically bound functions from
other modules).  I have already pointed out that we could use
special closures, as in
\begin{verbatim}
    (fun loop/2)(9, do_it(V9State))
    (fun ou_constants:pi/0)()
\end{verbatim}
and I'm tempted to leave well alone; the syntax may be clumsy, but it
is needed anyway.

If a shorter syntax is required, an extra leading colon will serve.
The syntax of a function call becomes
\begin{verbatim}
    <primary>(<arg list>)
|    [:][<atom>:]<atom>(<arg list>)
\end{verbatim}
as in
\begin{verbatim}
    :loop(9, do_it(V9State))
    :ou_constants:pi()
\end{verbatim}
A colon might seem easy enough to miss, but the rightwards jog of the
word is the visual effect that ensures it is noticed.

\subsection{Section summary}

The changes are
\begin{verbatim}
    -static.        This module may be statically bound.
    -import_static(Module, FunctorList).
    -use_static(Module, FunctorList)
    :<call>            indicates a dynamic call
    static/dyamic is otherwise determined by declaration.
\end{verbatim}

\section{Ain't Misbehavin'}

This proposal will require changes to pretty nearly every file in the
Erlang system, but the changes will be comparatively minor.

Except for one thing.

An important part of the way people design and think about Erlang
programs is ``behaviours''.  It's not entirely unfair to say that
behaviours are a kind of inheritance.  The behaviour module provides
a generic behaviour will callbacks for things that are ``subclass
responsibility''; the client module starts a process in the
behaviour module, telling it which module to call back to.

There are two interesting points here.

One is that currently the client module passes its own name to the
behaviour process, and that automatically provides it with access
to all the callbacks.  Of course the client module could pass
closures for all the callbacks, but there are usually several of
them, so we'd have to arbitrarily impose an order on them, and either
greatly increase the number of parameters passed, or package them up
in some kind of data structure, again an arbitrary choice.

The scheme presented so far in this report would make behaviours
much clumsier to write and to use.

The second interesting point is that while the client module
{\em defines} the callback functions, it is the behaviour module
which is {\em in charge of the interface}.  For these functions,
we know where the calls are, and want to change them, but have to
find all the definitions.  This is the reverse of the problem we
have considered so far.

\subsection{-behaviour}

There is already a directive
\begin{quote}
-behaviour({\it ModuleName}).
\end{quote}
which says that the current module uses the behaviour module
called {\it ModuleName}.

A Smalltalk programmer takes one look at this:
\begin{verbatim}
    -module(foo).
    -behaviour(bar).
    -export([start/0, ...]).
    start() -> bar:start(foo, ...).
\end{verbatim}
and says ``ah hah!  Foo is (like) a class; the processes started by
foo;start/0 are instances of that class; Foo is a subclass of Bar;
Foo's processes inherit behaviour (some of it private) from Bar.''

This viewpoint raises the interesting possibility that a behaviour
module (bar) might itself inherit behaviour from another behaviour
module (zoo, say).  It doesn't surprise a Smalltalk programmer to
find that this possiblity is actual, with \verb|gen_server|, for
example, inheriting from \verb|gen|, although \verb|gen_server.erl|
doesn't actually say \verb|-behaviour(gen)|.

There are many ways to implement inheritance.  The SmallEiffel compiler
from INRIA does it a particularly clever way, highlighting the importance
of static binding (when it is appropriate).  In Erlang terms, this would
suggest including a copy of the behaviour module, propagating the module
argument around, and turning the call-backs into direct calls (which could
then be inlined).  However, that would change the semantics.

The smallest workable change to Erlang leaves the interaction between
a behaviour module and its ``subclasses'' as the dynamic binding it is
now.  All we do is add another argument to -behaviour.

The revised directive is
\begin{quote}
-behaviour({\it ModuleName}, {\it FunctorList}).
\end{quote}

This directive, which I have proposed before, is a hybrid between
\verb|-behaviour| and \verb|-export_to|.  It makes the following
assertions:
\begin{itemize}
\item {\it ModuleName} will name a module
\item that module will be a behaviour module
\item that behaviour module is ``in charge'' of the interfaces
of all of the functions named in the {\it FunctorList}
\item the functions named in the {\it FunctorList} are {\em all}
of the call-backs required by the behaviour module
\item this module is exporting its versions of those function
to the behaviour module, and not to any other module (except as
stated in other directives)
\end{itemize}

For system integrity reasons, it is important not to export call-back
functions generally.  For an easy example of excess export, try
\begin{verbatim}
% erl
1> unregister(user), user:start().
\end{verbatim}

At run time there is almost no difference between \verb|-export_to|
and \verb|-behaviour|.  During maintenance, there is a huge difference.
The \verb|-export_to| directive says that this module is ``in charge of
the interface''; the \verb|-behaviour| directive says that the other
module is in charge of the interface.

\subsection{Don't call me, I'll call you}

A behaviour module uses its call-back functions, but the current language
not only doesn't require this relationship to be declared, it doesn't
allow it.  We need a new directive that is similar to -use.

The directive
\begin{quote}
-call\_back(FunctorList).
\end{quote}
makes the following assertions:
\begin{itemize}
\item This module is a behaviour module
\item The functions named in the {\it FunctorList} are all and only the
call-back functions required by this module
\item These functions may, and indeed must, be called with a module
prefix that is a simple variable
\item These functions may not be called without a module prefix or
with any other module prefix than a variable, except as otherwise
declared in the module.
\item no other -call\_back directive is allowed in this module.
\item if $f/n$ is a functor in the {\it FunctorList} and $M$ is a
variable, the call $M:f(e_1, \dots, e_n)$ should be allowed to
proceed if and only if
\begin{itemize}
\item the value of $M$ is an atom $m$
\item $m$ names a loaded module
\item the module named $m$ declared that it uses this behaviour module
\item and exported $f/n$ to this module.
\end{itemize}
\end{itemize}

Note that this cross-link checking implies {\em no} run-time overhead.
In fact, with the aid of these directives we can make such calls {\em more}
efficient than they presently are.  Alternatively, we could use the
existing machinery unchanged; these directives would merely ensure that we
were doing so consistently.

\subsection{Section Summary}

Put this together with other statements about calls, and we arrive
at the following formats for calls:
\begin{itemize}
\item $V(e_1, \dots e_n)$ where $V$ is a variable that at run time is
bound to a special or general closure
\item $f(e_1, \dots e_n)$ where $a/n$ is defined in the current module
\item $f(e_1, \dots e_n)$ where $a/n$ is -imported statically
\item $f(e_1, \dots e_n)$ where $a/n$ is -imported (dynamically)
\item $:f(e_1, \dots e_n)$ one of the above, forced to be dynamic
\item $M:f(e_1, \dots, e_n)$ where $M$ is a variable, this is a 
behaviour module, and $M=m$ where $m$ provides $f/n$ to this module
(dynamically)
\item $m:f(e_1, \dots, e_n)$ where $f/n$ is -used or -imported dynamically
\item $m:f(e_1, \dots, e_n)$ where $f/n$ is -used or -imported statically
\item $:m:f(e_1, \dots, e_n)$ one of the above, forced to be dynamic
\end{itemize}
and the format
\begin{itemize}
\item ({\bf fun} $m:f/n$)$(e_1, \dots, e_n)$
\end{itemize}
has been used in exposition.  There is enough of a discontinuity amongst
these forms that treating the prefixed forms as instances of a single
\begin{quote}
{\it expr}$(e_1, \dots, e_n)$
\end{quote}
form would confuse more than it clarified.

The revised -behaviour and new -call\_back directives act like inverse
-import and -export directives respectively.

\subsection{Planned Obsolesence}

The idea of marking interface elements as obsolesent is an old one.
My first encounter with them was when Burroughs decided that full support
for up-level pointers was too expensive, and changed their Algol compiler
to put a special mark in object files that might need the special run-time
support.  At compile-time they warned about the obsolesent feature.  A
later release of the system software deleted support for it.  Official
programming language standards have done the same kind of thing.

Two of the programming languages I know have a similar facility:  Eiffel
and Java.  It is a very useful device indeed.

There are two ways you can use a facility for marking interface
elements obsolete.  One is not very effective; the other is very useful.

When Java 1.1 came out, a number of features in the 1.0 interface were
declared obsolete.  This is the ineffective method.  People developing
Java software with JDK 1.1 compilers just had to put up with these
warnings, because they {\em had} to use the 1.0 interfaces in order to
write code that would work with the Java systems embedded in browsers.

The same thing is happening with Java 1.2.  At Otago, we have a nasty
problem:  shall we switch to Metrowerks 5?  If we do, we lose Pascal,
and we still have students coming through who were taught Pascal.  But
if we stick with Metrowerks 4, we'll have to stick with Java 1.6, while
the textbook we want to use is Java 2.0.  (Yes, the obvious solution is
to install MachTen and use gpc as the Pascal compiler.  Not a popular
choice here, for some reason.)

This is the ineffective case.  A lot of things were supposed to be
obsolete in Fortran, but refused to lie down and die.  By the time
{\em other} people are using an interface, it's very hard to persuade
them to change {\em their} code to go along with {\em your} idea of
what is an improvement.

This happened at Quintus.  When we changed from the 1.x releases to
2.0, interpreted code became much more compatible with compiled code,
quite a bit faster, and rather more efficient in its use of space.
But we had some unhappy customers, because this involved a chance to
the semantics of changes to running code, something they had been told
not to depend on.  I even showed one customer how he could make his
program run 700 times faster by {\em not} using the deprecated feature,
but that did not earn his gratitude.  What he {\em really} wanted was
not to have to change his code.

I don't think an -obsolete directive can really do much for changes
to published interfaces that adequate documentation won't do:  it merely
alerts customers that they need to lobby for their pet monster's life.

But an -obsolete directive can do something very useful {\em within}
a project.  Ideally, if you are thinking of changing an interface,
you just mark it -obsolete, refresh the system, and see what complaints
you get.

For discussion, I propose
\begin{quote}
-obsolete[({\it Version})].
\end{quote}

This says that the immediately following function definition is
obsolete now (no {\it Version}) or as of version {\it Version}.

The Eiffel equivalent includes a string to be displayed, and the
Java @deprecated comment is also associated with text.  The idea
there is that the text tells a client what to use instead.  That
is useful, but how elaborate do you want to get, and how much
text do you want to store at run time?  I think it's enough to
save the location of the directive, and then a convention can be
set up for where to put the helpful transition comment.

For the purpose of making refactoring more reliable, you don't
need such a comment anyway.  You know what change you have in mind;
the -obsolete directive is simply there to help you find where to
make the change.

\section{Report summary}

Relevant directives:
\begin{verbatim}
-import(Module, FunctorList). % unchanged
-import_static(Module, FunctorList).
-use(Module, FunctorList).
-use_static(Module, FunctorList).
-export(FunctorList). % unchanged
-export_to(Module, FunctorList).
-behaviour(Module, FunctorList). % changed
-call_back(FunctorList).
-obsolete[(Version)].
\end{verbatim}

Legal forms of function call:
\begin{itemize}
\item $V(e_1, \dots e_n)$ where $V$ is a variable that at run time is
bound to a special or general closure
\item $f(e_1, \dots e_n)$ where $a/n$ is defined in the current module
\item $f(e_1, \dots e_n)$ where $a/n$ is -imported statically
\item $f(e_1, \dots e_n)$ where $a/n$ is -imported (dynamically)
\item $:f(e_1, \dots e_n)$ one of the above, forced to be dynamic
\item $M:f(e_1, \dots, e_n)$ where $M$ is a variable, this is a 
behaviour module, and $M=m$ where $m$ provides $f/n$ to this module
(dynamically)
\item $m:f(e_1, \dots, e_n)$ where $f/n$ is -used or -imported dynamically
\item $m:f(e_1, \dots, e_n)$ where $f/n$ is -used or -imported statically
\item $:m:f(e_1, \dots, e_n)$ one of the above, forced to be dynamic
\end{itemize}

\section{The attachments}

There are three plain text files:
\begin{itemize}
\item{io\_msgs.erl} defines message formats.  It is a good style rule that
all message sends and all {\bf receive}s should use named patterns rather
than literal patterns, and that these patterns should be defined in
-static modules with plenty of comments to say what they mean.  This is
very much a first draft for the io modules.
\item{io.erl} is the io module.  All I really wanted to do was to exhibit
the necessary changes to user.erl.  One of the hard parts in cleaning up
user.erl was deciding how to handle the
\begin{quote}
\{put\_chars,{\it Module, Name, Arguments}\}
\end{quote}
message, and the cleanest method turned out to be to eliminate it completely.
That required compensating changes in io.erl, so here it is.
\item{user.erl} is all I originally wanted to exhibit.  It is the module
that watches the standard I/O streams (file descriptors 0 and 1).
An unrelated change is that I have removed one use of the process dictionary;
there is one remaining use of the process dictionary I would like to get rid
of as well, but that's straightforward.
\end{itemize}

I claim that
\begin{itemize}
\item the revised code better supports finding function/pattern uses
\item it wasn't all that hard for me to make all these changes,
and someone familiar with the code would find it ever so simple
\item the revised code is easier for people to understand.
\end{itemize}

\section*{The End}
\end{document}

