Giving function a larger arity

Tue Nov 12 09:18:38 UTC 2013

And plan 2 doesn't require a magic data type. :)

On Tue, Nov 12, 2013 at 9:36 AM, Simon Peyton-Jones
<simonpj at microsoft.com>wrote:

>  There is a difference between plan A and B.  For example, if
>
>                 f :: (OneShot a -> b) -> [a] -> [b]
>
> then EVERY function passed to f would have to be one-shot (Plan A).  But
> under plan B you could have two calls
>
>
>
>                 …f (\x. blah)….. f (\y{-#ONESHOT#-}. blah2)….
>
>
>
> and only the second would be a one-shot lambda.
>
>
>
> So if anything plan B seems more flexible.
>
>
>
> Simon
>
>
>
>
>
> *From:* John Lato [mailto:jwlato at gmail.com]
> *Sent:* 12 November 2013 00:12
>
> *To:* Simon Peyton-Jones
> *Cc:* glasgow-haskell-users at haskell.org; Akio Takano
> *Subject:* Re: Giving function a larger arity
>
>
>
> 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.
>
>
>
> On Mon, Nov 11, 2013 at 3:29 PM, Simon Peyton-Jones <simonpj at microsoft.com>
> wrote:
>
>  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).
>
>
>
> Simon
>
>
>
> *From:* John Lato [mailto:jwlato at gmail.com]
>
> *Sent:* 11 November 2013 17:29
>
> *To:* Simon Peyton-Jones
> *Cc:* glasgow-haskell-users at haskell.org; Akio Takano
> *Subject:* RE: Giving function a larger arity
>
>
>
> 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.
>
> 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.
>
> John L.
>
> On Nov 11, 2013 5:12 AM, "Simon Peyton-Jones" <simonpj at microsoft.com>
> wrote:
>
>  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
>
> 1.       There can be big performance boosts
>
> 2.       If you push a redex inside a lambda
>
> But as you point out (2) may be arbitrarily bad unless you know the lambda
> is called at most once (is “one-shot”).
>
>
>
> 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.)
>
>
>
> What is a more general solution?  I can think of two.
>
>
>
> A.      Declare one-shot-ness in the type.  Something like this:
>
> newtype OneShot a = OS a
>
> newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))
>
>                 plus telling GHC that anything with a OneShot type is a
> one-shot lambda.
>
>
>
> B.      Declaring one-shot-ness in the terms.  Something like
>
> ..Builder (\x {-# ONESHOT #-} -> blah)…
>
>                 That would declare this particular lambda to be one-shot,
> but not any other.
>
>
>
> Notes
>
> ·         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.
>
> ·         Plan B is more explicit all the use sites.
>
> ·         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
>
> ·         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.)
>
>
>
> Simon
>
>
>
> *From:* Glasgow-haskell-users [mailto:
> glasgow-haskell-users-bounces at haskell.org] *On Behalf Of *Akio Takano
> *Sent:* 11 November 2013 09:19
> *To:* glasgow-haskell-users at haskell.org
> *Subject:* Giving function a larger arity
>
>
>
> Hi,
>
> 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.
>
> 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.
>
> 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.
>
> 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).
>
> 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.
>
> This problem happened many times to me. In particular Reader and State
> monads often triggered it.
>
> I'm using GHC 7.6.3.
>
> Any advice?
>
> Thank you,
> Takano Akio
>
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>
>
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20131112/5b6ccea4/attachment.html>