<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;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 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;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
tt
{mso-style-priority:99;
font-family:"Courier New";}
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;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;}
span.line
{mso-style-name:line;}
span.kr
{mso-style-name:kr;}
span.p
{mso-style-name:p;}
span.n
{mso-style-name:n;}
span.o
{mso-style-name:o;}
span.kt
{mso-style-name:kt;}
span.EmailStyle29
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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:1011682763;
mso-list-type:hybrid;
mso-list-template-ids:-1259196152 134807553 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
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"><span style="mso-fareast-language:EN-US">I’m pretty reluctant to change the Core Language to support one very dark corner use-case. Then every Core consumer and producer must understand the semantics of this new field, and respect that
semantics.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">As I understand it, our definition<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<pre><tt>keepAlive# k x s = case nodiv x s of (# s1, r #) -><o:p></o:p></tt></pre>
<pre><tt> case touch# k s1 of (# s2, _ #) -><o:p></o:p></tt></pre>
<pre><tt> (# s2, r #)</tt><o:p></o:p></pre>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">does just what we want, except perhaps efficiency, without changing the language. If that’s true, let’s convince ourselves that<o:p></o:p></span></p>
<ul style="margin-top:0cm" type="disc">
<li class="MsoListParagraph" style="margin-left:0cm;mso-list:l0 level1 lfo1"><span style="mso-fareast-language:EN-US">The efficiency cannot be recovered<o:p></o:p></span></li><li class="MsoListParagraph" style="margin-left:0cm;mso-list:l0 level1 lfo1"><span style="mso-fareast-language:EN-US">The loss of efficiency matters a lot<o:p></o:p></span></li></ul>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">before taking more drastic steps.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">For completeness, <o:p>
</o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"> nodiv :: IO a -> IO a<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">behaves like the identity function except that (nodiv e) never says “guarantees to diverges”<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><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"> Sylvain Henry <sylvain@haskus.fr>
<br>
<b>Sent:</b> 26 May 2020 18:04<br>
<b>To:</b> Ben Gamari <ben@well-typed.com>; Simon Peyton Jones <simonpj@microsoft.com><br>
<b>Cc:</b> GHC developers <ghc-devs@haskell.org><br>
<b>Subject:</b> Re: keepAlive# primop<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p>Hi ghc-devs,<o:p></o:p></p>
<p>After a discussion today about `keepAlive#`, I think Option E [1] is even more appealing.<o:p></o:p></p>
<p>To recap the idea was to have keep-alive variable sets attached to case-expressions in Core. E.g. `case {k} x of ...`<o:p></o:p></p>
<p><o:p> </o:p></p>
<p>1. One of the issue was the semantics of `keepAlive#`. `keepAlive#` is very intricate with evaluation. As Simon mentioned we want a semantics like:<o:p></o:p></p>
<pre><tt> keepAlive# k x ==> x `seq` touch# k `seq` x</tt><o:p></o:p></pre>
<p>with potentially a special `seq` to deal with diverging `x`.<o:p></o:p></p>
<p>With `case {k} x of ...` we have this semantics. Even if we throw the case alternatives if `x` diverges, we don't throw the keep-alive set so we're good.<o:p></o:p></p>
<p><o:p> </o:p></p>
<p>2. Simon wanted to push `keepAlive#` into case-expressions. With this approach we should only have to fix case-of-case to take keep-alive sets into account.<o:p></o:p></p>
<pre><span class="kr">case</span><span class="line"> </span><span class="p">{</span><span class="n">k</span><span class="p">}</span><span class="line"> </span><span class="p">(</span><span class="kr">case</span><span class="line"> </span><span class="p">{</span><span class="n">k2</span><span class="p">}</span><span class="line"> </span><span class="n">x</span><span class="line"> </span><span class="kr">of</span><span class="line"> </span><span class="o">..</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="n">a</span><span class="p">;</span><span class="line"> </span><span class="o">...</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="n">b</span><span class="p">)</span><span class="line"> </span><span class="kr">of</span><o:p></o:p></pre>
<pre><span class="line"> </span><span class="kt">C0</span><span class="line"> </span><span class="o">..</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="n">e1</span><o:p></o:p></pre>
<pre><span class="line"> </span><span class="kt">C1</span><span class="line"> </span><span class="o">..</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="n">e2</span><o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre><span class="o">===></span><o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre><span class="kr">case</span><span class="line"> </span><span class="p">{</span><span class="n">k</span><span class="p">,</span><span class="n">k2</span><span class="p">}</span><span class="line"> </span><span class="n">x</span><span class="line"> </span><span class="kr">of</span><o:p></o:p></pre>
<pre><span class="line"> </span><span class="o">...</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="kr">case</span><span class="line"> </span><span class="p">{</span><span class="n">k</span><span class="p">}</span><span class="line"> </span><span class="n">a</span><span class="line"> </span><span class="kr">of</span><span class="line"> </span><span class="p">{</span><span class="line"> </span><span class="kt">C0</span><span class="line"> </span><span class="o">..</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="n">e1</span><span class="p">;</span><span class="line"> </span><span class="kt">C1</span><span class="line"> </span><span class="o">...</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="n">e2</span><span class="line"> </span><span class="p">}</span><o:p></o:p></pre>
<pre><span class="line"> </span><span class="o">...</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="kr">case</span><span class="line"> </span><span class="p">{</span><span class="n">k</span><span class="p">}</span><span class="line"> </span><span class="n">b</span><span class="line"> </span><span class="kr">of</span><span class="line"> </span><span class="p">{</span><span class="line"> </span><span class="kt">C0</span><span class="line"> </span><span class="o">..</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="n">e1</span><span class="p">;</span><span class="line"> </span><span class="kt">C1</span><span class="line"> </span><span class="o">...</span><span class="line"> </span><span class="o">-></span><span class="line"> </span><span class="n">e2</span><span class="line"> </span><span class="p">}</span><o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre><o:p> </o:p></pre>
<p>3. Compared to other approaches: we don't have to use stack frames (good for performance) and we don't have to deal with a continuation (good for Core optimizations, hence perf).<o:p></o:p></p>
<p>4. Implementing this approach is quite straightforward even if it modifies Core. I did it last month in [2]. This patch doesn't fully work yet with `-O` because some transformation (related to join points IIRC) doesn't take keep-alive sets into account but
it should be pretty easy to fix if we want to use this approach.<o:p></o:p></p>
<p><o:p> </o:p></p>
<p>Given how hard it is to come up with a good design/implementation of other approaches, this one strikes me as probably the more principled we have and yet it is relatively easy to implement. What do you think?<o:p></o:p></p>
<p>Cheers,<br>
Sylvain<o:p></o:p></p>
<p><o:p> </o:p></p>
<p>[1] <a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fwikis%2Fproposal%2Fwith-combinator%23option-e-tag-core-case-expression-with-kept-alive-variables&data=02%7C01%7Csimonpj%40microsoft.com%7C048cbe5f73764660a89e08d80196cc57%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637261094481517008&sdata=FgsyLDDHU9uwfy3N2WERGxey1maas7o%2BKvlOYRRt1yo%3D&reserved=0">
https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables</a><o:p></o:p></p>
<p>[2] <a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fhsyl20%2Fghc%2F-%2Fcommits%2Fhsyl20-keepalive&data=02%7C01%7Csimonpj%40microsoft.com%7C048cbe5f73764660a89e08d80196cc57%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637261094481517008&sdata=8In4f2ghmFkHd0BK8iUUOoXT5L4L2smtaD4cNBNKfIg%3D&reserved=0">
https://gitlab.haskell.org/hsyl20/ghc/-/commits/hsyl20-keepalive</a><o:p></o:p></p>
<p><o:p> </o:p></p>
<p><o:p> </o:p></p>
<div>
<p class="MsoNormal">On 13/04/2020 19:51, Ben Gamari wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<pre><o:p> </o:p></pre>
<pre>Ccing ghc-devs@ since this discussion is something of general interest<o:p></o:p></pre>
<pre>to the community.<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre><o:p> </o:p></pre>
<pre>Sylvain Henry <a href="mailto:sylvain@haskus.fr"><sylvain@haskus.fr></a> writes:<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<pre>Simon, Ben,<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>I've been reading and thinking about `readRW#` issues which are very <o:p></o:p></pre>
<pre>related to issues we have with `keepAlive#` primop.<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>To recap, the problem is that we want some transformations (that Simon <o:p></o:p></pre>
<pre>has listed in [1]) to consider:<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>```<o:p></o:p></pre>
<pre>case runRW# f of ...<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>case keepAlive# k a of ...<o:p></o:p></pre>
<pre>```<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>as if they were really:<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>```<o:p></o:p></pre>
<pre>case f realWorld# of ...<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>case a of ...<o:p></o:p></pre>
<pre>```<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>BUT without breaking the semantics of runRW# and keepAlive#.<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>I have been thinking about a solution that I have described on the wiki: <o:p></o:p></pre>
<pre><a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fwikis%2Fproposal%2Fwith-combinator%23option-e-tag-core-case-expression-with-kept-alive-variables&data=02%7C01%7Csimonpj%40microsoft.com%7C048cbe5f73764660a89e08d80196cc57%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637261094481527002&sdata=MVHNThzNSCyckXB0KajxAjOWPAl3kUpgjNWD4F6OWO0%3D&reserved=0">https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables</a><o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>The idea is to keep a set of variable names in each Core case-expression <o:p></o:p></pre>
<pre>that are kept alive during the evaluation of the scrutinee.<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>I think it would work very nicely with your `newState#` primop described <o:p></o:p></pre>
<pre>in [2], both for `runST` and for `unsafeDupablePerformIO` (details on <o:p></o:p></pre>
<pre>the wiki).<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>It requires a little more upfront work to adapt the code involving <o:p></o:p></pre>
<pre>case-expressions. But it will force us to review all transformations to <o:p></o:p></pre>
<pre>check if they are sound when keep-alive sets are not empty, which we <o:p></o:p></pre>
<pre>would have to do anyway if we implemented another option. We could start <o:p></o:p></pre>
<pre>by disabling transformations involving non-empty keep-alive sets and <o:p></o:p></pre>
<pre>iterate to enable the sound ones.<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>I would like your opinions on the approach. I may have totally missed <o:p></o:p></pre>
<pre>something.<o:p></o:p></pre>
</blockquote>
<pre><o:p> </o:p></pre>
<pre>Thanks for writing this down!<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>Indeed it is an interesting idea. However, as expressed on IRC, I<o:p></o:p></pre>
<pre>wonder whether this problem rises to the level where it warrants an<o:p></o:p></pre>
<pre>adaptation to our Core representation. It feels a bit like the<o:p></o:p></pre>
<pre>tail is wagging the dog here, especially given how the "tail" here<o:p></o:p></pre>
<pre>merely exists to support FFI.<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>That being said, this is one of the few options which remain on the<o:p></o:p></pre>
<pre>table that doesn't require changes to user code. Moreover, the<o:p></o:p></pre>
<pre>applicability to runRW# is quite intriguing.<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>Another (admittedly, more ad-hoc) option that would avoid modifying Core<o:p></o:p></pre>
<pre>would be to teach the simplifier about the class of<o:p></o:p></pre>
<pre>"continuation-passing" primops (e.g. `keepAlive#` and `runRW#`), allowing it<o:p></o:p></pre>
<pre>to push case analyses into the continuation argument. That is,<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre> case keepAlive# x expr of pat -> rhs<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre> ~><o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre> keepAlive# x (case expr of pat -> rhs)<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>Of course, doing this is a bit tricky since one must rewrite the<o:p></o:p></pre>
<pre>application of keepAlive# to ensure that the resulting application is<o:p></o:p></pre>
<pre>well-typed. Admittedly, this doesn't help the runRW# case (although this<o:p></o:p></pre>
<pre>could presumably be accommodated by touch#'ing the final state token in<o:p></o:p></pre>
<pre>the runRW# desugaring emitted by CorePrep).<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>On the whole, I'm not a fan of this ad-hoc option. It increases the<o:p></o:p></pre>
<pre>complexity of the simplifier all to support a single operation. By<o:p></o:p></pre>
<pre>comparison, the Core extension looks somewhat appealing.<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>Cheers,<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>- Ben<o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre><o:p> </o:p></pre>
<pre>[1] <a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fwikis%2Fproposal%2Fwith-combinator%23option-e-tag-core-case-expression-with-kept-alive-variables&data=02%7C01%7Csimonpj%40microsoft.com%7C048cbe5f73764660a89e08d80196cc57%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637261094481527002&sdata=MVHNThzNSCyckXB0KajxAjOWPAl3kUpgjNWD4F6OWO0%3D&reserved=0">https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables</a><o:p></o:p></pre>
<pre><o:p> </o:p></pre>
<pre>P.S. A minor note: the keepAlive# "pseudo-instruction" mentioned on the<o:p></o:p></pre>
<pre>Wiki [1] is precisely the touch# operation we have today.<o:p></o:p></pre>
</blockquote>
</div>
</div>
</body>
</html>