<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=us-ascii">
<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;}
@font-face
{font-family:Verdana;
panose-1:2 11 6 4 3 5 4 4 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;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.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;}
--></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">There is a difference between plan A and B. For example, if<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"> f :: (OneShot a -> b) -> [a] -> [b]<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">then EVERY function passed to f would have to be one-shot (Plan A). But under plan B you could have two calls<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"> …f (\x. blah)….. f (\y{-#ONESHOT#-}. blah2)….<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">and only the second would be a one-shot lambda.
<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">So if anything plan B seems more flexible.<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>
<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""> John Lato [mailto:jwlato@gmail.com]
<br>
<b>Sent:</b> 12 November 2013 00:12<br>
<b>To:</b> Simon Peyton-Jones<br>
<b>Cc:</b> glasgow-haskell-users@haskell.org; Akio Takano<br>
<b>Subject:</b> Re: Giving function a larger arity<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">
Yes, that's what I meant. I was thinking that from an implementation perspective, it would be nice if all the one-shot hacks were in a single place, and if plan A facilitated that it would be a good reason to support that approach. But I suppose checking
an annotation is no harder than checking a type, so it's probably irrelevant.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:6.0pt;margin-right:0cm;margin-bottom:12.0pt;margin-left:0cm">
<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">
On Mon, Nov 11, 2013 at 3:29 PM, Simon Peyton-Jones <<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.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">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1F497D">Well, Plan A is indeed an extended version of the ”state hack”. Instead of just (State# RealWorld#)
being magically considered one-shot, we’d also add (OneShot t).</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1F497D"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1F497D">Simon</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1F497D"> </span><o:p></o:p></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" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><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"">
John Lato [mailto:<a href="mailto:jwlato@gmail.com" target="_blank">jwlato@gmail.com</a>]
</span><o:p></o:p></p>
<div>
<p class="MsoNormal"><b>Sent:</b> 11 November 2013 17:29<o:p></o:p></p>
</div>
<p class="MsoNormal"><b>To:</b> Simon Peyton-Jones<br>
<b>Cc:</b> <a href="mailto:glasgow-haskell-users@haskell.org" target="_blank">glasgow-haskell-users@haskell.org</a>; Akio Takano<br>
<b>Subject:</b> RE: Giving function a larger arity<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p>Originally I thought Plan B would make more sense, but if Plan A were implemented could this one-shot type annotation be unified with the state hack? I'm envisioning something like RULES, where if the type matches ghc knows it's a one-shot lambda.<o:p></o:p></p>
<p>I think it would be better to not do any analysis and leave this completely up to the user. My intention is to get a mechanism to tell ghc it's okay to recompute something in a lambda, essentially a manual state hack. I seem to recall wanting this, but I
don't remember the exact use case. It's possible it was one-shot anyway. <o:p></o:p></p>
<p>John L.<o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">On Nov 11, 2013 5:12 AM, "Simon Peyton-Jones" <<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.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-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Strangely enough I’ve been thinking about eta expansion in the last day or two. It’s one of GHC’s
more delicate corners, because</span><o:p></o:p></p>
<p><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">1.</span><span style="font-size:7.0pt;color:#1F497D">
</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">There can be big performance boosts</span><o:p></o:p></p>
<p><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">2.</span><span style="font-size:7.0pt;color:#1F497D">
</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">If you push a redex inside a lambda</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">But as you point out (2) may be arbitrarily bad unless you know the lambda is called at most once
(is “one-shot”).</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">There is really no good way to declare a lambda to be one-shot right now. As you discovered, full
laziness tends to defeat your attempts to do so! (A workaround is to switch off full laziness, but that doesn’t feel right.)</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">What is a more general solution? I can think of two.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><o:p></o:p></p>
<p><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">A.</span><span style="font-size:7.0pt;color:#1F497D">
</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Declare one-shot-ness in the type. Something like this:</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:72.0pt">
<span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">newtype OneShot a = OS a</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:72.0pt">
<span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> plus telling GHC that anything with a OneShot type is a one-shot lambda.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><o:p></o:p></p>
<p><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">B.</span><span style="font-size:7.0pt;color:#1F497D">
</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Declaring one-shot-ness in the terms. Something like</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:72.0pt">
<span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">..Builder (\x {-# ONESHOT #-} -> blah)…</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> That would declare this particular lambda to be one-shot, but not any other.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Notes</span><o:p></o:p></p>
<p style="mso-margin-top-alt:5.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:35.7pt">
<span style="font-size:11.0pt;font-family:Symbol;color:#1F497D">·</span><span style="font-size:7.0pt;color:#1F497D">
</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Plan A would require a bit of fiddling to move your values in and out of the OneShot type. And it’d make the terms a bit bigger at compile time.</span><o:p></o:p></p>
<p style="mso-margin-top-alt:5.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:35.7pt">
<span style="font-size:11.0pt;font-family:Symbol;color:#1F497D">·</span><span style="font-size:7.0pt;color:#1F497D">
</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Plan B is more explicit all the use sites.</span><o:p></o:p></p>
<p style="mso-margin-top-alt:5.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:35.7pt">
<span style="font-size:11.0pt;font-family:Symbol;color:#1F497D">·</span><span style="font-size:7.0pt;color:#1F497D">
</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Both plans would be vulnerable to user error. I could imagine and analysis that would guarantee that you met the one-shot claim; but it would necessarily be quite conservative.
That might or might not be OK</span><o:p></o:p></p>
<p style="mso-margin-top-alt:5.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:35.7pt">
<span style="font-size:11.0pt;font-family:Symbol;color:#1F497D">·</span><span style="font-size:7.0pt;color:#1F497D">
</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">GHC already embodies a version of (A): the “state hack” means that a lambda whose binder is a state token (State# RealWorld#) is treated as one-shot. We have many bug reports
describing when this hack makes things bad, but it is such a huge win for more programs that it is on by default. (Your “rebuild” idea might work better with (State# Realorld# -> Builder) rather than (() -> Builder) for that reason.)</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Simon</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><o:p></o:p></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" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><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"">
Glasgow-haskell-users [mailto:<a href="mailto:glasgow-haskell-users-bounces@haskell.org" target="_blank">glasgow-haskell-users-bounces@haskell.org</a>]
<b>On Behalf Of </b>Akio Takano<br>
<b>Sent:</b> 11 November 2013 09:19<br>
<b>To:</b> <a href="mailto:glasgow-haskell-users@haskell.org" target="_blank">glasgow-haskell-users@haskell.org</a><br>
<b>Subject:</b> Giving function a larger arity</span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:6.0pt">Hi,<br>
<br>
I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.<br>
<br>
Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.<br>
<br>
In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of
it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.<br>
<br>
I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this
problem can add a lot of boxing to an otherwise allocation-free loop).<br>
<br>
One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when
the full-laziness optimization was explicitly disabled.<br>
<br>
This problem happened many times to me. In particular Reader and State monads often triggered it.<br>
<br>
I'm using GHC 7.6.3.<br>
<br>
Any advice?<br>
<br>
Thank you,<br>
Takano Akio<o:p></o:p></p>
</div>
</div>
</div>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;margin-bottom:12.0pt"><br>
_______________________________________________<br>
Glasgow-haskell-users mailing list<br>
<a href="mailto:Glasgow-haskell-users@haskell.org" target="_blank">Glasgow-haskell-users@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/glasgow-haskell-users" target="_blank">http://www.haskell.org/mailman/listinfo/glasgow-haskell-users</a><o:p></o:p></p>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</body>
</html>