| 1 | %%% -*-latex-*- |
| 2 | %%% |
| 3 | %%% Background philosophy |
| 4 | %%% |
| 5 | %%% (c) 2009 Straylight/Edgeware |
| 6 | %%% |
| 7 | |
| 8 | %%%----- Licensing notice --------------------------------------------------- |
| 9 | %%% |
| 10 | %%% This file is part of the Simple Object Definition system. |
| 11 | %%% |
| 12 | %%% SOD is free software; you can redistribute it and/or modify |
| 13 | %%% it under the terms of the GNU General Public License as published by |
| 14 | %%% the Free Software Foundation; either version 2 of the License, or |
| 15 | %%% (at your option) any later version. |
| 16 | %%% |
| 17 | %%% SOD is distributed in the hope that it will be useful, |
| 18 | %%% but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 19 | %%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 20 | %%% GNU General Public License for more details. |
| 21 | %%% |
| 22 | %%% You should have received a copy of the GNU General Public License |
| 23 | %%% along with SOD; if not, write to the Free Software Foundation, |
| 24 | %%% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
| 25 | |
| 26 | \chapter{Philosophical background} |
| 27 | |
| 28 | %%%-------------------------------------------------------------------------- |
| 29 | \section{Superclass linearization} |
| 30 | |
| 31 | Before making any decisions about relationships between superclasses, Sod |
| 32 | \emph{linearizes} them, i.e., imposes a total order consistent with the |
| 33 | direct-subclass/superclass partial order. |
| 34 | |
| 35 | In the vague hope that we don't be completely bogged down in formalism by the |
| 36 | end of this, let's introduce some notation. We'll fix some class $z$ and |
| 37 | consider its set of superclasses $S(z) = \{ a, b, \dots \}$. We can define a |
| 38 | relation $c \prec_1 d$ if $c$ is a direct subclass of $d$, and extend it by |
| 39 | taking the reflexive, transitive closure: $c \preceq d$ if and only if |
| 40 | \begin{itemize} |
| 41 | \item $c = d$, or |
| 42 | \item there exists some class $x$ such that $c \prec_1 x$ and $x \preceq d$. |
| 43 | \end{itemize} |
| 44 | This is the `is-subclass-of' relation we've been using so far.\footnote{% |
| 45 | In some object systems, notably Flavors, this relation is allowed to fail |
| 46 | to be a partial order because of cycles in the class graph. I haven't |
| 47 | given a great deal of thought to how well Sod would cope with a cyclic |
| 48 | class graph.} % |
| 49 | |
| 50 | The problem comes when we try to resolve inheritance questions. A class |
| 51 | should inherit behaviour from its superclasses; but, in a world of multiple |
| 52 | inheritance, which one do we choose? We get a simple version of this problem |
| 53 | when we try to resolve inheritance of slot initializers: only one initializer |
| 54 | can be inherited. |
| 55 | |
| 56 | We start by collecting into a set~$I$ the classes which define an initializer |
| 57 | for the slot. If $I$ contains both a class $x$ and one of $x$'s superclasses |
| 58 | then we should prefer $x$ and consider the superclass to be overridden. So |
| 59 | we should confine our attention to \emph{least} classes: a member $x$ of a |
| 60 | set $I$ is least, with respect to a particular partial order, if $y \preceq |
| 61 | x$ only when $x = y$. If there is a single least class in our set the we |
| 62 | have a winner. Otherwise we want some way to choose among them. |
| 63 | |
| 64 | This is not uncontroversial. Languages such as \Cplusplus\ refuse to choose |
| 65 | among least classes; instead, any program in which such a choice must be made |
| 66 | is simply declared erroneous. |
| 67 | |
| 68 | Simply throwing up our hands in horror at this situation is satisfactory when |
| 69 | we only wanted to pick one `winner', as we do for slot initializers. |
| 70 | However, method combination is a much more complicated business. We don't |
| 71 | want to pick just one winner: we want to order all of the applicable methods |
| 72 | in some way. Insisting that there is a clear winner at every step along the |
| 73 | chain is too much of an imposition. Instead, we \emph{linearize} the |
| 74 | classes. |
| 75 | |
| 76 | %%%-------------------------------------------------------------------------- |
| 77 | \section{Invariance, covariance, contravariance} |
| 78 | |
| 79 | In Sod, at least with regard to the existing method combinations, method |
| 80 | types are \emph{invariant}. This is not an accident, and it's not due to |
| 81 | ignorance. |
| 82 | |
| 83 | The \emph{signature} of a function, method or message describes its argument |
| 84 | and return-value types. If a method's arguments are an integer and a string, |
| 85 | and it returns a character, we might write its signature as |
| 86 | \[ (@|int|, @|string|) \to @|char| \] |
| 87 | In Sod, a method's arguments have to match its message's arguments precisely, |
| 88 | and the return type must either be @|void| -- for a dæmon method -- or again |
| 89 | match the message's return type. This is argument and return-type |
| 90 | \emph{invariance}. |
| 91 | |
| 92 | Some object systems allow methods with subtly different signatures to be |
| 93 | defined on a single message. In particular, since the idea is that instances |
| 94 | of a subclass ought to be broadly compatible~(see \xref{sec:phil.lsp}) with |
| 95 | existing code which expects instances of a superclass, we might be able to |
| 96 | get away with bending method signatures one way or another to permit this. |
| 97 | |
| 98 | \Cplusplus\ permits \emph{return-type covariance}, where a method's return |
| 99 | type can be a subclass of the return type specified by a less-specific |
| 100 | method. Eiffel allows \emph{argument covariance}, where a method's arguments |
| 101 | can be subclasses of the arguments specified by a less-specific |
| 102 | method.\footnote{% |
| 103 | Attentive readers will note that I ought to be talking about pointers to |
| 104 | instances throughout. I'm trying to limit the weight of the notation. |
| 105 | Besides, I prefer data models as found in Lisp and Python where all values |
| 106 | are held by reference.} % |
| 107 | |
| 108 | Eiffel's argument covariance is unsafe.\footnote{% |
| 109 | Argument covariance is correct if you're doing runtime dispatch based on |
| 110 | argument types. Eiffel isn't: it's single dispatch, like Sod is.} % |
| 111 | Suppose that we have two pairs of classes, $a \prec_1 b$ and $c \prec_1 d$. |
| 112 | Class $b$ defines a message $m$ with signature $d \to @|int|$; class $a$ |
| 113 | defines a method with signature $c \to @|int|$. This means that it's wrong |
| 114 | to send $m$ to an instance $a$ carrying an argument of type $d$. But of |
| 115 | course, we can treat an instance of $a$ as if it's an instance of $b$, |
| 116 | whereupon it appears that we are permitted to pass a~$c$ in our message. The |
| 117 | result is a well-known hole in the type system. Oops. |
| 118 | |
| 119 | \Cplusplus's return-type covariance is fine. Also fine is argument |
| 120 | \emph{contravariance}. If $b$ defined its message to have signature $c \to |
| 121 | @|int|$, and $a$ were to broaden its method to $d \to @|int|$, there'd be no |
| 122 | problem. All $c$s are $d$s, so viewing an $a$ as a $b$ does no harm. |
| 123 | |
| 124 | All of this fiddling with types is fine as long as method inheritance or |
| 125 | overriding is an all-or-nothing thing. But Sod has method combinations, |
| 126 | where applicable methods are taken from the instance's class and all its |
| 127 | superclasses and combined. And this makes everything very messy. |
| 128 | |
| 129 | It's possible to sort all of the mess out in the generated effective method |
| 130 | -- we'd just have to convert the arguments to the types that were expected by |
| 131 | the direct methods. This would require expensive run-time conversions of all |
| 132 | of the non-invariant arguments and return values. And we'd need some |
| 133 | complicated rule so that we could choose sensible types for the method |
| 134 | entries in our vtables. Something like this: |
| 135 | \begin{quote} \itshape |
| 136 | For each named argument of a message, there must be a unique greatest type |
| 137 | among the types given for that argument by the applicable methods; and |
| 138 | there must be a unique least type among all of the return types of the |
| 139 | applicable methods. |
| 140 | \end{quote} |
| 141 | I have visions of people wanting to write special no-effect methods whose |
| 142 | only purpose is to guide the translator around the class graph properly. |
| 143 | Let's not. |
| 144 | |
| 145 | %% things to talk about: |
| 146 | %% Liskov substitution principle and why it's mad |
| 147 | |
| 148 | %%%----- That's all, folks -------------------------------------------------- |
| 149 | |
| 150 | %%% Local variables: |
| 151 | %%% mode: LaTeX |
| 152 | %%% TeX-master: "sod.tex" |
| 153 | %%% TeX-PDF-mode: t |
| 154 | %%% End: |