More points for lazy evaluation

In a recent blog post Bob Harper shows one use of laziness, but I think he misses the real import points of laziness. So I will briefly enumerate what I think are the important points of lazyness (excuse me for not coming up with any kind of pun about points).

First, I'd like to say that I don't think strict or lazy matters that much in practice; they both work fine. I have programmed in regular non-strict Haskell as well as strict Haskell, and most things carry over well to a strict Haskell.  Furthermore, when I say strict language I mean a strict language with at least non-termination as an effect; total languages is another matter.

Lazy bindings

I like to tell Haskell beginners that any subexpression can be named and "pulled out", modulo name capture, of course. For instance

    ... e ...

is the same as

    let x = e
    in  ... x ...

The key thing is that

    ... e ... e ...

is the same as

    let x = e
    in  ... x ... x ...

so that common subexpressions can be given a name.

This is (in general) just wrong in a strict language, of course. Just take the simple example

    if c then error "BOO!" else 0

Which is not the same as

    let x = error "BOO!"
    in  if c then x else 0

In this case you can easily fix the problem by delaying the computation with a lambda (a common theme).

    let x () = error "BOO!"
    in  if c then x () else 0

But for a slightly more complicated example this simple technique goes wrong. Consider

    map (\ a -> a + expensive) xs

where expensive does not depend on a. In this case you want to move the expensive computation out of the loop (cf. loop invariant code motion in imperative languages). Like so

    let x = expensive
    in  map (\ a -> a + x) xs

In a lazy language x will be evaluated exactly zero times or once, just as we want. Using the delaying trick doesn't work here:

    let x () = expensive
    in  map (\ a -> a + x ()) xs

since expensive will get evaluated once for every list element.

This is easy enough to remedy, by introducing an abstraction for lazy computations (which will contain an assignment to compute the value just once). The signature for the abstract type of lazy values is something like

    data Lazy a
    delay :: (() -> a) -> Lazy a
    force :: Lazy a -> a

Note that the delay needs to take a function to avoid the a being evaluated early.
(This is probably what Bob would name a benign effect and is easily programmed using unsafePerformIO, which means it needs careful consideration.)

And so we get

    let x = delay (\ () -> expensive)
    in  map (\ a -> a + force x) xs

This isn't exactly pretty, but it works fine. In a language with macros the ugliness can be hidden better.

Lazy functions

Even strict languages like ML and C have some lazy functions even if they don't call them that, like SML's if, andthen, and orelse. You really need the if construct to evaluate the condition and then one of the branches depending on the condition. But what if I want to define my own type with the same kind of functions? In ML I can't, in C I would have to use a macro.

The ability to define new functions that can be used as control constructs is especially important when you want to design embedded domain specific languages. Take the simple example of the when (i.e., one-arm if) function in Haskell.

    when :: (Monad m) => Bool -> m () -> m ()

A quite common use of this function in monadic code is to check for argument preconditions in a function, like

    f x = do
        when (x < 0) $
            error "x must be >= 0"
        ...

If the when function is strict this is really bad, of course, since the call to error will happen before the when is called.

Again, one can work around this by using lazy values, like

    myAnd :: MyBool -> Lazy MyBool -> MyBool
    ...
    ... myAnd x (delay (\ () -> y)) ...

But in my opinion, this is too ugly to even consider. The intent of the function is obscured by the extra noise to make the second argument lazy.

I think every language needs a mechanism for defining some form of call-by-name functions. And many languages have this in the form of macros (maybe built in like in Lisp, or as a preprocessor like C).
If a language cannot define lazy function it simply lacks in abstraction power. I think any kind of fragment of the language should be nameable and reusable. (Haskell lacks this ability for patterns and contexts; a wart in the design.) So if you notice a repeated expression pattern, like

    if c then t else False

and cannot give this a name, like

    and c t = if c then t else False

and then use it with the same effect as the orginal expression, well, then your language is lacking.

For some language constructs the solution adopted by Smalltalk (and later Ruby), i.e., a very lightweight way on constructing closures is acceptable. So, for instance, I could accept writing

    ... myAnd x {y} ...

(In SML you could make something using functors, but it's just too ugly to contemplate.)

Lazy constructors

Lazy constructors were sort of covered in what Bob claimed to be the point of laziness, so I'll just mention them for completeness.  Sometimes you need them, but in my experience it's not very often.

Cyclic data structures

This is related to the last point.

Sometimes you really want cyclic data structures. An example are the Haskell data types in Data.Data that describe data types and constructors. A data type descriptor needs to contain a list of its constructors and a constructor descriptor needs to contain the data type descriptor.
In Haskell this can be described very naturally by having the two descriptors reference each other.
In SML this is not possible. You will have to break the cycle by somthing like a reference (or a function).
In OCaml you can define cyclic data structures in a similar fashion to Haskell, so this isn't really a problem with strict languages, but rather a feature that you can have if you like. Of course, being able to define cyclic data leads to non-standard elements in your data types, like

    data Nat = Zero | Succ Zero
    omega :: Nat
    omega = Succ omega

So having the ability to define cyclic data structures is a double edged sword.
I find the lack of a simple way to define cyclic data a minor nuisance only.

Reuse

I've saved my biggest gripe of strict evaluation for last. Strict evaluation is fundamentally flawed for function reuse.
What do I mean? I will illustrate with and example.
Consider the any function is Haskell:

any :: (a -> Bool) -> [a] -> Bool
any p = or . map p

It's quite natural to express the any function by reusing the
map and or functions.  Unfortunately, it doesn't
behave like we would wish in a strict language.  The any function should scan the list from the head forwards and as soon as an
element that fulfills the predicate is found it should return true and stop
scanning the list.  In a strict language this would not happen, since
the predicate will be applied to every element before the or
examines the elements.

So we are forced to manually fuse the two functions, doing so we get:

any :: (a -> Bool) -> [a] -> Bool
any p = foldr False (\ x r -> p x || r)

or :: [Bool] -> Bool
or = foldr False (||)



foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

But the misery doesn't end here. This still doesn't do the right thing, because the strict language will recurse all the way down the list since it will call foldr before f. So we either have to fuse again, or invent a new version of foldr that delays the recursive call.
One more fusion gets us to

any p []     = False
any p (y:ys) = y || any p ys

So where's the function reuse? Nowhere in sight.

With strict evaluation you can no longer with a straight face tell people: don't use recursion, reuse the recursion patterns in map, filter, foldr, etc. It simply doesn't work (in general).

Using macros doesn't really save us this time, because of the recursive definitions. I don't really know of any way to fix this problem short of making all (most?) functions lazy, because the problem is pervasive.  I.e., in the example it would not be enough to fix foldr; all the functions involved need to be lazy to get the desired semantics.

I find this the biggest annoyance with strict evaluation, but at the same time it's just an annoyance, because you can always rewrite the code to make it work. But strict evaluation really, fundamentally stops you from reusing functions the way you can with laziness.

As an aside, the definition of any doesn't work in SML for another reason as well, namely the value restriction. But that's just a language wart, like the monomorphism restriction in Haskell.

Complexity

Another complaint Bob Harper had about lazy evaluation is the difficulty of finding out the complexity of functions. I totally agree that the space complexity is very messy in a lazy language. For (sequential) time complexity I don't see any need to worry.
If strict a function has O(f(n)) complexity in a strict language then it has complexity O(f(n)) in a lazy language as well.  Why worry? :)

Summing up

One of the most important principles in all software design is DRY, i.e., Don't Repeat Yourself. This means that common patterns that we can find in a program should be abstractable so you can reuse them. In a lazy language you can use functions for abstracting control structures, which a strict language does not permit (at least not in a convenient way). This can be mitigated by providing some other abstraction mechanism, like macros (hopefully some kind of sane macros).
For the reasons above, I find it more convenient to program in a lazy language than a strict one. But a strict language with the ability to define lazy bindings, lazy functions, and lazy constructors is good enough that I find it usable.