Re: Static typechecking in OO [was Re: Strong Types ?]

>
> For example assume class hierarchy is like this:
>
> my_base_class <-- my_derived_1 <-- my_subderived_1
> ^ ^
> | |
> my_derived_2 my_subderived_2
> ^
> |
> my_subderived_3


Awesome ascii art :D


> my_base_class is abstract (pure virtual in C++ nomenctalture) so it can not
> have any instances.
>
> my_derived_1 has method foo() while my_derived_2 has method bar() while
> my_base_class has none of those.
>
> Now in one module there is a following definition (using C++ derived
> syntax):
>
> void do_special_thing(virtual my_derived_1 &d1)
> {
> d1.foo();
>
> }
>
> And in some other there is:
>
> void do_special_thing(virtual my_derived_2 &d2)
> {
> d2.bar();
>
> }
>
> So in such a language one could write:
>
> for(polimorphic_container<my_base_class>::iterator i = my_container.begin();
> i != my_container.end();
> ++i)
> {
> do_special_thing(*i);
>
> }


Alas you couldn't. Method overload resolution is performed on the
known type, in this case my_base_class. In this particular example
that would result in a compile time failure as there isn't a
compatible type.


In case I misunderstood, and the virtual modifier in the parameter
list for do_special_thing is telling the compiler to use a more
specific type, the compiler will have to do some form of type check at
runtime for the branching. Essentially the copmiler would be emitting
code like that you have below, all you would have added is syntactic
sugar.


>
> Instead of today's C++:
>
> for(polimorphic_container<my_base_class>::iterator i = my_container.begin();
> i != my_container.end();
> ++i)
> {
> my_derived_1 *d1 = dynamic_cast<my_derived_1*>(&*i);
> if(d1)
> {
> d1->foo();
> }
> else
> {
> static_cast<my_derived_2&>(*i).bar();
> }
>
> }
>
> Notice, that compiler can statically check at every call site if there is no
> such my_base_class subclass for which there is not any matching
> do_special_thing() variant.


The problem is, your generic_list<my_base_class> can contain any of
the subtypes, and the compiler can't determine at compile time what
code to emit.


>
> switch class(obj)
> {
> case my_derived_1:
> obj.foo();
> break;
>
> case my_derived_2:
> obj.bar();
> break;
>
> }
>
> Again, a compiler could (statically) check if above switch covers all the
> possible variants.


The underlying problem with this is the same as above, the type check
is still at runtime. What's changing is the mechanism for it, and
syntax around it.


The reality is that the type system provided by most mainstream
languages, say C++, Java, the CLR, Obj-C cannot be entirely statically
typed due to the ability to downcast. A downcast is intrinsically a
runtime operation.


However there's no actual requirement for an OO type system to provide
support for downcasting. There are people who believe that
downcasting is a sign of bad design even -- and by downcasting they
include any kind of switch on type semantic (though i can't find any
of the "casting considered harmful" pages at the moment).


There are plenty of ways to not use a cast to accomplish something.
In the above example each class would merely have a virtual
do_special_thing method, that just did the appropriate thing
internally. Obviously other cases exist but there are many ways to
get around the problem. A trivial example is walking a tree which can
be done many ways, but the most obvious is the "Visitor Pattern" (
http://en.wikipedia.org/wiki/Visitor_pattern )


All that these mechanisms do use dynamic dispatch (a double dispatch
in the case of the visitor pattern) to perform the switch on type, but
this is sufficient to ensure complete static type safety because at no
point is it necessary to access a concrete type -- eg. a type not
known at compile time.


Of course so far we're just talking about OO type systems in
imperative languages, we can also look at other forms of OO type
system. There are probably a few but I'm familiar (through painful
experience) with that of Haskell.


The Haskell OO system is entirely statically typed (as with the rest
of the language) but has a number of contraints. The most obvious is
that it does not allow any form of downcasting. In most
implementations it would not actually be possible to introduce an
ability to downcast, even if it was desired. Another interesting
difference is that unlike the OO systems from earlier, the OO system
in Haskell (referred to as "Type Classes") completely seperates the
definition of the data type (eg. struct) from the definition of the
class.


A simple Haskell class:


class Comparable a where
    equal :: a->a->Bool
    notEqual :: a->a->Bool


Broadly speak this would be equivalent to
abstract class Comparable<a> {
    Bool equal(a, a);
    Bool notEqual(a,a);
}


Now if we wanted something to actually be comparable, we might go:
instance Comparable Int where
    equal x y = magical code
    notEqual x y = magical code


Now let's add subtyping:
class (Eq a) => Ordinal a where
      lessThan :: a ->a->Bool
      greaterThan :: a->a->Bool


which would be equivalent to
abstract class Ordinal<a> : Comparable<a> {
      Bool lessThan(a, a);
      ...
}


but if we were to look at the underlying types more carefully it would
be represented as
abstract class Ordinal<a> {
    Comparable<a> comparable();
    Bool lessThan(a, a);
    ...
}


So now an *up*cast isn't producing the same pointer -- if you have an
Ordinal type and you want to pass it to a method that expects a
Comparable type you have to pass the comparable member of the instance
of ordinal. This has the critical effect of making a later downcast
completely impossible, and yet Haskell is still used for realworld
applications -- demonstrating that downcasting is unnecessary.


Curiously this mechanism for inheritance is only practically possible
due to the seperation of the class from the data type.


Hmmm... I can't remember what my point was meant to be, but i'll
settle for "look, we can completely statically typecheck an OO
language, if we don't have downcasts"


--Oliver


PS. Oh, Haskell also doesn't have a null value :D

Return to the comp.compilers page.
Search the comp.compilers archives again.