Tag Archives: Haskell

Haskell – Lazy Evaluation

Evaluation Strategies

An expression that has the form of a function applied to one or more arguments that can be “reduced”by performing the application is called a reducible expression, or redex for short. As indicated by the use of quotations marks in the preceding sentence, such reductions do not necessarily decrease the size of an expression, although in practice this is often the case.

Example:

mult :: (Int, Int) -> Int
mult (x, y) = x * y

Consider the expression mult(1+2, 2+3). This expression contain three redexes, namely the sub-expressions 1+2 and 2+3, which have the form of the function + applied to two arguments, and the entire expression mult(1+2, 2+3) itself, which has the form of the function mult applied to a pair of arguments. Performing the corresponding reductions gives the expression mult(3, 2+3), mult(1+2, 5) and (1+2)*(2+3).

When evaluating an expression, in what order should reductions be performed? One common strategy, call innermost evaluation, is to always choose a redex that is innermost, in the sens that it contains no order redex. If there is more than one innermost redex, by convention, we choose that which begins at the leftmost position in the expression.

Innermost evaluation can also be characterized in terms of how arguments are passed to functions. In particular, using this strategy ensures that the argument of a function is always fully evaluated before the function itself is applied. That is, arguments are passed by value.

Another common strategy for evaluating an expression, dual to innermost evaluation, is to always choose a redex that is outermost, in the sense that it is contained in no other redex. If there is more than one such redex, then as previously, we choose that which begins at the leftmost position. Not surprisingly, this evaluation strategy is called outermost evaluation.

In terms of how arguments are passed to functions, using outermost evaluation allows functions to be applied before their arguments are evaluated. For this reason, we say that arguments are passed by name.

Note, however, that many built-in functions require their arguments to be evaluated before being applied, even when using outermost evaluation. For example, built-in arithmetic operators such as * and + cannot be applied until their two arguments have been evaluated to numbers. Functions with this property are called strict.

 

Lambda Expressions

Example:

mult :: Int -> Int -> Int
mult x = y -> x * y

Note that in Haskell, the selection of redexes within lambda expression is prohibited. The rational for not “reducing under lambdas” is that functions are viewed as black boxes that we are not permitted to look inside. More formally, the only operation that can be performed on a function is that of applying it to an argument. As, such, reduction within the body of a function is only permitted once the function has been applied.

Using innermost and outermost evaluation, but not under lambdas, is normally referred to as call-by-value and call-by-name evaluation, respectively.