Personal tools

Non-strict semantics

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(more motivation and examples)
m
Line 13: Line 13:
 
Actually any terminating computation must only consume a finite 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
 
but surprisingly there are many applications with formally infinite data
where all partial computation only depend on a finite amount of data.
+
where all partial computations only depend on a finite amount of data.
 
Why is this related to non-strict semantics?
 
Why is this related to non-strict semantics?
 
Consider the list <hask>1:2:undefined</hask>.
 
Consider the list <hask>1:2:undefined</hask>.
Line 27: Line 27:
 
In principle it can be infinitely long, but e.g. for amplifying the signal only current data is necessary.
 
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,
 
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.
+
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.
 
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
+
E.g. you may write
 
<haskell>
 
<haskell>
 
fadedMusic = envelope (fadeIn ++ hold ++ fadeOut) music
 
fadedMusic = envelope (fadeIn ++ hold ++ fadeOut) music
 
</haskell>
 
</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.
+
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:
 
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.
+
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, power series, continued fractions, decision trees, real numbers.
+
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.
 
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.
 
You can program the processing of an XML tree by a sequence of transformations of the whole XML tree.

Revision as of 14:14, 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 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