CINXE.COM

<!DOCTYPE html> <html id="page"> <head> <meta http-equiv="Content-Type" content="text/html;charset=UTF-8"/> <meta name="viewport" content="width=device-width"/> <title>The type inference mystery novel part 2 - Haxe - The Cross-platform Toolkit</title> <link rel="stylesheet" type="text/css" href="/css/bootstrap.min.css"/> <link rel="stylesheet" type="text/css" href="/css/font-awesome.css"/> <link rel="stylesheet" type="text/css" href="/css/style.css?v=2018-03-05"/> <link rel="stylesheet" type="text/css" href="/css/haxe-nav.css"/> <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico"/> <link href="/css/open_sans.css" rel="stylesheet" type="text/css"/> <link rel="alternate" type="application/atom+xml" title="RSS Feed haxe.org" href="https://haxe.org/blog/rss/"/> <link rel="search" type="application/opensearchdescription+xml" title="Search haxe.org" href="https://haxe.org/opensearch.xml"/>  <meta name="description" content="Will Detective Haxe redeem himself and overcome his inner demons?"/>  <meta name="twitter:card" content="summary"/> <meta name="twitter:creator" content="@haxe_org"/> <meta name="twitter:site" content="@haxe_org"/> <meta name="twitter:title" content="The type inference mystery novel part 2 - Haxe - The Cross-platform Toolkit"/> <meta name="twitter:description" value="Will Detective Haxe redeem himself and overcome his inner demons?"/> <meta name="twitter:image" content="https://haxe.org/img/share.jpg"/>  <meta property="og:title" content="The type inference mystery novel part 2 - Haxe - The Cross-platform Toolkit"/> <meta property="og:type" content="article"/> <meta property="og:image" content="https://haxe.org/img/share.jpg"/> <meta property="og:description" content="Will Detective Haxe redeem himself and overcome his inner demons?"/> <meta property="og:site_name" content="Haxe - The Cross-platform Toolkit"/> </head> <body> <nav class="section nav dark"> <div class="navbar navbar-fixed-top navbar-inverse"> <div class="navbar-inner"> <button class="btn btn-navbar" data-target=".nav-collapse" data-toggle="collapse" type="button"> </button> <a class="brand haxe-logo" href="/"><img alt="Haxe" height="21" onerror="this.src='/img/haxe-logo-horizontal-on-dark.png'" src="/img/haxe-logo-horizontal-on-dark.svg" width="107"/></a> <div class="nav-collapse collapse"> <ul class="nav pull-right search-link-menu"> <li> <a href="/search/"></a> </li> </ul> <div class="container"><ul class="nav"> <li class=""><a href="/">Home</a></li><li class=""><a href="/download/">Download</a></li><li class=" active"><a href="/blog/" class="active">Blog</a></li><li class=" dropdown"><a href="/use-cases/" data-toggle="dropdown" class="dropdown-toggle">Use Cases </a><ul class="dropdown-menu"><li class=""><a href="/use-cases/">Overview</a></li><li class=""><a href="/use-cases/games/">Games</a></li><li class=""><a href="/use-cases/web/">Web</a></li><li class=""><a href="/use-cases/mobile/">Mobile</a></li><li class=""><a href="/use-cases/desktop/">Desktop</a></li><li class=""><a href="/use-cases/cli/">Command Line</a></li><li class=""><a href="/use-cases/cross-platform-apis/">Cross Platform APIs</a></li><li class=" divider"></li><li class=""><a href="/use-cases/who-uses-haxe.html">Who Uses Haxe</a></li></ul></li><li class=" dropdown"><a href="/foundation/" data-toggle="dropdown" class="dropdown-toggle">Haxe Foundation </a><ul class="dropdown-menu"><li class=""><a href="/foundation/">About The Foundation</a></li><li class=""><a href="/foundation/people.html">Who is who</a></li><li class=""><a href="/foundation/jobs.html">Jobs</a></li><li class=" divider"></li><li class=""><a href="/foundation/supported-projects.html">Supported Projects</a></li><li class=""><a href="/foundation/support-plans.html">Support Plans</a></li><li class=""><a href="/foundation/donate.html">Donate</a></li><li class=" divider"></li><li class=""><a href="/foundation/branding.html">Branding</a></li><li class=""><a href="/foundation/shop.html">Shop</a></li><li class=""><a href="/foundation/open-source.html">Open Source</a></li><li class=""><a href="/foundation/contact.html">Contact</a></li></ul></li><li class=""><a href="/foundation/support-plans.html">Support Plans</a></li><li class=" divider"></li><li class=" dropdown"><a href="/documentation/introduction" data-toggle="dropdown" class="dropdown-toggle">Learn Haxe </a><ul class="dropdown-menu"><li class=""><a href="/documentation/introduction/">Introduction</a></li><li class=""><a href="/manual/">Manual</a></li><li class=""><a href="https://code.haxe.org/">Code Cookbook</a></li><li class=""><a href="https://api.haxe.org/">API Documentation</a></li><li class=" divider"></li><li class=""><a href="/videos/">Videos</a></li><li class=" divider"></li><li class=""><a href="https://try.haxe.org/">Try Haxe online</a></li><li class=""><a href="https://lib.haxe.org/">Haxelib</a></li></ul></li> <li class=" dropdown"> <a href="/HaxeFoundation" data-toggle="dropdown" class="dropdown-toggle">Connect </a> <ul class="dropdown-menu"> <li><a href="https://github.com/HaxeFoundation" rel="external"> GitHub</a></li> <li><a href="https://github.com/HaxeFoundation/haxe/issues" rel="external"> Bug reports</a></li> <li><a href="https://stackoverflow.com/questions/tagged/haxe" rel="external"> Stack Overflow</a></li> <li><a href="http://community.haxe.org/" rel="external"> Forums</a></li> <li><a href="https://discordapp.com/invite/0uEuWH3spjck73Lo" rel="external nofollow"> Discord</a></li> <li><a href="https://gitter.im/HaxeFoundation/haxe" rel="external nofollow"> Gitter</a></li> <li><a href="https://haxe.org/blog"> Blog</a></li> <li class="divider"></li> <li><a href="https://www.facebook.com/haxe.org/" rel="external"> Facebook</a></li> <li><a href="https://twitter.com/search?q=%23haxe" rel="external"> #haxe</a></li> <li><a href="https://twitter.com/haxelang" rel="external"> @haxelang</a></li> <li><a href="https://twitter.com/haxe_org" rel="external"> @haxe_org</a></li> <li class="divider"></li> <li><a href="https://haxe.org/foundation/contact.html" rel="external">Contact</a></li> </ul> </li> </ul></div> </div> </div> </div> </nav> <div class="page-wrap"> <header class="section article-header" style="background-image: url(/img/blog/backgrounds/SsoKppt2pqY.jpg)"> <div class="darken-bg"></div> <div class="container"> <h1>The type inference mystery novel part 2</h1> Will Detective Haxe redeem himself and overcome his inner demons? Article by <a href="/blog/author/simn/" class="label pushstate">Simon Krajewski</a> on <a href="/blog/type-inference-mystery-novel-part-2/" class="label pushstate">2020-07-14</a>. <a href="#disqus_thread" class="label disqus-comment-count" data-disqus-identifier="57">Comments</a> </div> </header> <link rel="home" type="application/rss+xml" href="/blog/rss/"/> <div class="section article-view"> <div class="container"> <article><h1>The type inference mystery novel part 2</h1> <a href="https://haxe.org/blog/type-inference-mystery-novel/">Last time we spoke</a>, Detective Haxe was in a bad spot. The villains had managed to lead him astray by overloading his deductive process. There was a misconception, a glaring contradiction that could only mean that an invalid assumption had been made. And although there was a glimmer of hope at the end, the audience was left wondering if our protagonist would persevere. Now, a month later, Detective Haxe has again assembled everyone in the room and is about to announce the culprit. It seems like a d茅j脿 vu, the recurrence of an event that took place in the past. This would be about the same case, the same suspects, and the same detective. But something had changed... In order to understand what transpired, we have to travel back in time. No monomorphs were harmed during the making of this article. <h2>The Freedom of Constraints</h2> <a href="https://en.wikipedia.org/wiki/Paul_Watzlawick">Paul Watzlawick</a> asserted that "every communication has a content and relationship aspect". This implies that we can't simply take any given content and detach it from its context without losing its overall meaning. I can jokingly call a friend a "stupid idiot", but if I try the same with a random stranger on the street, the results might be quite different, even if the delivery in terms of tonality and such is identical. In a similar fashion, while the term "dying infants" might offend or shock a lot of people, it is a perfectly acceptable thing to discuss among developers of generational garbage collectors. I asked a non-programmer friend if the term "constraint" has a negative connotation for him, and he agreed that it does. This didn't surprise me, because we generally associcate a constraint with a limitation, and that's generally something negative. However, the interpretation is likely more favorable when asking a programmer, mathematician, or BDSM practitioner. That brings me to the topic of Constrained Monomorphs, which were <a href="https://github.com/HaxeFoundation/haxe/pull/9549">implemented</a> shortly after the last type inference article. In that article, we learned that monomorphs can be bound, which is the process of associating a type with them. Now, we can also constrain them, which is a bit more gentle. We use this, for example, when dealing what used to be "open structures": <pre class="highlighted"> class Main { static function main() {} static function test(a) { a.age = 24; $type(a); // Unknown<0> : { age : Int } } } </pre> Inside the <code>test</code> function, after the <code>a.age = 24</code> assignment, we know that <code>a</code> has a structure which has (at least) a field <code>age</code> of type <code>Int</code>. However, we don't know what exactly the type is, hence it is still "unknown". This is what the print tells us. The notation is borrowed from how <a href="https://haxe.org/manual/type-system-type-parameter-constraints.html">type parameter constraints</a> are defined, and we indeed use constrained monomorphs for those as well: <pre class="highlighted"> class Main { static function main() { var a = test(); $type(a); // Unknown<0> : Float } static function test<T:Float>():T { return null; } } </pre> Again, we don't know what exactly the type is, but it is at least <code>Float</code>. It could be <code>Int</code>, or something else that can be assigned to <code>Float</code>. In general, constraints are very useful whenever we want to describe some sort of lower bound. There is, however, a slight risk here: If our constraints are too liberal, they could <strike>enroll in an American college</strike> create a type-hole. Imagine if, in the open structure example, we would just allow further and further structural constraints to be added, even outside the function in question. This would weaken our typing, as a typo like <code>agee</code> would create a new field constraint instead of a compilation error. Intuitively, we have to stop allowing additional constraints once we're done typing the function. <h2>Free Spirits</h2> Honestly, Detective Haxe is a bit of a dolt sometimes. He conducts all these fancy investigations, weaves this beautiful web of relationships between various actors, and grows trees that reach the heavens and span the horizon - and yet he never even kept a proper list of the monomorphic suspects he's observing. They are free spirits that roam the Haxian Plains, which is very romantic, but not very pratical when you actually want to get a hold of them. And we do want to get a hold of them. We just established that we have to stop allowing additional inference - that the constrained monomorph has to be closed. In order to do so, we need to know how to contact it so that we can turn towards them after typing a function and say "Just one more thing..." Fortunately, this was straightforward for the open structure case because there's only a single place where these monomorphs are created, so it was <a href="https://github.com/HaxeFoundation/haxe/pull/9549/files#diff-7751fb5a214587d52bb38306d17d7dbbR518">part of the original pull request</a>. We can observe that this works as advertised: <pre class="highlighted"> class Main { static function main() { var x = null; $type(x); // Unknown<0> $type(test); // (a : { age : Int }) -> Void test(x); $type(x); // { age : Int } x.agee; // { age : Int } has no field agee (Suggestion: age) } static function test(a) { a.age = 24; $type(a); // Unknown<0> : { age : Int } } } </pre> We assign the monomorph that belongs to <code>x</code> to the argument of the <code>test</code> function. While <code>a</code> inside that function is still a constrained monomorph, we can see that the argument type of the <code>test</code> function is <code>{ age : Int }</code> from the outside - a good old plain structure type. Thus, the monomorph of <code>x</code> ends up being bound to the structure type and a typo like <code>x.agee</code> is detected as expected. All this is a consequence of Haxe keeping track of the monomorph of <code>a</code> while typing <code>test</code>, and then closing the monomorph afterwards. Closing a monomorph means looking at its constraints and determining a type that it should be bound to. Currently, this happens in two situations:<ol><li>If the monomorph is structurally constrained like in the example here, bind it to a structure type that contains all the structural constraint fields.</li><li>If the monomorph is constrained to a single type, bind it to that type.</li></ol> This is all that was needed for these open structure monomorphs. But there are others. Monomorphs are everywhere. One might be right behind you as you're reading this, waiting for you to be so immersed in this story that you stop paying attention to your surroundings, and then... But fear not, for Detective Haxe is ahead of the curve. He equipped his trusty bug net and went ahead <a href="https://github.com/HaxeFoundation/haxe/commit/5fad913a1c843fe413ae3df214ed137c60f764f4">catching all those critters</a>. Well, not all of them, but most of them. Some remain free and might be plotting their revenge, but that's a problem for another day. For now, it's time for the climax. <h2>Reductio ad Impossibile</h2> We are back in the present time. Detective Haxe has just laid out the original example again: <pre class="highlighted"> extern class Extern { @:overload static function itWasYou(i1:Int, i2:Int):Void; @:overload static function itWasYou(s1:String, s2:String):Void; @:overload static function itWasYou(f1:Float, f2:Float):Void; } function main() { var a = null; $type(a); // Unknown<0> Extern.itWasYou(a, "foo"); } </pre> Just like before, he starts his deduction. Looking at the first overload, he again concludes that <code>a</code> must be <code>Int</code>. At this point, the true culprit quietly snickers. "He's falling for the same trick again. What a stupid idiot." The detective again tries to unify <code>"foo"</code> with <code>i2:Int</code>, and, again, this unification doesn't work. The culprit can barely contain his laughter. But then it happens. <blockquote> "Therefore, I have indirectly proven that <code>a</code> cannot be <code>Int</code>, because that assumption leads to a contradiction!"</blockquote> A dramatic pause <blockquote> "I was just pretending to be retarded!"</blockquote> The culprit gasps. <blockquote> "Now, I shall <a href="https://github.com/HaxeFoundation/haxe/pull/9696">reset</a> that assumption and start over!"</blockquote> There it is. <blockquote> "If we assume that <code>a</code> is actually <code>String</code> from the second overload, then we can assign <code>"foo"</code> to <code>s2:String</code> - the unification works! This is the truth of this case!"</blockquote> And with that, the mystery was solved. <h2>Aftermath</h2> In the end, the actual change was quite minor: once we had a list of all the monomorphs, all we needed to do is remember their state before unifying the call to an overloaded function and then resetting it upon failure. I already had this idea when writing the last article, but actually finding these dreaded monomorphs was more annoying than I thought. Technically, the whole constrained monomorph business is not strictly related to this overload reset problem. However, reorganizing monomorph handling like that made it a lot simpler to deal with this problem, too. We also got <a href="https://github.com/HaxeFoundation/haxe/issues/9559">type parameter constraints on local function</a> as a fallout from this change, and there are some <a href="https://github.com/HaxeFoundation/haxe/issues/9553">plans</a> to further extend this. Overall, I think Haxe's type inference is heading in the right direction and I look forward to further improvements (and writing about them)! If you have suggestions for future articles, please let me know. ... and if you see Detective Haxe at the bar, don't buy him a drink. Last time somebody did that, he ended up hopping through the precinct with his pants at his ankles while repeatedly yelling "Int should be Int!"</article> <div class="well"> <div class="row-fluid"> <div class="span2"> <img src="/img/people/SimonKrajewski.jpg" class="img-circle" alt="Avatar for Simon Krajewski" width="72" height="72" title="Simon Krajewski"/> </div> <div class="span10"> <h3>By <a href="/blog/author/simn/">Simon Krajewski</a> </h3> Published <a href="/blog/type-inference-mystery-novel-part-2/" class="pushstate">2020-07-14</a> <div class="tags"> </div> <div class="share-buttons">  <a href="https://twitter.com/share" class="twitter-share-button" style="display:inline-block" data-show-count="false">Tweet</a> <script async="async" src="//platform.twitter.com/widgets.js" charset="utf-8"></script>    <div id="fb-root" style="display:inline-block"></div> <script>(function(d, s, id) { var js, fjs = d.getElementsByTagName(s)[0]; if (d.getElementById(id)) return; js = d.createElement(s); js.id = id; js.src = "//connect.facebook.net/en_US/all.js#xfbml=1"; fjs.parentNode.insertBefore(js, fjs); }(document, 'script', 'facebook-jssdk'));</script>  <div class="fb-like" data-href="https://haxe.org/blog/type-inference-mystery-novel-part-2/" style="display:inline-block" data-layout="button_count" data-action="like" data-show-faces="true"></div> </div> </div> </div> </div> <div id="disqus_thread"></div> </div> </div> <script> window.DISQUSWIDGETS = undefined; window.disqus_shortname = "haxe"; window.disqus_config = function () { this.page.title = "The type inference mystery novel part 2"; this.page.identifier = "57"; this.page.url = "https://haxe.org/blog/type-inference-mystery-novel-part-2/"; }; </script> <script id="disqus-script" src="//haxe.disqus.com/embed.js"></script> <script src="//haxe.disqus.com/count.js"></script> </div> <footer class="section dark site-footer"> <div class="container"> <div class="sitemap clearfix"> <ul> <li class="column"> <h5><a href="/">Home</a></h5> <h5><a href="/download/">Download</a></h5> <h5><a href="/blog/">Blog</a></h5> <h5><a href="/foundation/support-plans.html">Support Plans</a></h5> </li> <li class="column"> <h5><a href="/use-cases/">Use Cases</a></h5> <ul> <li><a href="/use-cases/">Overview</a></li> <li><a href="/use-cases/games/">Games</a></li> <li><a href="/use-cases/web/">Web</a></li> <li><a href="/use-cases/mobile/">Mobile</a></li> <li><a href="/use-cases/desktop/">Desktop</a></li> <li><a href="/use-cases/cli/">Command Line</a></li> <li><a href="/use-cases/cross-platform-apis/">Cross Platform APIs</a></li> <li><a href="/use-cases/who-uses-haxe.html">Who Uses Haxe</a></li> </ul> </li> <li class="column"> <h5><a href="/foundation/">Haxe Foundation</a></h5> <ul> <li><a href="/foundation/">About The Foundation</a></li> <li><a href="/foundation/people.html">Who is who</a></li> <li><a href="/foundation/jobs.html">Jobs</a></li> <li><a href="/foundation/supported-projects.html">Supported Projects</a></li> <li><a href="/foundation/support-plans.html">Support Plans</a></li> <li><a href="/foundation/donate.html">Donate</a></li> <li><a href="/foundation/branding.html">Branding</a></li> <li><a href="/foundation/shop.html">Shop</a></li> <li><a href="/foundation/open-source.html">Open Source</a></li> <li><a href="/foundation/contact.html">Contact</a></li> </ul> </li> <li class="column"> <h5><a href="/documentation/introduction">Learn Haxe</a></h5> <ul> <li><a href="/documentation/introduction/">Introduction</a></li> <li><a href="/manual/">Manual</a></li> <li><a href="https://code.haxe.org/">Code Cookbook</a></li> <li><a href="https://api.haxe.org/">API Documentation</a></li> <li><a href="/videos/">Videos</a></li> <li><a href="https://try.haxe.org/">Try Haxe online</a></li> <li><a href="https://lib.haxe.org/">Haxelib</a></li> </ul> </li> </ul> </div> <div class="copyright"> © 2024 <a href="/foundation/" title="Haxe Foundation Website" class="hf-link">Haxe Foundation</a> </div> </div> </footer> <script src="/js/jquery.min.js"></script> <script src="/js/bootstrap.min.js"></script> <script src="/js/client.min.js"></script>  <noscript><iframe src="//www.googletagmanager.com/ns.html?id=GTM-NXV3XR" height="0" width="0" style="display:none;visibility:hidden"></iframe></noscript> <script>(function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start': new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0], j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src= '//www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f); })(window,document,'script','dataLayer','GTM-NXV3XR');</script>  </body> </html>