doc/: Switch to a manually maintained bibliography database.

[sod] / doc / cutting-room-floor.tex

%%% -*-latex-*-
%%%
%%% Conceptual background
%%%
%%% (c) 2015 Straylight/Edgeware
%%%

%%%----- Licensing notice ---------------------------------------------------
%%%
%%% This file is part of the Sensible Object Design, an object system for C.
%%%
%%% SOD is free software; you can redistribute it and/or modify
%%% it under the terms of the GNU General Public License as published by
%%% the Free Software Foundation; either version 2 of the License, or
%%% (at your option) any later version.
%%%
%%% SOD is distributed in the hope that it will be useful,
%%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%%% GNU General Public License for more details.
%%%
%%% You should have received a copy of the GNU General Public License
%%% along with SOD; if not, write to the Free Software Foundation,
%%% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

\chapter{Cutting-room floor}

%%%--------------------------------------------------------------------------
\section{Generated names}

The generated names for functions and objects related to a class are
constructed systematically so as not to interfere with each other.  The rules
on class, slot and message naming exist so as to ensure that the generated
names don't collide with each other.

The following notation is used in this section.
\begin{description}
\item[@<class>] The full name of the `focus' class: the one for which we are
  generating name.
\item[@<super-nick>] The nickname of a superclass.
\item[@<head-nick>] The nickname of the chain-head class of the chain
  in question.
\end{description}

\subsection{Instance layout}

%%%--------------------------------------------------------------------------
\section{Class objects}

\begin{listing}
typedef struct SodClass__ichain_obj SodClass;

struct sod_chain {
  size_t n_classes;                     /* Number of classes in chain */
  const SodClass *const *classes;       /* Vector of classes, head first */
  size_t off_ichain;                    /* Offset of ichain from instance base */
  const struct sod_vtable *vt;          /* Vtable pointer for chain */
  size_t ichainsz;                      /* Size of the ichain structure */
};

struct sod_vtable {
  SodClass *_class;                     /* Pointer to instance's class */
  size_t _base;                         /* Offset to instance base */
};

struct SodClass__islots {

  /* Basic information */
  const char *name;                     /* The class's name as a string */
  const char *nick;                     /* The nickname as a string */

  /* Instance allocation and initialization */
  size_t instsz;                        /* Instance layout size in bytes */
  void *(*imprint)(void *);             /* Stamp instance with vtable ptrs */
  void *(*init)(void *);                /* Initialize instance */

  /* Superclass structure */
  size_t n_supers;                      /* Number of direct superclasses */
  const SodClass *const *supers;        /* Vector of direct superclasses */
  size_t n_cpl;                         /* Length of class precedence list */
  const SodClass *const *cpl;           /* Vector for class precedence list */

  /* Chain structure */
  const SodClass *link;                 /* Link to next class in chain */
  const SodClass *head;                 /* Pointer to head of chain */
  size_t level;                         /* Index of class in its chain */
  size_t n_chains;                      /* Number of superclass chains */
  const sod_chain *chains;              /* Vector of chain structures */

  /* Layout */
  size_t off_islots;                    /* Offset of islots from ichain base */
  size_t islotsz;                       /* Size of instance slots */
};

struct SodClass__ichain_obj {
  const SodClass__vt_obj *_vt;
  struct SodClass__islots cls;
};

struct sod_instance {
  struct sod_vtable *_vt;
};
\end{listing}

\begin{listing}
void *sod_convert(const SodClass *cls, const void *obj)
{
  const struct sod_instance *inst = obj;
  const SodClass *real = inst->_vt->_cls;
  const struct sod_chain *chain;
  size_t i, index;

  for (i = 0; i < real->cls.n_chains; i++) {
    chain = &real->cls.chains[i];
    if (chain->classes[0] == cls->cls.head) {
      index = cls->cls.index;
      if (index < chain->n_classes && chain->classes[index] == cls)
        return ((char *)cls - inst->_vt._base + chain->off_ichain);
      else
        return (0);
    }
  }
  return (0);
}
\end{listing}

%%%--------------------------------------------------------------------------
\section{Classes}
\label{sec:class}

\subsection{Classes and superclasses} \label{sec:class.defs}

A @<full-class-definition> must list one or more existing classes to be the
\emph{direct superclasses} for the new class being defined.  We make the
following definitions.
\begin{itemize}
\item The \emph{superclasses} of a class consist of the class itself together
  with the superclasses of its direct superclasses.
\item The \emph{proper superclasses} of a class are its superclasses other
  than itself.
\item If $C$ is a (proper) superclass of $D$ then $D$ is a (\emph{proper})
  \emph{subclass} of $C$.
\end{itemize}
The predefined class @|SodObject| has no direct superclasses; it is unique in
this respect.  All classes are subclasses of @|SodObject|.

\subsection{The class precedence list} \label{sec:class.cpl}

Let $C$ be a class.  The superclasses of $C$ form a directed graph, with an
edge from each class to each of its direct superclasses.  This is the
\emph{superclass graph of $C$}.

In order to resolve inheritance of items, we define a \emph{class precedence
  list} (or CPL) for each class, which imposes a total order on that class's
superclasses.  The default algorithm for computing the CPL is the \emph{C3}
algorithm \cite{barrett-1996:monot-super-linear-dylan}, though extensions may
implement other algorithms.

The default algorithm works as follows.  Let $C$ be the class whose CPL we
are to compute.  Let $X$ and $Y$ be two of $C$'s superclasses.
\begin{itemize}
\item $C$ must appear first in the CPL.
\item If $X$ appears before $Y$ in the CPL of one of $C$'s direct
  superclasses, then $X$ appears before $Y$ in the $C$'s CPL.
\item If the above rules don't suffice to order $X$ and $Y$, then whichever
  of $X$ and $Y$ has a subclass which appears further left in the list of
  $C$'s direct superclasses will appear earlier in the CPL.
\end{itemize}
This last rule is sufficient to disambiguate because if both $X$ and $Y$ are
superclasses of the same direct superclass of $C$ then that direct
superclass's CPL will order $X$ and $Y$.

We say that \emph{$X$ is more specific than $Y$ as a superclass of $C$} if
$X$ is earlier than $Y$ in $C$'s class precedence list.  If $C$ is clear from
context then we omit it, saying simply that $X$ is more specific than $Y$.

\subsection{Instances and metaclasses} \label{sec:class.meta}

A class defines the structure and behaviour of its \emph{instances}: run-time
objects created (possibly) dynamically.  An instance is an instance of only
one class, though structurally it may be used in place of an instance of any
of that class's superclasses.  It is possible, with care, to change the class
of an instance at run-time.

Classes are themselves represented as instances -- called \emph{class
  objects} -- in the running program.  Being instances, they have a class,
called the \emph{metaclass}.  The metaclass defines the structure and
behaviour of the class object.

The predefined class @|SodClass| is the default metaclass for new classes.
@|SodClass| has @|SodObject| as its only direct superclass.  @|SodClass| is
its own metaclass.

To make matters more complicated, Sod has \emph{two} distinct metalevels: as
well as the runtime metalevel, as discussed above, there's a compile-time
metalevel hosted in the Sod translator.  Since Sod is written in Common Lisp,
a Sod class's compile-time metaclass is a CLOS class.  The usual compile-time
metaclass is @|sod-class|.  The compile-time metalevel is the subject of
\xref{ch:api}.

\subsection{Items and inheritance} \label{sec:class.inherit}

A class definition also declares \emph{slots}, \emph{messages},
\emph{initializers} and \emph{methods} -- collectively referred to as
\emph{items}.  In addition to the items declared in the class definition --
the class's \emph{direct items} -- a class also \emph{inherits} items from
its superclasses.

The precise rules for item inheritance vary according to the kinds of items
involved.

Some object systems have a notion of `repeated inheritance': if there are
multiple paths in the superclass graph from a class to one of its
superclasses then items defined in that superclass may appear duplicated in
the subclass.  Sod does not have this notion.

\subsubsection{Slots} \label{sec:class.inherit.slots}
A \emph{slot} is a unit of state.  In other object systems, slots may be
called `fields', `member variables', or `instance variables'.

A slot has a \emph{name} and a \emph{type}.  The name serves only to
distinguish the slot from other direct slots defined by the same class.  A
class inherits all of its proper superclasses' slots.  Slots inherited from
superclasses do not conflict with each other or with direct slots, even if
they have the same names.

At run-time, each instance of the class holds a separate value for each slot,
whether direct or inherited.  Changing the value of an instance's slot
doesn't affect other instances.

\subsubsection{Initializers} \label{sec:class.inherit.init}
Mumble.

\subsubsection{Messages} \label{sec:class.inherit.messages}
A \emph{message} is the stimulus for behaviour.  In Sod, a class must define,
statically, the name and format of the messages it is able to receive and the
values it will return in reply.  In this respect, a message is similar to
`abstract member functions' or `interface member functions' in other object
systems.

Like slots, a message has a \emph{name} and a \emph{type}.  Again, the name
serves only to distinguish the message from other direct messages defined by
the same class.  Messages inherited from superclasses do not conflict with
each other or with direct messages, even if they have the same name.

At run-time, one sends a message to an instance by invoking a function
obtained from the instance's \emph{vtable}: \xref{sec:fixme-vtable}.

\subsubsection{Methods} \label{sec:class.inherit.methods}
A \emph{method} is a unit of behaviour.  In other object systems, methods may
be called `member functions'.

A method is associated with a message.  When a message is received by an
instance, all of the methods associated with that message on the instance's
class or any of its superclasses are \emph{applicable}.  The details of how
the applicable methods are invoked are described fully in
\xref{sec:fixme-method-combination}.

\subsection{Chains and instance layout} \label{sec:class.layout}

C is a rather low-level language, and in particular it exposes details of the
way data is laid out in memory.  Since an instance of a class~$C$ should be
(at least in principle) usable anywhere an instance of some superclass $B
\succeq C$ is expected, this implies that an instance of the subclass $C$
needs to contain within it a complete instance of each superclass $B$, laid
out according to the rules of instances of $B$, so that if we have (the
address of) an instance of $C$, we can easily construct a pointer to a thing
which looks like an instance of $B$ contained within it.

Specifically, the information we need to retain for an instance of a
class~$C$ is:
\begin{itemize}
\item the values of each of the slots defined by $C$, including those defined
  by superclasses;
\item information which will let us convert a pointer to $C$ into a pointer
  to any superclass $B \succeq C$;
\item information which will let us call the appropriate effective method for
  each message defined by $C$, including those defined by superclasses; and
\item some additional meta-level information, such as how to find the class
  object for $C$ given (the address of) one of its instances.
\end{itemize}

Observe that, while each distinct instance must clearly have its own storage
for slots, all instances of $C$ can share a single copy of the remaining
information.  The individual instance only needs to keep a pointer to this
shared table, which, inspired by the similar structure in many \Cplusplus\
ABIs, are called a \emph{vtable}.

The easiest approach would be to decide that instances of $C$ are exactly
like instances of $B$, only with extra space at the end for the extra slots
which $C$ defines over and above those already existing in $B$.  Conversion
is then trivial: a pointer to an instance of $C$ can be converted to a
pointer to an instance of some superclass $B$ simply by casting.  Even though
the root class @|SodObject| doesn't have any slots at all, its instances will
still need a vtable so that you can find its class object: the address of the
vtable therefore needs to be at the very start of the instance structure.
Again, a vtable for a superclass would have a vtable for each of its
superclasses as a prefix, with new items added afterwards.

This appealing approach works well for an object system which only permits
single inheritance of both state and behaviour.  Alas, it breaks down when
multiple inheritance is allowed: $C$ can be a subclass of both $B$ and $B'$,
even though $B$ is not a subclass of $B'$, nor \emph{vice versa}; so, in
general, $B$'s instance structure will not be a prefix of $B'$'s, nor will
$B'$'s be a prefix of $B$'s, and therefore $C$ cannot have both $B$ and $B'$
as a prefix.

A (non-root) class may -- though need not -- have a distinguished \emph{link}
superclass, which need not be a direct superclass.  Furthermore, each
class~$C$ must satisfy the \emph{chain condition}: for any superclass $A$ of
$C$, there can be at most one other superclass of $C$ whose link superclass
is $A$.\footnote{%
  That is, it's permitted for two classes $B$ and $B'$ to have the same link
  superclass $A$, but $B$ and $B'$ can't then both be superclasses of the
  same class $C$.} %
Therefore, the links partition the superclasses of~$C$ into nice linear
\emph{chains}, such that each superclass is a member of exactly one chain.
If a class~$B$ has a link superclass~$A$, then $B$'s \emph{level} is one more
than that of $A$; otherwise $B$ is called a \emph{chain head} and its level
is zero.  If the classes in a chain are written in a list, chain head first,
then the level of each class gives its index in the list.

Chains therefore allow us to recover some of the linearity properties which
made layout simple in the case of single inheritance.  The instance structure
for a class $C$ contains a substructure for each of $C$'s superclass chains;
a pointer to an object of class $C$ actually points to the substructure for
the chain containing $C$.  The order of these substructures is unimportant
for now.\footnote{%
  The chains appear in the order in which their most specific classes appear
  in $C$'s class precedence list.  This guarantees that the chain containing
  $C$ itself appears first, so that a pointer to $C$'s instance structure is
  actually a pointer to $C$'s chain substructure.  Apart from that, it's a
  simple, stable, but basically arbitrary choice which can't be changed
  without breaking the ABI.} %
The substructure for each chain begins with a pointer to a vtable, followed
by a structure for each superclass in the chain containing the slots defined
by that superclass, with the chain head (least specific class) first.

Suppose we have a pointer to (static) type $C$, and want to convert it into a
pointer to some superclass $B$ of $C$ -- an \emph{upcast}.\footnote{%
  In the more general case, we have a pointer to static type $C$, which
  actually points to an object of some subclass $D$ of $C$, and want to
  convert it into a pointer to type $B$.  Such a conversion is called a
  \emph{downcast} if $B$ is a subclass of $C$, or a \emph{cross-cast}
  otherwise.  Downcasts and cross-casts require complicated run-time
  checking, and can will fail unless $B$ is a superclass of $D$.} %
If $B$ is in the same chain as $C$ -- an \emph{in-chain upcast} -- then the
pointer value is already correct and it's only necessary to cast it
appropriately.  Otherwise -- a \emph{cross-chain upcast} -- the pointer needs
to be adjusted to point to a different chain substructure.  Since the lengths
and relative positions of the chain substructures vary between classes, the
adjustments are stored in the vtable.  Cross-chain upcasts are therefore a
bit slower than in-chain upcasts.

Each chain has its own separate vtable, because much of the metadata stored
in the vtable is specific to a particular chain.  For example:
\begin{itemize}
\item offsets to other chains' substructures will vary depending on which
  chain we start from; and
\item entry points to methods 
\end{itemize}
%%%--------------------------------------------------------------------------
\section{Superclass linearization}

Before making any decisions about relationships between superclasses, Sod
\emph{linearizes} them, i.e., imposes a total order consistent with the
direct-subclass/superclass partial order.

In the vague hope that we don't be completely bogged down in formalism by the
end of this, let's introduce some notation.  We'll fix some class $z$ and
consider its set of superclasses $S(z) = \{ a, b, \dots \}$.  We can define a
relation $c \prec_1 d$ if $c$ is a direct subclass of $d$, and extend it by
taking the reflexive, transitive closure: $c \preceq d$ if and only if
\begin{itemize}
\item $c = d$, or
\item there exists some class $x$ such that $c \prec_1 x$ and $x \preceq d$.
\end{itemize}
This is the `is-subclass-of' relation we've been using so far.\footnote{%
  In some object systems, notably Flavors, this relation is allowed to fail
  to be a partial order because of cycles in the class graph.  I haven't
  given a great deal of thought to how well Sod would cope with a cyclic
  class graph.} %
We write $d \succeq c$ and say that $d$ is a superclass of $c$ if and only if
$c \preceq d$.

The problem comes when we try to resolve inheritance questions.  A class
should inherit behaviour from its superclasses; but, in a world of multiple
inheritance, which one do we choose?  We get a simple version of this problem
when we try to resolve inheritance of slot initializers: only one initializer
can be inherited.

We start by collecting into a set~$I$ the classes which define an initializer
for the slot.  If $I$ contains both a class $x$ and one of $x$'s superclasses
then we should prefer $x$ and consider the superclass to be overridden.  So
we should confine our attention to \emph{least} classes: a member $x$ of a
set $I$ is least, with respect to a particular partial order, if $y \preceq
x$ only when $x = y$.  If there is a single least class in our set the we
have a winner.  Otherwise we want some way to choose among them.

This is not uncontroversial.  Languages such as \Cplusplus\ refuse to choose
among least classes; instead, any program in which such a choice must be made
is simply declared erroneous.

Simply throwing up our hands in horror at this situation is satisfactory when
we only wanted to pick one `winner', as we do for slot initializers.
However, method combination is a much more complicated business.  We don't
want to pick just one winner: we want to order all of the applicable methods
in some way.  Insisting that there is a clear winner at every step along the
chain is too much of an imposition.  Instead, we \emph{linearize} the
classes.

%%%--------------------------------------------------------------------------
\section{Invariance, covariance, contravariance}

In Sod, at least with regard to the existing method combinations, method
types are \emph{invariant}.  This is not an accident, and it's not due to
ignorance.

The \emph{signature} of a function, method or message describes its argument
and return-value types.  If a method's arguments are an integer and a string,
and it returns a character, we might write its signature as
\[ (@|int|, @|string|) \to @|char| \]
In Sod, a method's arguments have to match its message's arguments precisely,
and the return type must either be @|void| -- for a dæmon method -- or again
match the message's return type.  This is argument and return-type
\emph{invariance}.

Some object systems allow methods with subtly different signatures to be
defined on a single message.  In particular, since the idea is that instances
of a subclass ought to be broadly compatible~(see \xref{sec:phil.lsp}) with
existing code which expects instances of a superclass, we might be able to
get away with bending method signatures one way or another to permit this.

\Cplusplus\ permits \emph{return-type covariance}, where a method's return
type can be a subclass of the return type specified by a less-specific
method.  Eiffel allows \emph{argument covariance}, where a method's arguments
can be subclasses of the arguments specified by a less-specific
method.\footnote{%
  Attentive readers will note that I ought to be talking about pointers to
  instances throughout.  I'm trying to limit the weight of the notation.
  Besides, I prefer data models as found in Lisp and Python where all values
  are held by reference.} %

Eiffel's argument covariance is unsafe.\footnote{%
  Argument covariance is correct if you're doing runtime dispatch based on
  argument types.  Eiffel isn't: it's single dispatch, like Sod is.} %
Suppose that we have two pairs of classes, $a \prec_1 b$ and $c \prec_1 d$.
Class $b$ defines a message $m$ with signature $d \to @|int|$; class $a$
defines a method with signature $c \to @|int|$.  This means that it's wrong
to send $m$ to an instance $a$ carrying an argument of type $d$.  But of
course, we can treat an instance of $a$ as if it's an instance of $b$,
whereupon it appears that we are permitted to pass a~$c$ in our message.  The
result is a well-known hole in the type system.  Oops.

\Cplusplus's return-type covariance is fine.  Also fine is argument
\emph{contravariance}.  If $b$ defined its message to have signature $c \to
@|int|$, and $a$ were to broaden its method to $d \to @|int|$, there'd be no
problem.  All $c$s are $d$s, so viewing an $a$ as a $b$ does no harm.

All of this fiddling with types is fine as long as method inheritance or
overriding is an all-or-nothing thing.  But Sod has method combinations,
where applicable methods are taken from the instance's class and all its
superclasses and combined.  And this makes everything very messy.

It's possible to sort all of the mess out in the generated effective method
-- we'd just have to convert the arguments to the types that were expected by
the direct methods.  This would require expensive run-time conversions of all
of the non-invariant arguments and return values.  And we'd need some
complicated rule so that we could choose sensible types for the method
entries in our vtables.  Something like this:
\begin{quote} \itshape
  For each named argument of a message, there must be a unique greatest type
  among the types given for that argument by the applicable methods; and
  there must be a unique least type among all of the return types of the
  applicable methods.
\end{quote}
I have visions of people wanting to write special no-effect methods whose
only purpose is to guide the translator around the class graph properly.
Let's not.

%% things to talk about:
%% Liskov substitution principle and why it's mad

%%%----- That's all, folks --------------------------------------------------

%%% Local variables:
%%% mode: LaTeX
%%% TeX-master: "sod.tex"
%%% TeX-PDF-mode: t
%%% End: