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
49 We write $d
\succeq c$ and say that $d$ is a superclass of $c$ if and only if
52 The problem comes when we try to resolve inheritance questions. A class
53 should inherit behaviour from its superclasses; but, in a world of multiple
54 inheritance, which one do we choose? We get a simple version of this problem
55 when we try to resolve inheritance of slot initializers: only one initializer
58 We start by collecting into a set~$I$ the classes which define an initializer
59 for the slot. If $I$ contains both a class $x$ and one of $x$'s superclasses
60 then we should prefer $x$ and consider the superclass to be overridden. So
61 we should confine our attention to
\emph{least
} classes: a member $x$ of a
62 set $I$ is least, with respect to a particular partial order, if $y
\preceq
63 x$ only when $x = y$. If there is a single least class in our set the we
64 have a winner. Otherwise we want some way to choose among them.
66 This is not uncontroversial. Languages such as
\Cplusplus\ refuse to choose
67 among least classes; instead, any program in which such a choice must be made
68 is simply declared erroneous.
70 Simply throwing up our hands in horror at this situation is satisfactory when
71 we only wanted to pick one `winner', as we do for slot initializers.
72 However, method combination is a much more complicated business. We don't
73 want to pick just one winner: we want to order all of the applicable methods
74 in some way. Insisting that there is a clear winner at every step along the
75 chain is too much of an imposition. Instead, we
\emph{linearize
} the
78 %%%--------------------------------------------------------------------------
79 \section{Invariance, covariance, contravariance
}
81 In Sod, at least with regard to the existing method combinations, method
82 types are
\emph{invariant
}. This is not an accident, and it's not due to
85 The
\emph{signature
} of a function, method or message describes its argument
86 and return-value types. If a method's arguments are an integer and a string,
87 and it returns a character, we might write its signature as
88 \
[ (@|int|, @|string|)
\to @|char| \
]
89 In Sod, a method's arguments have to match its message's arguments precisely,
90 and the return type must either be @|void| -- for a dæmon method -- or again
91 match the message's return type. This is argument and return-type
94 Some object systems allow methods with subtly different signatures to be
95 defined on a single message. In particular, since the idea is that instances
96 of a subclass ought to be broadly compatible~(see
\xref{sec:phil.lsp
}) with
97 existing code which expects instances of a superclass, we might be able to
98 get away with bending method signatures one way or another to permit this.
100 \Cplusplus\ permits
\emph{return-type covariance
}, where a method's return
101 type can be a subclass of the return type specified by a less-specific
102 method. Eiffel allows
\emph{argument covariance
}, where a method's arguments
103 can be subclasses of the arguments specified by a less-specific
105 Attentive readers will note that I ought to be talking about pointers to
106 instances throughout. I'm trying to limit the weight of the notation.
107 Besides, I prefer data models as found in Lisp and Python where all values
108 are held by reference.
} %
110 Eiffel's argument covariance is unsafe.
\footnote{%
111 Argument covariance is correct if you're doing runtime dispatch based on
112 argument types. Eiffel isn't: it's single dispatch, like Sod is.
} %
113 Suppose that we have two pairs of classes, $a
\prec_1 b$ and $c
\prec_1 d$.
114 Class $b$ defines a message $m$ with signature $d
\to @|int|$; class $a$
115 defines a method with signature $c
\to @|int|$. This means that it's wrong
116 to send $m$ to an instance $a$ carrying an argument of type $d$. But of
117 course, we can treat an instance of $a$ as if it's an instance of $b$,
118 whereupon it appears that we are permitted to pass a~$c$ in our message. The
119 result is a well-known hole in the type system. Oops.
121 \Cplusplus's return-type covariance is fine. Also fine is argument
122 \emph{contravariance
}. If $b$ defined its message to have signature $c
\to
123 @|int|$, and $a$ were to broaden its method to $d
\to @|int|$, there'd be no
124 problem. All $c$s are $d$s, so viewing an $a$ as a $b$ does no harm.
126 All of this fiddling with types is fine as long as method inheritance or
127 overriding is an all-or-nothing thing. But Sod has method combinations,
128 where applicable methods are taken from the instance's class and all its
129 superclasses and combined. And this makes everything very messy.
131 It's possible to sort all of the mess out in the generated effective method
132 -- we'd just have to convert the arguments to the types that were expected by
133 the direct methods. This would require expensive run-time conversions of all
134 of the non-invariant arguments and return values. And we'd need some
135 complicated rule so that we could choose sensible types for the method
136 entries in our vtables. Something like this:
137 \begin{quote
} \itshape
138 For each named argument of a message, there must be a unique greatest type
139 among the types given for that argument by the applicable methods; and
140 there must be a unique least type among all of the return types of the
143 I have visions of people wanting to write special no-effect methods whose
144 only purpose is to guide the translator around the class graph properly.
147 %% things to talk about:
148 %% Liskov substitution principle and why it's mad
150 %%%----- That's all, folks --------------------------------------------------
154 %%% TeX-master: "sod.tex"
~mdw / sod / blob