Non-strict semantics

Non-strict semantics means that a function can have a definite value although its argument is undefined. E.g. in Haskell you get

Prelude> True || undefined
True

You will not be able to define a function or say in C which returns something if you pass an undefined value (e.g. one that is the result of an infinite loop). In fact, in or(true,infinite_loop()), the code of or will never be run. In Haskell it is possible because you Call by demand.

Details

Non-strict semantics allows to formally process infinite amount of data. Actually any terminating computation must only consume a finite amount of data, but surprisingly there are many applications with formally infinite data where all partial computations only depend on a finite amount of data. Why is this related to non-strict semantics? Consider the list 1:2:undefined. In the strict semantics this would be equivalent to undefined, because an undefined sub-expression implies an undefined expression. In the non-strict semantrics 1:2:undefined and undefined are very different. You can process the start of the list (that is 1 and 2) safely, as long as you do not touch the undefined. If you do not touch that part of the list, you don't care what it actually is, it might also be some infinite data stream. In the strict semantics an infinite stream is an infinite loop and thus undefined.

What does this mean in practice? Consider the processing of an audio stream: In principle it can be infinitely long, but e.g. for amplifying the signal only current data is necessary. Non-strict semantics ensures that only the needed audio data is fetched, and the garbage collector cares about freeing data that is no longer needed. The nice thing is that you can separate logical processing steps but the data is processed as it is requested. E.g. you may write

fadedMusic = envelope (fadeIn ++ hold ++ fadeOut) music

that is, you have the steps

• composing the fader control
• fetching the music signal
• amplify the music according to the fader envelope.

But the program is processed in the order of data: For the first emitted sample, the first sample of music and the first sample of the envelope are computed and then multiplied.

In much the same way you can process video sequences, decision trees, power series, continued fractions, real numbers. Also for finite but huge, or finite but still not completely known data, the non-strict semantics allows elegant programs. You can program the processing of an XML tree by a sequence of transformations of the whole XML tree. If the single transformations are carefully programmed then you can process a (serial) XML file from the beginning to the end without having to store the whole document in the memory at some time and without even knowing when and whether the document ends, and whether there will be some syntax error later in the file.

Although Haskell only requires the non-strict semantics all of its compilers use lazy evaluation, which is only one possible implementation of the non-strict semantics.

See also

• Jonathan Cast in Haskell Cafe about What is the role of $! ?
• Lazy vs. non-strict
• Maintaining laziness