How to dynamically dispatch extension methods?

Question

Swift allows you to define extension methods on any type or protocol. While extension methods on protocols are frequently used to provide default implementations, only methods listed in the main protocol body can go in the vtable, since you can define an extension method from anywhere. Consider this code:

// module A
public protocol AProtocol {
  func getSomeNumber() -> Int
}

public struct ExampleImplementation: AProtocol {
  public func getSomeNumber() -> Int { 4 }
}

// module B
import A

extension AProtocol {
  public func getSomeText() -> String {
    getSomeNumber().description
  }
}

public func printThing(_ x: some AProtocol) {
  print(x.getSomeText())
}

// module C
import A
import B

struct ActualImplementation: AProtocol {
  func getSomeNumber() -> Int { 5 }
  func getSomeText() -> String { "five" }
}

let x = ActualImplementation()
print(x.getSomeText()) // static lookup finds ActualImplementation.getSomeText and prints "five"
printThing(x) // since getSomeText isn't defined in module A, it's not in the vtable
              // so this uses the implementation from the extension and prints "5"

C#'s extension methods are just syntax sugar for static method calls and are resolved at compile time, so the equivalent code would also demonstrate this behavior in C#. Both Swift and C# have a concept of ABI stability and allow libraries to be distributed in binary form, so compile-time templates are a non-starter for these languages.

How could extension methods be dynamically dispatched in a language that allows binary dependencies?

Answer 1

Objective-C's solution

Objective-C is insane.

Background

You know, say, C# dynamic? How every method call needs to be dynamically dispatched because you have no idea what it is at compile time? Objective-C is like that. Due to things like method swizzling and runtime class registration, it's impossible to know what the implementation is at compile time even when you know the type and method name. All method calls compile down to a call to objc_msgSend(self, _cmd, ...) or one of its relatives.

Objective-C does dynamic dispatch of extension methods, just like we want! Apple's implementation is naturally closed-source, so let's look at GNUStep's implementation. methodForSelector: calls out to objc_msg_lookup. It has a lot of handling of various cases (e.g. the class object hasn't been initialized yet) but the core of it is just two lines:

    Class class = classForObject((*receiver));
    struct objc_slot2 * result = objc_dtable_lookup(class->dtable, selector->index);

What is a selector?

In Smalltalk and Objective-C, a selector is a representation of a method name. In Objective-C, the type of a selector is SEL, which is a pointer to an opaque struct. But we're looking at GNUStep -- we have an implementation of that struct! And what I found blew my mind:

struct objc_selector
{
    union
    {
        const char *name;
        uintptr_t index;
    };
    const char * types;
};

The first member of the struct is a C string containing the actual method name. I already knew that SEL stores the name somehow, so this much is not a surprise to me. But it's also an index into a sparse array! That objc_dtable_lookup is just a macro that expands to SparseArrayLookup. If I understand the comments correctly, the index being the actual pointer to the name is only for selectors created at runtime; selectors known to exist at compile/link time are packed into the dtable then.

So, how does it actually work?

Every selector is a unique number -- the hashing can be done at compile time rather than runtime, which means there's no need for the memory footprint and runtime slowdown of a hash table. If your language supports dynamic linking or creating methods at runtime, you may have to take care that new methods can be added without conflicts, such as by using a sparse array indexed on the method name.

Answer 2

I don't see much problem in adding extension methods to a vtable per se, it can work pretty much like usual inheritance. There's not so much difference between

public protocol AProtocol {
  func getSomeNumber() -> Int
}

extension AProtocol {
  public func getSomeText() -> String {
    getSomeNumber().description
  }
}

and

public interface A {
  public Int getSomeNumber();
}

public interface B extends A {
  public String getSomeText() {
    return this.getSomeNumber().toString();
  }
}

to me. In principle they can be compiled the same.

Funny things start happening when you have multiple inheritance, but both C++ and Java (with interfaces with default implementations) have solutions, albite different ones.

Alternatively you can pretty much side-step the problems altogether separating vtable from an object. That's the default implementation strategy for type classes (in Haskell and other languages) thus I heard it dubbed "type class pattern", but others call it "fat pointers". I think Laurence Tratt did a great job explaining how it works and how it compares to usual vtables using Rust for examples.