<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Feb 5, 2017, at 5:36 PM, Abe Schneider via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi Robert,<div class=""><br class=""></div><div class="">Exactly. The benefit being that you can figure out the correct function to dispatch entirely at compile time. My understanding is that Swift doesn’t do this because of the associated code bloat (and it’s usually not necessary). However, I think there is some important functionality by allowing specialization to control dispatch in a similar way to c++. There is also the design element — my (fairly) succinct Tensor class that used to be ~300 lines is now already close to an additional 1000 lines of code and growing. While the type of library I’m writing might be outside of what is normally done with Swift, I suspect the design pattern I’m using crops up in other places, as well as the need for dispatch on specialization (e.g. <a href="http://stackoverflow.com/questions/41640321/extending-collection-with-a-recursive-property-method-that-depends-on-the-elemen" class="">http://stackoverflow.com/questions/41640321/extending-collection-with-a-recursive-property-method-that-depends-on-the-elemen</a>).</div></div></div></blockquote><div><br class=""></div><div>You can’t figure out the correct function to dispatch entirely at compile time because Swift supports retroactive modeling. Let’s make this a super-simple example:</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>// Module A</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>public protocol P { }</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>public func f<T>(_:T) { print(“unspecialized”) }</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>public func f<T: P>(_: T) { print(“specialized”) }</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>public func g<T>(_ x: T) { f(x) }</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>// Module B</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>import A</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>func testG(x: Int) {</div><div><span class="Apple-tab-span" style="white-space:pre"> </span> g(x) // the best we can statically do is print “unspecialized”; Int doesn’t conform to A.P, but...</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>}</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>// Module C</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>import A</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>public extension A: P { } // dynamically, Int does conform to A.P!</div><div><br class=""></div><div>Swift’s model is that the selection among ad hoc overloads is performed statically based on local knowledge, and is consistent across all “specializations” of a generic function. Protocol requirements and overridable methods are the customization points.</div><div><br class=""></div><div>Selecting ad hoc overloads at runtime is possible, but of course it has downsides. You could run into run-time ambiguities, for example:</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>// Module A</div><div><div><span class="Apple-tab-span" style="white-space: pre;"> </span>public protocol P { }</div><div><span class="Apple-tab-span" style="white-space: pre;"> </span>public protocol Q { }</div><div><span class="Apple-tab-span" style="white-space: pre;"> </span>public func f<T>(_:T) { print(“unspecialized”) }</div><div><span class="Apple-tab-span" style="white-space: pre;"> </span>public func f<T: P>(_: T) { print(“specialized for P”) }</div><div class=""><div><span class="Apple-tab-span" style="white-space: pre;"> </span>public func f<T: Q>(_: T) { print(“specialized for Q”) }</div></div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space: pre;"> </span>public func g<T>(_ x: T) { f(x) }</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>// Module B</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>import A</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>public extension Int: P { }<span class="Apple-tab-span" style="white-space:pre"> </span></div><div class=""><br class=""></div><div class=""><div><span class="Apple-tab-span" style="white-space: pre;"> </span>// Module C</div><div><span class="Apple-tab-span" style="white-space: pre;"> </span>import A</div><div><span class="Apple-tab-span" style="white-space: pre;"> </span>public extension Int: Q { }<span class="Apple-tab-span" style="white-space: pre;"> </span></div></div><div class=""><br class=""></div></div><div><div><span class="Apple-tab-span" style="white-space: pre;"> </span>// Module C</div><div><span class="Apple-tab-span" style="white-space: pre;"> </span>import A</div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span>func testG(x: Int) {</div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span> g(x) // run-time ambiguity: which specialized “f” do we get?</div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</div><div class=""><br class=""></div><div class="">There are reasonable answers here if we know what the potential set of overloads is at compile-time. It’s a problem I’ve been interested in for a <a href="https://parasol.tamu.edu/~jarvi/papers/pldi06.pdf" class="">long time</a>. That dynamic dispatch can be implemented somewhat reasonably (the compiler can emit a static decision tree so long as we’re willing to limit the set of overloads to the ones that are visible from g(_:), and can be folded away by the optimizer when we’re specializing the function and the visibility of the types and/or protocols in question is limited.</div><div class=""><br class=""></div></div><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">As far as changes to Swift, `@_specialize` already does exactly this (except it is treated as a hint). You would need to transform the function to something like <function-name>_<mangled-type-name>(…) and a table of transformed functions, but after that you can just treat the functions as normal functions (and ignore the fact they were defined as generic). So, yes, specializations should be forced at every level. While this will lead to some code bloat, since it only occurs for the functions marked by the user, I would imagine it’s: (a) limited to the extent it occurs; and (b) manageable by simply not using the attribute (and using protocol witness tables instead). But at least that way you give the user the choice to do what is best for the particular situation.</div></div></div></blockquote><div><br class=""></div>For reference, `@_specialize` is doing dynamic dispatch. That dynamic dispatch gets optimized away when we specialize the generic function, the same way I mentioned about.</div><div><br class=""></div><div>There might be a reasonable solution to the problem you’re encountering. I don’t think it’s “force specialization at compile time like C++”, but something akin to grouping together multiple overloads where we want dynamic dispatch of callers that invoke them, statically diagnosing when that set of overloads can have ambiguities in it (see the paper I referenced above), and teaching the optimizers to resolve that dynamic dispatch statically whenever possible.</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>- Doug</div><div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><br class=""></div><div class="">Thanks!</div><div class="">A</div><div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Feb 5, 2017, at 1:46 PM, Robert Widmann <<a href="mailto:devteam.codafi@gmail.com" class="">devteam.codafi@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="content-type" content="text/html; charset=utf-8" class=""><div dir="auto" class=""><div class=""><span class=""></span></div><div class=""><div class=""><div class="">Oh, I see. The constraint solver is picking an overload that better matches the caller rather than the callee's type, which differs from C++ because the template expansion process considers specific-type overloads more specific. We don't consider less-generic prototypes than the caller here because we aren't performing a (major) syntactic transformation in the process of solving a system of type variables. In order to change the language to adopt this feature, Sema would have to have knowledge of the candidate set of specializations, either user-specified or SILOptimizer-generated, beforehand. It's not impossible to imagine, but it does create an interesting backdependency on future potential optimizations, and would potentially majorly change the behavior of a Debug or Release build (unless specialization were forced at all optimization levels).</div><div class=""><br class=""></div></div><div class="">~Robert Widmann</div><div class=""><br class="">2017/02/05 12:37、Abe Schneider <<a href="mailto:abe.schneider@gmail.com" class="">abe.schneider@gmail.com</a>> のメッセージ:<br class=""><br class=""></div><blockquote type="cite" class=""><div class="">Hi Robert,<br class=""><br class="">Sorry, I’m not sure I understand your question. In c++ you can do the following:<br class=""><br class=""><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class="">struct Storage {};</blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class="">struct CBlasStorage: Storage {};</blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><br class="">template <typename S> class Tensor {};</blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><br class="">template <typename S><br class="">Tensor<S> dot(const Tensor<S> &lhs, const Tensor<S> &rhs) {<br class=""> std::cout << "general version called" << std::endl;<br class=""> Tensor<S> result;<br class=""> return result;<br class="">}</blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><br class=""></blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class="">// specialized version for CBlasStorage<br class="">template <><br class="">Tensor<CBlasStorage> dot(const Tensor<CBlasStorage> &lhs, const Tensor<CBlasStorage> &rhs) {<br class=""> std::cout << "specialized version called" << std::endl;<br class=""> Tensor<CBlasStorage> result;<br class=""> return result;<br class="">}</blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><br class="">// this preserves type information and will call the appropriate `dot`<br class="">template <typename T><br class="">void doSomething(const Tensor<T> &lhs, const Tensor<T> &rhs) {<br class=""> auto result = dot(lhs, rhs);<br class="">}</blockquote><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><br class="">int main(int argc, char **argv) {<br class=""> Tensor<CBlasStorage> a, b;<br class=""> doSomething(a, b); // we should get "specialized version called"<br class="">}</blockquote><div class=""><br class=""></div><div class=""><br class=""></div>The potential equivalent for Swift could look like:<div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class="">@_specialize_all</div><div class="">func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }</div></blockquote><div class=""><br class=""></div>Which would cause the compile to create a version of `dot` per S type that it gets called with. Thus, when `doSomething` is called, it would dispatch to that version of `dot`, allowing the type information to be preserved in the same way it does in c++.<div class=""><br class=""></div><div class="">Abe<br class=""><div class=""><br class=""><blockquote type="cite" class="">On Feb 5, 2017, at 11:35 AM, Robert Widmann <<a href="mailto:devteam.codafi@gmail.com" class="">devteam.codafi@gmail.com</a>> wrote:<br class=""><br class="">I don't understand how this change would cause method dispatch to invoke a different prototype. Specialization in either language mentioned doesn't do that.<br class=""><br class="">~Robert Widmann<br class=""><br class="">2017/02/05 11:28、Abe Schneider via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> のメッセージ:<br class=""><br class=""><blockquote type="cite" class="">Hi all,<br class=""><br class="">The current behavior of generics in Swift causes it lose type information at compile time due to the desire of maintaining a single version of the function. This runs counter to how c++ works, which creates a new copy of a function per type, but preserves information to be preserved. This can cause unexpected behavior from the user’s perspective:<br class=""><br class=""> protocol DispatchType {}<br class=""> class DispatchType1: DispatchType {}<br class=""><br class=""> func doBar<D:DispatchType>(value:D) { <br class=""> print(“General function called")<br class=""> }<br class=""><br class=""> func doBar(value:DispatchType1) {<br class=""> print("DispatchType1 called")<br class=""> }<br class=""><br class=""> func test<D:DispatchType>(value:D) {<br class=""> doBar(value: value)<br class=""> }<br class=""><br class=""> test(value: d1) // “General function called”, but it’s not obvious why<br class=""><br class=""><br class="">The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and (b) there are some designs in which this behavior can complicate things.<br class=""><br class="">One example of a design where this behavior can be problematic is when a protocol is used to determine what functions get dispatched:<br class=""><br class=""> protocol Storage { … }<br class=""> class Tensor<S:Storage> { … }<br class=""><br class=""> class CBlasStorage: Storage { … }<br class=""> class OpenCLStorage: Storage { … }<br class=""><br class=""> func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }<br class=""><br class=""> // like behavior, these will not work if called from another generic function (but will work for non-generic functions)<br class=""> func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:CBlasStorage { … }<br class=""> func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:OpenCLStorage { … }<br class=""><br class="">In this case, depending on the underlying storage, we want an optimized version of `dot` to be called. To make this work correctly we can add static methods to `Tensor`, but this has several drawbacks: (a) it makes the `Tensor` class monolithic, every possible method must be determine a priori and be defined in the class; (b) it doesn’t allow new methods to be added Tensor without touching the main class; and (c) it unnecessarily forces users to user the more verbose `Tensor.dot(a, b)`.<br class=""><br class="">Point (a) in theory could be made better by creating a `TensorOps` protocols. However, because type constraints cannot currently be placed on extensions, it is not currently possible to implement.<br class=""><br class=""><br class="">One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.<br class=""><br class=""><br class="">Thanks!<br class="">Abe<br class="">_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class=""><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" class="">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class=""></blockquote></blockquote><br class=""></div></div></div></blockquote></div></div></div></blockquote></div><br class=""></div></div>_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></blockquote></div><br class=""></body></html>