On Sun, 2006-07-30 at 10:56 +0100, Jón Fairbairn wrote:

"David House" writes:

...

Hi all.

I've seen two definitions of a 'strict function', which I'm trying to unite in my mind:

1) f is strict iff f _|_ = _|_. 2) f is strict iff it forces evaluation of its arguments.

There is a large sticking point that in my minds seems to fit (1) but not (2): id. Clearly, id undefined is undefined, but I also don't think id forces evaluation of its argument. There was a mini-discussion concerning this topic last night on #haskell, but if there was a consensus conclusion, it passed me by.

Thanks in advance.

In (2), you have to be evaluating f on an argument before f can force the argument. If you evaluate id x, you necessarily evaluate x. I don't think (2) is a very good definition, since I don't know what "forces" means here.

Surely it just means evaluate to weak head normal form? Definition 2) relies on following a certain evaluation strategy: that operationally, functions always return results in weak head normal form. GHC follows this strategy. It's possibly to imagine returning thunks and then getting the caller to force the evaluation to WHNF. So under the latter model, 'id' would operationally do nothing. It would not force its argument. Under the more sensible model 'id' does force its argument to WHNF before returning. Duncan

On Sun, 2006-07-30 at 13:22 +0100, Jón Fairbairn wrote:

Duncan Coutts writes:

...

On Sun, 2006-07-30 at 10:56 +0100, Jón Fairbairn wrote:

...

"David House" writes:

...

1) f is strict iff f _|_ = _|_. 2) f is strict iff it forces evaluation of its arguments.

...

Definition 2) relies on following a certain evaluation strategy: that operationally, functions always return results in weak head normal form. GHC follows this strategy. It's possibly to imagine returning thunks and then getting the caller to force the evaluation to WHNF.

Which is pretty much my point. Use a definition of "strict" that doesn't depend on anything but denotations (or Böhm trees).

Yes, for being precise a denotational approach is simpler. However for an intuition about how strictness affects evaluation order and space and performance behaviour I find that 2) is quite a helpful way to look at things. It allows you to look at a function and ask: if I demand the result in WHNF (which I know will happen if the function is called at runtime) what demand will that place on other expressions, variables and arguments. The discussion on #haskell went on to conclude that we need better tools for showing us the inferred strictness of functions we write (eg by getting the compiler to tell us). It was also noted that many Haskell programmers, especially beginners have very little intuition about strictness and so can't get themselves out of troubles caused by too much or to little strictness, like performance problems, memory leaks and exceptions slipping past exception handlers. Duncan

On 30/07/06, Ian Lynagh wrote:

If the value of (id x) is demanded then the value of x will always be demanded. Therefore id is strict in its first argument. ... In place of your 2), I would say (f x0 .. xn) is strict in xi if demanding the value of (f x0 .. xn) requires demanding the value of xi.

Ah. Very helpful. Thanks. -- -David House, dmhouse@gmail.com