Pure dynamic casts?

[Steven Schveighoffer]

On Tue, 22 Sep 2009 21:21:13 -0400, Jarrett Billingsley  
<jarrett.billingsley at gmail.com> wrote:

> On Tue, Sep 22, 2009 at 8:48 PM, Steven Schveighoffer
> <schveiguy at yahoo.com> wrote:
>
>> Why have pure functions at all?  Seriously, all pure function  
>> reorderings
>> and reuse can be rewritten by human optimization.  If we aren't going to
>> look for places that pure functions can help optimize, why add them to  
>> the
>> language, it seems more trouble than its worth?
>>
>> If all it takes to optimize dynamic casts is to put pure on the function
>> signature, have we wasted that much time?
>
> But dynamic downcasting *isn't* pure, unless you can prove that the
> reference that you're downcasting is unique.
>
> class Base {}
> class Derived : Base {}
>
> struct S
> {
> 	Object o;
>
> 	Derived get()
> 	{
> 		return cast(Derived)o;
> 	}
> }
>
> void main()
> {
> 	S s;
> 	s.o = new Base();
> 	writeln(s.get());
> 	s.o = new Derived();
> 	writeln(s.get());
> }
>
> Dynamic downcasts are not pure. Simply. That's why they're *dynamic*.
> Without some kind of uniqueness typing, you cannot prove anything
> about the validity of such casts until runtime.

You cannot prove what they will return until runtime, but that doesn't  
mean they are not pure.

In your example, you are calling dynamic cast with two different  
references, so you'll get two different results.  The compiler has to be  
able to prove that the dynamic cast call is to the same object, which it  
can't by looking at the code for S.

Imagine a pure function foo, and then a normal function bar:

pure int foo(n) {...}

bar(int n)
{
    int x = foo(n);
}

Can any optimizations be made here?  No, unless you count memoization.   
But we've already established that memoization isn't useful for dynamic  
cast, as it isn't useful for any function that takes a mutable reference.   
It's also difficult to say that memoization is worth the effort without  
profiling.  But if you have the code:

bar(int n)
{
   int x = foo(n);
   x += foo(n);
}

Then you can damn sure optimize out one of those foos.  n didn't change.   
Same goes for dynamic cast.

Part of dynamic cast is easy to be proven pure.  If you imagine dynamic  
cast to be the function:

T dynamicCast(T)(U u)
{
   int offset = getOffset!T(u.classinfo);
   if(offset == CANNOT_CAST)
      return null;
   return cast(T)((cast(void *)u) + offset);
}

The function getOffset returns a constant CANNOT_CAST if the object cannot  
be cast from a U to a T, and returns the offset to add to the reference to  
convert the U to a T otherwise.

Then the function getOffset can be pure, since classinfo's are unique and  
immutable.  That's the expensive part anyways, the rest can be inlined,  
and you then then have a pure dynamic cast function, because you are  
calling dynamicCast with the same parameter over and over.

-Steve