From a theoretical perspective, object orientation may be characterized as combining abstract data types and polymorphism. These notions may be considered as the theoretical counterparts of the more operational notions of encapsulation and inheritance.
Additional keywords and phrases:
exceptions, type calculi,
parametric types, coercion, ad hoc polymorphism,
universal types, existential types,
unfolding, intersection types
Nixon is-a Quaker Nixon is-a Republican Quakers are Pacifists Republicans are not Pacifists
Incremental system evolution is in practice non-monotonic!
The meaning of is-a and is-not relations in a knowledge representation inheritance graph may equivalently be expressed as predicate logic statements. For example, the statements
$\backslash A\; x\; .\; Elephant(x)\; ->\; Mammal(x)$ $\backslash A\; x\; .\; Elephant(x)\; ->\; color(x)\; =\; gray$ $\backslash A\; x\; .\; Penguin(x)\; ->\; Bird(x)\; /\backslash \; \backslash neg\; CanFly(x)$
$V\; \backslash approx\; Int\; \backslash cup\; ...\; \backslash cup\; V\; \backslash times\; V\; \backslash cup\; V\; ->\; V$
type any = { } type entity = { age : int } type vehicle = { age : int, speed : int } type machine = { age : int, fuel : string } type car = { age : int, speed : int, fuel : string }
In
Example: $R\; =\; \{\; a1,\; a2\; \}\; +\; \{\; a2,\; a3\; \}\; =\; \{\; a1,\; a2,\; a3\; \}$
Independent attributes: M disjoint from P
Overlapping attributes: M overrules P
$($\ %l x.x) 1 = x[x:=1] = 1 $($\ %l x.x+1) 2 = (x+1)[x:=2] = 2 + 1 $($\ %l x.x+y+1) 3 = (x+y+1)[x:=3] = 3+y+1 $($\ %l y.(\ %l x.x+y+1) 3) 4) = $(($\ %l x.x+y+1) 3)[y:=4] = 3 + 4 + 1
Proof: take $W\; =\; \%l\; x.F\; (\; xx\; )$ and $X\; =\; WW$, then
$X\; =\; WW\; =\; ($\ %l x.F ( xx ) ) W = F ( WW ) = FX
$$\ %t ::=\ %r |\ %t_1 ->\ %t_2
int S(int x) { return x+1; } int twice(int f(int), int y) { return f(f(y)); } int twice_S(int y) { return twice(S,y); }
int SD(double x) { return x+1; } // twice(SD) rejected
class P {
P
public: P() { _self = 0; } virtual P* self() { return _self?_self->self():this; } virtual void attach(C* p) { _self = p; } private: P* _self; }; class C : public P {
$C\; <=\; P$
public: C() : P(this) { } C* self() { // ANSI/ISO return _self?_self->self():this; } void attach(P* p) { // rejected p->attach(self()); } void redirect(C* c) { _self = c; } private: C* _self; };
$+\; :\; \backslash bigwedge\; [\; Int\; \backslash *\; Int\; ->\; Int,\; Real\; \backslash *\; Real\; ->\; Real\; ]$
void f(int, double); void f(double, int); f(1,2.0); // f(int, double); f(2.0,1); // f(double,int); f(1,1); // error: ambiguous
class P; class C; void f(P* p) { cout << "f(P*)"; } // (1) void f(C* c) { cout << "f(C*)"; } // (2) class P { public: virtual void f() { cout << "P::f"; }// (3) }; class C : public P { public: virtual void f() { cout << "C::f"; } // (4) };
P* p = new P; // static and dynamic P* C* c = new C; // static and dynamic C* P* pc = new C; // static P*, dynamic C* f(p); // f(P*) f(c); // f(C*) f(pc); // f(P*) p->f(); // P::f c->f(); // C::f pc->f(); // C::f
Point* move(Point* p, int d); // require int Point::x Point* move(Point* p, int d) { p.x += d; return p; }
template< class T > // requires T::value() class P { public: P(T& r) : t(r) {} int operator==( P& p) { return t.value() == p.t.value(); } private: T& t; };
template< class T > class A {
A<T>
public: virtual T value() = 0; }; class Int : public A<int> { //Int $<=$ A<int> public: Int(int n = 0) : _n(n) {} int value() { return _n; } private: int _n; };
Int i1, i2; P<Int> p1(i1), p2(i2); if ( p1 == p2 ) cout << "OK" << endl;OK
class event {
event
protected: event(event* x) : ev(x) {} public: int type() { return ev->type(); } void* rawevent() { return ev; } private: event* ev; }; class xevent : public event {
X
public: int type() { return X->type(); } private: struct XEvent* X; };
$T\; =$\ %m\ %a.{ a:int, c:\ %a, b:\ %a->\ %a } $T\_1\; =\; \{\; a:int,\; c:T,\; b:T->T,\; d:bool\; \}$ $T\_2\; =$\ %m\ %a.{ a:int, c:\ %a, b:T->T, d:bool } $T\_3\; =$\ %m\ %a.{ a:int, c:\ %a, b:\ %a->\ %a, d:bool }
$T\_1,\; T\_2\; <=\; T$, $T\_3\; \backslash not<=\; T$ \zline{(contravariance)}
$P\; =\; \%l(\; self\; ).\{\; i\; =\; 5,\; id\; =\; self\; \}$
$C\; =\; \%l(\; self\; ).P(\; self\; )\; \backslash with\; \{\; b\; =\; true\; \}$
$\backslash Y(P):\%t$ where $\%t\; =\; \%m\; \%a.\{\; i:int,\; id:\%a\; \}$ and $P:\%t->\%t$
Simple typing -- $\backslash Y(C):\%s\; =\; \{\; i:int,\; id:\%t,\; b:bool\; \}$
Delayed -- $\backslash Y(C):\%s\text{'}\; =\; \%m\; \%a.\{\; i:int,\; id:\%a,\; b:bool\; \}$
We have $\%s\text{'}\; <=\; \%s$ \zline{(more information)}
$C\; =$\ %l( self ).P( self ) \with { b = true, $eq\; =$\ %l(o).(o.i = self.i and $o.b\; =\; self.b)$ $\}$
$\backslash Y(P)\; :\; \%t$ where
$\%t\; =\; \%m\; \%a.\{\; i:int,\; eq:\%a\; ->\; bool\; \}$
$\backslash Y(C):\%s$ where
$\%s\; =\; \%m\; \%a.\{\; i:int,\; id:\%a\; ->\; bool,\; b:\; bool\; \}$
However $\%s\; \backslash not<=\; \%t$ \zline{(subtyping error)}
F-bounded constraint $\%a\; <=\; F[\%a]$\n
Object instantiation:
$\backslash Y(P[\%s])$ for $\%s\; =\; \%m\; t.F[t]$\n
We have $P[\%s]:\%s\; ->\; F[\%s]$ because $F[\%s]\; =\; \%s$
$P\; =$\ %L\ %a <= F[\ %a].\ %l( self:\ %a).{ ... } $C\; =$\ %L\ %a <= G[\ %a].\ %l( self:\ %a).P[\ %a]( self ) \with { ... }
with recursive types
$F[\%a]\; =\; \{\; i:int,\; id:\%a\; ->\; bool\; \}$
$G[\%a]\; =\; \{\; i:int,\; id:\%a\; ->\; bool,\; b\; :\; bool\; \}$
Valid, because $G[\%a]\; <=\; F[\%a]$
However $\backslash Y(C[\%s])\; \backslash not<=\_\{subtype\}\; \backslash Y(P[\%t])$
class C inherit P redefine eq feature b : Boolean is true; eq( other : like Current ) : Boolean is begin Result := (other.i = Current.i) and (other.b = Current.b) end end C
p,v:P, c:C v:=c; v.eq(p); // error p has no b
class C : public P {
C++
int b; public: C() { ... } bool eq(C& other) { return other.i == i && other.b == b; } bool eq(P& other) { return other.i == i; } };
2
3
4
5
6
As further reading I recommend
draft version 0.1 (15/7/2001)