Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!comp.vuw.ac.nz!cc-server4.massey.ac.nz!E.Ireland
From: E.Ireland@massey.ac.nz (Evan Ireland)
Newsgroups: comp.lang.functional
Subject: Run-time strictness analysis
Keywords: strictness
Message-ID: <451sis-b@massey.ac.nz>
Date: 26 Nov 90 00:42:20 GMT
Reply-To: E.Ireland@massey.ac.nz
Organization: Information Sciences, Massey University, New Zealand
Lines: 65

Hi,

I am currently implementing a kind of run-time strictness analysis for
a Lazy Functional Abstract Machine, but I have been unable to find any
references to similar work.

My motivation for this is the apparent inefficiency caused by the use
of higher-order functions in lazy languages such as Haskell.  I have
found papers describing techniques for strictness analysis by abstract
interpretation in the presence of higher-order functions, however
these are compile-time techniques, and fail to address certain
efficiency problems.  I would appreciate it if anyone could send me
references or information on this topic.

As an example of the efficiency problems I am referring to, consider

    foldr :: (a -> b -> b) -> b -> [a] -> b

    foldr f z []     =  z
    foldr f z (x:xs) =  f x (foldr f z xs)

When compiling this, we must suspend the recursive application of
foldr, since it may not terminate, and f may or may not be strict in
its second argument, depending on the actual f that is provided at
run-time.  We could compile two versions of foldr, one `conservative'
and one `nice'.  Then at compile-time, for some calls to foldr, we may
know that it is safe to call the `nice' version to avoid unnecessary
suspensions, i.e. we know we have not inadvertently introduced
non-termination.  However this approach may lead to excessive code
generation, especially with functions taking several functions as
arguments.

Another problem with compile-time strictness analysis, especially for
languages with Haskell-like module systems, is that strictness
information has no place in a module interface (except perhaps as
annotations).  Assume that module B imports module A, and several
implementations of module A are allowed (perhaps with differing
strictness properties for some functions).  Module B should only need
recompilation if the interface for module A is changed, and not if we
happen to change module A's implementation.  This constraint, if
enforced, would limit the usefulness of compile-time strictness
analysis to intra-module (and standard library) optimisations.

My suggested run-time approach is to have each closure (function +
environment for free variables) carry strictness information, and at
run-time either evaluate or suspend certain expressions depending on
the strictness properties of the function they happen to be an
argument of.


    f x = g (h x) (x + 1)

Even if g is not strict in its second argument, we needn't delay the
(+) call in when x is already evaluated.  I would imagine that few
current implementations, if any, have optimisations of this sort.

*********************************************************************

A question for Haskell and other lazy f.l. implementors: What do you
do about functions like foldl and foldr in the standard library?  And
are they treated any differently than if they were user-defined
functions?

				  Evan Ireland (E.Ireland@massey.ac.nz),
School of Information Sciences, Massey University, Palmerston North, NZ.