\newcommand{\Dots}{\mbox{\(\cdots\)}}
\section{Motivation}
Whatever the data structures  built into a programming system,
applications soon turn up new kinds of data that match poorly to any of
the supplied primitives.
For example, primitive objects in S \cite{S} are essentially vectors
of a few prescribed modes (numeric, logical, complex and character string),
lists containing other objects as elements, and objects that represent
expressions in the language.
Even as simple a data structure as the {\em category} fits uncomfortably
into this scheme.
Conceptually, categories represent repeated values, each of which comes from
a finite set of levels; e.g., \Co{"Male"} and \Co{"Female"}, or
\Co{"Low"}, \Co{"Medium"}, and \Co{"High"}.
While the values could be represented as character strings, it is essential
that there is some known set of possible levels, so representing the
category as a character vector would be misleading.
The common statistical approach is to code the values as integers, but
even if the levels are retained as an attribute, this is dangerous also,
since most numeric operations are meaningless when applied to coded categories.
Notice also that sometimes, as in the second example, we would like to
include the notion that the levels are {\em ordered}, but not explicitly
numeric, while continuing to inherit the other properties of categories.

The challenge is to incorporate classes of objects such as this
into the user's view of the language in a seamless way, so that common
functions like printing, plotting and subsetting, behave ``correctly''
without the user worrying.
At the same time, one wants the job of the application programmer
to be made as simple as possible when designing new classes of objects
and providing software to use them.
Object-oriented programming systems (e.g., Clos \cite{Clos} or C++ \cite{CPP}) do this by allowing programmers to define {\em methods}; roughly,
definitions of generic functions that will be used when the argument
to the function belongs to a particular class of objects.
We present here a method mechanism to be used in S.
The mechanism can be used in designing new classes of objects; applications
have included basic classes like the categories,
objects that represent statistical models or analyses,
and objects arising in the interface between S and other programming
systems.
The mechanism resembles that used in object-oriented programming systems,
but other programming paradigms influencing S
cause some interesting variations in the approach.

\section{Background}\label{Introduction}
The S language \cite{S} follows, in an informal way,
three main programming
paradigms:
\begin{enumerate}
\item
Object-oriented programming;
\item
Functional languages;
\item
Interfaces.
\end{enumerate}
Object-oriented programming replaces the idea of executing a
program, in the traditional sense of a single set of
machine instructions, with actions that take place as the result of passing
{\em messages} between objects.
The messages can be thought  of as  requests to the object; for example,
that the object print itself.
The action occurring in response to the message typically depends
on the {\em class} to which an object belongs.
The definition of the class determines for which messages the object
has a {\em method}; that is, a definition in some programming language
of what should happen in response  to the message.
S shares an emphasis on general objects, and allows users to define
classes of objects (\cite{S}, chapter 8).
Classes as discussed there are informal.
A convention on the essential data structure for the class (in terms of what
components or attributes are expected) is shared among a collection of functions
written to create and use objects from the class.

While this informal approach is adequate for many applications, it has some
disadvantages.
The user must be somewhat conscious of the class structure, in order to
call the specific functions for that class.
For example, to print a summary of an object of class \Co{"lsfit"} one calls
a special summary function for that class, \Co{ls.summary()}.
For a different class, there would be a different function.

Instead, suppose there were a single
generic function, \Co{summary} equipped to:
\begin{enumerate}
\item
recognize the class, if any, of its argument;
\item
to use a special \Co{summary} method for that class, if one exists.
\end{enumerate}
Then the user need only remember how the generic function is called.
The results of applying the function to different classes of objects
should come out right automatically, provided the design of the classes
was sensibly done.

A mechanism incorporating these ideas will be included in the next
version of S.
Some of the features are:
\begin{itemize}
\item
Users of generic functions can expect the functions to adapt to new
classes of objects without any action on the users part.
\item
Designers of new classes of objects can redefine generic functions
by writing a {\em method}: a new function with the same arguments as
the generic function.
\item
Classes and methods can use a general form of {\em inheritance};
that is, one class of objects can inherit methods from one or more other classes.
The designer of a new class only needs to supply methods that
need to be different from those inherited.
\item
Methods can invoke inherited methods in a simple, general way,
simplifying the modification of methods to new classes.
\item
Groups of generic S functions (e.g., operators like arithmetic) 
often map into an interface to one C routine.
If all these functions adapt in essentially the same way to a
new class of objects, a single group method can be written for
all of them.
\item
Methods for operators are invoked when either or both of the operands
unambiguously identify a method.
\item
Methods can be written for
some key operations in the language that are not precisely functions (e.g.,
replacement and permanent assignment).
\item
Methods in S are functions that can be called explicitly.
In particular, a user can override the standard method for an object
and force it to be treated as an object from another class.
\end{itemize}

The use of methods allows programming in S to have much more
of the style of object-oriented programming systems.
However, methods in S differ from such systems in some interesting ways, partly from the influence of the other two paradigms.
The last feature above is an example.
Because all functions in S are objects and because function calls are the
central, essentially the only, activity in an S session, methods are not
restricted to automatic invocation, but can be used like any other function.

\section{The Mechanism}\label{basics}

Two conventions define the mechanism for methods in S.
First, the class of an object can be extracted or set by the function
\Co{class()}:
\begin{Example}
> class(myobject) <- "category"
> class(myobject)
 [1] "category"
\end{Example}
For the moment we think of the class as either a single character string
or \Co{NULL};
this will be extended when we talk about classes that inherit
methods from other classes.

Second, when a generic function is invoked, its default action will be
replaced by a method function whose name is defined by
pasting together the name of the generic function, \Co{"."},
and the name of the class.
If an object of this name exists, the body of the generic function will
be implicitly replaced by the body of the method.
For example, if function
\Co{print()} has been called with an object
of class \Co{"category"} as its argument, a function named
\Co{print.category} will be used as the method.

The function/class/method mechanism in S is uniform and  general,
but not obligatory.
Functions that look for methods are called {\em generic}, in the sense
that they only define generically what their effect should be, leaving
further specifications to be done by methods.
Generic functions are usually easy to identify.
The body of a generic function will be either a call to \Co{UseMethod()},
\begin{Example}
    print <- function(x, digits, quote = T)
        UseMethod()
\end{Example}
or will be a call to the \Co{.Internal()} interface,
\begin{Example}
    exp <- function(x)
        .Internal(exp(x),"do_math",T,108)
\end{Example}
Section \ref{generic} lists those internal functions that take methods.

All objects implicitly inherit from class \Co{default}.
Corresponding to generic functions like \Co{print()} will be a
default method, \Co{print.default()}.
Objects without a specific class or with a class inheriting no
other print method will be printed using \Co{print.default()}.
For generic functions invoking methods via the \Co{.Internal}
interface, the default method is also contained in the internal
code.
There is no \Co{exp.default()} method.


\section{An Example of Designing Methods}\label{Examples}

To make the discussion more concrete, we consider a class of objects
to implement categories with corresponding
methods.
S has had categories for some time; for example \cite{S}, p. 136.
The implementation of categories described there did not use methods, since those
did not exist.
Now we can re-design the class
\Co{"category"},
writing some appropriate
methods so categories behave sensibly when
used with common generic functions.
We choose a data structure in which the object has an attribute,
\Co{levels}, that represents the set of levels.
The object itself then consists of a vector of integer values
between 1 and \Co{length(levels(x))}.
We also allow elements of the object to be missing (that is, having
value \Co{NA}).
Not surprisingly, we are following the implementation
in \cite{S} in these choices.

Before designing methods, we should be able to generate
objects from the class.
The function \Co{category()} will do this:
\begin{Example}
category <- function(x, levels = sort(unique(x)),
  labels = as.character(levels)) \{
    y <- match(x, levels)
    names(y) <- names(x)
    levels(y) <- labels
    class(y) <- "category"
    y
\}
\end{Example}
For our first method, let's arrange to print the object.
The method will be a function object named \Co{print.category}.
The recommended way to create such
a method is to copy the generic function
to get the arguments, and then to replace the body of the generic
function with the appropriate definition for the method.

What {\em should} a printing method for categories do?
We want users to think of the data as values from the \Co{levels} set,
and a natural way to do that is to print the vector computed as
\begin{Example}
    levels(x)[x]
\end{Example}
This is usually a character vector, but to emphasize the levels,
we will print it without quotes,  using the
\Co{quote=F}
argument to \Co{print()}.
One more detail:
We allow \Co{NA} in the data, so before printing we should turn any \Co{NA}'s
into an additional level.
Adding some code to achieve this, we get our method:
\begin{Example}\label{print.category}
print.category <- function(x, digits, quote=T) \{
    class(x) <- NULL
    l <- levels(x)
    if(any(is.na(x))) \{
        l <- c(l, "NA")
        x[is.na(x)] <- length(l)
    \}
    x <- l[x]
    print(x, quote = F)
    invisible(x)
\}
\end{Example}
The class of the object was set to \Co{NULL} at the beginning of the
method, to avoid tripping over other possible methods when we
manipulate \Co{x} in  the body of the method.
As will become apparent, methods fall largely into two types:
those that understand something about the internal structure
of the objects, like this method, and those that expect most
of the work to be done by an inherited method, with just a little
pre- or post-processing.

We'll improve \Co{print.category()} a little in later discussion, but the above is
quite respectable.
As an example of its use,
\begin{Example}
> sex <- category( sample(c("Male","Female"), 25, T))
> sex
 [1] Male   Female Female Male   Female Female Female
 [8] Male   Male   Female Male   Male   Male   Male  
[15] Male   Female Male   Male   Male   Male   Male  
[22] Male   Male   Female Male  
\end{Example}
Later sections will show methods for other generic functions,
after we look at a
new class, ordered categories, as an example of inheritance.

\section{Inheritance}
A powerful tool in object-oriented programming is the ability of
objects to inherit methods from one or more other classes.
This greatly simplifies defining new classes that are generalizations
of existing classes.
Only methods related to the new features need be written.
S allows objects to inherit from other classes, if the class of the
object itself contains an attribute \Co{inheritance}.
Specifically,
\begin{Example}
attr(class(x),"inheritance")
\end{Example}
will either be
\Co{NULL}  or a character vector naming all the classes from which
\Co{x} inherits.
All classes implicitly inherit from the class
\Co{default}.

As an example, let's define a new class \Co{ordered} that is
just like \Co{category}, except that the levels
are now assumed to be ordered increasingly as given.
A function to generate objects from this class could be as follows:
\begin{Example}
ordered <- function(x, levels = sort(unique(x)),
   labels = as.character(levels))\{
    if(!missing(levels) && is.numeric(levels))
        levels <- sort(levels)
    y <- match(x, levels)
    names(y) <- names(x)
    levels(y) <- labels
    class(y) <- structure("ordered", inheritance = "category")
    y
\}
\end{Example}
The class of the object is set to a character string,
\Co{"ordered"},
with an attribute, \Co{inheritance},
which in general is a character vector defining all the other
classes from which the object should inherit.
The search for methods proceeds by looking at the current class
and then, in order, at the inheritance classes.

As an example, consider a character vector,
say \Co{rating.text}, containing
character strings \Co{"Low"}, \Co{"Medium"}, and \Co{"High"},
which we will convert to an ordered category.
\begin{Example}
> rating.text
 [1] "Medium" "High"   "Low"    "High"   "Medium" "Medium"
 [7] "High"   "Low"    "Low"    "High"   "Medium" "High"  
[13] "High"   "High"   "Medium" "Low"    "High"   "Low"   
[19] "High"   "Low"   
> ratings <- ordered(rating.text, levels =
+   c("Low","Medium","High"))'
> ratings
 [1] Medium High   Low    High   Medium Medium High  
 [8] Low    Low    High   Medium High   High   High  
[15] Medium Low    High   Low    High   Low   
\end{Example}
The \Co{levels} argument is needed in the call to \Co{ordered()}
to establish the correct ordering.
Because of inheritance, \Co{print(ratings)}
uses the method \Co{print.category()} if the method
\Co{print.ordered()} is not found.


A key tool in writing methods that exploit inheritance is the function
\Co{NextMethod()}.
The call
\begin{Example}
NextMethod()
\end{Example}
looks for an inherited method for the current generic function; that is, a method
corresponding to this function and one of the
classes from which the current class inherits.
It evaluates that method and returns its value as the value of
\Co{NextMethod()}.
All classes implicitly inherit from the class \Co{default}, so that
\Co{NextMethod()} invokes the default method if no other inherited
method is found.

Suppose
we decided to show the ordering of the levels after printing
the data for our new class.
The method arranges for most of the work to be done by the
inherited method, and then adds a line at the end to show the levels.
\begin{Example}
print.ordered<- function(x, digits, quote) \{
    NextMethod()
    cat("\(\backslash\)n", paste(levels(x),collapse=" < "), "\(\backslash\)n")
    invisible(x)
\}
\end{Example}
Our previous example now prints as follows:
\begin{Example}
> ratings
 [1] Medium High   Low    High   Medium Medium High  
 [8] Low    Low    High   Medium High   High   High  
[15] Medium Low    High   Low    High   Low   

 Low < Medium < High 
\end{Example}


As mentioned,
\Co{NextMethod()}  is useful even in cases not involving inheritance,
as a way of invoking the default method for the generic function.
For example, suppose we want to write a method for extracting subsets from
\Co{category} objects, because we want to ensure that the extracted
object continues to belong to class \Co{category}.
The generic function named \Co{"["} extracts subsets.
Its definition is:
\begin{Example}
"[" <- function(x, ..., drop = T)
  .Internal(x[...,drop], "S_extract", T, 1)
\end{Example}
If we apply this to a category,
\begin{Example}
> sex[1:5]
[1] 2 1 1 2 1
attr(, "levels"):
[1] "Female" "Male"  
\end{Example}
the class disappears.  Clearly we need a method,
\Co{"[.category()"}.
We proceed again by copying the
argument list from the generic function and writing a new body:
\begin{Example}\label{extr.category}
"[.category" <- function(x, ..., drop = T)\{
    y <- NextMethod()
    class(y) <- class(x)
    y
\}
\end{Example}
Now subsets of categories retain their class nature.
\begin{Example}
> sex[1:5]
[1] Male   Female Female Male   Female
\end{Example}

The style of \Co{"[.category()"} is a common way of writing methods:
do computations ignoring the current class, and then set
some attributes of the result (here just the class), before returning it.
The use of \Co{NextMethod()} is crucial.
Recursive use of the generic function directly can cause an infinite loop --
the object in question is still a category, so the generic function will invoke
the method once again, and so on, until S
complains when the maximum level of nesting of expressions is reached.
When applying \Co{NextMethod()}  isn't enough, the method may need to
do some computations using its knowledge of how the objects are
organized.  In this case, you should set the class of the object to
\Co{NULL}, as we did in \Co{print.category()},
to prevent accidental  infinite loops.
Another possible implementation of \Co{"[.category()"} would be:
\begin{Example}
"[.category" <- function(x, ..., drop = T)\{
    oldclass <- class(x)
    class(x) <- NULL
    y <- x[...]
    class(y) <- oldclass
    y
\}
\end{Example}
The object determining the choice of method
is not modified when the methods are invoked, either directly or
through inheritance.
This and inheritance imply that the class of the object
being handled in a method may be different from the specific class
for which the method was written.
The designer of methods must keep this in mind.
This is why we saved and restored the class of \Co{x} in the above,
rather than just setting the class to \Co{"category"}.

A related point applies to the designer of classes.
Asserting that one class inherits from another asserts that an inherited
method will work; for example,
the objects of class \Co{ordered} must have all the
information used to print objects of class \Co{category} if the \Co{NextMethod()}
call is to work in the definition of \Co{print.ordered()}.
So while S does not enforce any rules about which classes can inherit
from which other classes, the designer needs to ensure that inheriting
classes really do make sense when viewed by the inherited methods
as objects of another class.

\section{The Frames for Methods}\label{semantics}
When a generic function invokes a method, either by a call to
\Co{UseMethod()} or through a \Co{.Internal()} interface,
the method behaves as if it were called with the same arguments as
the generic function had.
When an inherited method is invoked
by a call to \Co{NextMethod()},
it behaves as if called from the previous method, with that method's
arguments.
When writing methods, the following details may be relevant:
\begin{itemize}
\item
actual arguments to the generic function are passed down
through \Co{NextMethod()}
with their current values at the time \Co{NextMethod()} is called.
\item
arguments that are missing in the call to the generic function will be missing
in the methods also;
\item 
lazy evaluation continues in effect; unevaluated arguments
stay unevaluated;
\end{itemize}
The writer of a method can fine-tune the inheritance by modifying
arguments before invoking \Co{NextMethod()}.
As an example, notice that \Co{print.category()} on page \pageref{print.category}
reinvoked the generic
function, with a different value for the \Co{quote} argument.
Alternatively, the call to \Co{print()} could be replaced by the two
lines
\begin{Example}
    if(missing(quote))quote <- F
    NextMethod()
\end{Example}
This is slightly more efficient, but more importantly,
it preserves the user's right to override the default quoting, simply
reversing the default setting.

The method  mechanism adds to the evaluation frame
a complete picture of the current situation, in four special objects:
\begin{description}
\item[\Co{.Class}] 
The class attribute corresponding to the current method (including
the inheritance attribute).
Each time \Co{NextMethod()} is used, the current \Co{.Class} is
added to the inheriting  \Co{.Class} as an attribute \Co{previous}.
See the examples below.
\item[\Co{.Generic}] 
The name of the generic function.
\item[\Co{.Method}\label{.Method}] 
The name of the method being used, as a character vector.
This object has a special form when methods are defined for
operators: see the discussion in
section \ref{groups} below.
\item[\Co{.Group}] 
The name of the group, in the case that the interface to methods
comes through one of the internal interfaces in table \ref{group.funs}
on page  \pageref{group.funs}.
\end{description}
These objects are maintained and used by the dispatcher mechanism
in the S evaluator, but of course they can be used also in writing
methods.
As an example, suppose we put a call to the browser in the \Co{print.category()}
method and use it to look at the special objects:
\begin{Example}
> print(sex)
Browser: print(sex) 
Selection: ?
1: .Class
2: .Method
3: .Generic
4: .Group
5: x
Selection: .Class
[1] "category"
Selection: .Method
[1] "print.category"
Selection: .Generic
[1] "print"
Selection: .Group
[1] ""
\end{Example}
Similarly, suppose that there were a browser call in \Co{print.ordered()}
when we printed \Co{ratings}.
The \Co{.Class} and \Co{.Method} objects in this case would be:
\begin{Example}
Selection: .Class
[1] "ordered"
attr(, "inheritance"):
[1] "category"
Selection: .Method
[1] "print.ordered"
\end{Example}
The \Co{print.category()} method would then be invoked by \Co{NextMethod()},
and this time the \Co{.Class} object would look as follows:
\begin{Example}
Selection: .Class
[1] "category"
attr(, "previous"):
[1] "ordered"
attr(attr(, "previous"), "inheritance"):
[1] "category"
\end{Example}
Puzzling out this slightly involved output will show that the  class
is \Co{"category"} as before, but now with an attribute \Co{"previous"},
containing the same object that was in \Co{.Class} in the previous
method.
This extra information in \Co{.Class} can usually be ignored, but it does
provide a mechanism for working back through the entire network of methods
involved in the current computation.

\section{Group Methods; Methods for Operators}\label{groups}
Internal interfaces invoke a particular C routine.
Usually one routine handles a number of related S functions; for example,
there is one internal interface for all the usual operators (arithmetic,
comparison, logical), either in binary or unary form,
and one for all the ``mathematical'' functions that transform
objects element-by-element,
including functions like \Co{log()}, \Co{sin()}, and also
less obviously mathematical functions like \Co{round()}.
Table \ref{group.funs} shows the functions in this group and in
various other groups of functions.
\begin{table}[hbt]
\centering
\begin{tabular}{|p{7em}|p{3in}|}
\hline
\multicolumn{1}{|c|}{\it Group} & \multicolumn{1}{c|}{\it Functions} \\
\hline
{\tt Math} & {\tt atan(x,~y);
cumsum(x);
abs(x);
acos(x);
acosh(x);
asin(x);
asinh(x);
atanh(x);
ceiling(x);
cos(x);
cosh(x);
exp(x);
floor(x);
log(x);
log10(x);
round(x,~digits);
signif(x,~digits);
sin(x);
sinh(x);
tan(x);
tanh(x);
trunc(x)} \\
\hline
{\tt Summary} & {\tt all(x);
any(x);
max(x);
min(x);
prod(x);
range(x);
sum(x)} \\
\hline
{\tt Ops} & {\tt e1\,+\,e2;
e1\,-\,e2;
e1\,*\,e2;
e1\,/\,e2;
e1\,\Hat\,e2;
e1\,<\,e2;
e1\,>\,e2;
e1\,<=\,e2;
e1\,>=\,e2;
e1\,!=\,e2;
e1\,==\,e2;
e1\,\%\%\,e2;
e1\,\%/\%\,e2;
e1\,\&\,e2;
e1\,|\,e2;
-e1;
!x} \\
\hline
\end{tabular}
\caption{The groups of functions for which methods can be written}\label{group.funs}
\end{table}
Methods often will be identical, or nearly so, for all the functions in
a group.
One can take advantage of this by writing one
{\em group} method,
rather than a separate method for each function in the group.
All the
functions in the group will obey the method for objects from the new class,
with only one piece of code to be written, saving
substantially on work and clutter when implementing a method
for all the 24 functions in the \Co{Math} group, for example.
The catch, of course, is that the new method must work correctly for
all the functions in the group.
The \Co{NextMethod()} function and the \Co{.Generic}
object object are the key tools in writing such methods.

Group methods are functions whose name consists of the {\em group}
name, not the name of the individual function, followed by \Co{"."},
followed by the name of the class.
The function \Co{Math.category()}, then, provides the method for
all the functions in the \Co{Math} group applied to categories.
Since we want to discourage the user from thinking of the
levels as numbers, the definition of this method is simple:
\begin{Example}
Math.category <- function(x,...)
	stop("A category is not a numeric object")
\end{Example}
Trivial?  Yes, but it prevents returning a meaningless (indeed, wrong)
answer that would have resulted if the generic definition had been used.

It is possible to have methods for individual functions included
in the group as well.  The individual method is always
chosen in preference to the group method.
Group methods that can treat all the included generic functions the same
way are the most convenient, but the method is free to do something
special depending on the particular function.
The value of the special object \Co{".Generic"} gives the name of the
generic function.
This could be an argument to the \Co{switch()} function to enumerate
special cases.


The same style used for the \Co{Math} group will usually work for
the \Co{Summary} group of functions.
In this case the result will not be an object of the same class
as the argument,
but rather a suitable summary object.
The \Co{Ops} group is frequently the most interesting.
This includes all the arithmetic, comparison and logical operators.
One is fairly likely to want a method for this group, so that operators
will work when the operands are
one object from a special class and one plain vector, or when
the two operands are compatible objects from the same special class.

Notice that S already supplies methods, implicitly, for
arrays and time-series.
A matrix and a vector can be operands to an operator, with the result
being a matrix.
Two matrices can be operands if their dimensions match.
Similar but more liberal definitions apply to time series (\cite{S}, page 296).
New classes of objects ought to have similar methods where they make sense.

An interesting feature here is that the traditional object-oriented view
is rather clumsy, because the {\em two} operands ought to be treated
equally in deciding what should happen.
Taken literally this suggests having to define a new class
of objects for each {\em pair}  of original classes.
Then a method would be defined for the various operator ``messages''
for each class pair, either explicitly or by inheritance.
Implementing such a scheme, however, would be very clumsy and in practice
a symmetric, pure  approach seems never to be taken.
The focus in S on the function as the primary arbiter of what method
to be used seems in this situation to be natural.

For the \Co{Ops} group of functions in Table \ref{group.funs},
the internal interface invokes a special method if the two operands, taken together
suggest a single method; specifically,
if one operand corresponds to a method that dominates that of the
other operand, or if they both correspond to the same method.
Otherwise, the default definition of the operator is used.
Either a group definition or an individual definition of a method
dominates if the other operand has no corresponding method,
and an individual definition dominates a group definition.

With the category class of objects, if a group method, \Co{Ops.category()}
has been defined (we will define one below), than any operation involving
two categories will be handed over to this method.
So will any operation in which either the left or the right operand is a category,
and the other operand either has no class attribute or else is a class for
which no special method is defined.
Notice that the special method is responsible for doing some further analysis
to determine which operand is the category and to check that two category
operands are compatible.
\begin{Example}
Ops.category <- function(e1, e2) \{
    if(nchar(.Method[1])) \{
        l1 <- levels(e1)
        e1 <- l1[e1]
    \}
    else l1 <- NULL
    if(nchar(.Method[2])) \{
        l2 <- levels(e2)
        if(length(l1)!=length(l2) || !all(sort(l2) == sort(l1)))
            stop("Operation on incompatible categories")
        e2 <- l2[e2]
    \}
    NextMethod()
\}
\end{Example}
This method, typically for operator group methods, proceeds to construct
suitable objects corresponding to the operand(s) belonging
to the class.
The \Co{.Method} object mentioned on page \pageref{.Method} has all the necessary
information.
The first and second elements of \Co{.Method} will be empty strings unless
the corresponding operand inherited from \Co{"category"}.
Notice that once we determine that both operands inherited, we implement a
check that the two objects are compatible, in the sense that they use
the same level set.
The particular test there ignores, as it should, the order of appearance of the
levels in the level set.

What the method does is to replace each category object by the corresponding
character vector, ensuring that operations work on the levels, not on the numbers
used to encode them.
For example,
\begin{Example}
> ratings=="Low"
 [1] F F T F F F F T T F F F F F F T F T F T
> ratings - 1
Error in call to "-": Non-numeric first operand
Dumped
\end{Example}
Without the special methods, the first example would have failed,
and the second would have produced a misleading answer.

\section{Replacement Methods; use of \protect{\Co{"..."}}}\label{Replacement}

Subscript expressions using square brackets often appear on the
left side of assignments, as replacements.
These too are good candidates for special methods.
S already provides a mechanism by which users can write their own
replacement functions (\cite{S}, page 217).
Replacements of the form
\begin{Example}
f(x) <- value
\end{Example}
are evaluated by S as the expression
\begin{Example}
x <- "f<-"(x, value)
\end{Example}
so that the user need only define the function \Co{"f<-"()}.
This mechanism combined with our mechanism for methods allows
methods to be generated for replacement operations.
One special case arises, however\label{replace}, in that S does not actually
call a function for replacements using the \Co{Extract/Replace}
internal interface:
\begin{Example}
[\,] [[\,]] $ dim dimnames levels tsp
\end{Example}
Substantial efficiency advantages come from doing the replacement
directly in the internal code.
Nevertheless, methods can be written for such replacement functions,
just as if a replacement function were being called.

Writing methods for either extraction or replacement, corresponding
to the generic function \Co{"["()} for example, introduces
the handling of arbitrary numbers of arguments.
The generic definition of \Co{"["()} is, as we saw before:
\begin{Example}
function(x, ..., drop = T)
.Internal(x[..., drop], "S_extract", T, 1)
\end{Example}
So methods for this function will have the same arguments.
When we wrote an extraction method for categories on page \pageref{extr.category}, we finessed handling the \Co{...} by using \Co{NextMethod()}.
Otherwise, there are two main mechanisms available:
\begin{itemize}
\item
A list of all the arguments corresponding to \Co{...}, evaluated,
is the result  of the expression \Co{list(...)};
\item
The special names \Co{..1}, \Co{..2}, etc. are interpreted to refer
to fictitious formal arguments corresponding to the first, second, etc.
arguments matching \Co{...}
\end{itemize}
It is worth mentioning briefly why such mechanisms are needed.
The \Co{...} construction is useful, but it is distinctly a
semantic blemish on the language.  Alone among the constructs in the
language, it cannot be said to correspond itself to an object.
Its effect is that of textual substitution as would be done in a
macro-style language.
From this compromise, though probably a  justified one, many difficulties
of implementation arise.

To show a nontrivial example of replacement methods, let's consider
a new class of objects, {\em data frames}.
These are objects that act like matrices, but that allow ``columns''
to be themselves numeric vectors, numeric matrices or categories (possibly
ordered).
They are implemented as  lists, whose elements form the columns of 
the data frames.
The attribute \Co{row.names} is always included to specify the rows of
the fictional matrix.
The class of the objects is \Co{data.frame}.

We can write a replacement method
for data frames, by defining a function \Co{"[<-.data.frame"()}.
The goal is to replace data as if the object were a matrix:
\begin{Example}
mydata[6, 1:2] <- NA
\end{Example}
sets the first two variables of the 6th observation to \Co{NA}.
The definition of the method is as follows:
\begin{Example}
"[<-.data.frame"<-
function(x, ..., value)
\{
    cl <- class(x)
    class(x) <- NULL
    rows <- attr(x, "row.names")
    has.2 <- !missing(..2)
    if(has.1 <- !missing(..1))
        iseq <- seq(along = rows)[..1]
    else \{
        nrows <- length(rows)
        if(length(value) < nrows)
            value <- value[rep(1:length(value), length = nrows)]
        if(has.2)
            x[..2] <- list(value)
        else x[] <- list(value)
        class(x) <- cl
        return(x)
    \}
    if(has.2) jseq <- seq(along = x)[..2]
    else jseq <- seq(along = x)
    n <- length(iseq)
    p <- length(jseq)
    m <- length(value)
    if(length(value) < p)
        value <- value[rep(1:m, length = p)]
    for(j in 1:p) \{
        jj <- jseq[j]
        x[[jj]][iseq] <- value[[j]]
    \}
    class(x) <- cl
    x
\}
\end{Example}
Clearly, this is a more serious bit of programming, although we have
simplified the actual method for presentation, ignoring the possibility
of character subscripts and \Co{NA}'s, and assuming the replacement
values come in a list.
Look at the actual definition of the method to see the full generality.

As before, the class of \Co{x} is set to \Co{NULL}, to
avoid any other methods being used.
The names \Co{..1} and \Co{..2} are used as if they were arguments.
The definitions of \Co{iseq} and \Co{jseq} generate explicit
subscripts for observations and variables.
The \Co{for} loop applies the replacement to each variable in turn.
Finally, the class attribute is replaced and the entire data frame
returned as the value of the function call, consistent with the
definition of user replacement functions.

\section{Assignment Methods}\label{Assignments}

One other piece of S evaluation, in addition to function calls, may
be relevant in designing new classes of data.
The process of assignment associates a name with an S object,
either in one of the frames active during the S session or as a
permanent S object.
Currently, methods are accepted for permanent assignment, by writing
a method for the generic function \Co{"<<-"()}.
General assignment methods would be easy to add, but our current
feeling is that the overhead would be excessive.
The need to do so may arise if in some way the assigned object is treated
differently from an ordinary S object.

To redefine permanent assignment, create a function whose name
is \Co{"<<-."}, followed by the name of the class.
This method will  be called just before a permanent assignment
is committed (\cite{S},  page 121).
The arguments to the method are \Co{x} (the name) and
\Co{value} (the S object to
be assigned that name).
As an example, we consider briefly a class of objects designed to
support large amounts of data.
The class \Co{extern} consists of objects that refer to
an external file containing the actual data.
Methods for these objects allow access to the data and other operations
on it without reading the entire object into memory, as would happen
for ordinary S objects.
The object is defined by two attributes:
the \Co{class} attribute, with value \Co{"extern"} and the \Co{where}
attribute, whose value is a character string identifying  the external
file holding the data.
We will not discuss this class in detail, but it provides an example of
a method for assignment.
Extern objects created in an expression have special \Co{where} names,
referring to files that will be removed automatically
at the end of the expression.
Permanent files for extern objects reside in a special subdirectory of the
working directory, in which they have the same name as the \Co{extern}
object that refers to them.
The method for permanent assignment sets up the appropriate file
and returns an \Co{extern} object for assignment with the correct
\Co{where} attribute.
\begin{Example}
"<<-.extern" <- function(x, value) \{
    perm.file <- paste(search()[1], ".Ext", x, sep="/")
    cur.file <- attr(value, "where")
    if(is.perm(cur.file)) \{
      if(cur.file != perm.file))
        unix( paste("cp", cur.file, perm.file))
    \} else unix( paste("mv", cur.file, perm.file)
    attr(value, "where") <- perm.file
    NextMethod()
\}
\end{Example}
The method essentially does two things: it puts the \Co{where}
file in the right place, by using either the \Co{mv} or \Co{cp}
command; and it sets the \Co{where} attribute in the object
to the correct file name.
Calling \Co{NextMethod()} completes the standard assignment with
the modified object.

\section{Generic Functions}\label{generic}
Generic functions that call \Co{UseMethod()} are easy to recognize, of
course, and new generic functions can be written in this form
at any time.
A new generic function, say \Co{precis()}, usually looks like this:
\begin{Example}
precis <- function(x)
    UseMethod()
\end{Example}
For most generic functions, a default method will also be written:
\begin{Example}
precis.default <- function(x) \{
    if(is.null(class(x)) cat("Mode:", mode(x),
         "Length:", length(x), "\(\backslash\)n")
    else cat("Class:", class(x),"\(\backslash\)n")
\}
\end{Example}
(If 
It is not obligatory that the body of the generic consist only of the
call to \Co{UseMethod()}, although the keep-it-simple motto encourages it.
The semantic definition of \Co{UseMethod()} is that it takes evaluates
the body of the chosen method in
frame of the caller.
Any changes to the objects in that frame can be made before calling
\Co{UseMethod()}.
Also, \Co{UseMethod()} can be given an argument, \Co{object}, which will
then be used instead of the first argument to the caller in determining
the class for the method.
It may be significant that no example has so far arisen where this flexibility
was important enough to depart from the simpler form of generic function.

Generic functions working through the \Co{.Internal} interface can't be
recognized by looking at the definition of the generic.
\begin{table}[hbt]
\centering
\small \tt
\begin{tabular}{|l l l l|}
\hline
x[..., drop] &
x[[..., drop]] &
x\$name &
e1 \%\% e2 \\
e1 \%/\% e2 &
e1 * e2 &
e1 ** e2 &
e1 + e2 \\
e1 - e2 &
e1 / e2 &
e1 \Hat e2 &
e1 < e2 \\
e1 <= e2 &
e1 == e2 &
e1 > e2 &
e1 >= e2 \\
e1 \& e2 &
e1 \&\& e2 &
e1 | e2 &
e1 || e2 \\
e1!=e2 &
-e1  &
!x &
\  \\
abs(x) &
acos(x) &
acosh(x) &
all(x) \\
any(x) &
as.{\it anything}(x) &
as.vector(x, mode) &
asin(x) \\
asinh(x) &
atan(x,y) &
atanh(x) &
attr(x, which) \\
attributes(x) &
ceiling(x) &
compname(x) &
cos(x) \\
cosh(x) &
cumsum(x) &
dim(x) &
dimnames(x) \\
exp(x) &
floor(x) &
length(x) &
levels(x) \\
log(x) &
log10(x) &
max(x) &
min(x) \\
mode(x) &
names(x) &
prod(x) &
range(x) \\
round(x, digits) &
signif(x, digits) &
sin(x) &
sinh(x) \\
storage.mode(x) &
sum(x) &
tan(x) &
tanh(x) \\
trunc(x) &
tsp(x) &
\  &
\  
\\ \hline
\end{tabular} \rm
\caption{\label{intern.funs}Functions in S for which internal code will detect special methods.}
\end{table}
Table \ref{intern.funs} lists all the functions using the \Co{.Internal()} interface
for which  methods can be written.
There must {\em not} be a default method for these
functions.
The default is provided by the internal code.
The list in Table \ref{intern.funs} is larger than that in Table \ref{group.funs},
because group methods are not allowed in all cases.
The decision, somewhat arbitrary, was that some internal interface
routines handled a group of functions too diverse or too unlikely to be
candidates for methods to justify the extra overhead in checking each
time for a group method.


\section{Comment}\label{Comment}
Methods provide a powerful tool for extending S to handle novel
classes of objects.
We have concentrated here on illustrating the technique and have kept
the methods as simple as possible.
In practical applications, designing the methods should be the most
carefully thought-out part of the project.
The best strategy to make methods correspond to the meaning
of a class of objects in serious applications can be challenging and
not entirely unambiguous.
These strategic questions, although requiring care and sometimes introducing
subtle issues, are not disadvantages.
Rather, they illustrate the substantive needs that can be addressed
directly with a rich software environment.

\section*{Acknowledgements}
The work on methods started out as a simple exercise (for the
implementer).
Since then it has evolved greatly, stimulated by the enthusiasm
and suggestions of early users as well as comments by others
who have worked with object-oriented programming.
While the result has been much more challenging for the implementer,
I hope it is still reasonably simple and useful from the user's view.
Suggestions and comments from Luke Tierney, Trevor Hastie, Daryl Pregibon,
David Lubinsky,
Doug Bates, Rick Becker, and Allan Wilks have been particularly helpful.
