Understanding UniqSupply
Sebastian Graf
sgraf1337 at gmail.com
Mon Jul 23 11:05:34 UTC 2018
Hi all,
I'm trying to understand when it is necessary to `splitUniqSupply`, or even
to create my own supply with `mkSplitUniqSupply`.
First, my understanding of how `mkSplitUniqSupply` (
https://hackage.haskell.org/package/ghc-8.4.1/docs/src/UniqSupply.html#mkSplitUniqSupply)
works is as follows:
- The `unsafeInterleaveIO` makes it so that `genSym` is actually forced
before any of the recursive calls to `mk_split` force their `genSym`,
regardless of evaluation order
- This guarentees a certain partial order on produced uniques: Any
parent `UniqSupply`'s `Unique` is calculated by a call to
compiler/cbits/genSym.c#genSym() before any `Unique`s of its offsprings are
- The order of `Unique`s on different off-springs of the same
`UniqSupply` is determined by evaluation order as a result of
`unsafeInterleaveIO`, much the same as when we create two different
`UniqSupply`s by calls to `mkSplitUniqSupply`
- So, `unfoldr (Just . takeUniqFromSupply) us) !! n` is always
deterministic and strictly monotone, in the sense that even forcing the
expression for n=2 before n=1 will have a lower `Unique` for n=1 than for
n=2.
- This is of course all an implementation detail
These are the questions that bother me:
1. `takeUniqSupply` returns as 'tail' its first off-spring, whereas
`uniqsFromSupply` always recurses into its second off-spring. By my
intuition above, this shouldn't really make much of a difference, so what
is the motivation for that?
2. The docs state that the character tag/domain/prefix in the call to
`mkSplitUniqSupply` should be unique to guarantee actual uniqueness of
produced `Unique`s. Judging from the implementation of `genSym`, which is
unaware of the specific domain to draw the next unique from, this is an
unnecessarily strong condition?! Also there are multiple places in the code
base spread over module boundaries even (e.g. CorePrep, SimplCore) that
call `mkSplitUniqSupply` with the same character anyway. Maybe there should
at least be some clarifying comment on why this isn't a problem?
3. Judging from SimplCore, we probably want to `splitUniqSupply` after
each iteration/transformation, either through a call to `splitUniqSupply`
or `getUniqueSupplyM`. Is that right?
4. What's the need for splitting anyway? I suspect it's a trick to avoid
state threading that would be necessary if we just had `type UniqSupply =
[Unique]`. Would that really be a bad thing, considering we mostly work in
`UniqSM` anyway? Is there anything else to it?
Happy to hear from you!
Cheers
Sebastian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20180723/631a8213/attachment.html>
More information about the ghc-devs
mailing list