<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Vincent Esche on Medium]]></title>
        <description><![CDATA[Stories by Vincent Esche on Medium]]></description>
        <link>https://medium.com/@regexident?source=rss-7093428db1e6------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*VZIbFTGniJB964R7s_HOvw.png</url>
            <title>Stories by Vincent Esche on Medium</title>
            <link>https://medium.com/@regexident?source=rss-7093428db1e6------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 14:19:38 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@regexident/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Syntactic Diabetes]]></title>
            <link>https://medium.com/definiteloops/syntactic-diabetes-bbf54b3b4487?source=rss-7093428db1e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/bbf54b3b4487</guid>
            <category><![CDATA[programming-languages]]></category>
            <category><![CDATA[swift]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Vincent Esche]]></dc:creator>
            <pubDate>Mon, 10 Apr 2017 09:31:49 GMT</pubDate>
            <atom:updated>2017-04-10T14:08:33.492Z</atom:updated>
            <content:encoded><![CDATA[<p>When learning a new language (be it a natural or programming language) one of the big first stumbling stones is getting a grasp of the basic grammar rules. For languages with a very simple and regular grammar this is less of a deal. But for others, such as German, it can be <a href="https://www.cs.utah.edu/%7Egback/awfgrmlg.html">quite intimidating</a>.</p><p>For a natural language there are basically three ways of encoding information: A language could encode information by the use of:</p><ol><li><em>Patterns</em>: An elaborate and rigid set of grammatical rules, allowing for an over all smaller set of irregular (and mostly unique) word inflections.</li><li><em>Specialization</em>: An exhaustively large set of irregular (and mostly unique) word inflection patterns, making up for the lack of a more complex and rigid grammar.</li><li><em>Verbosity</em>: An extensive set of function words making up for the lack of possibly both, a more expressive grammar, as well as inflection, at the cost of increased redundancy in the language.</li></ol><p>What a languages lacks in one department, it usually makes up in another. A common consensus among linguists is that all languages are equally complex. (Another take is that current linguistics simply lacks a coherent theory of complexity and by that a useful, objective measure of the latter.)</p><p>Things are similar for programming languages, with the spectrum probably laying somewhere between Haskell (for its highly expressive <a href="https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system">type-system</a>), Perl (for its infamous over-use of <a href="https://en.wikipedia.org/wiki/Sigil_(computer_programming)">sigils</a>) and AppleScript (function words everywhere).</p><p>Swift probably finds itself somewhere in the middle, leaning somewhat in the direction of Haskell.</p><p>In the context of programming one usually talks about <a href="https://en.wikipedia.org/wiki/Expressive_power_(computer_science)">practical expressive power</a> when comparing languages.</p><p>Comparing an implementation of the <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a> in Objective-C …</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6c1d02d4f883417d00c9b3c2b1a8a789/href">https://medium.com/media/6c1d02d4f883417d00c9b3c2b1a8a789/href</a></iframe><p>… with an equivalent one in Swift …</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e952b536882d0a054453e7029f82df33/href">https://medium.com/media/e952b536882d0a054453e7029f82df33/href</a></iframe><p>… one cannot but notice how the new cool kid on the block — Swift — is getting away solving the same problem with much less noise and fewer leaky abstractions, than old-timey Objective-C.</p><p>If Swift had a splitFirst() function on Array, as Rust does for Slice …</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/73417d39ec1d511339283e62f2e74090/href">https://medium.com/media/73417d39ec1d511339283e62f2e74090/href</a></iframe><p>… one could reduce it even further to …</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/45a605f2d649d09f34c41c59d945efb8/href">https://medium.com/media/45a605f2d649d09f34c41c59d945efb8/href</a></iframe><p>… eliminating the unsafe array access.</p><p>Swift manages to provide such a boost in productivity and expressivity substantially thanks to the adaption of well-established features common to many functional programming languages such as <a href="https://en.wikipedia.org/wiki/Pattern_matching">pattern matching</a>, <a href="https://en.wikipedia.org/wiki/Higher-order_function">higher-order functions</a>, some kind of <a href="https://en.wikipedia.org/wiki/Type_class">type-classes</a>, <a href="https://en.wikipedia.org/wiki/Algebraic_data_type">algebraic data types</a>, and last but not least a strong <a href="https://en.wikipedia.org/wiki/Type_system">type-system</a>.</p><p>Thanks to this <a href="https://en.wikipedia.org/wiki/Tuple">tuples</a>, <a href="https://en.wikipedia.org/wiki/Enumerated_type">enums</a> and <a href="https://en.wikipedia.org/wiki/Closure_(computer_programming)">closures</a> have become part of Swift’s most used and loved bells &amp; whistles.</p><p>Tuples and enums form the foundation of pattern matching in Swift.</p><p>Pattern matching in Swift are generally marked by the prefix case … (Swift does not use pattern matching everywhere, like other FP languages do, so the case … is necessary to tell the Swift compiler when use it):</p><p>Like, for example, when one wanted to make use of the result of the splitFirst() function:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0573d4660f9d6a2d17cbc108270393cb/href">https://medium.com/media/0573d4660f9d6a2d17cbc108270393cb/href</a></iframe><p>But wait, that’s far from idiomatic Swift, isn’t it? One would most likely write something like this instead …</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1ad7bcc5cacfb5ec1d2ad77152fabf02/href">https://medium.com/media/1ad7bcc5cacfb5ec1d2ad77152fabf02/href</a></iframe><p>… and have it lowered to the former by the Swift compiler.</p><h3>Syntactic Sugar</h3><p>Swift makes use of this so-called <a href="https://en.wikipedia.org/wiki/Syntactic_sugar">syntactic sugar</a> to make working with it more convenient and to allow for <a href="https://en.wikipedia.org/wiki/Progressive_disclosure">progressive disclosure</a>:</p><p>Swift’s if let foo = bar { } is syntactic sugar for the more verbose if case let .some(foo) = bar { }, allowing one to learn to use T? while sparing one a trip down the rabbit hole of learning what an enum is and how it works.</p><p>Interestingly up until Swift 2.x the following code actually worked, as Swift was simply pattern matching against .Some(_):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/34d141738fe69079026eb6acefddae26/href">https://medium.com/media/34d141738fe69079026eb6acefddae26/href</a></iframe><p>With Swift 3.0.0 this turned into the rather misleading error:</p><blockquote><em>Error: enum case ‘</em><em>Some’ not found in type ‘</em><em>Maybe&lt;Int&gt;’.</em></blockquote><p>… which with Swift 3.0.1 was then changed further into the current more useful error:</p><blockquote><em>Error: initializer for conditional binding must have Optional type, not ‘Maybe’.</em></blockquote><p>Another example of syntactic sugaring is for element in sequence { … }, which gets lowered, or may I say desugared, to:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/93877ba8a15b64aa1855c054a70d607d/href">https://medium.com/media/93877ba8a15b64aa1855c054a70d607d/href</a></iframe><p>Or take returning an instance of T from a function (_) -&gt; T?:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/950dbbc5f8cdf3016564e67862904d5f/href">https://medium.com/media/950dbbc5f8cdf3016564e67862904d5f/href</a></iframe><p>… which gets lowered to:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7adec1ff4c96c1487bd844c46c6ee992/href">https://medium.com/media/7adec1ff4c96c1487bd844c46c6ee992/href</a></iframe><p>And things get even funkier with indirect enums:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/72f73c3bde9fd60901bb01527ebf2d23/href">https://medium.com/media/72f73c3bde9fd60901bb01527ebf2d23/href</a></iframe><p>… which gets lowered down to something like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cb74869b32dd0869b15c3ba5b381ebff/href">https://medium.com/media/cb74869b32dd0869b15c3ba5b381ebff/href</a></iframe><p>… with Box&lt;T&gt; denoting a heap-allocated instance of T.</p><p>While at first all this doesn’t look like much of an improvement from the type declaration alone, the benefits become quite obvious when trying to actually use the type:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fb11ad4177d9924bb549403c9d3acc3a/href">https://medium.com/media/fb11ad4177d9924bb549403c9d3acc3a/href</a></iframe><p>The sugar-free version of this would look something like this (assuming Swift could pattern match on classes):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/99227d1e65a70bfc3770665a2f6631f9/href">https://medium.com/media/99227d1e65a70bfc3770665a2f6631f9/href</a></iframe><p>Apart from a LISP joke hiding in plain sight it should be uncontroversial to state that the former does much better in conveying one’s intentions.</p><p>Syntactic sugar makes complicated things look simple.</p><h3>Syntactic Salt</h3><p>While syntactic sugar aims to make it easier to write good code, <a href="https://en.wikipedia.org/wiki/Syntactic_sugar#Syntactic_salt">syntactic salt</a> aims to make it harder to write bad code.</p><p>As such Swift requires one to add a break-statement to an empty switch-block, even though those break by default in Swift.</p><p>Or take the requirement to append override … to a function declaration if one intends to override it.</p><p>The compiler has all the information it needs to figure these things out on its own. But as both things were cause of many bugs in languages that came before Swift, its authors decided to make things more explicit.</p><h3>Syntactic Saccharin</h3><p><a href="https://en.wikipedia.org/wiki/Syntactic_sugar#Syntactic_saccharin">Syntactic saccharin</a> refers to syntactic sugar that, while having good intentions, fails to do its thing, possibly making things even worse than without it.</p><p>One pattern that causes syntactic sugar to turn into syntactic saccharin is when the former, while trying to make things simpler, ends up introducing its own exceptions which now need to be learned in addition to the things it tries to simplify.</p><p>Assigning a non-optional value to an optional one works for both its de-sugared form = .some(42), as well as its sugared one: = 42:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/35c3c8bc13fa865aadbd5bf2ff82bff0/href">https://medium.com/media/35c3c8bc13fa865aadbd5bf2ff82bff0/href</a></iframe><p>This is great for progressive disclosure, as it allows new users to get up to speed with Swift rather quickly.</p><p>The downside of syntactic sugar is that it can give users a wrong image of a language’s semantics and in the worst case a false sense of safety.</p><p>As such a new user of Swift might deduce that any occurrence of type T? can always be filled with values of type T, as that’s what’s what clearly appears to be happening in the snippet above.</p><p>Reading through the official book on Swift one would further come across <a href="https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/Types.html#//apple_ref/doc/uid/TP40014097-CH31-ID448">this</a>:</p><blockquote><em>You can put parentheses around a named type or a compound type. However, adding parentheses around a type doesn’t have any effect. For example, </em><em>(Int) is equivalent to </em><em>Int.</em></blockquote><p>So, one would come to the conclusion, that the above could also be expressed like this (and indeed, it can):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b3b82aeb299930228dd03423d1d75353/href">https://medium.com/media/b3b82aeb299930228dd03423d1d75353/href</a></iframe><p>So, if this works with a single element, one might reason, then doing it with two shouldn’t be too far off, or should it?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c208c334bbe5083027d6cbb6c7f410fd/href">https://medium.com/media/c208c334bbe5083027d6cbb6c7f410fd/href</a></iframe><blockquote><em>Error: cannot express tuple conversion ‘</em><em>(Int, Int)’ to ‘</em><em>(Int?, Int?)’.</em></blockquote><p>While totally making sense from the type system’s point of view it produces cracks in the thin facade the syntactic sugar had set up to hide the nitty gritty details of <em>Optional&lt;T&gt;</em> and <em>enum in general.</em></p><p>In Swift .enumerated() returns a sequence of pair tuples with named fields (offset: Int, element: Base.Element), where offset represents a consecutive integer starting at 0, and element represents an element of the sequence:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ad05bdc784ff3418c2f0ead9e0ba1019/href">https://medium.com/media/ad05bdc784ff3418c2f0ead9e0ba1019/href</a></iframe><p>To destructure a tuple with named fields one provides local binding names for each field label:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/86e2cee313e2d3f9602f68158155bda0/href">https://medium.com/media/86e2cee313e2d3f9602f68158155bda0/href</a></iframe><p>Alternatively one can also just destructure it as if it was an unnamed tuple:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1d620a12cc9b1984ee245a1ef754ee28/href">https://medium.com/media/1d620a12cc9b1984ee245a1ef754ee28/href</a></iframe><p>The latter however lacks robustness against re-ordering of named fields in the tuple:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/277a218e294dc173597b4fa710a3ab09/href">https://medium.com/media/277a218e294dc173597b4fa710a3ab09/href</a></iframe><p>On a side note: By allowing indexed access to named tuples Swift essentially makes every change of field order a breaking change, due to leaky abstractions, which somewhat defeats their whole point of having tuples with supposedly order-invariant named fields.</p><p>Yet, this indexed access is what allows one to destructure pair in-place like so:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cb90ed5d207f11dfb5e762cfbbb50d8e/href">https://medium.com/media/cb90ed5d207f11dfb5e762cfbbb50d8e/href</a></iframe><p>Things are similar with enumerating Dictionary:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b401d4f915271b92eee7f9310789a2f7/href">https://medium.com/media/b401d4f915271b92eee7f9310789a2f7/href</a></iframe><p>So, what if one wanted to enumerate the key-value pairs of a dictionary by their indices?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7c7d821bee27fa2143ae3ba7489a7288/href">https://medium.com/media/7c7d821bee27fa2143ae3ba7489a7288/href</a></iframe><p>No problem. But what if one wanted to destructure pair?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/92ea30a5ca3b65a36f5603e7e86036cc/href">https://medium.com/media/92ea30a5ca3b65a36f5603e7e86036cc/href</a></iframe><blockquote><em>Error: cannot express tuple conversion ‘</em><em>(offset: Int, element: (key: Int, value: String))’ to ‘</em><em>(Int, (Int, String))’.</em></blockquote><p>All of a sudden Swift forces one to utilize the named variant:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f4d763d02ba9755535f7c7dcd2ce85fa/href">https://medium.com/media/f4d763d02ba9755535f7c7dcd2ce85fa/href</a></iframe><p>So now — due to an exception to the norm — one is forced to use named destructurings in some of the places, which a reader now might falsely expect to mean to convey a certain intent, albeit just being there out of sheer necessity.</p><p>In other cases syntactic sugar simply ends up exchanging a single slightly less convenient yet congruent language pattern with a bunch of subtly different alternatives, which now have to be learnt regardless of personal preference (after all one tends to read much more code of other people, with likely different stylistic preferences, than code one had written on one’s own):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d926c7f1e1e79e438d8f7c072c65af1d/href">https://medium.com/media/d926c7f1e1e79e438d8f7c072c65af1d/href</a></iframe><p>What does this code <a href="http://swift.sandbox.bluemix.net/#/repl/58eb452e64160b40ef07de10">end up printing</a>?</p><p>What if Swift had instead opted (which <a href="https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160201/008979.html">at one point it had</a>) to only provide a single and slightly improved version of if case let …?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e83b167f0afb09c0813a4bccdff747b8/href">https://medium.com/media/e83b167f0afb09c0813a4bccdff747b8/href</a></iframe><p>Swift’s let foo = bar is kind of weird in that it completely changes its behavior when prefixed by if … or guard … and at times results in awkward looking code like if let foo = foo { … }.</p><p>For the next few snippets consider array to be of type [(A, (B, C))].</p><p>Enumerating it is straight-forward with both for … in and .forEach(…):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/381754299de9017790447f308349eaf0/href">https://medium.com/media/381754299de9017790447f308349eaf0/href</a></iframe><p>And given that “(T) is equivalent to T”, as we learnt from the book, we could just as well write things like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/851643df716f6b02911edd811524f6f6/href">https://medium.com/media/851643df716f6b02911edd811524f6f6/href</a></iframe><p>Or we could destructure it:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ef75cbc9937624422fa5881ddbf11305/href">https://medium.com/media/ef75cbc9937624422fa5881ddbf11305/href</a></iframe><p>Now one might remember that parentheses are optional for the (…) in of closures and attempt to do the same with for … in, like so:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d430ed842551de1a861c5aae96a6ace0/href">https://medium.com/media/d430ed842551de1a861c5aae96a6ace0/href</a></iframe><p>And would promptly be confronted with an error for the former:</p><blockquote><em>Error: expected ‘</em>in<em>’ after </em>for-each<em> pattern.</em></blockquote><p>Similarly one might decide to destructure b even further, changing (a, b) to (a, (b, c)):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fbe21fe979bad64d27a5d200e118d84d/href">https://medium.com/media/fbe21fe979bad64d27a5d200e118d84d/href</a></iframe><p>At which point one would be told for the latter that:</p><blockquote><em>Error: unnamed parameters must be written with the empty name ‘</em>_<em>’.</em></blockquote><p>Which appears to be an awkward way of swiftc telling one that “nested destructuring is <a href="https://bugs.swift.org/browse/SR-1620">not (yet) implemented</a> for closure parameters”.</p><p>Another common form of syntactic sugar, or should I say saccharin, is the support for implicit self. within a type’s associated methods.</p><p>There are just way too many ways in which removing/renaming a previously shadowing local variable name can introduce nasty and hard to spot bugs. And the fact that there still is no support for refactoring in Swift’s tooling, thus forcing one to reach for poor-man’s refactoring tools such as find &amp; replace, just adds insult to injury.</p><p>Alas this ship <a href="https://github.com/apple/swift-evolution/blob/9cf2685293108ea3efcbebb7ee6a8618b83d4a90/proposals/0009-require-self-for-accessing-instance-members.md">has sailed</a>.</p><p>A syntactic sugar that does not cleanly apply to all possible use-cases or does not provide proper re-sugared error messages is at risk of effectively turning into syntactic saccharin.</p><p>While Swift tries to reach expressiveness through universal patterns, allowing for simpler language semantics, the use of leaky or fragmented syntactic sugars at times ends up forcing the user to learn both, the core language, plus all those sugars coming along with, and most notably, their numerous exceptions*. Further more, lifting library types up into language items (as seen with T?) for the sake of sugaring always risks turning user-land types into 2nd-class citizens of the language, <a href="https://www.youtube.com/watch?v=_ahvzDzKdB0">constraining its extensibility</a>.</p><p>*In case you were wondering what the hell all this had to do with the intro alluding to the hurdle of learning a foreign natural language.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bbf54b3b4487" width="1" height="1" alt=""><hr><p><a href="https://medium.com/definiteloops/syntactic-diabetes-bbf54b3b4487">Syntactic Diabetes</a> was originally published in <a href="https://medium.com/definiteloops">DefiniteLoops</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[All types are Equatable, but some are more equal than others]]></title>
            <link>https://medium.com/definiteloops/all-types-are-equatable-but-some-are-more-equal-than-others-73a958c01c9b?source=rss-7093428db1e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/73a958c01c9b</guid>
            <category><![CDATA[ios]]></category>
            <category><![CDATA[swift]]></category>
            <category><![CDATA[mac]]></category>
            <dc:creator><![CDATA[Vincent Esche]]></dc:creator>
            <pubDate>Mon, 27 Mar 2017 07:35:29 GMT</pubDate>
            <atom:updated>2017-10-19T20:03:53.312Z</atom:updated>
            <content:encoded><![CDATA[<p>It’s probably safe to say that hardly more than a week will get to go by upon taking up learning Swift before one encounters the Equatable protocol. It is one of the simplest and probably the most adopted protocol in the Swift stdlib:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1af052e8234e3ead5dbf36694cbed76a/href">https://medium.com/media/1af052e8234e3ead5dbf36694cbed76a/href</a></iframe><p>Implementing Equatable, alongside Hashable allows one’s types to be used as keys in a Dictionary&lt;K, V&gt; or a values in a Set&lt;V&gt;.</p><p>Taking a closer look at Dictionary and Set reveals that they actually share quite a lot in semantics and can thus even be implemented in terms of each other. As such one could implement a Dictionary&lt;K, V&gt; in terms of a Set&lt;(K, V)&gt;, conceptually*. Likewise one could implement a Set&lt;V&gt; in terms of a Dictionary&lt;V, ()&gt;**. One possible reason one might choose to do so is sharing logic, which otherwise would have to be maintained redundantly.</p><p>* Non-unary tuples in Swift cannot implement methods, so the proper way to do things would be actually using a small wrapper struct Pair&lt;K, V&gt; instead of (K, V), resulting in Set&lt;Pair&lt;K, V&gt;&gt;.</p><p>** The () (aka Void) type is a zero-sized type in Swift, also known as the <a href="https://en.wikipedia.org/wiki/Unit_type">unit type</a>. While itself – as well as its instances – are present during type checking, the compiler will actually strip them from the resulting binary. A tuple of type (V, ()) would thus boil down to the same size as just (V) (aka V).</p><p>For the sake of simplicity we shall only look at Set&lt;V&gt;, but most of the concepts and points to be made apply to Dictionary&lt;K, V&gt;, likewise.</p><p>So, what exactly is a Set&lt;V&gt;? And how does it differ from Array&lt;V&gt;?</p><p>Unlike an Array&lt;V&gt;, which retains the order of its elements, a Set&lt;V&gt; data structure (ignoring implementation details of whether it’s implemented in terms of an ordered TreeSet&lt;V&gt; or an unordered HashSet&lt;V&gt;) is defined to store its unique members in an unspecified order. Any prior order of its member objects is lost on insertion. Inserting two objects a and b for which the expression a == b evaluates to true, will result in only one of them actually getting inserted*. And unlike a CountingSet&lt;V&gt;, a Set&lt;V&gt; does not keep count of how often an object has been inserted. As such, inserting an object twice, followed by a single removal of said object, will result in the actual removal of said object from the set.</p><p>* Which one is inserted/kept depends on the implementation. In case of Swift calling set.insert(object) will not have any effect if object is already found in set. If one however wants to replace existing members one has to call set.update(with: object) instead.</p><p>The bare minimum API of a Set&lt;Element&gt; would thus be …</p><ul><li>init()</li><li>func insert(_ e: Element)</li><li>func remove(_ e: Element)</li><li>func contains(_ e: Element) -&gt; Bool</li></ul><p>… as well as some way to access its members without explicitly querying for members:</p><ul><li>func makeIterator() -&gt; Iterator</li></ul><p>Everything else can be implemented in terms of these methods.</p><p>So here are a couple of behaviors one would expect to hold true for a s: Set&lt;_&gt;:</p><ul><li>Calling s.insert(object) must either increment s.count by one (if object is not yet a member), or have it stay the same (if object is already a member).</li><li>Calling s.remove(object) must either decrement s.count by one (if object is a member), or have it stay the same (if object is not a member).</li><li>Calling (s.union(s)) must return a Set that is equivalent to s.</li><li>Likewise, calling (s.intersection(s)) must return a Set that is equivalent to s, too.</li><li>Calling (s.subtracting(s)) must return a Set that is empty.</li><li>Constructing s from a sequence of non-unique objects must result in a Set containing only unique objects from said sequence, while dropping all the redundant ones.</li><li>For any pair of Sets s &amp; t where s == t …</li><li>… where e is any member of t (or vice versa) calling s.contains(e) must also return true.</li><li>… calling s.isSubset(of: t) (or vice versa) must return true.</li><li>… calling s.isSuperset(of: t) (or vice versa) must return true.</li><li>… calling s.isDisjoint(with: t) (or vice versa) must return false.</li><li>… calling s.symmetricDifference(t) (or vice versa) must return an empty Set.</li></ul><p>Now what If I told you that <a href="http://swift.sandbox.bluemix.net/#/repl/58cf28b5c7c0f61c565cc711">none of these hold true</a> for Set&lt;Float&gt;, Set&lt;Double&gt;, and consequently Set&lt;V&gt;?</p><p>How can this be, given that both, Float and Double conform to Hashable (and therefor also Equatable), one of the (quite literally) key-requirements of Set&lt;Float&gt; and Set&lt;Double&gt;.</p><p>Let’s take a look at Apple’s official documentation for <a href="https://developer.apple.com/reference/swift/equatable">Equatable</a> to make sure we’re on the same page on what constitutes conformance to Equatable. The important part is this one:</p><blockquote><em>Since equality between instances of </em><em>Equatable types is an equivalence relation, any of your custom types that conform to </em><em>Equatable must satisfy three conditions, for any values </em><em>a, </em><em>b, and </em><em>c:</em></blockquote><blockquote>a == a is always true (Reflexivity)</blockquote><blockquote>a == b implies b == a (Symmetry)</blockquote><blockquote>a == b and b == c implies a == c (Transitivity)</blockquote><p>We already discussed in detail what constitutes the conformance of a type to Hashable in an <a href="https://blog.definiteloops.com/ha-r-sh-visitors-8c0c3686a46f">earlier article</a>, so we will not go int any detail on it here but will instead focus entirely on Equatable.</p><p>You have probably used the functionality of Equatable in combination with either Float and Double more often than you can remember and are wondering at this point what kind of weird behavior this could be alluding to.</p><p>After pondering for a moment you might remember that a fellow programmer once told you to never compare two floating-point numbers against each other. Bad things would happen, they said.</p><p>And indeed what they were referring to were the infamous rounding errors found in common <a href="https://en.wikipedia.org/wiki/IEEE_floating_point">floating-point representations</a>. As such 0.1 + 0.2 does not necessarily have to evaluate to the same value as 0.3 on its own. In fact Swift will indeed evaluate the expression 0.1 + 0.2 to a value of 0.30000000000000004, yet the expression 0.3 to a value of 0.29999999999999999. Some real numbers simply cannot be cleanly expressed as floating-point numbers. To add insult to injury even an expression of (a + b) + c could yield a (oh so slightly) different result than a + (b + c) for floating-point values. IEEE 754 floating-point numbers do not guarantee proper <a href="https://en.wikipedia.org/wiki/Associative_property">associativity</a>.</p><p>This however is actually not even what’s at play here. After all once a floating-point value is instantiated it does not change its value and thus should be equal to itself at any time. Once 42.0, always 42.0.</p><p>Now it’s quite likely that you never heard of NaN before, or have you? If so, no big surprise. After all we prefer to not talk about NaN around here, if possible. NaN is floating-point’s dirty laundry. It’s weird. It’s a wolf pack in sheep’s clothing.</p><p>Yep, there’s indeed more than one NaN: a total of 8388606 of them in Float alone, to be specific. And even more of them are to be found in Double. All of them operating under the facade of a single identifier and yet boldly proclaiming “I’m not with them!” when asked.</p><p>Remember this rule from Equatable?</p><blockquote><em>Reflexivity: </em><em>a == </em><em>a is always true.</em></blockquote><p>Well, as it turns out Float.nan != Float.nan. Spooky, eh?</p><p>What at first glance looks like a bug in Swift is unfortunately precisely how NaN is supposed to work. In pretty much every other major programming language, too.</p><p>When it comes to NaN it’s all about what NaN is not: a number.</p><p>It is a single name used for all members of the group of possible combinations of 32 (or 64 for Double) bits, that happen to <em>not</em> be a valid floating-point number representation, according to <a href="https://de.wikipedia.org/wiki/IEEE_754">IEEE 754</a>.</p><p>That’s quite a mouth-full and a <a href="https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">rabbit hole</a> for those who feel so inclined.</p><p>The strange behavior of Set is a direct result of this weird detail about Float/Double. It is blinded by its trust of Float/Double to play by the rules they both agreed upon (i.e. Equatable).</p><p>So, if this dubious NaN is so troublesome, one might ask, then why don’t we just remove it from Float/Double?</p><p>Well, turns out we can’t. NaN is an inevitable consequence of how floating-point numbers are represented in IEEE 754.</p><p>You could think of every Float/Double deep down actually being a Float?/Double? in disguise with Float.nan/Double.nan being the nil/.none case. Having them that way would actually clean things up drastically. We can’t however do it like that without both: breaking compatibility with every other major programming language, and saying goodbye to any future prospect of having a <a href="https://en.wikipedia.org/wiki/Foreign_function_interface">foreign function interface</a>. We would also be losing all the benefits of hardware-accelerated floating-point operations, which we could no longer make any use of.</p><p>So what <em>can</em> we do to fix this then?</p><p>Well, turns out there is a way to avoid this issue and make Swift’s stdlib more expressible at the same time. And it’s pretty straight-forward, too: Split up Equatable into two protocols.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f05a8ed5c4651d6308dc6b06ebfb01be/href">https://medium.com/media/f05a8ed5c4651d6308dc6b06ebfb01be/href</a></iframe><p>With Equatable and PartiallyEquatable in place Set&lt;Element : Hashable&gt; and Dictionary&lt;Key : Hashable, Value&gt; could remain as they are, but Float’s and Double’s conformance would be demoted from Equatable to PartiallyEquatable.</p><p>So while one could still compare two floating-point values a and b against each other via a == b (while still bringing all the weirdness of NaN with it!) one could not use them as a key or element to any data structure that requires conformance to Equatable (be it directly, or indirectly).</p><p>As such this would essentially prohibit any use of Set&lt;Float/Double&gt; or Dictionary&lt;Float/Double, _&gt; (and rightly so from a type-theoretical perspective), thus being a rather obvious breaking change. But one that should only break code that was probably an ill-informed mistake to begin with. After all as we saw earlier it’s not just NaN that’s a bit weird about them.</p><p>If one really, really wanted to use a T: FloatingPoint in a Hashable/Equatable context one would have to wrap it like this and then use SafeFloat&lt;_&gt; as the key/element:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e3cb89f6967ad9ab3ffb1895e410e6aa/href">https://medium.com/media/e3cb89f6967ad9ab3ffb1895e410e6aa/href</a></iframe><p>The guard !inner.isNaN else { return nil } is what makes this work safely.</p><p>Why and how the same problem/and solution (Comparable, PartiallyComparable) applies to Comparable will be left as an exercise for the reader. (Hint: protocol Comparable: Equatable { … })</p><p>If Swift had true generic protocols (No, what you’re thinking of are PATs, protocols with associated types. A solution to a different problem.), then the proper and more general definition of Equatable and PartiallyEquatable would actually be:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8ea07e6adebd1ff7f62603dde8f02eab/href">https://medium.com/media/8ea07e6adebd1ff7f62603dde8f02eab/href</a></iframe><p>… and similarly so for Comparable and PartiallyComparable.</p><p>This leaves us with one final question: “Why on earth should we care about NaN to begin with?” You have most likely never been in the presence of NaN before anyway.</p><p>What would you expect sequence.sorted() to do? If you answered with “Well, it returns the elements of the sequence, sorted” in your head, then you’re right on track.</p><p>As it turns out it is in fact exactly what the docs have to say about func sorted():</p><blockquote><em>Returns the elements of the sequence, sorted.</em></blockquote><p>So we should be able to safely expect the result of sequence.sorted() to hold true for any pair of elements a and b where a &lt; b the following property: a is to be found at a lower index in the sequence, than b .</p><p>But does it? <a href="http://swift.sandbox.bluemix.net/#/repl/58cf260cc7c0f61c565cc70e">Let’s find out</a>:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e66452e94c342f3bd617f5335664ec0e/href">https://medium.com/media/e66452e94c342f3bd617f5335664ec0e/href</a></iframe><p>Well, … that’s not quite what I would call sorted.</p><p>One more, just for fun:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/45097e781072baca09dcc1924fcb69d1/href">https://medium.com/media/45097e781072baca09dcc1924fcb69d1/href</a></iframe><p>I’ll leave it as an exercise for the reader to figure out what’s going on here and why this is pretty bad.</p><p>So, why should we care, again?</p><p>We should care, because every time one adds NaN to the mix one risk <a href="http://swift.sandbox.bluemix.net/#/repl/58cf28b5c7c0f61c565cc711">messing with the integrity of one’s program’s semantics</a>.</p><p>Reflexivity requires for every value of type T to return true for self == self. Float.nan is member of Float, but Float.nan == Float.nan evaluates to false. Thus Float/Double should clearly <em>never</em> have been declared to conform to Equatable. The fact that both Float and Double deliberately proclaim to conform to Equatable against better knowledge is leaving a gaping hole in the safety and soundness promises of Swift’s type system.</p><p>As we saw earlier Set&lt;Float/Double&gt; and Dictionary&lt;Float/Double, _&gt; are closely related to each other and basically share a lot of their semantics. As such everything we observed for the former will also apply to the latter in some form or another.</p><p>While one could consider Set&lt;Float/Double&gt; or Dictionary&lt;Float/Double, _&gt; a clear edge-case, it is important to understand that the weirdness creeps in as soon as one carelessly includes an instance property let _: Float or let _: Double in the implementation of a type’s static func == (lhs: Self, rhs: Self) -&gt; Bool.</p><p>It doesn’t help to have the sturdiest of all walls to secure your fortified castle if you then leave one of the outer doors wide open at night.</p><p>Update 1:</p><p>Sounds good!</p><h3>Joe Groff on Twitter</h3><p>@mjtsai @mjtsai @regexident There&#39;s WIP to make floats Equatable and Comparable using level 2 comparison (so NaN == NaN, NaN &amp;lt; number, -0 != 0)</p><p>Update 2:</p><p>The gift that keeps on giving:</p><h3>Ole Begemann on Twitter</h3><p>Poll] A Swift quiz: let a: [Float] = [1, .nan] let b: [Float] = [1, .nan] let copy = a a == b // (1) a == copy // (2) What&#39;s (1) and (2)?</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=73a958c01c9b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/definiteloops/all-types-are-equatable-but-some-are-more-equal-than-others-73a958c01c9b">All types are Equatable, but some are more equal than others</a> was originally published in <a href="https://medium.com/definiteloops">DefiniteLoops</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Ha(r)sh visitors]]></title>
            <link>https://medium.com/definiteloops/ha-r-sh-visitors-8c0c3686a46f?source=rss-7093428db1e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/8c0c3686a46f</guid>
            <category><![CDATA[swift]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[hashing]]></category>
            <dc:creator><![CDATA[Vincent Esche]]></dc:creator>
            <pubDate>Mon, 13 Mar 2017 15:36:25 GMT</pubDate>
            <atom:updated>2021-10-27T11:59:06.294Z</atom:updated>
            <content:encoded><![CDATA[<p>As soon as you try to use a custom type as either Key in a Dictionary or Element in a Set (which in Swift are implemented as HashMap and HashSet respectively), such as …</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a0c77c6be954d4e8794d0d291d9eb540/href">https://medium.com/media/a0c77c6be954d4e8794d0d291d9eb540/href</a></iframe><p>… you will be confronted with the following compiler errors:</p><blockquote><em>error: type ‘GridPoint’ does not conform to protocol ‘Equatable’</em></blockquote><blockquote><em>error: type ‘GridPoint’ does not conform to protocol ‘Hashable’</em></blockquote><p>You decide to tackle Equatable first, as unlike Hashable you’re already familiar with Equatable. A pair of GridPoints is to be considered equal if they share the same x and y coordinates:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c4686ec93c70db0cce8dd2ce84db44a6/href">https://medium.com/media/c4686ec93c70db0cce8dd2ce84db44a6/href</a></iframe><p>Now for Hashable we need to first look into what makes for a valid hash function? First of all a hash function has to exhibit <strong>determinism</strong>. Repeated calls (during a program’s runtime!) of hash(val) for a value val must return the same result. In other words, if hash(val) returns 42 then so must every future invocation of hash(val). Hash functions are allowed to return the same result for multiple different values (aka hash collisions).</p><p>Unless you’re dealing with specialized cryptographic hashing functions, such as <a href="https://en.wikipedia.org/wiki/Bcrypt">bcrypt</a> or <a href="https://en.wikipedia.org/wiki/Scrypt">scrypt</a>, for which one of the key-features is their slowness, one usually prefers their hash function to have good <strong>efficiency</strong>.</p><p>Within these constraints we could just go and make GridPoint conform to Hashable with this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ff80cd7a3508b36a6778615879fa1176/href">https://medium.com/media/ff80cd7a3508b36a6778615879fa1176/href</a></iframe><p>While it’s a valid implementation of Hashable (and a pretty darn fast one at that!), it’s far from being a useful one for our common purposes.</p><p>This leads us to another general desirable characteristic of a hash function: <strong>uniformity</strong>. That is, every hash value in the output range should be generated with roughly the same probability. Our implementation is in clear violation of this by giving 42 a probability of 100% and everything else a probability of 0%, due to only ever returning 42.</p><p>And for the sake of completeness, depending on your specific use-case, there may be a third characteristic:</p><ul><li><strong>continuity</strong>: A <a href="https://en.wikipedia.org/wiki/Locality-sensitive_hashing">locality-sensitive hash function</a> (as used in clustering) is expected to produce similar hashes for similar values.</li><li><strong>discontinuity:</strong> A <a href="https://en.wikipedia.org/wiki/Cryptographic_hash_function">cryptographic hash function</a> (as used in cryptographic checksums) is expected to cause a so-called <a href="https://en.wikipedia.org/wiki/Avalanche_effect"><strong>avalanche effect</strong></a><strong> </strong>for even the tiniest of differences.</li></ul><p>As should be clear by now it is far from trivial to come up with a hashing algorithm that conforms to aforementioned characteristics, let a lone a general one which works on arbitrary streams of bytes.</p><p>In addition to implementing custom hash functions being a rather delicate matter there are a couple of other points to make on the problems of Hashable`:</p><ol><li>Application developers should not have to embark on the task of implementing hashing algorithms. We have experts for that. For good reasons. There are probably hundreds of implementations of hashValue that couldn’t even be considered useful or at least valid general-purpose hashes, let alone cryptographic ones.</li><li>Many types (even some primitives!) require deep domain-knowledge in order to correctly implement Hashable for them. Traps everywhere.</li><li>Badly implementing hashValue opens the doors for DDOS attacks when being exposed to the web, as it happens when using Swift on the server.</li><li>One cannot exchange the hashing algorithm used by a type one does not own. And even for the types one does indeed own exchanging the hashing algorithm is far more involved than passing it a different implementation.</li><li>One cannot implement more than one hashing algorithm at a time for a given type.</li></ol><p>In short: Hashable is utterly error-prone and does not compose well. And that’s a shame!</p><p>But let’s go through each of those four points in more detail.</p><h3>Ordinary application developers should not implement hashing algorithms:</h3><p>There is an entire research field in computer science dedicated to coming up with secure general-purpose hashing algorithms. Incredibly smart people spend years investigating the requirements and coming up with implementations of new secure hashing algorithms. Just to have it <a href="https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html">be broken</a> few years later. MD4/MD5/SHA1 just being some of them. This stuff is hard.</p><p>Yet it’s exactly what Hashable in its current form forces us to do. For every type you write and want to be Hashable, you have to implement var hashValue: Int, i.e. your very own DIY hash function.</p><h3>Required Domain-knowledge for valid implementations:</h3><p>Hashing (on a bit-wise level) of some of the most widely used types in Swift is non-trivial. As such there are quite a few nasty traps to navigate around when it comes to calculating a hash of an IEEE 754 floating-point value. And equally so for UTF8-encoded Strings, interestingly.</p><p>In both cases those traps are consequences of tradeoffs that were made when the internal bit representation of both types were specified in their respective standards.</p><p>In short, every time a type supports multiple bit-representations to represent the same semantic value you need to perform some kind of normalization/canonicalization upfront:</p><p>Float/Double:</p><ol><li>There exist (among other peculiarities) representations for both positive, as well as negative zero. As such 1.0 * 0.0 will produce a different bit pattern than, say -1.0 * 0.0. As 0.0 and -0.0 are defined to be equal by IEEE 754, both need to produce the same hash.</li></ol><p>String:</p><ol><li>Both, &quot;u\u{308}&quot; and &quot;\u{FC}&quot; represent a “ü” aka. “LATIN SMALL LETTER U WITH DIAERESIS”, as commonly found in German or Turkish texts (among others). Both are valid UTF8 sequences, yet result in different bit-representations of the same (semantically equivalent) string. In fact &quot;u\u{308}&quot; == &quot;\u{FC}&quot; will evaluate to true in Swift.</li></ol><p>It is thus ill-advised to simply hash a Float/Double or String value’s bytes.</p><p>These traps are intrinsic to how floating-point numbers and/or strings work in modern computers. They are by no means a unique problem of Swift. And luckily for us the Swift stdlib already provides us with an implementation of Hashable for them. It’s still worth knowing what’s going on under the hood.</p><h3>Badly implementing `var hashValue` opens the doors for DDOS attacks:</h3><p>Open the official documentation for <a href="https://web.archive.org/web/20170730121658/https://developer.apple.com/documentation/swift/hashable">Hashable</a>, and you will actually be presented this example code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4630ced04e59a43df9f741da5789991e/href">https://medium.com/media/4630ced04e59a43df9f741da5789991e/href</a></iframe><p>This unfortunately is a perfect example of how not to implement Hashable.</p><p>Let’s take it for a test run, shall we?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c3237dbfc0f33d6ee992618014d0ca01/href">https://medium.com/media/c3237dbfc0f33d6ee992618014d0ca01/href</a></iframe><p>Given a <a href="https://en.wikipedia.org/wiki/Perfect_hash_function">perfect hash function</a> we would expect hashes.count == width * height to return true, i.e. every GridPoint was mapped to its own unique hash.</p><p>Perfect hashing function however usually isn’t applicable and one has to made due with a good-enough hash function.</p><p>A good-enough hash function would still be expected to produce a unique hash for most of the GridPoints within an area of 1000 × 1000. As such we would expect hashes.count to be somewhat close – if not equal – to, 1_000_000 (but not larger, obviously).</p><p>Running the snippet above, calculating hashes of all GridPoints (given the above implementation) on a 1000 × 1000 grid results in just 1024 unique hash values for 1_000_000 unique values.</p><p>In other words: The recommended implementation causes 99.9% of values to trigger a hash collision.</p><p>This is bad. Real bad.</p><p>We might just as well have kept it at return 42 at this point.</p><p>(Out of those 1_000_000 values the <em>median</em> collision count was 976 with <em>min</em> and <em>max</em> being 976 and 1000 respectively.)</p><p>If even the official Swift documentation gets the implementation of hashValue wrong, then who is to expect the average Swift programmer to do any better?</p><p>In contrast, running the same snippet using HashVisitable and the semi-secure Fnv1aHash (see below) results in zero collisions!</p><p>Let’s imagine you were writing a server-side Swift thing that used an HTML canvas to draw a heat map of grid-points. For the sake of convenience you decide to provide a REST api for passing the data set to the server via JSON-encoded POST requests.</p><p>Your server would unpack the JSON and put all grid-points into a Dictionary&lt;GridPoint, Int&gt; to count the number of total taps per point, so you can map those frequencies on a color gradient. Now all an attacker would have to do to bring your server to its knees (via DDOS) was to call the API repeatedly.</p><p>Swift’s String attempts to mitigate such attacks by relying on the secure (as in yet to-be-broken) <a href="https://en.wikipedia.org/wiki/SipHash">SipHash</a> algorithm, these days. As honorable as it is though, it’s merely fighting symptoms. The problem is to be found in the API itself, not individual hash implementations.</p><p>We’re making some progress though: Back in the days Objective-C’s NSString actually just returned its length (UTF-16 code-points) as its hash, IIRC. A more than questionable decision, when taking <a href="https://en.wikipedia.org/wiki/Zipf%27s_law">Zipf’s law</a> into account. Even as a non-cryptographic hash.</p><h3>One cannot exchange hashing algorithms:</h3><p>So, let’s first address the question of why one would want/need to use an alternative hashing algorithm? Swift’s way of doing things served us well so far, hasn’t it?</p><p>For public APIs in Swift on the server you would clearly want s secure hashing algorithm, while if on the other hand your hashing algorithm was slow but super secure and your data came from a trusted source, then every use of hashing in time-critical “hot” pieces of your program would needlessly slow down program evaluation.</p><p>So what you want instead is a way to use the hasher of your choice on a per-instance level. So the type signatures of Set&lt;Value&gt; or Dictionary&lt;Key, Value&gt; would become Set&lt;Value, Hasher = SipHash48&gt; or Dictionary&lt;Key, Value, Hasher = SipHash48&gt;. This would be a non-breaking change and default to a secure hash. If upon benchmarking you find a bottleneck in a hashing-related part of your code you could then simply change your collection’s hasher to a hasher like SipHash24, a less but reasonably secure hasher that is significantly faster.</p><p>The only way to use a different hashing algorithms for a given type right now (Swift 3.x) is to either:</p><p>Subclass it (if it’s a class to begin with) and override var hashValue (which prevents you from ever again calling the original one). This might also have inconvenient consequences of unexpectedly degrading the performance of other uses of T in your program.</p><p>… or to:</p><p>Extend the API by a second property: var alternativeHashValue. And a third var alternativeToTheAlternativeHashValue, and so on. Neither of those would be recognized by Set&lt;T&gt; though: When adding your object into a Set&lt;T&gt; it would still end up calling var hashValue.</p><p>Needless to say neither one happens to work, let alone scale particularly well.</p><h3>One cannot implement multiple hashing algorithms:</h3><p>Now, I’m the first to admit that a scenario where one needs to have multiple hashing algorithms is rather rare.</p><p>There are however certain circumstances where multiple hashes per value are desired, if not outright necessary: <a href="https://en.wikipedia.org/wiki/Bloom_filter">Bloom Filters</a>.</p><p>The elevator pitch of a Bloom Filter goes something like this:</p><blockquote><em>Imagine having a </em><em>Set&lt;T&gt; that didn’t actually have to store any of the things you put into it, yet could tell you with certainty whether you had </em>not<em> inserted a particular object before.</em></blockquote><p>How these things <a href="https://blog.medium.com/what-are-bloom-filters-1ec2a50c68ff">actually work in detail</a> is beyond the scope of this article. What is important however is the fact that a Bloom Filter BloomFilter&lt;T&gt; requires T to provide more than one hash per value to work reliably.</p><p>So, how would one go about fixing these “issues”?</p><p>By implementing 👉<a href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25">this</a> 👈 Swift-Evolution proposal.</p><p>As the name implies this new API makes use of the <a href="https://en.wikipedia.org/wiki/Visitor_pattern">visitor pattern</a>. Instead of implementing the hashing logic on the type T itself we are moving it into dedicated Hasher types, which then get passed to the objects to be hashed. Neatly decoupled.</p><p>ContiguouslyHashable marks a special family of types which allow for simply passing their contiguous memory to the given hasher en bloc, which Float, Double and String would decidedly not conform to, while for types matching these criteria then it would be a simple matter of tagging them with the protocol.</p><p>It is important to note at this point that — with HashVisitable in place — one would rarely (if ever) have to implement a hasher on one’s own. The stdlib would provide a pre-picked set of battle-tested hashers.</p><p>The only code the average application developer would ever have to write is an extension like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2da1630c7cb3a501d7e402331ad5cc82/href">https://medium.com/media/2da1630c7cb3a501d7e402331ad5cc82/href</a></iframe><p>Implementations of data structures such as Set or Dictionary would then change any occurrences of let hash = value.hashValue to something like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4036730e170f48626219084892eb7436/href">https://medium.com/media/4036730e170f48626219084892eb7436/href</a></iframe><p>As the owner of, say struct GridPoint, you now don’t have to know anything about how to implement hashing without shooting yourself in the foot anymore. All you need to know is which members you want to feed into the hasher. That’s it.</p><p>And as for the case of a Bloom Filter requiring multiple hashes:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8e659270bf414b3be455d70c93c0800c/href">https://medium.com/media/8e659270bf414b3be455d70c93c0800c/href</a></iframe><p>Program safety and performance in Swift would benefit greatly from a migration to a proper visitor-based hashing API.</p><p>And in the light of Swift’s concept of “gradual exposure“ of language features (and computer science concepts) hiding the ugly details of hashing from non-expert Swift developers would eliminate a whole an unintuitive chapter from the syllabus that formerly would have been required-reading, while actually making the Swift ecosystem more secure.</p><p>Again, the only piece of the proposed API, that the average user would ever be exposed to, is having to write something like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4de07a4056169a50edec224c6704009e/href">https://medium.com/media/4de07a4056169a50edec224c6704009e/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8c0c3686a46f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/definiteloops/ha-r-sh-visitors-8c0c3686a46f">Ha(r)sh visitors</a> was originally published in <a href="https://medium.com/definiteloops">DefiniteLoops</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Playing Jenga with Swift’s Type Checker]]></title>
            <link>https://medium.com/definiteloops/playing-jenga-with-swifts-type-checker-7c4f13f6d2a4?source=rss-7093428db1e6------2</link>
            <guid isPermaLink="false">https://medium.com/p/7c4f13f6d2a4</guid>
            <category><![CDATA[programming-languages]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[swift]]></category>
            <dc:creator><![CDATA[Vincent Esche]]></dc:creator>
            <pubDate>Mon, 27 Feb 2017 13:44:28 GMT</pubDate>
            <atom:updated>2017-05-17T22:32:38.058Z</atom:updated>
            <content:encoded><![CDATA[<p>Imagine for a moment that you are a programmer with reasonable experience in Objective-C, who, upon having been pitched the benefits of Swift for far too long by now, decides to finally get one’s feet wet with it.</p><p>Out of all the attractive aspects of Swift there is one in particular, that piqued your interest: Type Inference.</p><p>You loath having to type the same redundant type declarations over and over again. Type Inference sounds almost too good to be true for you. You’re stoked.</p><p>You open <a href="https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/TheBasics.html">“The Swift Programming Language”</a> and scroll down to the chapter on “Type Safety and Type Inference“, which reads as follows:</p><blockquote><em>Swift is a type-safe language. […] Because Swift is type safe, it performs type checks when compiling your code and flags any mismatched types as errors. […] Type inference is particularly useful when you declare a constant or variable with an initial value. […] For example, if you assign a literal value of </em><em>42 to a new constant without saying what type it is, Swift infers that you want the constant to be an </em><em>Int, because you have initialized it with a number that looks like an integer:</em></blockquote><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/53827b81bed3284f9a806880bfa65a09/href">https://medium.com/media/53827b81bed3284f9a806880bfa65a09/href</a></iframe><p>Now with the meaning of life at your disposal you tell yourself, ”I might just as well do something with it”</p><p>You open up a playground: UltimateQuestion.playground and ponder about what to do next.</p><p>Being of the cautious kind you decide to go the safe route and validate your answer before using it elsewhere:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f7fbb17d5058ad87acc20fd5b812b0f1/href">https://medium.com/media/f7fbb17d5058ad87acc20fd5b812b0f1/href</a></iframe><p>Your plan is to put the calculation of aforementioned answer (42) in a closure (you really like closures, and I can’t blame you!), so you type:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fffcf49c1c82b8b4f7511f6b733929ef/href">https://medium.com/media/fffcf49c1c82b8b4f7511f6b733929ef/href</a></iframe><p>Happy with your work you hit compile.</p><pre><em>error: unable to infer complex closure return type; add explicit type to disambiguate</em></pre><p>You are confused. While you would have wholeheartedly agreed upon the whole “Question of Life, the Universe, and Everything” being of a rather complex matter, you’d have expected your answer (42) to it to be of a rather trivial nature.</p><p>Not willing to give up on the idea of “type inference“ already, you decide to not follow Swift’s advice, and instead simply change your closure to this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a0960c0585d7725cb7fdd13ac9727fd1/href">https://medium.com/media/a0960c0585d7725cb7fdd13ac9727fd1/href</a></iframe><p>This time Swift accepts your answer without complaints.</p><p>While still none the wiser you decide to just play along while things seem to work.</p><p>So, with all parts “working” now you would just have to pass one to the other, and Bob is your uncle, right?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ee5e2fee4d658fa927b35d73301490ff/href">https://medium.com/media/ee5e2fee4d658fa927b35d73301490ff/href</a></iframe><p>Right? … Well, no.</p><pre><em>error: cannot convert value of type ‘</em><em>Int’ to expected argument type ‘</em><em>UInt’</em></pre><p>“Fine”, you say, “I’ll just pass it in by value then.”</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6da03ffb4cd0f94a754810853fd2c39f/href">https://medium.com/media/6da03ffb4cd0f94a754810853fd2c39f/href</a></iframe><p>This works. But you would actually like to avoid magic numbers in your code, and thus end up changing it to this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2545e3e0a536b84eb06b21b0d4d06fd0/href">https://medium.com/media/2545e3e0a536b84eb06b21b0d4d06fd0/href</a></iframe><p>Which promptly leads back to this:</p><pre><em>error: cannot convert value of type ’</em><em>Int’ to expected argument type ‘</em><em>UInt’</em></pre><p>“Oh no, not again …”, you mumble.</p><p>After a quick consideration you decide to skip the validation and just use your answer unchecked.</p><p>In order to avoid having to re-calculate it over and over again in the future you decide to at least cache your answer:</p><p>Should be as simple as that:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/225eea839dd6b60c72b32af28da8a89f/href">https://medium.com/media/225eea839dd6b60c72b32af28da8a89f/href</a></iframe><p>Things are looking fine so far. You are happy, Swift is happy.</p><p>Having invested quite a bit of time into the calculation of your answer however, you come to <em>think</em> “I better be prepared for additional answers, in case those come up, all of a sudden”, and change your code to:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4f72be4de0304c2001ca9021acc834ef/href">https://medium.com/media/4f72be4de0304c2001ca9021acc834ef/href</a></iframe><p>Promptly followed by an unexpected <em>*Slap!*</em> to the face:</p><pre><em>error: empty collection literal requires an explicit type</em></pre><p>“Fine, I’ll add some type then.”, you <em>think</em> to yourself:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8868b5e81a1c4bfad107538d0e338daf/href">https://medium.com/media/8868b5e81a1c4bfad107538d0e338daf/href</a></iframe><p><em>*Slap!*</em></p><pre>error: cannot convert value of type ‘Int’ to expected argument type ‘UInt’</pre><p>“Alright”, you <em>think</em> to yourself, “raw literals and validation via map and plain old literal-inferred Ints it is then.”:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a13191a5bc5a6d8ab97ff4fb3cf08a4d/href">https://medium.com/media/a13191a5bc5a6d8ab97ff4fb3cf08a4d/href</a></iframe><p><em>*Slap!*</em></p><pre><em>error: unable to infer complex closure return type; add explicit type to disambiguate</em></pre><p>You decide to give it one more try. But as someone seems to have cast a spell on precious 42 you decide to give 43 a go this time:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3d66fa99eff609ecb46cabc0bc4000b9/href">https://medium.com/media/3d66fa99eff609ecb46cabc0bc4000b9/href</a></iframe><p><em>*Slap!*</em></p><pre><em>error: Binary operator ‘+’ cannot be applied to two ‘Int’ operands</em></pre><p>“What? Now this is just getting silly.”, you mumble.</p><p>Having gone through your third coffee by now you come to the conclusion that your precious answer maybe just is of no practical use at all, and decide to call it a day and embark in something more fruitful for the rest of it.</p><h3>Technical discussion</h3><p>To truly understand why things are the way they are in Swift-land, one has to take a closer look at Swift’s type checker.</p><p>Why does Swift compile …</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/be4345b47745b5ed2bb69087bfd668f3/href">https://medium.com/media/be4345b47745b5ed2bb69087bfd668f3/href</a></iframe><p>… without complaints, yet get all confused with …?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9b9e93c0ecae8db9e77e88780a6e3cea/href">https://medium.com/media/9b9e93c0ecae8db9e77e88780a6e3cea/href</a></iframe><p>One would expect both of these minimalistic programs to be <em>semantically equivalent</em> and thus be handled identically by the compiler, no?</p><p>The answer to this question and many more can be found in the Swift project’s official documentation on its <a href="https://github.com/apple/swift/blob/master/docs/TypeChecker.rst">“Type Checker Design and Implementation”</a> (emphasis mine):</p><blockquote><em>Swift implements </em><strong><em>bi-directional type inference</em></strong><em> using a </em><strong><em>constraint-based type checker</em></strong><em> that is reminiscent of the classical </em><strong><em>Hindley-Milner type inference algorithm</em></strong><em>. […]</em></blockquote><blockquote><em>The Swift language contains a number of features not part of the Hindley-Milner type system, including constrained </em><strong><em>polymorphic types</em></strong><em> and </em><strong><em>function overloading</em></strong><em>, which </em><strong><em>complicate the presentation and implementation</em></strong><em> somewhat. On the other hand, Swift </em><strong><em>limits the scope of type inference to a single expression or statement</em></strong><em>, for purely practical reasons: we expect that we can provide better performance and vastly better diagnostics when the problem is limited in scope.</em></blockquote><p>That’s quite a mouthful for anybody not accustomed to <a href="https://en.wikipedia.org/wiki/Type_theory">Type Theory</a> and <a href="https://en.wikipedia.org/wiki/Lambda_calculus">Lambda Calculus</a>.</p><p>So let’s go through each highlighted part one by one and break things down:</p><ol><li>“… <strong>bi-directional type inference</strong> …”</li></ol><p>In a very (over-)simplified view this means (among other things) that during Swift’s type checking the type inference can inform the type checker and vice versa.</p><p>Instead of trying to figure out the type of an expression on its own, as type inference does, bi-directional type inference alternates between figuring out and inferring types and checking expressions against types already known.</p><ol><li>“… <strong>constraint-based type checker</strong> …”</li></ol><p>Just like you use protocol constraints to limit your generic types to certain set of possible types, the compiler inserts additional constraints to your program during compilation. Basically, every time you leave out and expect Swift to infer it for you the compiler inserts a constraint, constraining the set of possible candidate types to the limited knowledge it already has about the value. It then uses a technique called <a href="https://en.wikipedia.org/wiki/Constraint_programming">constraint solving</a> for figuring out the most general type model of the latent types of the program at hand.</p><ol><li>“… <strong>Hindley-Milner type inference algorithm</strong> …”</li></ol><p>If you’ve ever been in contact with any of the ML languages, like SML, OCaml, F#, Elm, then you’ve been exposed to <a href="https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system">Hindley-Milner typing</a>, a popular type of type inference algorithm.</p><p>The Hindley-Milner type inference algorithm is <a href="http://cs.stackexchange.com/a/6619/6874">worst-time exponential</a>.</p><ol><li>“… <strong>polymorphic types</strong> and <strong>function overloading</strong>, […] <strong>complicate the presentation and implementation</strong> somewhat …”</li></ol><p><a href="http://stackoverflow.com/questions/12532552/what-part-of-milner-hindley-do-you-not-understand">Classical Hindley-Milner type inference</a> does not support polymorphic types or function overloading and already is worst-time exponential.</p><p>Swift now however had to extend its Hindley-Milner type inference in order to allow for polymorphic types or function overloading being added as language features. And most of us probably wouldn’t want to miss them.</p><p>This extension now happens to complicate things even further for the type checker.</p><p>Saying that this “complicate(s) [things] somewhat” is one heck of an understatement, actually.</p><p>Type inference in non-pure real-world programming languages is a pretty darn complicated matter.</p><ol><li>“… Swift <strong>limits the scope of type inference to a single expression or statement</strong> …”</li></ol><p>Last but not least we get to the actual answer to our initial question of “what’s up with all those type checking errors?”.</p><p>Repeat after me: “Swift limits the scope of type inference to a <strong>single expression</strong> or <em>statement</em>”.</p><p>We could close the case right here.</p><p>Or we could take a look at what this actually means in practice.</p><p>In Swift let foo = bar() is called a statement. Statements in Swift are basically everything you <em>cannot</em> assign to a variable (i.e. let foobar = (let foo = bar()) is invalid Swift).</p><p>When Swift looks at:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7c55fc2f15d19c0ed5c7d66a94295faf/href">https://medium.com/media/7c55fc2f15d19c0ed5c7d66a94295faf/href</a></iframe><p>… it looks at it one statement/expression after another.</p><p>The result of the line (fun foo(_ bar: UInt) {}) is actually fully typed already ((UInt) -&gt; ()), so let’s skip straight to the second one: foo(42).</p><p>The type of 42 is unknown and thus has to be inferred by Swift. Luckily however we know the type of func foo and can thus simply look up the missing type information from the knowledge we have about the func foo. As such we can infer 42 to be of type UInt.</p><p>So far so good.</p><p>Now let’s see what happens when we try to do the same with the second program:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2257849ffc4a091d1f737b5c842f10cf/href">https://medium.com/media/2257849ffc4a091d1f737b5c842f10cf/href</a></iframe><p>Again, the result of the first line is fully typed already, so we skip straight to the second line.</p><p>The second line gives us neither a type for the left hand side of the assignment, nor the right-hand side. We thus need make use of Swift’s default inference type for integer literals: Int and thus make it the inferred type of bar.</p><p>And this is where things begin to fall apart: We just inferred bar to be of type Int, but func foo expects a value of type UInt.</p><p>Without some kind of backtracking beyond its type inference scopes Swift is incapable of correcting this obvious mistake.</p><h3>Conclusion</h3><p>Having discussed the overall operation of Swift’s type inference, we now understand why it sometimes fails to properly deduce the correct types for some snippets of code, leading to surprise and confusion for those not in the know.</p><p>Exposure to additional programming languages (just as for natural ones) gives one the great opportunity to approach a situation with a different pair of glasses. One such language in the context of Swift can be Rust. A language which shares quite a bit of language culture and concepts with Swift and was listed as a major inspiration for Swift during its initial release event at WWDC.</p><p>Rust, as it happens, does not even blink when confronted with equivalent snippets of code: <a href="https://is.gd/zmBCTq"><em>it just works™</em></a>.</p><p>This is in big parts made possible by a type checker whose type inference can reach way beyond single expressions/statements. It is worth mentioning however that, while rather similar on the surface, Rust’s type system does differ quite a bit from Swift’s (of which neither I would dare to call simpler than the other), so take this comparison with a grain of salt.</p><p>All this being said the wishful programmer in me just hopes these matters to improve sooner rather than later for Swift.</p><p>Update: Upon having received a couple of comments on how “all examples are contrived cases of foo being <em>falsely(?)</em> typed as Int” I should clarify:</p><p>It’s specifically the special handling of Int that I’m criticizing. If (integer) literals were to be type-erased as ExpressibleByIntegerLiteral then the behavior of Swift’s type checker would be <a href="https://en.wikipedia.org/wiki/Principle_of_least_astonishment">much more predictable</a>/understandable and overall consistent:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e93c7d8ef8a32775a70e9d8c7fa9d6f0/href">https://medium.com/media/e93c7d8ef8a32775a70e9d8c7fa9d6f0/href</a></iframe><p>No surprises to be had any more. It works as expected. And if things end up being ambiguous, we get a compiler error, as would be expected. Adding ambiguity to your code (without knowing) doesn’t change its behavior (as is the case right now), but instead makes it fail compilation:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/451d16998235f8d318439d5dfd12516a/href">https://medium.com/media/451d16998235f8d318439d5dfd12516a/href</a></iframe><p>Predictability &amp; consistency are paramount to a smooth learning curve.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7c4f13f6d2a4" width="1" height="1" alt=""><hr><p><a href="https://medium.com/definiteloops/playing-jenga-with-swifts-type-checker-7c4f13f6d2a4">Playing Jenga with Swift’s Type Checker</a> was originally published in <a href="https://medium.com/definiteloops">DefiniteLoops</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>