+%%% -*-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.} %
+
+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:
~mdw / sod / commitdiff