[Cython] Cython, Go and static duck typing

[Dag Sverre Seljebotn]

On 08/13/2011 02:28 PM, Stefan Behnel wrote:
> Dag Sverre Seljebotn, 13.08.2011 13:09:
>> I read up on Go's interface model last week and am very excited about it.
>> Perhaps this was old news to a lot of you, but it was new to me.
>>
>> This post is mostly just to make sure everybody is aware of prior art
>> here
>> in case it is a good fit for Cython down the road. I hope I'm not
>> starting
>> a long wasteful thread, let's keep it FYI, and if it's interesting I can
>> try to learn a bit more of the technical details and write up a CEP prior
>> to next summer's GSoC or something...
>>
>> The idea of polymorphism in Go might be phrased in the Cython language
>> as:
>>
>> cdef interface Walker:
>> int walk(float)
>>
>> cdef class Foo: # note: Does not inherit from Walker!
>> cdef int walk(self, float length):
>> ....
>>
>>
>> def f(Walker obj):
>> obj.walk(2.3)
>>
>> f(Foo())
>>
>> This is duck typing, in the sense that Foo has no knowledge of the Walker
>> interface (at module compilation time) -- it just satisfies it by
>> implementing the same interface. The point of casting/conversion has all
>> the information needed to build the vtable (somehow...). This of course
>> uses a little more memory, but it is still bounded by the number of code
>> lines you could write...
>>
>> This has a lot more flexibility (libraries don't have to agree on
>> which one
>> should have the "ultimate superclass", they can just agree on method
>> names), and it just fits my brain and workflow much better as well:
>> I'd use
>> profiling to pinpoint the spots where I really need a vtable instead of
>> dict lookups, and then it is more natural to introduce the interface
>> in the
>> caller, rather than to go back into the callee to introduce a type
>> hierarchy (which might be more geared towards optimizing calls than
>> towards
>> what type relation is "natural").
>>
>> Implementing this in Cython is likely going to be tougher than in Go
>> if we
>> want to support <Walker>obj, where obj has type "object", and not only
>> <Walker><Foo>obj. But I'd think it is not impossible, just somewhat more
>> costly on assignment...but that is often amortized over multiple calls.
>
> I like that. However, I also agree that it will be tricky to implement
> in C. Think of this case:
>
> cdef class X:
> cdef int walk(self, float length):
> ...
>
> cdef class Y:
> pass
>
> cdef class Z(Y):
> cdef int walk(self, float length):
>
> Here, the method is in two different places of the vtable in both cases,
> so the necessary access code in C would need to be different.

Yup, vtables must be generated on "cast sites" (but see below), and then 
I suppose passing around interface references would pass around two 
pointers, a vtable pointer and the "self" object.

> Go has the advantage of using static typing, so the type of the values
> that is being passed into the interface variable is always known. It may
> not be known in Cython or Python.

True, but I don't think this is a serious obstacle. Here's one scheme:

a) Each interface is given an unique ID. By resolving this at module 
load time it should be sufficient with 32-bit IDs.

b) Keep a hash table for each cdef class, which can be pointed to by the 
object. It'd be our own custom implementation designed for looking up by 
32-bit ints, so no string compares etc.

c) If there's a miss (which happens almost never), one needs to generate 
a vtable from some RTTI of the cdef class. This vtable stays allocated 
for the duration of the process, and is probably used by "cast sites" as 
well (at module load time).

It doesn't have all the details but I think it shows that it should be 
fast enough even without fully static typing.

Dag Sverre