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

oliverhunt@gmail.com wrote:
>>
>> 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.


virtual tells compiler to dispatch on actual (runtime) type.




> Essentially the copmiler would be emitting
> code like that you have below, all you would have added is syntactic
> sugar.


Type checking is not a syntactic sugar. Whether underlying code uses dynamic
or static dispatch is a technical detail. What is important is a static
guarantee that there is no situation where proper dispatch could not be
performed/.




>> 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.


Of course it can. Runtime type dispatch is a thing known for decades.




>> 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.


Type security check is done at compile time and that's what's important.


> What's changing is the mechanism for it, and
> syntax around it.


What's changing is a static guarantee that no type error could occur at
runtime.




> 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.


But static type checking is about guaranteeing that no type errors would
occur at runtime. it's not about banishment of runtime mechanisms.




> 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).


But such checked downcasting does not break static type safety so it


>
> 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


And that's what my example accomplishes -- there is complete static type
safety. There is no way to compile code which then could not dispatch in
runtime. There are executions paths depending on type, but all possible
types are covered.




[Haskell example snipped]


> 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"


Ad mine is that limited (checked) downcasts do not break static type safety
either.


rgds


Sebastian Kaliszewski
--
"Never underestimate the power of human stupidity" / from Notebooks of L.L.

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