<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Jun 2, 2016 at 4:12 AM, Simon Peyton Jones <span dir="ltr"><<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">





<div lang="EN-GB" link="blue" vlink="purple">
<div><span class="">
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:36pt">
If names get different ordering keys when reified from different modules (seems like they'd have to, particularly given ghc's "-j"), then we end up with an unpleasant circumstance where these do not compare as equal<u></u><u></u></p>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</span><p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
The I believe that global, top level names (NameG) are not subject to this ordering stuff, so I don’t think this problem can occur.</p></div></div></blockquote><div><br></div><div>True, top level names are NameG.  The reified Info for a top level Dec may include NameU, though.  For example, the type variables in 'Maybe' are NameU:</div><div><br></div><div><div>$(do TyConI (DataD _ _ [KindedTV (Name _ nf) _] _ _ _) <- reify ''Maybe</div><div>     lift (show nf))</div><div><br></div><div>The resulting expression is something like "NameU 822083586"</div></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div lang="EN-GB" link="blue" vlink="purple"><div><span class=""><p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm"><u></u></p>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:36pt">
This is a breaking change and it doesn't fix the problem that NameFlavour is<u></u><u></u></p>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:36pt">
not abstract and leaks the Uniques. It would break at least:<u></u><u></u></p>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</span><p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
But why is NameU exposed to clients?   GHC needs to know, but clients don’t.  What use are these packages making of it?</p></div></div></blockquote><div><br></div><div>It's being leaked in the public inteface via Ord.  The Eq instance is fine, because these are Uniques, so the results should be consistent.  </div><div><br></div><div>There are two goals in contention here:</div><div><br></div><div>1) Having some ordering on Names so that they can be used in Map or Set</div><div>2) Having law-abiding Eq / Ord instances.  We'd need a 'PartialOrd' to really handle these well.  In that case, the ordering would be based on everything but the NameU int, but 'Eq' would still follow it</div><div><br></div><div>A few ideas for different approaches to resolving this:</div><div><br></div><div>1) Document it.  Less appealing than fixing it in the API, but still would be good.  </div><div><br></div><div>2) Remove the 'Ord' instance, and force the user to pick 'NamePartialOrd' newtype (partial ord on the non-unique info), or 'UnstableNameOrd' newtype (current behavior).  A trickyness of this approach is that you'd need containers that can handle (PartialOrd k, Eq k) keys.  In lots of cases people are using the 'Ord' instance with 'Name's that are not 'NameU', so this would break a lot of code that was already deterministic.</div><div><br></div><div>3) Some approaches like this ordering key, but I'm not sure how it will help when comparing NameUs from different modules?</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div lang="EN-GB" link="blue" vlink="purple"><div><p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm"><u></u></p>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
S<u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:Calibri,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:Calibri,sans-serif"><u></u> <u></u></span></p>
<div style="border-style:none none none solid;border-left-width:1.5pt;border-left-color:blue;padding:0cm 0cm 0cm 4pt">
<div>
<div style="border-style:solid none none;border-top-width:1pt;border-top-color:rgb(225,225,225);padding:3pt 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:11pt;font-family:Calibri,sans-serif">From:</span></b><span lang="EN-US" style="font-size:11pt;font-family:Calibri,sans-serif"> ghc-devs [mailto:<a href="mailto:ghc-devs-bounces@haskell.org" target="_blank">ghc-devs-bounces@haskell.org</a>]
<b>On Behalf Of </b>Michael Sloan<br>
<b>Sent:</b> 02 June 2016 02:07<br>
<b>To:</b> Bartosz Nitka <<a href="mailto:niteria@gmail.com" target="_blank">niteria@gmail.com</a>><br>
<b>Cc:</b> ghc-devs Devs <<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a>><br>
<b>Subject:</b> Re: Template Haskell determinism<u></u><u></u></span></p>
</div>
</div><div><div class="h5">
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
+1 to solving this.  Not sure about the approach, but assuming the following concerns are addressed, I'm (+1) on it too:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
This solution is clever!  However, I think there is some difficulty to determining this ordering key.  Namely, what happens when I construct the (Set Name) using results from multiple reifies?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
One solution is to have the ordering key be a consecutive supply that's initialized on a per-module basis.  There is still an issue there, though, which is that you might store one of these names in a global IORef that's used by a later TH splice.  Or, similarly,
 serialize the names to a file and later load them.  At least in those cases you need to use 'runIO' to break determinism.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
If names get different ordering keys when reified from different modules (seems like they'd have to, particularly given ghc's "-j"), then we end up with an unpleasant circumstance where these do not compare as equal.  How about having the Eq instance ignore
 the ordering key?  I think that mostly resolves this concern.  This implies that the Ord instance should also yield EQ and ignore the ordering key, when the unique key matches.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
One issue with this is that switching the order of reify could unexpectedly vary the behavior.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
Does the map in TcGblEnv imply that a reify from a later module will get the same ordering key?  So does this mean that the keys used in a given reify depend on which things have already been reified?  In that case, then this is also an issue with your solution. 
 Now, it's not a big problem at all, just surprising to the user.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
If the internal API for Name does change, may as well address <a href="https://ghc.haskell.org/trac/ghc/ticket/10311" target="_blank">
https://ghc.haskell.org/trac/ghc/ticket/10311</a> too.  I agree with SPJ's suggested solution of having both the traditional package identifier and package keys in 'Name'.  <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
-Michael<u></u><u></u></p>
</div>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
On Tue, May 31, 2016 at 6:54 AM, Bartosz Nitka <<a href="mailto:niteria@gmail.com" target="_blank">niteria@gmail.com</a>> wrote:<u></u><u></u></p>
<blockquote style="border-style:none none none solid;border-left-width:1pt;border-left-color:rgb(204,204,204);padding:0cm 0cm 0cm 6pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
Template Haskell with its ability to do arbitrary IO is non-deterministic by<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
design. You could for example embed the current date in a file. There is<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
however one kind of non-deterministic behavior that you can trigger <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
accidentally. It has to do with how Names are reified. If you take a look at <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
the definition of reifyName you can see that it puts the assigned Unique in a<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
NameU:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
  reifyName :: NamedThing n => n -> TH.Name<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
  reifyName thing<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
    | isExternalName name = mk_varg pkg_str mod_str occ_str<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
    | otherwise           = TH.mkNameU occ_str (getKey (getUnique name))<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
    ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
NameFlavour which NameU is a constructor of has a default Ord instance, meaning<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
that it ends up comparing the Uniques. The relative ordering of Uniques is not<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
guaranteed to be stable across recompilations [1], so this can lead to <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
ABI-incompatible binaries.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
This isn't an abstract problem and it actually happens in practice. The <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
microlens package keeps Names in a Set and later turns that set into a list.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
The results have different orders of TyVars resulting in different ABI hashes<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
and can potentially be optimized differently.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
I believe it's worth to handle this case in a deterministic way and I have a<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
solution in mind. The idea is to extend NameU (and potentially NameL) with an<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
ordering key. To be more concrete:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
-   | NameU !Int<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
+   | NameU !Int !Int<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
This way the Ord instance can use a stable key and the problem reduces to<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
ensuring the keys are stable. To generate stable keys we can use the fact that<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
reify traverses the expressions in the same order every time and sequentially<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
allocate new keys based on traversal order. The way I have it implemented now <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
is to add a new field in TcGblEnv which maps Uniques to allocated keys:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
+        tcg_th_names :: TcRef (UniqFM Int, Int),<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
Then the reifyName and qNewName do the necessary bookkeeping and translate the<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
Uniques on the fly.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
This is a breaking change and it doesn't fix the problem that NameFlavour is<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
not abstract and leaks the Uniques. It would break at least:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
- singletons<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
- th-lift<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
- haskell-src-meta<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
- shakespeare<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
- distributed-closure<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
I'd like to get feedback if this is an acceptable solution and if the problem<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
is worth solving.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
Cheers,<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
Bartosz<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
[1] <a href="https://ghc.haskell.org/trac/ghc/wiki/DeterministicBuilds#NondeterministicUniques" target="_blank">
https://ghc.haskell.org/trac/ghc/wiki/DeterministicBuilds#NondeterministicUniques</a><u></u><u></u></p>
</div>
</div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:12pt;margin-left:0cm">
<br>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<a href="https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail.haskell.org%2fcgi-bin%2fmailman%2flistinfo%2fghc-devs&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7c1a4a84c9341546403e1508d38a8246ee%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=mjEDuk%2fuRsDLg0q63zaIBeh5e2IyfKnKjcEcRLDvERE%3d" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><u></u><u></u></p>
</blockquote>
</div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:6pt;margin-left:0cm">
<u></u> <u></u></p>
</div>
</div></div></div>
</div>
</div>

</blockquote></div><br></div></div>