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
.

Relevant Pages

  • Coding a translator between languages with high abstraction levels
    ... Language embedded in Haskell, http://www.haskell.org/). ... I don't have much experience in compiler design and development apart ... translator as a Haskell compiler backend (ForSyDe is just Haskell ...
    (comp.compilers)
  • Re: Functional Languages and Java interoperability
    ... ASTs, ... depending on the language. ... Since you mentioned Scala and Haskell, AFAIK there will be no such ... compiler, so there is also not "the" AST of an expression. ...
    (comp.lang.functional)
  • Re: OO in Python? ^^
    ... However, what it's not is manifestly typed - you don't have to put the types in yourself; rather, the compiler works it out. ... There's no way to infer concrete types for h or a, so Haskell gets generic; it says "okay, so i don't know what type a is, but it's got to be something, so let's call it alpha; we're adding two alphas, and one thing i know about adding is that adding two things of some type makes a new thing of that type, so the type of some-alpha + some-alpha is alpha, so this function returns an alpha". ... Laziness is really a property of the implementation, not the the language - in an idealised pure functional language, i believe that a program can't actually tell whether the implementation is eager or lazy. ...
    (comp.lang.python)
  • Re: Functional Languages and Java interoperability
    ... ASTs, ... depending on the language. ... Since you mentioned Scala and Haskell, AFAIK there will be no such ... compiler, so there is also not "the" AST of an expression. ...
    (comp.lang.functional)
  • Re: Static typechecking in OO [was Re: Strong Types ?]
    ... the compiler will have to do some form of type check at ... virtual tells compiler to dispatch on actual type. ... downcasting is a sign of bad design even -- and by downcasting they ... But such checked downcasting does not break static type safety so it ...
    (comp.compilers)