<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=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@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:12.0pt;
        font-family:"Times New Roman",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;}
span.EmailStyle17
        {mso-style-type:personal-reply;
        font-family:"Calibri",sans-serif;
        color:#1F497D;}
.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;}
--></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="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Yes; but we should jolly well figure out a way to do better for guards.  These guards are no more than patterns really!<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;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" style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Richard Eisenberg [mailto:eir@cis.upenn.edu]
<br>
<b>Sent:</b> 11 December 2015 15:59<br>
<b>To:</b> George Karachalias <george.karachalias@gmail.com><br>
<b>Cc:</b> Ben Gamari <ben@well-typed.com>; Simon Peyton Jones <simonpj@microsoft.com>; GHC developers <ghc-devs@haskell.org><br>
<b>Subject:</b> Re: Performance of pattern checker on OptCoercions<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">If I understand correctly, you're saying that the problem is due to my use of guards, not anything with fancy types. If that's correct, then this sort of thing might be a trap anyone could stumble into. (The code in OptCoercion is fairly
 routine for Haskell.) It seems like disabling checking guards by default may be best, but I'd love a flag (not with -Wall) to enable it optionally.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Richard<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">On Dec 11, 2015, at 6:27 AM, George Karachalias <<a href="mailto:george.karachalias@gmail.com">george.karachalias@gmail.com</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">Hello Ben,<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Fri, Dec 11, 2015 at 11:58 AM, Ben Gamari <<a href="mailto:ben@well-typed.com" target="_blank">ben@well-typed.com</a>> wrote:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<p class="MsoNormal"><br>
Hi George,<br>
<br>
Richard has encountered a bit of a performance cliff when merging his<br>
no-kinds work. In particular OptCoercions now results in multiple<br>
gigabytes of memory consumption during compilation due to the pattern<br>
checker. The problem seems to be the opt_trans_rule binding, which has<br>
numerous equations, each of which has patterns of various complexities<br>
and guards. Might this be another case where disabling the pattern<br>
checker is unavoidable?<o:p></o:p></p>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I am afraid so. I have just responded to the ticket about it. The essence is the<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">difference between `f` and `g` below:<o:p></o:p></p>
</div>
<p class="MsoNormal">f x = case x of<o:p></o:p></p>
<div>
<p class="MsoNormal">  []      -> ...<br>
  (_:_) -> ...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">g y | []      <- y = ...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">      | (_:_) <- y = ...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">`f` will generate an empty uncovered set while g will generate:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">uncovered =<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">  { x |> { x ~ [], x ~ (_:_) }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">  , x |> { x ~ (_:_), x ~ [] } }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">which is also semantically empty but this cannot be detected until we call the<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">term oracle on it to see the inconsistency. Since pattern guards can pattern match<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">against <b><i>any</i></b> variable whilst case expressions match a single expression (`x` above)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">I can not make the check treat them the same.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">From what I see, until now the pattern guards in <b><i>opt_trans_co</i></b> involved mostly<br>
pattern matching with Maybe which has only two constructors. I can easily assume<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">that this is the reason we did not have such a problem until now. So many guards<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">are already a challenge for the pattern match checker but maybe changing this (by<br>
this I mean to <b>not</b> use pattern guards on types with many constructors because this<br>
is the most expensive thing for the whole check) is enough to make GHC bootstrap.<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I hope this helps, I am really confident that this is the cause of the problem.<br>
Nevertheless, I will look into it more to see if I can find another source.<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">George<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">-- <o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif;color:#660000">things you own end up owning you</span><o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</body>
</html>