λ Tony’s blog λ

A Fling with Lazy Evaluation

Lazy evaluation is a core topic in computer programming that is also widely misunderstood and often, erroneously trivialised. Here, I will attempt to demonstrate some of the attributes of many common mainstream programming languages; namely strict programming languages. I will also attempt to distinguish intrinsically strict languages from optionally lazy languages by focusing on what intrinsically strict means. As a note, strict evaluation (or strictness) is what lazy evaluation (or laziness) is not.

Some languages are optionally lazy, including one that I use quite a lot in my work called Scala. This means I have the option of laziness, however, the default in all cases is strictness. I have to explicitly annotate laziness (=> in Scala). Some languages are optionally strict; one that I use a lot is Haskell. Laziness is the default, while strictness is explicitly annotated (seq or ! in Haskell). There are many debates about which is the correct default, but whatever the outcome of such a debate, the issue I describe next is one that demands much more attention.

Some languages are forcibly strict. It is these languages that I intend to focus on for the remainder of this post. I assume that my reader either understands or is at least open to just how debilitating a language is that does not support user-defined lazy evaluation in any form whatsoever. I will explicitly discuss the Java programming language, though what I describe is equally applicable to C, C# and many other languages.

In Java, the only lazy constructs are:

if/else
while
for
? : (ternary operator)
&&
||

This is extremely limiting. To make the case clear, I will focus on a particular example of this. Consider the && function of type (Boolean x Boolean) -> Boolean. Here is a profound assertion:

It is impossible to write && in Java yourself.

Some of you might be quick to rebut:

// Sure I can!
boolean and(boolean b, boolean c) {
  return b && c;
}

This is a very crucial and amateur mistake as you will soon see.

Since the domain of the && function is so small, there is room enough to enumerate it below:

a   b   a && b
t   t   t
t   f   f
f   t   f
f   f   f
t   ⊥   ⊥
⊥   t   ⊥
f   ⊥   f
⊥   f   ⊥

Wait just a minute!! What are those last 4 entries in the table and just WTF is that upside-down T doing!? That upside-down T represents what is called the bottom element, sometimes also written as _|_ when only ASCII is available. It is an extremely important part of the && function (and all functions in fact!). In Java, the bottom element is typically represented by throwing an exception (or sometimes, with null).

Remember, two functions are equivalent if for every element of the domain, the result of function application to that element on either function is equivalent. Here is a more formal definition for function equivalence:

Two functions, f and g, are equivalent if the following property holds:
∀ x. f x ⇔ g x

We could rewrite the + function for int as follows:

int sum(int a, int b) {
  return a + b;
}

I won’t list out the table for each element in the domain of +, since it is so long, so you’ll either have to do it yourself, or take my word for it that the sum function above is equivalent to +

However, why can’t we rewrite &&? If we look at the table for && above and select the penultimate entry, we note the following:

false && ⊥ == false

It is this entry that disallows us from rewriting &&. Look at the following function:

boolean bottom() {
  throw new Error();
}

What is the result of false && bottom()? It is false of course! This is because && is lazy in its second argument (sometimes; specifically, when the first argument is false). This is impossible to emulate in your own Java function. If we take the earlier function that attempted (but failed) to rewrite && and call:

and(false, bottom())

The result of this function is ⊥ and not false, like it is with &&. Therefore, this function is not equivalent to &&. Further, I restate that it is not possible to write such a function in these languages. Unlike +. which is strict in both of its arguments, && is not and this makes it impossible to write a user-defined version of && and therefore, ||, if/else and ?: and importantly, many other potential functions that many Java programmers are probably not even aware of (Dynamic Programming Algorithms anyone?).

If you are ever forced to use these severely limited programming languages, you could be thankful that you have some primitive lazy constructs for doing very primitive operations (oppression), or you could be resentful for not having the expressive power of other, lazy languages (resistance against oppression)

Below is a session with my Scala interpreter to demonstrate that it is indeed possible to write && in Scala (lazyAnd), but not Java. Note that the functions (def declarations) and final variables (val declarations) below are Java functions and final variables all running in a JVM (invoked by the Scala interpreter):

scala> val x = false && error("bottom")
x: Boolean = false

scala> def and(a: Boolean, b: Boolean) = a && b
and: (Boolean,Boolean)Boolean

scala> val y = and(false, error("bottom"))
java.lang.Error: bottom

scala> def lazyAnd(a: Boolean, b: => Boolean) = a && b // can't do this in Java, C#, C, etc.
lazyAnd: (Boolean,=> Boolean)Boolean

scala> val z = lazyAnd(false, error("bottom"))
z: Boolean = false

This entry was posted on Tuesday, September 4th, 2007 at 11:13 am and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

9 Responses to “A Fling with Lazy Evaluation”

Josef Svenningsson Says:
September 4th, 2007 at 8:40 pm
While and for loops are also lazy constructs.

Apart from that, thanks for bringing up an important point.
Sohail Says:
September 5th, 2007 at 1:33 am
Awesome. That is just plain awesome.
Lionel Barret Says:
September 5th, 2007 at 5:18 am
Good point, but you could use a more complex example like Simon Peyton-Jones did in his video. I think it was a best move algo for a chess program : the possible position tree is too big to be completely evaluated before applying the scoring function for each position, so the tree is a lazy iterator.
Hey! by the way, (python) iterators are another good example !
Anyway, excellent introduction to a important topic.

( note you could have explained the + equivalence with a nice recursion.)
John "Z-Bo" Zabroski Says:
September 5th, 2007 at 7:41 am
I agree with Lionel Barret about the + equivalence. That was the only weak point of an otherwise excellent post.

I’d like to see you expand this further by mentioning imperative programming and how this can be used to describe more precise or perhaps more intricate imperative knowledge. Doing so would tie up the last discussion we had nicely and also be a good way to introduce really powerful control structures like continuations - think about it.
FeepingCreature Says:
September 5th, 2007 at 8:22 am
D supports lazy evaluation of function parameters.
Just sayin’
The Java example expressed in D with lazy eval would be

__bool and(lazy bool b, lazy bool c) { return b && c; }

Or a slightly more powerful version

__// takes an arbitrary number of lazy arguments
__bool and(bool delegate()[] dgs…) {
____assert(dgs.length);
____foreach (dg; dgs) if (!dg()) return false;
____return true;
__}
(The underscores are just indentation)

We can demonstrate that it works by means of the following example:

__import std.stdio;
__bool bottom() {
____throw new Exception(”You hit rock bottom”);
__}
__void main() { writefln(and(false, bottom)); }

which, correctly, outputs “false”.
Ricky Clarkson Says:
September 7th, 2007 at 10:47 pm
Another way of thinking about it is that lazy languages make each expression (and each part of each expression) like a lambda expression in a strict language. More accurately a memoised lambda expression, like Common Lisp’s force and delay.

You could write your own && in Java, but it would be called with lambdas rather than the same way && is. Here’s a sample call:

boolean b=myAnd(new Lazyb()
{
    public boolean invoke()
    {
        return false;
    }
},new Lazyb()
{
    public boolean invoke()
    {
        throw new Error();
    }
});

or, in the hypothetical Java 7:

boolean b=myAnd({=>false},{=>throw new Error()});

Brad Clow Says:
September 20th, 2007 at 1:44 pm

It can be done by introducing your own Boolean type:

public final class Test {
    private static final MyBool TRUE;
    private static final MyBool FALSE;
    private static final MyBool BOTTOM;

    static {
        TRUE = new MyBool() {
            public boolean myBool() {
                return true;
            }
        };

        FALSE = new MyBool() {
            public boolean myBool() {
                return false;
            }
        };

        BOTTOM = new MyBool() {
            public boolean myBool() {
                throw new Error();
            }
        };
    }

    public static void main(String[] args) {
        System.out.println(and(TRUE, TRUE));
        System.out.println(and(FALSE, TRUE));
        System.out.println(and(FALSE, BOTTOM));
    }

    static boolean and(MyBool b, MyBool c) {
        if (b.myBool()) {
            return c.myBool() ? true : false;
        } else {
            return false;
        }
    }

    private interface MyBool {
        boolean myBool();
    }
}

As Tony pointed out to me, you can rename MyBool to Thunk and add a type parameter (which in this case would be Boolean).

Anonymous Coward Says:
October 21st, 2007 at 2:01 pm
I’m not sure “Dynamic Programming” means what you think it means. I’ve implemented a great many DP algorithms. Can you tell me exactly what problem Java poses to implement the DP 0-1 Knapsack. The “0-1 Knapsack” is one of the ultimate DP algo. Another famous DP algo is, say, the “Levenhstein edit distance”… And I happen to also have implemented this one perfectly fine in Java.

I think you want to open Wikipedia at “dynamic programming”.

“dynamic programming algorithm” != “an algorithm written in a dynamic programming language”

If you’re really talking about dynamic programming algorithms, then I’d like you to cite at least of the famous DP algo that would be problematic to write in Java…

DP algorithms like 0-1 Knapsack and Levenhstein have been known as “dynamic programming” since decades. So I think “dynamic programming algorithm” doesn’t mean what you think it means.

Besides that your blog is interesting but it’s all hair-splitting at the 3GL level. Anyone at least half interested in OOA/OOD can only but laugh at all this nitpicking.
Tony Morris Says:
October 21st, 2007 at 6:59 pm
Hi Anonymous Coward,
I know what Dynamic Programming means. I’d just *love* to see your Levenshtein Distance written in Java
Here’s mine in Scala:
http://tinyurl.com/ywuk86

You will note that its essence is 5 lines of code. Again, I await your Java solution
You think this is nitpicking? First, it has *nothing* at all to do with OOA/OOD and neither does Java for that matter. I only just had a whinge recently about passing under-qualified comment and the topic was “OO” (how about that?), so I best refrain for now for my own sanity. Interestingly, Wadler’s type-classes came up in that discussion; have you heard of them before? I find that they are a good place to start a discussion and meaningful critique of OO. Certainly, Java and its offensive type system isn’t.

Good luck with that Levenshtein Distance without laziness!!

A Fling with Lazy Evaluation

9 Responses to “A Fling with Lazy Evaluation”

Leave a Reply