Skip to content

Lack of eta expansion in NoFib's fft2

According to what I wrote in my Master's thesis a few years ago, the following example is inspired by NoFib's fft2 benchmark:

foo :: ([a] -> [a]) -> [a] -> [a]
foo f a = f a
{-# NOINLINE foo #-}


bar :: Int -> [Int] -> [Int]
bar n =
  let bar' = bar (n-1) in
  if sum [0..n] < 10
    then \xs -> 10:xs
    else \xs -> foo bar' xs

main = print ( bar 1 [2])

The point here is that even though bar has arity 1 as written, it could be eta-expanded: Assuming we'd eta-expand bar, the sharing of the pap bar' turns out unnecessary, because foo will call bar' only once, with one arg.

Neither Call Arity nor Demand Analysis is able to detect that:

  • Call Arity doesn't see that foo will call bar' only once, because it doesn't have a signature mechanism. Neither could it, because it analyses let body before RHS.
  • Demand Analysis computes a signature for foo from which it can tell that bar' is only called once with one arg (MCM(L)). But likewise, it analyses bar's RHS before looking at how it's used. Thus, it doesn't see that the only external call in main is one with two args. Thus, upon analysing bar's RHS, it has to assume that \xs can be entered many times, each of which might result in one call to the PAP bar'. Thus to DmdAnal, it appears as if bar' is shared, which prohibits eta-expansion of bar.

The DmdAnal variant of my Master's thesis was able to eta-expand bar. I believe !5349 is able to do so, too, but I can't tell at the moment because I don't have it checked out and built at the moment. Simon and I are working on a way to do the same in a way that is explainable to someone else.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information