The two concepts are very very similar. In normal OOP languages, we attach a vtable (or for interfaces: itable) to each object:
| V | a | b | the object with fields a, b
| o | p | q | the vtable with method slots o(), p(), q()
This allows us to invoke methods similar to
In Haskell, the method table is more like an implicit hidden argument:
method :: Class a => a -> a -> Int
would look like the C++ function
int method(Class<A>*, A*, A*)
Class<A> is an instance of typeclass
Class for type
A. A method would be invoked like
The instance is separate from the values. The values still retain their actual type. While typeclasses allow some polymorphism, this is not subtyping polymorphism. That makes it impossible to make a list of values that satisfy a
Class. E.g. assuming we have
instance Class Int ... and
instance Class String ..., we cannot create a heterogeneous list type like
[Class] that has values like
[42, "foo"]. (This is possible when you use the “existential types” extension, which effectively switches to the Go approach).
In Go, a value doesn't implement a fixed set of interfaces. Consequently it can't have a vtable pointer. Instead, pointers to interface types are implemented as fat pointers that include one pointer to the data, another pointer to the itable:
`this` fat pointer
| | |
| o | p | q | | a | b | the data with
+---+---+---+ +---+---+ fields a, b
itable with method
slots o(), p(), q()
The itable is combined with the data into a fat pointer when you cast from an ordinary value to an interface type. Once you have an interface type, the actual type of the data has become irrelevant. In fact, you can't access the fields directly without going through methods or downcasting the interface (which may fail).
Go's approach to interface dispatch comes at a cost: each polymorphic pointer is twice as large as a normal pointer. Also, casting from one interface to another involves copying the method pointers to a new vtable. But once we've constructed the itable, this allows us to cheaply dispatch method calls to many interfaces, something which traditional OOP languages suffer with. Here, m is the number of methods in the target interface, and b is the number of base classes:
- C++ does object slicing or needs to chase virtual inheritance pointers when casting, but then has simple vtable access. O(1) or O(b) cost of upcasting, but O(1) method dispatch.
- The Java Hotspot VM doesn't have to do anything when upcasting, but upon interface method lookup does a linear search through all itables implemented by that class. O(1) upcasting, but O(b) method dispatch.
- Python doesn't have to do anything when upcasting, but uses a linear search through a C3-linearized base class list. O(1) upcasting, but O(b²) method dispatch? I'm not sure what the algorithmic complexity of C3 is.
- The .NET CLR uses an approach similar to Hotspot but adds another level of indirection in an attempt to optimize for memory usage. O(1) upcasting, but O(b) method dispatch.
The typical complexity for method dispatch is much better since method lookup can often be cached, but the worst case complexities are quite horrible.
In comparison, Go has O(1) or O(m) upcasting, and O(1) method dispatch. Haskell has no upcasting (constraining a type with a type class is a compile-time effect), and O(1) method dispatch.