<p>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:</p>
<pre class="lang-swift prettyprint-override"><code>// module A
public protocol AProtocol {
  func getSomeNumber() -&gt; Int
}

public struct ExampleImplementation: AProtocol {
  public func getSomeNumber() -&gt; Int { 4 }
}

// module B
import A

extension AProtocol {
  public func getSomeText() -&gt; String {
    getSomeNumber().description
  }
}

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

// module C
import A
import B

struct ActualImplementation: AProtocol {
  func getSomeNumber() -&gt; Int { 5 }
  func getSomeText() -&gt; String { &quot;five&quot; }
}

let x = ActualImplementation()
print(x.getSomeText()) // static lookup finds ActualImplementation.getSomeText and prints &quot;five&quot;
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 &quot;5&quot;
</code></pre>
<p>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.</p>
<p>How could extension methods be dynamically dispatched in a language that allows binary dependencies?</p>

<dynamic-dispatch><extension-methods>
How to dynamically dispatch extension methods?
CC BY-SA 4.0
2023-05-23T18:33:27.413Z
What do you mean by "binary dependencies"? Do you need a different solution than the one(s) that C# and Swift use?
RubenVerg
CC BY-SA 4.0
2023-05-23T18:34:40.663Z
If a library is distributed in source, it may be possible to add these to the vtable at compile time, since the compiler will be able to see all extension methods at once. If module A is compiled as a binary dependency, however, it can’t know what extension methods its consumers may define.
Bbrk24
CC BY-SA 4.0
2023-05-23T18:40:58.190Z
oh, right. somehow I interpreted "binary" as two-fold and not as compiled. I still can't tell if the C# and Swift solutions are fine and you are looking for alternatives, or if those are incompatible with your needs.
RubenVerg
CC BY-SA 4.0
2023-05-23T18:43:49.073Z
I am specifically looking for something that allows dynamic dispatch of, in this case `getSomeText()`, even when module A and/or module B are binary dependencies — which is something Swift and C# can’t do.
Bbrk24
CC BY-SA 4.0
2023-05-23T18:53:00.227Z
Is `getSomeText()` actually dispatched dynamically? It seems since it's implemented in terms of the underlying interface that it would be dispatched statically and only the call to `getSomeNumber()` would be dynamic. Or could it be overridden by other implementations of the protocol?
chrysante
CC BY-SA 4.0
2023-05-23T19:11:28.110Z
@chrysante What you’ve described (static dispatch) is how it actually works in these languages, yes. However, that’s not the behavior I want.
Bbrk24
CC BY-SA 4.0
2023-05-23T19:19:06.137Z
Okay now I get it. Maybe you can have a hashtable indexed with the mangled name or some other type id for each 'extension protocol' that maps to the required vtable? That table could then reside in the binary of module B. I also want to solve a similar problem in my language however but I'm afraid the dispatch through hashtables might be very slow. But adding new v-pointers to the objects in the already compiled binary is of course not possible...
chrysante
CC BY-SA 4.0
2023-05-23T19:47:28.100Z
Dirty solution: subclasses? Maybe all classes can have a static variable through which an extension class defined in another library would be defined, so that if you try to construct a class in a project that has brought in an extension class, instead of the original constructor being called the extension is called which would then have the extended VTable? This might only work for _one_ extension class though.
kouta-kun
CC BY-SA 4.0
2023-05-23T20:01:27.007Z
Since method names are known at compile time, the hashtable could use pointers to interned strings rather than actually hashing the string’s contents, which should speed it up a bit.
Bbrk24
CC BY-SA 4.0
2023-05-23T21:00:06.923Z
@kouta-kun It might be possible to make that work for multiple extensions if you make it a linked list instead of a single vtable. Each extension vtable starts with its module ID and a pointer to the next vtable in the list. Not sure how that would compare performance-wise to a hashmap.
Bbrk24
<h1>Objective-C's solution</h1>
<p>Objective-C is insane.</p>
<h2>Background</h2>
<p>You know, say, C# <code>dynamic</code>? 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 <code>objc_msgSend(self, _cmd, ...)</code> or one of its relatives.</p>
<p>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. <code>methodForSelector:</code> calls out to <code>objc_msg_lookup</code>. It has a lot of handling of various cases (e.g. the class object hasn't been initialized yet) but <a href="https://github.com/gnustep/libobjc2/blob/71e38a048fc06fea0c2015662540d46a33b5c45d/sendmsg2.c#L98" rel="noreferrer">the core of it</a> is just two lines:</p>
<pre class="lang-objectivec prettyprint-override"><code>    Class class = classForObject((*receiver));
    struct objc_slot2 * result = objc_dtable_lookup(class-&gt;dtable, selector-&gt;index);
</code></pre>
<h2>What <em>is</em> a selector?</h2>
<p>In Smalltalk and Objective-C, a selector is a representation of a method name. In Objective-C, the type of a selector is <code>SEL</code>, which is a pointer to an opaque struct. But we're looking at GNUStep -- we <em>have</em> an implementation of that struct! And <a href="https://github.com/gnustep/libobjc2/blob/71e38a048fc06fea0c2015662540d46a33b5c45d/selector.h#L8" rel="noreferrer">what I found</a> blew my mind:</p>
<pre class="lang-c prettyprint-override"><code>struct objc_selector
{
    union
    {
        const char *name;
        uintptr_t index;
    };
    const char * types;
};
</code></pre>
<p>The first member of the struct is a C string containing the actual method name.  I already knew that <code>SEL</code> stores the name somehow, so this much is not a surprise to me. But it's <em>also</em> an index into a sparse array! That <code>objc_dtable_lookup</code> is <a href="https://github.com/gnustep/libobjc2/blob/71e38a048fc06fea0c2015662540d46a33b5c45d/dtable.h#L14" rel="noreferrer">just a macro</a> that expands to <code>SparseArrayLookup</code>. 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.</p>
<h2>So, how does it actually work?</h2>
<p>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.</p>

CC BY-SA 4.0
2023-05-23T22:16:40.220Z
2023-05-24T22:53:40.300Z
2023-05-24T22:53:40.300Z
Bbrk24
<p>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</p>
<pre class="lang-swift prettyprint-override"><code>public protocol AProtocol {
  func getSomeNumber() -&gt; Int
}

extension AProtocol {
  public func getSomeText() -&gt; String {
    getSomeNumber().description
  }
}
</code></pre>
<p>and</p>
<pre class="lang-java prettyprint-override"><code>public interface A {
  public Int getSomeNumber();
}

public interface B extends A {
  public String getSomeText() {
    return this.getSomeNumber().toString();
  }
}
</code></pre>
<p>to me. In principle they can be compiled the same.</p>
<p>Funny things start happening when you have <em>multiple</em> inheritance, but both C++ and Java (with interfaces with default implementations) have solutions, albite different ones.</p>
<p>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 &quot;type class pattern&quot;, but others call it &quot;fat pointers&quot;. I think <a href="https://tratt.net/laurie/blog/2019/a_quick_look_at_trait_objects_in_rust.html" rel="nofollow noreferrer">Laurence Tratt</a> did a great job explaining how it works and how it compares to usual vtables using Rust for examples.</p>

CC BY-SA 4.0
2023-05-25T08:41:52.297Z
2023-05-25T08:41:52.297Z
Alex Chichigin
CC BY-SA 4.0
2023-05-25T11:18:44.097Z
See, the thing that makes extensions different from subclasses is that it adds to existing objects. If I model extensions as subclasses, then factory methods in module A would create objects without the extension methods, which definitely isn’t what I want.
Bbrk24
CC BY-SA 4.0
2023-05-26T15:33:46.150Z
@Bbrk24 it can work differently if you detach the vtable from an object as per the last paragraph. In that case your factory method will simply create the objects (without vtables at all) and the logic in other modules can use whatever else mechanism necessary to construct or find the right vtable for that object with all the right extension methods that are known at that point.
Alex Chichigin
# How to dynamically dispatch extension methods?
Posted by: username_0 on 2023-05-23
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?
**Tags:** dynamic-dispatch extension-methods
> **Comments:**
> **username_1**: What do you mean by "binary dependencies"? Do you need a different solution than the one(s) that C# and Swift use?  
> **username_0**: If a library is distributed in source, it may be possible to add these to the vtable at compile time, since the compiler will be able to see all extension methods at once. If module A is compiled as a binary dependency, however, it can’t know what extension methods its consumers may define.  
> **username_1**: oh, right. somehow I interpreted "binary" as two-fold and not as compiled. I still can't tell if the C# and Swift solutions are fine and you are looking for alternatives, or if those are incompatible with your needs.  
> **username_0**: I am specifically looking for something that allows dynamic dispatch of, in this case `getSomeText()`, even when module A and/or module B are binary dependencies — which is something Swift and C# can’t do.  
> **username_2**: Is `getSomeText()` actually dispatched dynamically? It seems since it's implemented in terms of the underlying interface that it would be dispatched statically and only the call to `getSomeNumber()` would be dynamic. Or could it be overridden by other implementations of the protocol?  
> **username_0**: @chrysante What you’ve described (static dispatch) is how it actually works in these languages, yes. However, that’s not the behavior I want.  
> **username_2**: Okay now I get it. Maybe you can have a hashtable indexed with the mangled name or some other type id for each 'extension protocol' that maps to the required vtable? That table could then reside in the binary of module B. I also want to solve a similar problem in my language however but I'm afraid the dispatch through hashtables might be very slow. But adding new v-pointers to the objects in the already compiled binary is of course not possible...  
> **username_3**: Dirty solution: subclasses? Maybe all classes can have a static variable through which an extension class defined in another library would be defined, so that if you try to construct a class in a project that has brought in an extension class, instead of the original constructor being called the extension is called which would then have the extended VTable? This might only work for _one_ extension class though.  
> **username_0**: Since method names are known at compile time, the hashtable could use pointers to interned strings rather than actually hashing the string’s contents, which should speed it up a bit.  
> **username_0**: @kouta-kun It might be possible to make that work for multiple extensions if you make it a linked list instead of a single vtable. Each extension vtable starts with its module ID and a pointer to the next vtable in the list. Not sure how that would compare performance-wise to a hashmap.  
---
## 2 answers
### Answer by username_0 on 2023-05-23. Score: 6
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 by username_4 on 2023-05-25. Score: 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.
> **Comments:**
> **username_0** (2023-05-25): See, the thing that makes extensions different from subclasses is that it adds to existing objects. If I model extensions as subclasses, then factory methods in module A would create objects without the extension methods, which definitely isn’t what I want.  
> **username_4** (2023-05-26): @Bbrk24 it can work differently if you detach the vtable from an object as per the last paragraph. In that case your factory method will simply create the objects (without vtables at all) and the logic in other modules can use whatever else mechanism necessary to construct or find the right vtable for that object with all the right extension methods that are known at that point.  
---
