[Haskell-cafe] Runtime strictness analysis for polymorphic HOFs?

[Claus Reinke]

> 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. :-(

As has been pointed out, strictness analysis is not decidable. That doesn't
mean it is undecidable - running the code and seeing what it does gives a
naive semi-decision procedure. So strictness analysis can be made more
precise by using more and more runtime information; unfortunately it also
becomes less and less useful as a static analysis in the process (in practice,
not just termination is important, but also efficiency of the analyses, so an
analysis would tend to become unusable before it became possibly non-
terminating - there are trade-offs between precision and efficiency).

For typical higher-order functions, there's a simple workaround, already
employed in the libraries, namely to split the definition into a simple front
that may be inlined, and a recursive back where the parameter function 
is no longer a parameter. Then, after inlining the front at the call site, the
back can be compiled and analysed with knowledge of the parameter
function. See the comment above foldl:

http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/GHC-List.html#foldl

Claus