3 %%% Background philosophy
5 %%% (c) 2009 Straylight/Edgeware
8 %%%----- Licensing notice ---------------------------------------------------
10 %%% This file is part of the Simple Object Definition system.
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.
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.
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.
26 \chapter{Philosophical background
}
28 %%%--------------------------------------------------------------------------
29 \section{Superclass linearization
}
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.
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
42 \item there exists some class $x$ such that $c
\prec_1 x$ and $x
\preceq d$.
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
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
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.
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.
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
76 %%%--------------------------------------------------------------------------
77 \section{Invariance, covariance, contravariance
}
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
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
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.
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
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.
} %
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.
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.
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.
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
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.
145 %% things to talk about:
146 %% Liskov substitution principle and why it's mad
148 %%%----- That's all, folks --------------------------------------------------
152 %%% TeX-master: "sod.tex"
~mdw / sod / blob