Should folds in containers package remain INLINE
Simon PeytonJones
simonpj at microsoft.com
Mon May 7 10:02:47 CEST 2012
 > Can you give a concrete example. It's hard to be certain but what you
 describe sounds like exactly what INLINABLE does.
Your example didn't use any type classes, so GHC won't specialise it. (Specialising on *value* parameters is another story.)
But your words mention type classes, so maybe it will. It's hard to tell. Maybe you can try it and see.
Simon
 Original Message
 From: librariesbounces at haskell.org [mailto:libraries
 bounces at haskell.org] On Behalf Of wren ng thornton
 Sent: 06 May 2012 01:31
 To: libraries at haskell.org
 Subject: Re: Should folds in containers package remain INLINE

 On 5/4/12 5:01 AM, Simon PeytonJones wrote:
 >
 >  I know one thing I run into a lot, especially with folds but also
 >  with other generic functions, is that what I really want is type
 >  class specialization. That is, at compile time inline the function
 >  enough to make the type class parameters static so that the methods
 >  can be inlined back into the generic function; and then at runtime
 >  do typebased dispatch to the specialized versions just like if you
 >  were looking up the instance record or doing SPECIALIZE lookup. The
 >  goal being to remove the indirect calls in inner loops, but in a
 >  particularly restricted way since instances are known at compile
 >  time and therefore code bloat will be limited (unlike, say, function
 or record arguments).
 >
 > Can you give a concrete example. It's hard to be certain but what you
 describe sounds like exactly what INLINABLE does.

 For a (semi)concrete example, say we have an implementation of the
 forwardbackward algorithm. The algorithm is O(n^3) but those are some
 nice tight loops. The algorithm can be parametrized by your choice of
 semiring. So we make a type class for semirings in order to make the
 algorithm generic, but we want the algorithm to be specialized on the
 type class rather than performing indirect calls in the middle of
 O(n^3).

 The (firstorder) forward algorithm is defined by the recurrence:

 alpha :: Position > State > Probability
 alpha 0 s0 = prior s0
 alpha j sj =
 let i = j1 in
 sum [ alpha i si * p si sj  si < states i ]

 where prior and p are probability models, states gives us all the
 possible states at that position, the sum and (*) are actually for the
 semiring of choice, and where we actually store everything in a table in
 order to do dynamic programming.

 The backward algorithm is defined similarly:

 beta :: Position > State > Probability
 beta T sT = coprior sT
 beta i si =
 let j = i+1 in
 sum [ p si sj * beta j sj  sj < states j ]

 where T is some known constant, namely the maximum position.

 For efficiency reasons, the actual code is a good deal more complicated
 than the above recurrences, but the basic idea is the same. We don't
 particularly want to specialize on the parameters (prior, p, states,...)
 since those are defined dynamically, but we do want to specialize on the
 semiring since the set of semirings we'll care about is fixed at compile
 time.

 Given what Johan Tibell said, I think INLINABLE will in fact do this;
 but his description of the pragma differs from what I recalled of back
 when we came up with it. Hence the question.

 
 Live well,
 ~wren

 _______________________________________________
 Libraries mailing list
 Libraries at haskell.org
 http://www.haskell.org/mailman/listinfo/libraries
More information about the Libraries
mailing list