# Non-strict semantics

### From HaskellWiki

(more motivation and examples) |
(There is no call by demand page. Additionally, it linked users to the edit page, which displayed a 'Forbidden Action' error messasge.) |
||

(3 intermediate revisions by 2 users not shown) | |||

Line 7: | Line 7: | ||

</haskell> | </haskell> | ||

− | 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 | + | 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. |

+ | == Details == | ||

Non-strict semantics allows to formally process infinite amount of data. | Non-strict semantics allows to formally process infinite amount of data. | ||

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 | + | 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 28: | ||

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 | + | 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 | + | 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 | + | 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. | ||

Line 47: | Line 52: | ||

Although Haskell only requires the non-strict semantics all of its compilers use [[lazy evaluation]], | 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. | which is only one possible implementation of the non-strict semantics. | ||

− | |||

− | |||

==See also== | ==See also== | ||

* Jonathan Cast in Haskell Cafe about [http://www.haskell.org/pipermail/haskell-cafe/2007-November/034807.html What is the role of $! ?] | * Jonathan Cast in Haskell Cafe about [http://www.haskell.org/pipermail/haskell-cafe/2007-November/034807.html What is the role of $! ?] | ||

− | |||

* [[Lazy vs. non-strict]] | * [[Lazy vs. non-strict]] | ||

+ | * [[Maintaining laziness]] | ||

+ | |||

[[Category:Glossary]] | [[Category:Glossary]] |

## Revision as of 01:55, 23 October 2011

**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.

## 1 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 listbecause an undefined sub-expression implies an undefined expression.

In the non-strict semantricsIf 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.

## 2 See also

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