<div dir="ltr">And plan 2 doesn't require a magic data type. :)</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Nov 12, 2013 at 9:36 AM, Simon Peyton-Jones <span dir="ltr"><<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-GB" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">There is a difference between plan A and B. For example, if<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> f :: (OneShot a -> b) -> [a] -> [b]<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">then EVERY function passed to f would have to be one-shot (Plan A). But under plan B you could have two calls<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> …f (\x. blah)….. f (\y{-#ONESHOT#-}. blah2)….<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">and only the second would be a one-shot lambda.
<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">So if anything plan B seems more flexible.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Simon<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></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:<a href="mailto:jwlato@gmail.com" target="_blank">jwlato@gmail.com</a>]
<br>
<b>Sent:</b> 12 November 2013 00:12</span></p><div class="im"><br>
<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>
</div><b>Subject:</b> Re: Giving function a larger arity<u></u><u></u><p></p>
</div>
</div><div><div class="h5">
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal" style="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.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal" style="margin-right:0cm;margin-bottom:12.0pt;margin-left:0cm">
<u></u> <u></u></p>
<div>
<p class="MsoNormal" style="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:<u></u><u></u></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"><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><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d">Simon</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d"> </span><u></u><u></u></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:<a href="mailto:jwlato@gmail.com" target="_blank">jwlato@gmail.com</a>]
</span><u></u><u></u></p>
<div>
<p class="MsoNormal"><b>Sent:</b> 11 November 2013 17:29<u></u><u></u></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<u></u><u></u></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <u></u><u></u></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.<u></u><u></u></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. <u></u><u></u></p>
<p>John L.<u></u><u></u></p>
<div>
<p class="MsoNormal">On Nov 11, 2013 5:12 AM, "Simon Peyton-Jones" <<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>> wrote:<u></u><u></u></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"><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><u></u><u></u></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><u></u><u></u></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><u></u><u></u></p>
<p class="MsoNormal"><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><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal"><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><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal"><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><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></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><u></u><u></u></p>
<p class="MsoNormal" style="margin-left:72.0pt">
<span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">newtype OneShot a = OS a</span><u></u><u></u></p>
<p class="MsoNormal" style="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><u></u><u></u></p>
<p class="MsoNormal"><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><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></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><u></u><u></u></p>
<p class="MsoNormal" style="margin-left:72.0pt">
<span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">..Builder (\x {-# ONESHOT #-} -> blah)…</span><u></u><u></u></p>
<p class="MsoNormal"><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><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Notes</span><u></u><u></u></p>
<p style="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><u></u><u></u></p>
<p style="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><u></u><u></u></p>
<p style="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><u></u><u></u></p>
<p style="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><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Simon</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></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"">
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><u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<p class="MsoNormal" style="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<u></u><u></u></p>
</div>
</div>
</div>
</div>
<p class="MsoNormal" style="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><u></u><u></u></p>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div></div></div>
</div>
</div>
<br>_______________________________________________<br>
Glasgow-haskell-users mailing list<br>
<a href="mailto:Glasgow-haskell-users@haskell.org">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><br>
<br></blockquote></div><br></div>