[Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Paul Chiusano  6/14/09 4:43 PM  Hello, I was recently trying to figure out if there was a way, at runtime, to do better strictness analysis for polymorphic HOFs, for which the strictness of some arguments might depend on the strictness of the strictness of function types that are passed as arguments [1]. As an example, consider foldl. The 'seed' parameter of foldl can be made strict as long as the binary function used for the fold is strict in its arguments. Unfortunately, because strictness analysis is done statically, Haskell can't assume anything about the strictness of the binary function  assuming we only compile one instance of foldl, it must be the most conservative version possible, and that means making the seed parameter lazy. :( I started thinking about ways you could to a check at runtime for this sort So, my question is: does doing this sort of runtime analysis seem like a Note that I'm not suggesting Haskell should do anything like this. I'm Best, [1]: http://pchiusano.blogspot.com/2009/06/perfectstrictnessanalysispart1.html http://pchiusano.blogspot.com/2009/06/perfectstrictnessanalysispart2.html 
Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Eugene Kirpichov  6/14/09 8:18 PM  2009/6/15 Paul Chiusano <paul.c...@gmail.com>: The idea looks cool, but perfect strictness analysis is not possible, > Best,> _______________________________________________ > HaskellCafe mailing list > Haskel...@haskell.org > http://www.haskell.org/mailman/listinfo/haskellcafe > >  
Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Jason Dagit  6/14/09 10:24 PM  On Sun, Jun 14, 2009 at 8:18 PM, Eugene Kirpichov <ekirp...@gmail.com>wrote: > The idea looks cool, but perfect strictness analysis is not possible,
[1] http://lambdatheultimate.org/node/2003 Jason 
Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Luke Palmer  6/15/09 1:20 AM  On Sun, Jun 14, 2009 at 5:42 PM, Paul Chiusano <paul.c...@gmail.com>wrote: > Others have commented on the undecidability of your problem. I can't come However, there is nothing undecidable about your larger goal of creating a Luke 
Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Claus Reinke  6/15/09 10:39 AM  > I was recently trying to figure out if there was a way, at runtime, to do As has been pointed out, strictness analysis is not decidable. That doesn't For typical higherorder functions, there's a simple workaround, already http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/GHCList.html#foldl Claus

Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Paul Chiusano  6/15/09 12:22 PM  Thanks for replies everyone. :) I had not heard of Rice's theorem but it's not too surprising. A couple thoughts I had: 1. In general determining whether a function is strict is undecideable. But a conservative approximation can certainly be guaranteed to terminate. And what is stopping us from having our conservative analysis continue at runtime, as terms are evaluated by the running program? I think I could formulate some notion of having the running program incorporate all available information from terms that have already been evaluated into its analysis. This could be considered the best possible analysis that doesn't affect the termination properties of the program. (Since it does not affect evaluation order of the program or what terms are evaluated.) Of course, like Claus says there are tradeoffs here since a more accurate analysis might not be efficient enough timewise to be useful. But like I said, we already have a "budget" for doing some analysis at runtime since unnecessary memory allocation of thunks also incurs a runtime cost. 2. Having to rewrite higherorder functions so they can be inlined and So, right now it sounds like I should maybe explore this problem a bit more Best, On Mon, Jun 15, 2009 at 1:39 PM, Claus Reinke <claus....@talk21.com>wrote: 
Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Stefan Holdermans  6/17/09 3:31 AM  Dear Paul, This thread as well as your blog post is very interesting. Hopefully I On your blog, you mention that your scheme for runtime strictness One way to do this, would be by storing strictness information in the const :: a > b > a could read a > {S} > b >{L} a Here, we have annotated the functionspace constructor (>) with An annotated type like the one above can be easily inferred by a const <a> <b> (x :: a) (y :: b) = x So, now const takes two extra arguments, both of which are types const 2 'x' becomes const <Int> <Char> 2 'x' While typing information can proof valuable to have around at compile Pretty much the same holds for the strictness annotations that are const <a> <b> (x :: a{S}) (y :: b{L}) = x where a {S} indicates strictness and {L} laziness. Viewing strictness annotations as types, a natural step is to allow apply :: (a > b) > a > b is supposed to work on both strict and lazy functions. Moreover, (a >{i} b) >{S} >{i} b Here, i is a strictness variable that is to be instantiated with apply <a> <b> {i} (f :: (a >{i} b){S}) (x :: a{i}) Of course, just as with ordinary types, strictness annotations don't But what if we don't erase these annotations? Then we can use Performing strictness analysis on foldl, foldl :: (b > a > b) > b > [a] > b we find the annotated type (b >{i} >{j} b) >{L} b >{i} [a] >{S} > b Indeed, whether foldl is strict in its second argument depends on foldl <a> <b> {i} {j} (f :: (b >{i} >{j} b){L}) (e :: b{i}) (l :: Allright, that's messy, but bear with me. (At this point, we could Now, let's apply the foldl to (+), 0, and [1 .. 1000000] assuming that (+) :: Int >{S} Int >{S} Int and let's pass in the arguments in three steps. First we pass in the foldl <Int> <Int> :: (Int >{i} Int >{j} Int) >{L} Int >{i} Then the strictness arguments: foldl <Int> <Int> <S> <S> :: (Int >{S} >Int >{S} Int) >{L} Int  Now we have obtained a specialised version of foldl that is lazy in foldl <Int> <Int> <S> <S> (+) (0) [1 .. 1000000] Moreover, this can be done for each recursive call as well, So, the on strictness information depending decision that is to made First, let us abstract from function types annotated with S or L and infixl 9 # class Fun f where That is, functions are constructed by means of the method lam and Haskell's builtin lazy function space (>) provides a natural instance Fun (>) where In addition, we provide a strict functionspace constructor (:>): newtype a :> b = S {unS :: a > b} instance Fun (:>) where Now we can have a "handannotated" version of foldl: foldl :: (Fun i, Fun j) => i b (j a b) > i b ([a] :> b) Note how the type arguments i and j play the roles of the strictness What's important to note is that the transformation from the "normal" Now, let's try it out. Say we have two versions of addition on lplus :: Int > Int > Int splus :: Int :> Int :> Int There we go: *Main> foldl # lplus # 0 # [1 .. 1000000] *Main> foldl # splus # 0 # [1 .. 1000000] Isn't that neat? Of course, whether this scheme would work out in practice depends on Well, just my two cents. :) Cheers, Stefan 
Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Paul Chiusano  6/17/09 3:07 PM  Stefan, Thank you for the detailed response! In trying to follow your email I got a bit confused by your notation  const :: a > b > a const x y = x could read a > {S} > b >{L} a > Here, we have annotated the functionspace constructor (>) with
Best, > information to participate in runtime decisions as welljust as you 
Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Ryan Ingram  6/17/09 5:33 PM  Also, partial application + seq throws a wrench in things: seq (const undefined) () but seq (const undefined ()) () So const is only strict in its first argument when fully applied; I That is, these two functions need to have different types: const1 = \x > seq x (\y > x) The first is strict always whereas the second is only strict when fully applied.  ryan On Wed, Jun 17, 2009 at 3:07 PM, Paul Chiusano<paul.c...@gmail.com> wrote:> Did you mean to say that const is strict in its first param and lazy in its > _______________________________________________ 
Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Stefan Holdermans  6/17/09 10:39 PM  Ryan, > Also, partial application + seq throws a wrench in things: [...] You're absolutely right. I did not take into account the effects of http://people.cs.uu.nl/stefan/pubs/holdermans09spreading.html .

Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Stefan Holdermans  6/17/09 10:39 PM  Paul, > In trying to follow your email I got a bit confused by your notation  I'm sorry for the confusion. Indeed, const, as the type was intended I prefer to put the annotation on the function arrow as strictness is

Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Stefan Holdermans  6/18/09 4:35 AM  Paul, >> Did you mean to say that const is strict in its first param and Ah, sorry. Now I see where I really confused you. Someone pointed out a >{S} b >{L} a HTH,

Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Edward Kmett  6/18/09 7:31 AM  I have been exploring a weak form of runtime strictness analysis in a tracing JIT project of my own in the spirit of TraceMonkey. Basically a tracing JIT doesn't compile blocks of code but instead once a tracing point has been passed often enough, it starts a trace from that point logging the series of instructions executed to a bounded log. If you make it back to the starting point before the log fills up then you've identified a superblock with a bunch of side exits for handling when your assumptions are violated. What is interesting is in a lazy setting, if you are tracing a bytecode But the key concern for the sake of the current discussion is that it models Edward Kmett > Hello,
> I started thinking about ways you could to a check at runtime for this sort > Note that I'm not suggesting Haskell should do anything like this. I'm > about space usage ... which might be hopelessly unrealistic goal! I guess > Best, > _______________________________________________ 
Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Max Bolingbroke  6/18/09 9:31 AM  2009/6/18 Edward Kmett <ekm...@gmail.com>:
This sounds absolutely awesome! Is the source code for your prototype Cheers,

Re: [Haskellcafe] Runtime strictness analysis for polymorphic HOFs?  Edward Kmett  6/19/09 12:46 AM  Hi Max, I don't have anything in a public repository at this time. I have been exploring a series of designs in this space trying to see if any could be applied to a system like GHC's bytecode interpreter, but up to now I've been working mostly with cooperatively jitting x8664 assembly to x8664 assembly for a possibly commercial project. I have only recently started trying to adapt my research to a more functional setting. If you hop on #haskell some time, I'd be happy to talk further. Edward Kmett
