Lazy vs. non-strict

(this is a bit of a stub. Feel free to edit)

Haskell is often described as a lazy language. However, the language specification simply states that Haskell is non-strict, which is not quite the same thing as lazy. See Non-strict semantics for a brief example.

(describe WHNF)

Laziness is simply a common implementation technique for non-strict languages, but it is not the only possible technique. One major drawback with lazy implementations is that they are not generally amenable to parallelisation. This paper states that experiments indicate that little parallelism can be extracted from lazy programs:

"The Impact of Laziness on Parallelism and the Limits of Strictness Analysis" (G. Tremblay G. R. Gao) http://citeseer.ist.psu.edu/tremblay95impact.html

Lenient, or optimistic, evaluation is an implementation approach that lies somewhere between lazy and strict, and combines eager evaluation with non-strict semantics. This seems to be considered more promising for parallelisation.

This paper implies (section 2.2.1) that lenient evaluation can handle circular data structures and recursive definitions, but cannot express infinite structures without explicit use of delays:

"How Much Non-­strictness do Lenient Programs Require?" (Klaus E. Schauser, Seth C. Goldstein) http://citeseer.ist.psu.edu/schauser95how.html

Some experiments with non-lazy Haskell compilers have been attempted: http://www.haskell.org/haskellwiki/Research_papers/Runtime_systems#Optimistic_Evaluation