All you ever wanted to know about evaluation strategies (and more)
f <some expression> means "compute the value of <some expression> and apply f to the result", right?
Wrong. See, there are different ways of passing arguments to functions. In many languages, such as C or Python, an argument is indeed always evaluated before the body of the function it is passed to runs. However the same can't be said of Haskell, for example. Indeed, in this language, only arguments whose values are actually required to produce a value are evaluated. In fact, things get crazier: if the call to the function itself does not influence the functional behavior of the program (i.e. its behavior with regards to output values only, abstracting over e.g. the notion of time), then it can be elided.
The big families of evaluation strategies are as follows:
- value-based: evaluate each argument before calling the function.
- reference-based: evaluate each argument before calling the function — additionally, the arguments can be used as handles through which values residing outside of the function can be modified.
- lazy evaluation: compute only the values of the arguments which are actually required to evaluate in the function.
- doesn't deserve a name, as we will see: compute only the values of the arguments which are actually required to evaluate in the function — additionally, the arguments can be used as handles through which values residing outside of the function can be modified.
We can organize these strategies based on the following properties:
- strictness: do we have the guarantee that each argument will be evaluated exactly once when the function is called?
- purity: is this strategy compatible with pure languages?
Let's visualize the result:
imperative languages, functional languages
The strategies employed in functional and imperative languages are outlined (note that a single language may implement several strategies, and then usually makes it possible to apply them on a per argument basis, as in C when only some of a function's arguments are pointers). The fact that pure functional languages are incompatible with impure strategies should be obvious enough, but there is more to say about strictness.
Imperative languages are impure. In settings where side-effects are common, strictness is a natural choice: having effectful expressions being evaluated depending on complex implicit criteria would be very confusing.
On the other hand, functional languages aim at some form of purity, and pure languages can afford laziness. In practice, most functional languages are not that pure, so they stick to passing by value. The most famous lazy language is probably Haskell, which is as close to a useful pure functional language as it gets (for more details, see on impurity (and Haskell)).
There are some examples of non-strict impure strategies, e.g. ALGOL 60 style call-by-name. There may be a good reason why this hasn't caught on, though. For more details, see Jensen's device or call-by-macro vs. call-by-name (in summary: don't).
Note that the categories outlined here correspond to archetypes which can be implemented in different ways: call-by-need, sharing, copy-restore, reference to const, call-by-macro, …
Aside: laziness and conditionals
Note that in lazy languages, the if-then-else construct can be implemented as a function (usually, some syntactic sugar is added for convenience); laziness provides a natural framing of the evaluation of conditionals (and of short-circuiting). In contrast, imperative languages have to treat them as special cases.
Aside: C
In C, internal side effects can be a thing even when using call-by-value: consider what happens when passing a pointer-containing structure by value, or tricks such as pointer arithmetic on the addresses of local elements (stack buffer overflow style). The pervasiveness of side-effects in this language is such that you can never know whether a definition is pure or not without reading it in full (on the other hand, C++'s notion of constexprs makes it possible to isolate some pure fragments, albeit in a clumsy way).
Still, call-by-value was classified as a pure evaluation strategy. How come? The reason for this is that it is possible to do call-by-value in a pure language, whereas the same can't be said of call-by-reference. In other words, the impurity is not brought by the evaluation strategy, it's just that using a pure strategy in an impure context doesn't somehow redeem said context.
Aside: bridges between evaluation strategies
So, you are programming in an imperative language and you would like to enjoy the benefits of laziness? That's perfectly fine: you can emulate laziness in strict languages through thunks (in languages with functional features) or through structures (in this case, the name of the argument should not be used directly in the function; rather, it should be replaced with a call to a function which computes the value of the argument, or fetches it if it is already known). This is of course best suited to evaluate expressions written in the pure subset of the language in question (albeit some type of impurities tend to be fine, e.g. reading a file from disk).
Emulating strictness in lazy languages is less useful: owing to their purity, whether an argument is evaluated or not does not impact the functional behavior of a function (marking arguments as strict could help the compiler generate higher performance code in some situations, though). Still, it can be useful to pretend that arguments are strictly evaluated to get an upper bound on complexity.
Aside: call-by-name vs. call-by-name
"Call-by-name" can mean both the aforementioned ALGOL 60 abomination and an uncommon form of lazy evaluation, where expressions passed as arguments are evaluated each time they are used. That is, if they are unused, then they are not evaluated. However, if they are used ten times, then the computation runs ten times.