Commit | Line | Data |
---|---|---|
3be8c2bf MW |
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: |