Difference between revisions of "User:Benmachine/Non-strict semantics"
Jump to navigation
Jump to search
Benmachine (talk | contribs) (New page: An expression language is said to have '''non-strict semantics''' if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to...) |
Benmachine (talk | contribs) (Redirected page to Non-strict semantics) |
||
| (24 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | #REDIRECT [[Non-strict semantics]] |
||
| − | An expression language is said to have '''non-strict semantics''' if expressions can have a value even if some of their subexpressions do not. Haskell is one of the few modern languages to have non-strict semantics by default: nearly every other language has [[strict semantics]], in which if any subexpression fails to have a value, the whole expression fails with it. |
||
| − | |||
| − | === What? === |
||
| − | |||
| − | Any sufficiently capable programming language is ''non-total'', which is to say you can write expressions that do not produce a value: common examples are an infinite loop or unproductive recursion, e.g. the following definition in Haskell: |
||
| − | |||
| − | <haskell> |
||
| − | noreturn :: Integer -> Integer |
||
| − | noreturn x = negate (noreturn x) |
||
| − | </haskell> |
||
| − | |||
| − | or the following Python function: |
||
| − | |||
| − | def noreturn(x): |
||
| − | while True: |
||
| − | x = -x |
||
| − | |||
| − | return x # not reached |
||
| − | |||
| − | both fail to produce a value when executed. We say that <tt>noreturn x</tt> is undefined, and write <tt>noreturn x = [[Bottom|⊥]]</tt>. |
||
| − | |||
| − | In Python the following expression: |
||
| − | |||
| − | {7: noreturn(5), 2: 0}[2] |
||
| − | |||
| − | also fails to have a value, because in order to construct the dictionary, the interpreter tries to work out <tt>noreturn(5)</tt>, which of course doesn't return a value. This is called '''innermost-first''' evaluation: in order to call a function with some arguments, you first have to calculate what all the arguments are, starting from the innermost function call and working outwards. The result is that Python is strict, in the sense that calling any function with an undefined argument produces an undefined value, i.e. <tt>f(⊥) = ⊥</tt>. |
||
| − | |||
| − | In Haskell, an analogous expression: |
||
| − | |||
| − | <haskell> |
||
| − | lookup 2 [(7, noreturn 5), (2, 0)] |
||
| − | </haskell> |
||
| − | |||
| − | in fact has the value <hask>Just 0</hask>. The program does not try to compute <hask>noreturn 5</hask> because it is irrelevant to the overall value of the computation: only the values that are necessary to the result are computed. This is called '''outermost-first''' evaluation because the first thing you look at is the call to <hask>lookup</hask> to decide if it needs to evaluate its arguments, and then if it does, you look at the arguments. The upshot is that Haskell has some functions which are not strict, i.e. sometimes <hask>f ⊥ ≠ ⊥</hask>. This means that Haskell functions need not completely compute their arguments, which is why e.g. <hask>take 3 [1..]</hask> can produce <hask>[1,2,3]</hask> even though it is given a conceptually infinite list. |
||
| − | |||
| − | === Why? === |
||
| − | |||
| − | The important thing to understand about non-strict semantics is that it is not a performance feature. Non-strict semantics means that only the things that are needed for the answer are evaluated, but if you write your programs carefully, you'll only compute what is absolutely necessary ''anyway'', so the extra time spent working out what should and shouldn't be evaluated is time wasted. For this reason, non-strict programs tend to be a little slower than strict programs. |
||
Latest revision as of 21:29, 14 September 2013
Redirect to: