No, NameU and NameL both lack package key / package id. -Michael
On Wed, Jun 29, 2016 at 7:34 AM, Edward Z. Yang <[email protected]> wrote: > No, nameBase is not the right thing to use here; you also need the > unit ID (in GHC 8.0 parlance; package key in GHC 7.10; package id > in GHC 7.8 and before). If you have that information, then > GHC establishes an invariant that if two names compare stably equal, > then the uniques associated with them are the same. > > Edward > > Excerpts from Michael Sloan's message of 2016-06-10 17:16:44 -0400: >> Hey, sorry for not getting back to this sooner! >> >> Perhaps I should have added the following to my list of goals in contention: >> >> (3) (==) shouldn't yield True for Names that have different unique ids. >> >> 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. >> >> -Michael >> >> On Sun, Jun 5, 2016 at 10:15 AM, Edward Z. Yang <[email protected]> wrote: >> >> > I must admit, I am a bit confused by this discussion. >> > >> > It is true that every Name is associated with a Unique. But you don't >> > need the Unique to equality/ordering tests; the names also contain >> > enough (stable) information for stable comparisons of that sort. So >> > why don't we expose that instead of the Unique? >> > >> > Edward >> > >> > Excerpts from Michael Sloan's message of 2016-06-04 18:44:03 -0700: >> > > On Thu, Jun 2, 2016 at 4:12 AM, Simon Peyton Jones < >> > [email protected]> >> > > wrote: >> > > >> > > > 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 >> > > > >> > > > >> > > > >> > > > 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. >> > > > >> > > >> > > 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: >> > > >> > > $(do TyConI (DataD _ _ [KindedTV (Name _ nf) _] _ _ _) <- reify ''Maybe >> > > lift (show nf)) >> > > >> > > The resulting expression is something like "NameU 822083586" >> > > >> > > > This is a breaking change and it doesn't fix the problem that >> > NameFlavour >> > > > is >> > > > >> > > > not abstract and leaks the Uniques. It would break at least: >> > > > >> > > > >> > > > >> > > > But why is NameU exposed to clients? GHC needs to know, but clients >> > > > don’t. What use are these packages making of it? >> > > > >> > > >> > > 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. >> > > >> > > There are two goals in contention here: >> > > >> > > 1) Having some ordering on Names so that they can be used in Map or Set >> > > 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 >> > > >> > > A few ideas for different approaches to resolving this: >> > > >> > > 1) Document it. Less appealing than fixing it in the API, but still >> > would >> > > be good. >> > > >> > > 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. >> > > >> > > 3) Some approaches like this ordering key, but I'm not sure how it will >> > > help when comparing NameUs from different modules? >> > > >> > > > S >> > > > >> > > > >> > > > >> > > > >> > > > >> > > > *From:* ghc-devs [mailto:[email protected]] *On Behalf Of >> > *Michael >> > > > Sloan >> > > > *Sent:* 02 June 2016 02:07 >> > > > *To:* Bartosz Nitka <[email protected]> >> > > > *Cc:* ghc-devs Devs <[email protected]> >> > > > *Subject:* Re: Template Haskell determinism >> > > > >> > > > >> > > > >> > > > +1 to solving this. Not sure about the approach, but assuming the >> > > > following concerns are addressed, I'm (+1) on it too: >> > > > >> > > > >> > > > >> > > > 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? >> > > > >> > > > >> > > > >> > > > 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. >> > > > >> > > > >> > > > >> > > > 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. >> > > > >> > > > >> > > > >> > > > One issue with this is that switching the order of reify could >> > > > unexpectedly vary the behavior. >> > > > >> > > > >> > > > >> > > > 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. >> > > > >> > > > >> > > > >> > > > >> > > > >> > > > If the internal API for Name does change, may as well address >> > > > https://ghc.haskell.org/trac/ghc/ticket/10311 too. I agree with SPJ's >> > > > suggested solution of having both the traditional package identifier >> > and >> > > > package keys in 'Name'. >> > > > >> > > > >> > > > >> > > > -Michael >> > > > >> > > > >> > > > >> > > > On Tue, May 31, 2016 at 6:54 AM, Bartosz Nitka <[email protected]> >> > wrote: >> > > > >> > > > Template Haskell with its ability to do arbitrary IO is >> > non-deterministic >> > > > by >> > > > >> > > > design. You could for example embed the current date in a file. There >> > is >> > > > >> > > > however one kind of non-deterministic behavior that you can trigger >> > > > >> > > > accidentally. It has to do with how Names are reified. If you take a >> > look >> > > > at >> > > > >> > > > the definition of reifyName you can see that it puts the assigned >> > Unique >> > > > in a >> > > > >> > > > NameU: >> > > > >> > > > >> > > > >> > > > reifyName :: NamedThing n => n -> TH.Name >> > > > >> > > > reifyName thing >> > > > >> > > > | isExternalName name = mk_varg pkg_str mod_str occ_str >> > > > >> > > > | otherwise = TH.mkNameU occ_str (getKey (getUnique >> > name)) >> > > > >> > > > ... >> > > > >> > > > NameFlavour which NameU is a constructor of has a default Ord instance, >> > > > meaning >> > > > >> > > > that it ends up comparing the Uniques. The relative ordering of >> > Uniques is >> > > > not >> > > > >> > > > guaranteed to be stable across recompilations [1], so this can lead to >> > > > >> > > > ABI-incompatible binaries. >> > > > >> > > > >> > > > >> > > > This isn't an abstract problem and it actually happens in practice. The >> > > > >> > > > microlens package keeps Names in a Set and later turns that set into a >> > > > list. >> > > > >> > > > The results have different orders of TyVars resulting in different ABI >> > > > hashes >> > > > >> > > > and can potentially be optimized differently. >> > > > >> > > > >> > > > >> > > > I believe it's worth to handle this case in a deterministic way and I >> > have >> > > > a >> > > > >> > > > solution in mind. The idea is to extend NameU (and potentially NameL) >> > with >> > > > an >> > > > >> > > > ordering key. To be more concrete: >> > > > >> > > > >> > > > >> > > > - | NameU !Int >> > > > >> > > > + | NameU !Int !Int >> > > > >> > > > >> > > > >> > > > This way the Ord instance can use a stable key and the problem reduces >> > to >> > > > >> > > > ensuring the keys are stable. To generate stable keys we can use the >> > fact >> > > > that >> > > > >> > > > reify traverses the expressions in the same order every time and >> > > > sequentially >> > > > >> > > > allocate new keys based on traversal order. The way I have it >> > implemented >> > > > now >> > > > >> > > > is to add a new field in TcGblEnv which maps Uniques to allocated keys: >> > > > >> > > > >> > > > >> > > > + tcg_th_names :: TcRef (UniqFM Int, Int), >> > > > >> > > > >> > > > >> > > > Then the reifyName and qNewName do the necessary bookkeeping and >> > translate >> > > > the >> > > > >> > > > Uniques on the fly. >> > > > >> > > > >> > > > >> > > > This is a breaking change and it doesn't fix the problem that >> > NameFlavour >> > > > is >> > > > >> > > > not abstract and leaks the Uniques. It would break at least: >> > > > >> > > > >> > > > >> > > > - singletons >> > > > >> > > > - th-lift >> > > > >> > > > - haskell-src-meta >> > > > >> > > > - shakespeare >> > > > >> > > > - distributed-closure >> > > > >> > > > >> > > > >> > > > I'd like to get feedback if this is an acceptable solution and if the >> > > > problem >> > > > >> > > > is worth solving. >> > > > >> > > > >> > > > >> > > > Cheers, >> > > > >> > > > Bartosz >> > > > >> > > > >> > > > >> > > > [1] >> > > > >> > https://ghc.haskell.org/trac/ghc/wiki/DeterministicBuilds#NondeterministicUniques >> > > > >> > > > >> > > > _______________________________________________ >> > > > ghc-devs mailing list >> > > > [email protected] >> > > > http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >> > > > < >> > 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 >> > > >> > > > >> > > > >> > > > >> > _______________________________________________ ghc-devs mailing list [email protected] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
