<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=""><div><blockquote type="cite" class=""><div class="">On Mar 13, 2017, at 8:55 AM, Dimitri Racordon via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Hello fellow evolutionists,</div>
<div class=""><br class="">
</div>
<div class="">I’m not sure this list is the best place to talk about this, so please redirect me if it should be discussed elsewhere.</div></div></div></blockquote><div><br class=""></div>More of a swift-dev topic. CC'ing there, BCC'ing evolution.</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="">While trying to implement algebraic data types in Swift, I stumble upon an interesting problem. Let’s consider the following example:</div>
<div class=""><br class="">
</div>
<div class="">
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">protocol</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Term {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">struct</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Zero:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">struct</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Succ:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> pred:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">var</span><span style="font-variant-ligatures: no-common-ligatures" class=""> term:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Zero</span><span style="font-variant-ligatures: no-common-ligatures" class="">()</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">for</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">_</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">in</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">0</span><span style="font-variant-ligatures: no-common-ligatures" class=""> ..<
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">20000</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Succ</span><span style="font-variant-ligatures: no-common-ligatures" class="">(</span><span style="font-variant-ligatures: no-common-ligatures" class="">pred:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">term</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
</div>
<div class=""><br class="">
</div>
<div class="">This code will take forever to execute (about 1 minute on my mbp late 2013), whereas if I replace the structures with reference types it will finish almost instantly, which is what one would expect from such a simple data structure. Most likely,
the problem lays in the fact that a deep copy is produced every time a new level of recursion is created. However, I guess this case could be detected by the compiler, as the `term` variable passed as parameter is immediately affected to the rvalue of the
expression using it.</div>
<div class=""><br class="">
</div>
<div class="">An even more powerful approach would be to keep track of the reference on the original `term` value under the hood, and update it if necessary in a copy-on-write fashion. As I understand it, this would enable this code to be efficiently executed
as well:</div></div></div></blockquote><div><br class=""></div>Yes, this is something we're already looking at doing in general for this kind of "existential" use of a protocol, precisely because of this kind of nested-type problem.</div><div><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="">
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">protocol</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Term {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">struct</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Leaf:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">struct</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Tree:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> left:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> right:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">var</span><span style="font-variant-ligatures: no-common-ligatures" class=""> tree:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Leaf</span><span style="font-variant-ligatures: no-common-ligatures" class="">()</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">for</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">_</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">in</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">0</span><span style="font-variant-ligatures: no-common-ligatures" class=""> ..<
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">20000</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">tree</span><span style="font-variant-ligatures: no-common-ligatures" class=""> =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Tree</span><span style="font-variant-ligatures: no-common-ligatures" class="">(left:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">tree</span><span style="font-variant-ligatures: no-common-ligatures" class="">, right:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">tree</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
</div>
<div class=""><br class="">
</div>
<div class="">Interestingly, while enumerations are value types, indirect enumerations don’t suffer the performance issue of the above examples. Note however that the issue will reappear if the enum isn’t marked `indirect`.</div>
<div class=""><br class="">
</div>
<div class="">
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">protocol</span><span style="font-variant-ligatures: no-common-ligatures" class=""> Term {}</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(186, 45, 162);" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">indirect</span><span style="font-variant-ligatures: no-common-ligatures;" class="">
</span><span style="font-variant-ligatures: no-common-ligatures" class="">enum</span><span style="font-variant-ligatures: no-common-ligatures;" class=""> Nat:
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures;" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">case</span><span style="font-variant-ligatures: no-common-ligatures" class=""> zero</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">case</span><span style="font-variant-ligatures: no-common-ligatures" class=""> succ(</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Term</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div></div></div></div></blockquote><div><br class=""></div>I do have to note that this is a very strange of writing Nat. Why recurse through a protocol type instead of recursing concretely?</div><div><br class=""></div><div>John.</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="">
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class="">
</div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">var</span><span style="font-variant-ligatures: no-common-ligatures" class=""> term =
</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Nat</span><span style="font-variant-ligatures: no-common-ligatures" class="">.</span><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">zero</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">for</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">_</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #ba2da2" class="">in</span><span style="font-variant-ligatures: no-common-ligatures" class="">
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">0</span><span style="font-variant-ligatures: no-common-ligatures" class=""> ..<
</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">20000</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">term</span><span style="font-variant-ligatures: no-common-ligatures" class=""> = .</span><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">succ</span><span style="font-variant-ligatures: no-common-ligatures" class="">(</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">term</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div>
<div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">
<span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div>
</div>
<div class=""><br class="">
</div>
Thanks,
<div class="">Dimitri Racordon<br class="">
<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>