Redexes and Lazy Evaluation

One of the most important techniques used to execute Haskell program code is lazy evaluation. It has many benefits, but it could present a problem with memory terms, if it is not used properly.

In Haskell, a program is performed through expression evaluation. A technique called graph reduction is used in evaluation. It prevents duplicate steps in the process of expression evaluation. Let’s look at an example.

upSquare c = c*c

The preceding function could be called with an argument such as 2+3.

upSquare (2+3)

The evaluation works as follows: from the definition of function, c becomes c = 2+3:

upSquare (2+3)
=> (2+3)*(2+3)

Then, the + and * operators are evaluated.

(2+3)*(2+3)
=>5*(2+3)
=>5*5
=>25

In the preceding example, the same steps are performed many times; namely, 2+3 is evaluated twice, even if it is the same. To avoid these useless evaluations, so you apply a technique called graph reduction. This means that the expressions could be represented as graphs, as shown in Figure 4-1.

Figure 4-1. Expression as graph

In Figure 4-1, the blue section (on the left) represents the function, and the green section (on the right) represents the arguments for that function. In a similar way, the expressions are represented in the memory, with the help of pointers. All defined functions are linked to a reduction rule . For our example, the rule is shown in Figure 4-2.

Figure 4-2. Rule for reduction

The circle with label x is replacing a subgraph. For the * operator function, there is a single subgraph, because the arguments have the same value. If you commonly use this kind of subgraph, you can prevent useless operations.

A reducible expression (redex) represents a subgraph that fits with a rule. A redex can be reduced; namely, the focused pair is updated in accordance with the rule. The redexes shown in Figure 4-3 are in the upSquare example: upSquare could be reduced or the + operator function could be reduced.

Figure 4-3. Redexes for upSquare

In the first step, let’s apply the reduction for the upSquare function , and then, we evaluate the redex for +, obtaining the sequence shown in Figure 4-4.

Figure 4-4. Reduction process for upSquare

It updated the colored redex at each stage. In the second-to-last graph, we introduced a novel redex, corresponding to the multiplication rule. The result is 25.

If there is no expression in the graph that can be reduced, then the process of reduction is finished and we obtain the result. The last form of expression is called normal form, which represents the result of an evaluation process. In our example, Figure 4-5 shows the result.

Figure 4-5. The result of upSquare(2+3)

For every expression, there is a graph. For example, the list obtained through the operations 9:10:11:[] (which is in the normal form, because there is nothing else to reduce) has the graph shown in Figure 4-6 associated with it.

Figure 4-6. Steps for obtainig the list [9,10,11]

A graph is in the normal form if it is finite and has no cycles. The cycles or infinity could occur because of the recursion.

In Haskell, the evaluation does not always end when the expression reaches the normal form. There is a particular type of normal form called weak head normal form ( WHNF) . If the topmost node of a graph is a constructor, then the graph is in WHNF. For example, the expression (2+3) : [] in Figure 4-7 is stated in the WHNF form because its root is an instance of the constructor (:) of the list, and it is not in the normal form because the first parameter has a redex.

Figure 4-7. Example of WHNF form

A graph that is not in the WHNF is called an unevaluated expression, or thunk. Even if an expression is in WHNF, the parameters for the constructor could be unevaluated expressions. A good example is the following piece of code.

Prelude> onesList = 1 : onesList

The onesList is a list obtained by adding the digit 1 to itself (so, it becomes infinite). Even the associated graph has a topmost constructor, its argument is an unevaluated expression.

Usually, expressions contain more redexes. From this fact rises a natural question: In what order are they reduced?

Many programming languages are based on eager evaluation , which means the arguments of a function are first reduced to normal form, and then the function itself is reduced. This technique is not adopted by Haskell, however. In Haskell, the evaluation technique is lazy evaluation, which means that the topmost function is evaluated first. If necessary, it evaluates some arguments of the function. Let’s consider the logicalAnd function , which implements logicalAnd.

logicalAnd :: Bool -> Bool -> Bool
logicalAnd True x = x
logicalAnd False x = False

This function works with two reduction rules: one for True as the first argument, and one for False as the first argument, as shown in Figure 4-8.

Figure 4-8. Reduction rules for logicalAnd function

The logicalAnd ('x' == 'y') ('a' == 'b') expression is represented in Figure 4-9.

Figure 4-9. Evaluation of logicalAnd ('x' == 'y') ('a' == 'b')

The parameters of the function are redexes. The first parameter of the function verifies if the first argument fits the True constructor. So, the next step in lazy evaluation is to reduce the first parameter, as shown in Figure 4-10.

Figure 4-10. Lazy evaluation and reducing rules

The last argument is no longer verified, because we already achieved a redex. Lazy evaluation always tries to reduce the topmost node; so, using the definition of logicalAnd, we obtain False, as shown in Figure 4-11.

Figure 4-11. The final result for logicalAnd ('x' == 'y') ('a' == 'b')

This is in normal form, so the reduction process stops, and the result is obtained.

Parallel Strategies in Haskell

In Haskell, there are many techniques for deterministic parallelism. The Strategies library supplies methods for controlling granularity through chunking, assessment control, and sparking.

The spark represents the smallest unity of work in the Haskell runtime system. It binds to a thunk that can be evaluated. The runtime system procedure choses sparks from a circular buffer, called a spark pool, when runnable threads do not exist. Even if the sparks are not evaluated, the computation will not become stuck. The normal schedule flow does not wait for a spark that remained unevaluated, because its evaluation is ongoing. Because Haskell uses lazy evaluation, operations on lists do not require that to evaluate the whole list. The Strategies library allows you to indicate the level of evaluation expected for the input.

It is not necessary to compile programs with the -threaded flag. The GHC runtime system could provide data about logging details of inner events. This could be combined with a good profiling tool, such as ThreadedScope. Let’s compile a program using these options:

ghc --make -threaded -eventlog -rtsopts -O2 myprogram.hs

eventlog is used for profiling events and rtsopts sets runtime options.

Let’s take the Fibonacci example and write it in three different ways.

nfibo :: Integer -> Integer
nfibo n | n < 2 = 1
nfibo n = nfibo (n-1) + nfibo (n-2)

-- The version using Eval monad
efibo :: Integer -> Integer
efibo n | n < 2 = 1
efibo n = runEval $ do
        nf1 <- rpar (efibo(n-1))
        nf2 <- rpar (efibo(n-2))
        return (nf1 + nf2)

-- The version using Strategy
sfibo :: Integer -> Integer
sfibo n | n < 2 = 1
sfibo n = withStrategy strat nf1 + nf2
        where nf1 = nfibo(n-1)
                   nf2 = nfibo(n-2)
                   strat v = do rpar nf1; rse1 nf2; return v

The Eval monad and Strategies are very close. Strategies performs a more powerful abstraction for easing the issues that come from regulating granularity. It forces the evaluation to be made by the user.

type Strategy a = a -> Eval a

using :: a -> Strategy a -> a
x `using` s = runEval (s x)
withStrategy :: Strategy a -> a -> a ->a
withStrategy s x = runEval (s x)

In the preceding code, using and withStrategies are logically the same. They provide syntactic sugar. The Strategies library could be considered an extension of the Eval monad, which has syntactic sugar and control over evaluation orderliness.

In the preceding Fibonacci function implementation, it is difficult to determine how sfib will be executed, because the rpar strategy does not provide any guarantee for the evaluation process; it is used to alert the runtime system to first deal with the thunks if runnable threads that need to be scheduled do not exist.

scanP :: (Num a, NFData a) => Int -> (a -> a -> a) -> [a] -> [a]
scanP d f list = concat reducedList
        where
             scanList = map (scanl1 f) (chunk d list) `using` parList rdeepseq
             reducedList = reduce f scanList
             strat v = do rpar reducedList; return v

reduce :: (a-> a -> a) -> [[a]] -> [[a]]
reduce f [ ] = [ ]
reduce f x:[ ] = [x]
reduce f x:y:xs= x : reduce f (map (f $ last x) y : xs)

chunk :: Int -> [a] -> [[a]]
chunk _ [ ] = [ ]
chunk n xs = as : chunk n bs where (as, bs) = splitAt n xs

x `using` s = runEval ( s x)
parList :: Strategy a -> Strategy [a]

scanList = map (scanl1 f) (chunk d list) `using` parListChunk 4 rdeepseq

evalList :: Strategy a -> Strategy [a]

divConq :: (a -> b)
        -> a
        -> (a -> Bool)
        -> (b -> b -> b)
        -> (a -> Maybe (a,a))
        -> b
divConq f arg threshold combine divide = go arg
        where
                go arg =
                        case (divide arg) of
                           Nothing -> f arg
                           Just (l0, r0) -> combine l1 r1 `using` strat
                                where l1 = go l0
                                           r1 = go r0
                                     strat x = do r l1; r r1; return x
                                     r | threshold arg = rseq
                                               | otherwise = rpar

sort :: Ord a => [a] -> [a] -> [a]
sort [ ] yl = yl
sort xl [ ] = xl
sort xl@(x:xs) yl@(y:ys)
        | x <= y = x : sort xs yl
        | x > y = y : sort xl ys

mergeSort :: Ord a => [a] -> [a]
mergeSort [ ] = [ ]
mergeSort [x] = [x]
mergeSort xs = sort (mergeSort xs1) (mergeSort xs2)
        where (xs1, xs2) = splitAt (length xs `div` 2) xs

mergeSort_dc :: Ord a => Int -> [a] -> [a]
mergeSort_dc thres xs = divConq f xs threshold combine divide
        where
            f :: Ord a => [a] -> [a]
            f x = x
            threshold :: [a] -> Bool
            threshold x = length x < thres
            combine x1 x2 = sort x1 x2
            divide :: [a] -> Maybe ([a], [a])
            divide x = case (splitAt (length x `div` 2) x) of
                        ([ ], x2) -> Nothing
                        (x1, [ ]) -> Nothing
                        res -> Just res

Summary

This chapter covered the main strategies used in the evaluation process, including the following topics:

• Redexes and lazy evaluation

• The smaller units at work during the Haskell runtime system

• Scan functions

• Skeletons for the high level of abstraction in distributed computation patterns