Personal tools

Non-strict semantics

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m
(more motivation and examples)
Line 8: Line 8:
   
 
You will not be able to define a function <code>or</code> 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 <code>or(true,infinite_loop())</code>, the code of <code>or</code> will never be run. In Haskell it is possible because you [[Call by demand]].
 
You will not be able to define a function <code>or</code> 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 <code>or(true,infinite_loop())</code>, the code of <code>or</code> will never be run. In Haskell it is possible because you [[Call by demand]].
  +
  +
  +
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 computation only depend on a finite amount of data.
  +
Why is this related to non-strict semantics?
  +
Consider the list <hask>1:2:undefined</hask>.
  +
In the strict semantics this would be equivalent to <hask>undefined</hask>,
  +
because an undefined sub-expression implies an undefined expression.
  +
In the non-strict semantrics <hask>1:2:undefined</hask> and <hask>undefined</hask> 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 <hask>undefined</hask>.
  +
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 my write
  +
<haskell>
  +
fadedMusic = envelope (fadeIn ++ hold ++ fadeOut) music
  +
</haskell>
  +
that is, you have the steps of composing the fader control, fetch the music signal and 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 multiplied.
  +
  +
In much the same way you can process video sequences, power series, continued fractions, decision trees, 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==
 
==See also==

Revision as of 14:07, 27 November 2007

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.


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 computation 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 my write

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

that is, you have the steps of composing the fader control, fetch the music signal and 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 multiplied.

In much the same way you can process video sequences, power series, continued fractions, decision trees, 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