Java
Article

In Praise of Laziness

By Pierre-Yves Saumont

I’m lazy. But it’s the lazy people who invented the wheel and the bicycle because they didn’t like walking or carrying things. – Lech Walesa

Laziness is the mother of all bad habits. But ultimately she’s a mother and we should respect her. ― Shikamaru Nara

In everyday life, laziness is generally seen as a bad habit that has to be fought, or even as an illness that must be cured. But whether you consider laziness as good or bad, you might agree that laziness consists merely in trying to get the most from the least effort. This means avoiding useless efforts. One way to reach this goal is procrastination, which consists of not doing anything before it’s really necessary. This is what laziness is about in computing. Some will argue that procrastination is about not doing anything even when it has become truly necessary. In computing, this would simply be called a bug.

What Is Laziness?

In programming, laziness is most often related to the way things are evaluated. Lazy evaluation means delaying a computation until the result is needed, and that’s to be opposed to eager evaluation. Languages that use lazy evaluation are said to be lazy languages. Languages that evaluate things eagerly are called strict languages.

Some languages are lazy, others are strict. Some are strict by default and optionally lazy, while others are… well, the opposite. Java is said to be a strict language. But what does that mean?

When we say that Java is a strict language, it’s generally in a very specific context: Java is strict in evaluating references and method arguments, which means that references and method arguments are eagerly evaluated.

Lets take an example. If you write int x = 5 it causes the literal value 5 to be referenced by the name x. It’s sometimes said that the value 5 is stored in the variable x, by analogy with the way it’s done by computers, which will store some data representing 5 in some location represented by x. Note however that writing the line above does not store 5 in x as long as the program is not executed. More on this later.

So it seems to be clear that the data on the right of the equal sign is referenced by the name on the left of this sign. However, if we write int x = 2 + 3 it doesn’t cause 2 + 3, which is an operation, to be referenced by the variable x. Instead, x will reference the result of the operation.

This is the difference between being lazy and being strict, or the difference between lazy evaluation and eager evaluation. With eager evaluation, the expression on the right of the equal sign is first computed, and the result is then referenced by the name on the left.

Consider the following Java program:

public static void main(String... args) {
    int x = 2 + 3;
    int y = 18 / 2;
    System.out.println(y);
}

Having computed the value of x is completely useless, since this value is not used anywhere. If Java was a lazy language, it would only have computed y, and this would have happened as the result of executing the println method.

So, Java is strict, meaning that it evaluates things eagerly, and this is true, among other things, for variables and method arguments. This can be shown by another little example:

public static void main(String... args) {
    displayMessage(getLocalizedMessage(), getDefaultMessage());
}

private static void displayMessage(
        String localizedMessage, String defaultMessage) {
    if (localizedMessage != null && localizedMessage.length() != 0) {
        System.out.println(localizedMessage);
    } else {
        System.out.println(defaultMessage);
    }
}

private static String getDefaultMessage() {
    System.out.println("Evaluating default message");
    return "Bye!";
}

private static String getLocalizedMessage() {
    System.out.println("Evaluating localized message");
    return "Ciao!";
}

Running this program displays:

Evaluating localized message
Evaluating default message
Ciao!

This shows that, although the defaultMessage parameter is not used, it has been evaluated, resulting in a call to getDefaultMessage(). So Java is a strict language.

Or is it?

Different Types of Laziness

Laziness may be implemented at the language level. A lazy language will simply evaluate something only when it is needed. This might have some consequences if evaluation depends upon external conditions. If the expression to evaluate is referentially transparent, which means that it does not depend upon something that is external and might hence not change over time, evaluation will give the same result at any time. In this case lazy evaluation will not change the outcome of the program.

This is of course the case for something like int x = 2 + 3 but what about int x = getValue(y)? The getValue() method could access the network to get the value. The network connection could be available at some time and not at others. Or it could read the result of some other computation that might be changed by another thread.

The consequence is that lazy evaluation itself is only referentially transparent if the expression to evaluate is referentially transparent. In this example, it means that the value returned by the getValue() method should only depend on its argument y. (This is a simplification, since it could also depend on some immutable external data.)

But beside language laziness, you can also encounter type laziness, as in the following Java example:

Supplier x = () -> getValue(y);

Here, x is eagerly evaluated to an object of type Supplier<Integer>, but the getValue method is not called until we need its result and get it by calling Supplier.get.

So, it’s clear that beside the fact that the language can be lazy or strict, we may still benefit from laziness by using lazy types. The main difference will be that, with a lazy language, a lazy A will be an A, whereas in a strict language, a lazy A will have another type, not related to A (in the sense that we will not be able to assign a lazy A value to a reference of type A).

Why ALL Languages Are Lazy

So it’s clear that Java is a strict language, although we are able to implement laziness in types. But is Java really strict? Let’s look at the displayMessage method implementation:

if (localizedMessage != null && localizedMessage.length() != 0) {
    System.out.println(localizedMessage);
} else {
    System.out.println(defaultMessage);
}

Obviously, the first branch of the conditional if..else instruction has been evaluated, resulting in the localized message being printed to the console, but the second branch has not. This is fortunate, since we could not do anything with a language that would always evaluate both branches of a conditional instruction. And this is possible because if..else is a lazy construct that evaluates only the necessary branch.

So Java is not a “strict” language. It is a language that is strict in some domains, and lazy in others. And all languages are lazy in some domains, because this is the essence of programming: A program is a lazy construct that is evaluated when you run it. Without laziness, there would be no possible programming.

This is also true in everyday life. Without laziness, we couldn’t plan anything. When you write down a shopping list, although it’s a list of goods, it’s not evaluated. Imagine if you could not add an article to the list without immediately (“eagerly”) going to the store to buy it. This would be pretty inefficient.

So the list is in fact not a list of goods, but a program that will eventually produce a list of goods when evaluated. In the case of a list of ingredients to make a cake for a party, if the party is then canceled, you might never evaluate the list. This is laziness, and it is obviously a good habit to wait until you are sure things are really needed before evaluating them.

So Java does have laziness, after all.

When Is Java Lazy?

Java has several lazy constructs and operators. We already saw that the if ... else structure is lazy. In reality, it’s both strict and lazy. Consider the general form:

if (<condition>) {
    <branch 1>
} else {
    <branch 2>
}

You’ll see that the condition is always evaluated, but only one branch is. So we can say that if ... else is strict regarding its condition and lazy regarding the branches.

Other lazy Java constructs are the for and while loops, switch ... case and try ... catch ... finally. Like if ... else, these structures are strict regarding some elements and lazy regarding others.

Java also has a few lazy operators. They are the so called “short-circuiting” boolean operators && and || and the ternary operator ?:. Consider the following example:

String string = getString();
boolean condition = string != null && string.length() > 0;

Here, the length method will not be called if string is null because although the && operator is strict regarding its left argument, it is lazy regarding the right one.

Can you think of a way to implement the same thing with a method, such as:

String string = getString();
boolean condition = and(string != null, string.length() > 0);

boolean and(boolean condition1, boolean condition2) {
    // ?
}

Whatever the implementation of the and method, it will not work because Java is strict regarding method parameters, so both conditions will be evaluated even if condition1 is false, leading to a possible NullPointerException if string is null. The only way to implement such a method is to change the types:

String string = getString();
boolean condition = and(() -> string != null, () -> string.length() > 0);

boolean and(BooleanSupplier condition1, BooleanSupplier condition2) {
    if (condition1.getAsBoolean()) {
        if (condition2.getAsBoolean()) {
            return true;
        }
    }
    return false;
}

The Benefits of Laziness

Beside the necessity for all languages to be lazy in some way, lazy evaluation is needed in different cases. One is, as we just saw, when some combination of conditions might cause an error. In such cases, lazy evaluation of these conditions allows avoiding the error by not executing some part of the program. This is a pattern that is very often used (although probably not often enough) to test for null or for some other condition before using data.

Another use case of laziness is to save execution time and processing resources. We generally want to execute only the relevant parts of the program, depending on some conditions. This is what most control structures are for. If we eventually don’t need a value, why should we spend time and processor resources to evaluate it?

Another area where laziness is useful is to free our programs from effects. This is a very important point in functional programming, but it is also used in other paradigms. In functional programming, we try to completely separate effects (meaning interaction with the outside world) from the rest of the program. The reason for this is that programs without effects are easier to design, easier to test, and safer, because they are deterministic.

The Costs of Laziness

Whether laziness is implemented at the language level or at the type level, there’s still a choice to be made about when exactly evaluation of a lazy expression will occur. If laziness is implemented at the language level, it’s a choice for the language designer. If it is at type level, it’s a choice for the type designer, meaning the programmer.

We’ve seen that lazy evaluation will occur only when the value is needed. This is in contrast with what Java does, for example by evaluating arguments as soon as they are received by a method.

Consider the following example:

public static void main(String... args) {
    display(createMessage("Bob"), true);
    display(createMessage("Mark"), false);
}

private static void display(String message, boolean condition) {
    if (condition) {
        System.out.println(message);
    } else {
        System.out.println("Hi!");
    }
}

private static String createMessage(String name) {
    System.out.println("Creating message for " + name);
    return "Hello, " + name;
}

This example will print:

Creating message for Bob
Hello, Bob
Creating message for Mark
Hi!

What we observe is that due to eager evaluation, the message for Bob is computed although the value is not used. So the following program, using type laziness, is more efficient:

public static void main(String... args) {
    display(() -> createMessage("Bob"), true);
    display(() -> createMessage("Mark"), false);
}

private static void display(Supplier<String> message, boolean condition) {
    if (condition) {
        System.out.println(message.get());
    } else {
        System.out.println("Hi!");
    }
}

private static String createMessage(String name) {
    System.out.println("Creating message for " + name);
    return "Hello, " + name;
}

We can verify, by running the program, that it does not create the message if it’s not used. On the other hand, we may have the inverse result (in terms of efficiency) it the value is used several times:

public static void main(String... args) {
    display(() -> createMessage("Bob"), true);
    display(() -> createMessage("Mark"), false);
}

private static void display(Supplier<String> message, boolean condition) {
    if (condition) {
        System.out.println(message.get());
        System.out.println(message.get());
        System.out.println(message.get());
    } else {
        System.out.println("Hi!");
        System.out.println("Hi!");
        System.out.println("Hi!");
    }
}

private static String createMessage(String name) {
    System.out.println("Creating message for " + name);
    return "Hello, " + name;
}

Now, the result is as follows:

Creating message for Bob
Hello, Bob
Creating message for Bob
Hello, Bob
Creating message for Bob
Hello, Bob
Hi!
Hi!
Hi!

This shows that the message is constructed again each time it is used. This example uses what is called call by name evaluation, which means that the value is not evaluated before being needed, but it’s evaluated each time it’s needed.

Of course, since we are using type laziness and are in fact implementing laziness ourselves, it’s easy to solve this problem by storing the evaluated value so that it’ll be evaluated only once:

private static void display(Supplier<String> message, boolean condition) {
    if (condition) {
        String evaluatedMessage = message.get();
        System.out.println(evaluatedMessage);
        System.out.println(evaluatedMessage);
        System.out.println(evaluatedMessage);
    } else {
        // [...]
    }
}

But we might prefer that this process be abstracted into the lazy type. This means that we would have to create our own type rather than use the standard Java 8 Supplier interface. Supposing we would call this type Lazy<T>, we would use it somewhat like this:

display(new Lazy<>(() -> createMessage("Bob")), true);

If well implemented, it would evaluate the message only on the first call. This type of evaluation is known as call by need evaluation, and it’s similar to the function optimizing technique known as memoization, in which a function computes the value corresponding to its argument the first time the argument value is encountered and stores it in a cache in order to be able to much faster serve it from the cache the next time it’s needed.

Note that call by need evaluation also has some drawbacks. As always, it’s a matter of trading some resource for another. Here, it’s trading memory space for processing time. But unlike function memoization, we have only one value to cache, so cache invalidation (which is a huge domain with its own multiple problems) is generally not needed.

Another drawback of call by need that’s generally stressed is that it might change the result of the program if this result depends upon some side effect of the evaluation. This change may be irrelevant if the side effect is not part of the “business” result of the program, for example if it’s logging or counting the number of accesses to a method. But it could be a more “business” side effect, like sending a message to a progress bar, thus modifying the overall outcome of the evaluation.

This is however not a concern for us if we are involved in functional programming, since in functional programming, functions and effects are never mixed. In fact, pure functional programs are organized in such a way that effects occur outside of the program.

Laziness may also affect the outcome of programs relying upon shared mutable state since it might cause the executing thread to run faster, changing the access order to mutable state. Once again, this is not a concern for functional programs, since functional programs does not share mutable state in a way that could change the program outcome.

But the main problem with call by need is when the value should change on each call. This is obviously not the case for an expression value assigned to a reference, but it could be for a recursive method call, where the value might change for each step. With lazy call by need evaluation, the argument would be evaluated on the first step and would not be reevaluated on each subsequent recursive step. If the condition to stop recursion was based upon the value of this argument, recursion would never cleanly stop.

Making the Impossible Possible

We’ve seen that laziness may be used to make programs more efficient by avoiding useless computations. On some occasions, it may even make possible some computations that would not be possible otherwise because they would never terminate.

Consider, for example, the following program:

  • take the list of positive integers
  • filter the primes
  • take the first hundred elements and display the result to the console.

This program would display the first hundred prime numbers. Without laziness, this would be impossible because the second step would never finish since the list of positive integers is infinite. And without a lazy representation of “the list of positive integers” the first step would not mean anything computable either.

Obviously, we would not only need a powerful implementation of lazy scalar types (for lazily operating on single values), but also lazy vectorial types (or lazy collections; for operating on a multitude of values). This will be the subject of a future article.

Summary

We explored how laziness applies to programming languages:

  • Strict languages evaluate things when they are declared; lazy languages evaluate things when they are used.
  • All programming languages are lazy in some way, because some parts of programs are not evaluated, depending on some conditions.
  • Java is said to be a strict languages because it evaluates references and method arguments as soon as the are declared, even if they are not used.

Then we uncovered some deeper truths regarding laziness:

  • Laziness may be implemented at the language level (by languages designers) or at the type level (by the programmer).
  • Referential transparency is very important when laziness is involved, because it guarantees that the result of expression evaluation will be the same whenever this evaluation occurs.
  • Lazy evaluation may happen each time the expression value is used (call by name) or only the first time, the result being cached to be reused if needed again (call by need)
  • Laziness saves processing resource when the value of some expression is not needed. On the other hand, it might cost some additional processing resources if is implemented as call by name and some values are needed several times. Laziness also makes possible to handle infinite collections of data.
  • zephyrus

    Very cool article!
    Thank you!

Recommended
Sponsors
Get the latest in Java, once a week, for free.