<div dir="ltr">Hey, sorry for not getting back to this sooner!<div><br>Perhaps I should have added the following to my list of goals in contention:</div><div><br></div><div>(3) (==) shouldn't yield True for Names that have different unique ids.<br><br></div><div>We can only have stable comparisons if goal (3) isn't met, and two different unique Names would be considered to be equivalent based on the nameBase.  This is because Ord is a total order, not a partial order.  As described in my prior email, PartialOrd could be added, but it'd be inconvenient to use with existing Ord based containers.</div><div><div><br></div></div><div>-Michael</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Jun 5, 2016 at 10:15 AM, Edward Z. Yang <span dir="ltr"><<a href="mailto:ezyang@mit.edu" target="_blank">ezyang@mit.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I must admit, I am a bit confused by this discussion.<br>
<br>
It is true that every Name is associated with a Unique.  But you don't<br>
need the Unique to equality/ordering tests; the names also contain<br>
enough (stable) information for stable comparisons of that sort.  So<br>
why don't we expose that instead of the Unique?<br>
<br>
Edward<br>
<br>
Excerpts from Michael Sloan's message of 2016-06-04 18:44:03 -0700:<br>
<div><div class="h5">> On Thu, Jun 2, 2016 at 4:12 AM, Simon Peyton Jones <<a href="mailto:simonpj@microsoft.com">simonpj@microsoft.com</a>><br>
> wrote:<br>
><br>
> > If names get different ordering keys when reified from different modules<br>
> > (seems like they'd have to, particularly given ghc's "-j"), then we end up<br>
> > with an unpleasant circumstance where these do not compare as equal<br>
> ><br>
> ><br>
> ><br>
> > The I believe that global, top level names (NameG) are not subject to this<br>
> > ordering stuff, so I don’t think this problem can occur.<br>
> ><br>
><br>
> True, top level names are NameG.  The reified Info for a top level Dec may<br>
> include NameU, though.  For example, the type variables in 'Maybe' are<br>
> NameU:<br>
><br>
> $(do TyConI (DataD _ _ [KindedTV (Name _ nf) _] _ _ _) <- reify ''Maybe<br>
>      lift (show nf))<br>
><br>
> The resulting expression is something like "NameU 822083586"<br>
><br>
> > This is a breaking change and it doesn't fix the problem that NameFlavour<br>
> > is<br>
> ><br>
> > not abstract and leaks the Uniques. It would break at least:<br>
> ><br>
> ><br>
> ><br>
> > But why is NameU exposed to clients?   GHC needs to know, but clients<br>
> > don’t.  What use are these packages making of it?<br>
> ><br>
><br>
> It's being leaked in the public inteface via Ord.  The Eq instance is fine,<br>
> because these are Uniques, so the results should be consistent.<br>
><br>
> There are two goals in contention here:<br>
><br>
> 1) Having some ordering on Names so that they can be used in Map or Set<br>
> 2) Having law-abiding Eq / Ord instances.  We'd need a 'PartialOrd' to<br>
> really handle these well.  In that case, the ordering would be based on<br>
> everything but the NameU int, but 'Eq' would still follow it<br>
><br>
> A few ideas for different approaches to resolving this:<br>
><br>
> 1) Document it.  Less appealing than fixing it in the API, but still would<br>
> be good.<br>
><br>
> 2) Remove the 'Ord' instance, and force the user to pick 'NamePartialOrd'<br>
> newtype (partial ord on the non-unique info), or 'UnstableNameOrd' newtype<br>
> (current behavior).  A trickyness of this approach is that you'd need<br>
> containers that can handle (PartialOrd k, Eq k) keys.  In lots of cases<br>
> people are using the 'Ord' instance with 'Name's that are not 'NameU', so<br>
> this would break a lot of code that was already deterministic.<br>
><br>
> 3) Some approaches like this ordering key, but I'm not sure how it will<br>
> help when comparing NameUs from different modules?<br>
><br>
> > S<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
</div></div>> > *From:* ghc-devs [mailto:<a href="mailto:ghc-devs-bounces@haskell.org">ghc-devs-bounces@haskell.org</a>] *On Behalf Of *Michael<br>
> > Sloan<br>
> > *Sent:* 02 June 2016 02:07<br>
> > *To:* Bartosz Nitka <<a href="mailto:niteria@gmail.com">niteria@gmail.com</a>><br>
> > *Cc:* ghc-devs Devs <<a href="mailto:ghc-devs@haskell.org">ghc-devs@haskell.org</a>><br>
> > *Subject:* Re: Template Haskell determinism<br>
<div><div class="h5">> ><br>
> ><br>
> ><br>
> > +1 to solving this.  Not sure about the approach, but assuming the<br>
> > following concerns are addressed, I'm (+1) on it too:<br>
> ><br>
> ><br>
> ><br>
> > This solution is clever!  However, I think there is some difficulty to<br>
> > determining this ordering key.  Namely, what happens when I construct the<br>
> > (Set Name) using results from multiple reifies?<br>
> ><br>
> ><br>
> ><br>
> > One solution is to have the ordering key be a consecutive supply that's<br>
> > initialized on a per-module basis.  There is still an issue there, though,<br>
> > which is that you might store one of these names in a global IORef that's<br>
> > used by a later TH splice.  Or, similarly, serialize the names to a file<br>
> > and later load them.  At least in those cases you need to use 'runIO' to<br>
> > break determinism.<br>
> ><br>
> ><br>
> ><br>
> > If names get different ordering keys when reified from different modules<br>
> > (seems like they'd have to, particularly given ghc's "-j"), then we end up<br>
> > with an unpleasant circumstance where these do not compare as equal.  How<br>
> > about having the Eq instance ignore the ordering key?  I think that mostly<br>
> > resolves this concern.  This implies that the Ord instance should also<br>
> > yield EQ and ignore the ordering key, when the unique key matches.<br>
> ><br>
> ><br>
> ><br>
> > One issue with this is that switching the order of reify could<br>
> > unexpectedly vary the behavior.<br>
> ><br>
> ><br>
> ><br>
> > Does the map in TcGblEnv imply that a reify from a later module will get<br>
> > the same ordering key?  So does this mean that the keys used in a given<br>
> > reify depend on which things have already been reified?  In that case, then<br>
> > this is also an issue with your solution.  Now, it's not a big problem at<br>
> > all, just surprising to the user.<br>
> ><br>
> ><br>
> ><br>
> ><br>
> ><br>
> > If the internal API for Name does change, may as well address<br>
> > <a href="https://ghc.haskell.org/trac/ghc/ticket/10311" rel="noreferrer" target="_blank">https://ghc.haskell.org/trac/ghc/ticket/10311</a> too.  I agree with SPJ's<br>
> > suggested solution of having both the traditional package identifier and<br>
> > package keys in 'Name'.<br>
> ><br>
> ><br>
> ><br>
> > -Michael<br>
> ><br>
> ><br>
> ><br>
> > On Tue, May 31, 2016 at 6:54 AM, Bartosz Nitka <<a href="mailto:niteria@gmail.com">niteria@gmail.com</a>> wrote:<br>
> ><br>
> > Template Haskell with its ability to do arbitrary IO is non-deterministic<br>
> > by<br>
> ><br>
> > design. You could for example embed the current date in a file. There is<br>
> ><br>
> > however one kind of non-deterministic behavior that you can trigger<br>
> ><br>
> > accidentally. It has to do with how Names are reified. If you take a look<br>
> > at<br>
> ><br>
> > the definition of reifyName you can see that it puts the assigned Unique<br>
> > in a<br>
> ><br>
> > NameU:<br>
> ><br>
> ><br>
> ><br>
> >   reifyName :: NamedThing n => n -> TH.Name<br>
> ><br>
> >   reifyName thing<br>
> ><br>
> >     | isExternalName name = mk_varg pkg_str mod_str occ_str<br>
> ><br>
> >     | otherwise           = TH.mkNameU occ_str (getKey (getUnique name))<br>
> ><br>
> >     ...<br>
> ><br>
> > NameFlavour which NameU is a constructor of has a default Ord instance,<br>
> > meaning<br>
> ><br>
> > that it ends up comparing the Uniques. The relative ordering of Uniques is<br>
> > not<br>
> ><br>
> > guaranteed to be stable across recompilations [1], so this can lead to<br>
> ><br>
> > ABI-incompatible binaries.<br>
> ><br>
> ><br>
> ><br>
> > This isn't an abstract problem and it actually happens in practice. The<br>
> ><br>
> > microlens package keeps Names in a Set and later turns that set into a<br>
> > list.<br>
> ><br>
> > The results have different orders of TyVars resulting in different ABI<br>
> > hashes<br>
> ><br>
> > and can potentially be optimized differently.<br>
> ><br>
> ><br>
> ><br>
> > I believe it's worth to handle this case in a deterministic way and I have<br>
> > a<br>
> ><br>
> > solution in mind. The idea is to extend NameU (and potentially NameL) with<br>
> > an<br>
> ><br>
> > ordering key. To be more concrete:<br>
> ><br>
> ><br>
> ><br>
> > -   | NameU !Int<br>
> ><br>
> > +   | NameU !Int !Int<br>
> ><br>
> ><br>
> ><br>
> > This way the Ord instance can use a stable key and the problem reduces to<br>
> ><br>
> > ensuring the keys are stable. To generate stable keys we can use the fact<br>
> > that<br>
> ><br>
> > reify traverses the expressions in the same order every time and<br>
> > sequentially<br>
> ><br>
> > allocate new keys based on traversal order. The way I have it implemented<br>
> > now<br>
> ><br>
> > is to add a new field in TcGblEnv which maps Uniques to allocated keys:<br>
> ><br>
> ><br>
> ><br>
> > +        tcg_th_names :: TcRef (UniqFM Int, Int),<br>
> ><br>
> ><br>
> ><br>
> > Then the reifyName and qNewName do the necessary bookkeeping and translate<br>
> > the<br>
> ><br>
> > Uniques on the fly.<br>
> ><br>
> ><br>
> ><br>
> > This is a breaking change and it doesn't fix the problem that NameFlavour<br>
> > is<br>
> ><br>
> > not abstract and leaks the Uniques. It would break at least:<br>
> ><br>
> ><br>
> ><br>
> > - singletons<br>
> ><br>
> > - th-lift<br>
> ><br>
> > - haskell-src-meta<br>
> ><br>
> > - shakespeare<br>
> ><br>
> > - distributed-closure<br>
> ><br>
> ><br>
> ><br>
> > I'd like to get feedback if this is an acceptable solution and if the<br>
> > problem<br>
> ><br>
> > is worth solving.<br>
> ><br>
> ><br>
> ><br>
> > Cheers,<br>
> ><br>
> > Bartosz<br>
> ><br>
> ><br>
> ><br>
> > [1]<br>
> > <a href="https://ghc.haskell.org/trac/ghc/wiki/DeterministicBuilds#NondeterministicUniques" rel="noreferrer" target="_blank">https://ghc.haskell.org/trac/ghc/wiki/DeterministicBuilds#NondeterministicUniques</a><br>
> ><br>
> ><br>
> > _______________________________________________<br>
> > ghc-devs mailing list<br>
> > <a href="mailto:ghc-devs@haskell.org">ghc-devs@haskell.org</a><br>
> > <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
</div></div>> > <<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" rel="noreferrer" target="_blank">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</a>><br>
> ><br>
> ><br>
> ><br>
</blockquote></div><br></div>