<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
p.Code, li.Code, div.Code
{mso-style-name:Code;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:9.0pt;
font-family:"Courier New";}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;
font-weight:normal;
font-style:normal;
text-decoration:none none;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
.MsoPapDefault
{mso-style-type:export-only;
margin-top:6.0pt;
margin-right:0cm;
margin-bottom:6.0pt;
margin-left:0cm;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:580598690;
mso-list-template-ids:-612492110;}
@list l1
{mso-list-id:596598787;
mso-list-template-ids:763807672;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l2
{mso-list-id:1365516018;
mso-list-type:hybrid;
mso-list-template-ids:-1480429908 134807567 134807577 134807579 134807567 134807577 134807579 134807567 134807577 134807579;}
@list l2:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l3
{mso-list-id:1663853507;
mso-list-template-ids:-612492110;}
@list l4
{mso-list-id:1786578088;
mso-list-template-ids:-612492110;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-GB" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">Some quick responses<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">1. <b>Splitting</b><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:36.0pt">What's the need for splitting anyway?<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">Just so you can use uniques in a tree-like way, without threading the supply around. No more than that.
<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">This is not needed everywhere. For example, the Simplifier threads it thus:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="Code">newtype SimplM result<o:p></o:p></p>
<p class="Code"> = SM { unSM :: SimplTopEnv -- Envt that does not change much<o:p></o:p></p>
<p class="Code"> -> UniqSupply -- We thread the unique supply because<o:p></o:p></p>
<p class="Code"> -- constantly splitting it is rather expensive<o:p></o:p></p>
<p class="Code"> -> SimplCount<o:p></o:p></p>
<p class="Code"> -> IO (result, UniqSupply, SimplCount)}<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">I suspect that (now that SimplM is in IO anyway) we could use an IORef instead, and maybe speed up the compiler.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">But perhaps not all uses are so simple to change.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">2. <b>The</b> <b>tree</b><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">The crucial thing is that there /is/ a data structure – a tree, that is the unique supply. So if you have<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"> f u s = ….(splitUniqueSupply us)…..(splitUniqueSupply us)….<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">you’ll get the same trees in the two calls. The supply is just a purely-functional tree.
<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">So, for example <o:p></o:p></span></p>
<ul type="disc">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l1 level1 lfo1">
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<o:p></o:p></li></ul>
<p class="MsoNormal"><span style="font-size:12.0pt">I don’t think this is important, except perhaps to avoid creating a thunk.<o:p></o:p></span></p>
<ul type="disc">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l1 level1 lfo1">
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]<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l1 level1 lfo1">
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`<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l1 level1 lfo1">
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.<o:p></o:p></li></ul>
<p class="MsoNormal"><span style="font-size:12.0pt">I don’t think any of these points are important or relied on. A different impl could behave differently.<o:p></o:p></span></p>
<ol start="1" type="1">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l3 level1 lfo2">
`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?<o:p></o:p></li></ol>
<p class="MsoNormal"><span style="font-size:12.0pt">I think this is unimportant. I.e. it should be fine to change it.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<ol start="1" type="1">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo4">
Judging from SimplCore, we probably want to `splitUniqSupply` after each iteration/transformation, either through a call to `splitUniqSupply` or `getUniqueSupplyM`. Is that right?<o:p></o:p></li></ol>
<p class="MsoNormal"><span style="font-size:12.0pt">I don’t understand the question. If you use the same supply twice, you’ll get (precisely) the same uniques. That may or may not be ok<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt">SImon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US">From:</span></b><span lang="EN-US"> ghc-devs <ghc-devs-bounces@haskell.org>
<b>On Behalf Of </b>Sebastian Graf<br>
<b>Sent:</b> 23 July 2018 12:06<br>
<b>To:</b> ghc-devs <ghc-devs@haskell.org><br>
<b>Subject:</b> Understanding UniqSupply<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
Hi all,<o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
I'm trying to understand when it is necessary to `splitUniqSupply`, or even to create my own supply with `mkSplitUniqSupply`.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
<o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm">
First, my understanding of how `mkSplitUniqSupply` (<a href="https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fhackage.haskell.org%2Fpackage%2Fghc-8.4.1%2Fdocs%2Fsrc%2FUniqSupply.html%23mkSplitUniqSupply&data=02%7C01%7Csimonpj%40microsoft.com%7C58b620e0f148448bbe0608d5f08c485e%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636679407654961407&sdata=cA6N%2FGzMVYKD0fAVkbG%2BC%2F%2FuXuhenR95CwhHQAZrUQ4%3D&reserved=0">https://hackage.haskell.org/package/ghc-8.4.1/docs/src/UniqSupply.html#mkSplitUniqSupply</a>)
works is as follows:<o:p></o:p></p>
</div>
<div>
<ul type="disc">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l1 level1 lfo1">
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<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l1 level1 lfo1">
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<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l1 level1 lfo1">
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`<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l1 level1 lfo1">
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.<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l1 level1 lfo1">
This is of course all an implementation detail<o:p></o:p></li></ul>
<div>
<p class="MsoNormal">These are the questions that bother me:<o:p></o:p></p>
</div>
</div>
<div>
<ol start="1" type="1">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l4 level1 lfo5">
`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?<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l4 level1 lfo5">
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?<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l4 level1 lfo5">
Judging from SimplCore, we probably want to `splitUniqSupply` after each iteration/transformation, either through a call to `splitUniqSupply` or `getUniqueSupplyM`. Is that right?<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l4 level1 lfo5">
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?<o:p></o:p></li></ol>
<div>
<p class="MsoNormal">Happy to hear from you!<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal">Cheers<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Sebastian<o:p></o:p></p>
</div>
</div>
</div>
</div>
</body>
</html>