Merge branch 'master' into doc

[sod] / doc / sod-backg.tex

%%% -*-latex-*-
%%%
%%% Background philosophy
%%%
%%% (c) 2009 Straylight/Edgeware
%%%

%%%----- Licensing notice ---------------------------------------------------
%%%
%%% This file is part of the Simple Object Definition system.
%%%
%%% 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{Philosophical background}

%%%--------------------------------------------------------------------------
\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: