Java

Lazy Computations in Java with a Lazy Type

    Pierre-Yves Saumont
    Share

    Table of Contents

    I chose a lazy person to do a hard job.
    Because a lazy person will find an easy way to do it.     ― Bill Gates

    Java is said to be a strict language, which means that expressions are evaluated eagerly, as soon as they are declared, by opposition with lazy languages in which expression are evaluated only when their value is needed. The difference is important because some expression values may never be needed, depending on some conditions.

    Lazy evaluation saves computing resources by avoiding unneeded computations. Laziness makes possible to manipulate data that would be impossible to use in computations, such as infinite lists, or finite data that would overflow the available memory, such as huge files. It’s then important to be able to use lazy evaluation even in languages that are strict by nature, like Java. In such languages, we need to learn how to implement lazy types, which is what we will do in this article.

    In a previous article, I explained what laziness means. I talked about where laziness may be implemented (at language level or at type level), and when evaluation would eventually occur. We saw that call by name causes evaluation to occur each time a value is needed, whereas call by need consists of evaluating the value on the first need and storing it in case it would be needed again later. We also saw that laziness allows saving processing resources in case a value would eventually not be needed. But there is more to it.

    Abstracting Computational Contexts

    Laziness is not only a pattern to save resources. It is a computational context that can be applied to any expression. In this sense, it is not to be opposed to strictness (the fact that evaluation is performed as soon as an expression is defined). It is to be opposed to expressions out of context. Expressions can be used out of context or in context. Of course, one could argue that all expressions are defined in the context of a program. So let’s say that some expressions may be defined in an additional context layer. And since all expressions are defined in the context of a program (as far as we are concerned), we will forget about this “top” context, and consider only the additional context layer.

    Laziness is a specific context. When an expression is put in this context, it simply means that it might not be already evaluated. And furthermore, putting it into this context prevents evaluation, until we need it to occur. Note that we might however put in laziness context an expression that is already evaluated. This would of course change nothing regarding evaluation, but it could be useful to combine expressions, as we will see soon.

    There are lots of other possible computational contexts. We could manipulate expressions which take a long time to evaluate. These expressions could be put in a different context in which evaluation would start immediately, but allowing us to manipulate them before evaluation completes. Or we could put expressions in a specific context allowing us to deal transparently with error conditions. In such a context, an expression would be evaluated either to its result or to an error. But what about an evaluation that would take a long time and might produce an error? Well, we could define a specific context for this, but we might better compose the two former contexts. Composing contexts of different types is an interesting problem. But for the moment, we will only consider composing several instances of the same context, meaning composing laziness. But before looking at this, we must first implement type laziness.

    A Simple Approach to Type Laziness

    Programmers have always known how to implement a minimal amount of laziness where they needed it. The simplest way to implement a lazy property is probably the following:

    private String message;

public String getMessage() {
    if (message == null) {
        message = constructMessage();
    }
    return message;
}

    In this example, the message property is lazily evaluated the first time we call its getter. The constructMessage method is “lazily” called, but this is not because of the method call itself, but because it happens in an if conditional structure, which is lazy. Unfortunately, we can’t use this technique for method arguments because as soon as we will use the message property as a method argument, it will be evaluated, even if we do not use the value:

    public String message;

public String getMessage() {
    if (message == null) {
        message = constructMessage();
    }
    return message;
}

private String constructMessage() {
    System.out.println("Evaluating message");
    return "Message";
}

public void doNothingWith(String string) {
    // do nothing
}

public void testLaziness() {
    doNothingWith(getMessage());
}

    This example will print Evaluating message on the console, although we never use the resulting value. Can we do better?

    Using an Existing Type

    Yes, we can. We always could, but it is much easier now that we have lambdas and method references. Before Java 8, we could have written:

    public void doNothingWith(Supplier<String> string) {
    // do nothing
}

public void testLaziness() {
    doNothingWith((new Supplier<String>() {
        @Override
        public String get() {
            return getMessage();
        }
    }));
}

    Of course, since the Supplier interface did not exist, we would have had to create it, which is reasonably easy:

    public interface Supplier<T> {

    T get();

}

    With Java 8, we can use the standard java.util.function.Supplier interface and a lambda:

    public void testLaziness() {
    doNothingWith(() -> getMessage());
}

    Or better, we can replace the lambda with a method reference:

    public void testLaziness() {
    doNothingWith(this::getMessage);
}

    Note that these examples are not equivalent. Using an anonymous class will cause the creation of an instance of this class. On contrary, using a lambda will not cause the creation of an object, but only of a method. And if using a method reference, no method will even be created, since the referenced method will simply be called. This has some importance in terms of efficiency, but not only. The main consequence, from the programmer’s point of view, is that the this reference will refer to the anonymous class in the first case, and to the enclosing class in case of a lambda or a method reference.

    Composing Lazy Types

    The laziness we gain by using Supplier is useful, but we can make it much more powerful. Imagine we have two lazy strings that we want to concatenate:

    private String constructMessage(
        Supplier<String> greetings, Supplier<String> name) {
    return greetings.get() + name.get();
}

    What is the benefit of laziness if we are forced to evaluate expressions to compose them? If we know for sure that we will need the result of the composition, it makes sense to evaluate expressions before composing them. But we might want to compose two lazy expressions and get a lazy result. This means that we would want to compose to values in context without having to take them out of context. For this, we just have to wrap the composition in a new instance of the lazy context, which means a Supplier:

    private Supplier<String> constructMessage(
        Supplier<String> greetings, Supplier<String> name) {
    return () -> greetings.get() + name.get();
}

    Of course, we have to change the type of the returned value. Instead of returning the result of composing the values, we are returning a program that, when executed (meaning when Supplier.get() is called), will evaluate both strings and compose them to create the expected result. This is what laziness is: small programs wrapping expressions that will be evaluated when these programs are executed.

    Designing an Advanced Lazy Type

    This is a good start, since it’s already more powerful than simple laziness, but we can do much better. The Supplier interface can only delay evaluation until we call the get method. It does not allow, by itself, composing lazy values. And what if the get method throws an exception? And what if we want to apply a function to this lazy value without causing evaluation? We can handle all these problems externally, but since Java is an object oriented language, we should delegate this work to the lazy type itself. We can start with creating our own interface:

    @FunctionalInterface
public interface Lazy<A> {

    A get();

}

    We might want to be able to use our interface where a Supplier is expected. To make this possible, all we have to do is to extend Supplier:

    @FunctionalInterface
public interface Lazy<A> extends Supplier<A> { }

    Lazily Applying Functions

    As a first feature, we want to allow transforming the not-yet-evaluated value by lazily applying a function to the result of the evaluation. We will do this by creating a map method taking as its parameter the function we want to apply:

    default <B> Lazy<B> map(Function<A, B> f) {
    return () -> f.apply(get());
}

    We may have to deal with the possibility of an exception in the get method. We have several possibilities:

    • Rethrow the exception. We have not much to do for this, since it will automatically happen if we do nothing. It should be noted, though, that the exception can only be a RuntimeException, since the methods in the JDK’s functional interfaces can’t throw checked exceptions. So if evaluation throws a checked exception, we must either handle it in place or wrap it in an unchecked one before rethrowing. Throwing exceptions is however something we want to avoid in functional programming.

    • Return a special type indicating that an error as occurred. This could be an Optional<B>. The main drawback is that Optional can’t carry the exception. It only indicates that a value could have been present although it is not, but it can’t say why. We’ll see in a future article how to address this problem.

    • Return a default value. Of course, we do not know which value to return, so it must be provided by the caller.

    Implementing the case returning a default value is easy:

    default <B> Lazy<B> map(Function<A, B> f, B defaultValue) {
    return () -> {
        try {
            return f.apply(get());
        } catch (Exception e) {
            return defaultValue;
        }
    };
}

    This could be used as in the following example:

    static Lazy<String> name1 = () -> {
    System.out.println("Evaluating name1");
    return "Bob";
};

static Lazy<String> name2 = () -> {
    System.out.println("Evaluating name2");
    throw new RuntimeException();
};

static Function<String, String> constructMessage =
        name -> String.format("Hello, %s!", name);

public static void main(String... args) {
    String defaultValue = "Sorry, but I don't talk to anonymous people.";
    System.out.println(name1.map(constructMessage, defaultValue).get());
    System.out.println("----");
    System.out.println(name2.map(constructMessage, defaultValue).get());
}

    And here is the result displayed on the console:

    Evaluating name1
Hello, Bob!
----
Evaluating name2
Sorry, but I don't talk to anonymous people.

    But of course, we will sometimes need to use a lazily evaluated default value, which is straightforward:

    default <B> Lazy<B> map(Function<A, B> f, Lazy<B> defaultValue) {
    return () -> {
        try {
            return f.apply(get());
        } catch (Exception e) {
            return defaultValue.get();
        }
    };
}

    Returning an Optional is a bit more complex. Here is a possible implementation:

    default <B> Lazy<Optional<B>> mapOption(Function<A, B> f) {
    return () -> {
        try {
            return Optional.of(f.apply(get()));
        } catch (Exception e) {
            return Optional.empty();
        }
    };
}

    This would give the same result provided we change a little our example program:

    public static void main(String... args) {
    String defaultValue = "Sorry, but I don't talk to anonymous people.";
    System.out.println(name1
            .mapOption(constructMessage)
            .get()
            .orElse(defaultValue));
    System.out.println("----");
    System.out.println(name2
            .mapOption(constructMessage)
            .get()
            .orElse(defaultValue));
}

    Mapping a Function Returning a Lazy Type

    Sometimes, instead of a Function<A, B>, we will need to map a function with a Lazy<B> result. If we pass such a function to the map method, the result will be a Lazy<Lazy<B>>. Whatever the usefulness of being Lazy, being lazily lazy is a bit too much, so we need a way to transform a Lazy<Lazy<B>> into a Lazy<B>. This is also a very common use case, and it is generally called flatten or join. Here is how we can implement it:

    static <A> Lazy<A> flatten(Lazy<Lazy<A>> lla) {
    return lla.get();
}

    This is fine, but it can only be implemented as a static method. As the need arises most frequently while mapping a function, it is preferable to create a special version of map, that we call flatMap:

    default <B> Lazy<B> flatMap(Function<A, Lazy<B>> f) {
    return () -> f.apply(get()).get();
}

    With such a function, we can compose as many lazy values as we need without evaluating anything:

    static Lazy<String> lazyGreetings = () -> {
    System.out.println("Evaluating greetings");
    return "Hello";
};

static Lazy<String> lazyFirstName = () -> {
    System.out.println("Evaluating first name");
    return "Jane";
};

static Lazy<String> lazyLastName = () -> {
    System.out.println("Evaluating last name");
    return "Doe";
};

public static void main(String... args) {
    Lazy<String> message = lazyGreetings
        .flatMap(greetings -> lazyFirstName
            .flatMap(firstName -> lazyLastName
                .map(lastName -> String.format(
                        "%s, %s %s!", greetings, firstName, lastName))));
    System.out.println("Message has been composed but nothing has been evaluated yet");
    System.out.print(message.get());
}

    The result is:

    Message has been composed but nothing has been evaluated yet
Evaluating greetings
Evaluating first name
Evaluating last name
Hello, Jane Doe!

    This shows that nothing is evaluated before the get method is called on the result.

    Putting a Value in Context

    As I already said, we sometimes need to put an already evaluated expression in lazy context. It does not change anything regarding evaluation, but it is needed to compose evaluated expressions with non evaluated ones. This is done by a static method which is generally called return or unit. Java uses a different convention for this, calling this method of, so we will define such a method in our interface:

    static <A> Lazy<A> of(A a) {
    return () -> a;
}

    "Lazy Types In Java"

    Abstracting Behavior

    The Lazy type we have implemented shares much of its behavior with many other types like Optional, CompletableFuture, Stream or the functional singly linked list of functional languages (but not the java.util.List). Having a flatMap method as well as a way to create a Lazy<A> from an instance of A makes our lazy type Lazy a monad (providing these methods fulfill some additional conditions). And all monads can be composed with monads of the same type and with functions, in the same way we did it here.

    Using monads allows abstracting a specific behavior (here, laziness) from the way this behavior may be composed with other elements, by providing a context in which ordinary computations may occur, although these ordinary computations would normally not apply. This is what we have seen when we applied a Function<A, B> to a lazy A without transforming this lazy A into an evaluated one.

    Some other monads may seem very similar to our Lazy monad. For example, a Future<A> (not the Java Future, but something more like the CompletableFuture) also represents non evaluated data. The big difference with a Lazy<A> is that Lazy is intended to delay evaluation (and possibly avoid it) while Future is mainly intended to eagerly start an evaluation which result will only be available later. Beside this, all other characteristics, such as the way to compose them through the use of map and flatMap, are equivalent, although these methods have been given different names.

    A Better Way to Handle Effects

    In our example, we have been calling the get method in order to start evaluation when we wanted to be able to print the result to the console. In other words, we have extracted the value from its context in order to apply an effect to it. This cancels the effect of laziness. Of course, this is sometimes eventually needed, but we should strive to delay this as much as possible. Fundamentalist functional programmers use very sophisticated techniques for this, but for starters we can use much simpler ones.

    The mapping we implemented above consists of introducing a raw function inside the context of laziness, rather than extracting the value to pass it to the function. We can do the same with effects. Instead of calling get to print the evaluated result to the console, we can pass the effect of printing to the console into the Lazy context. For this, we will use a method that we will call forEach, although there is only a single value in context. This allows us to abstract the principle, which is similar for most contexts, under a single name.

    The implementation is very simple:

    default void forEach(Consumer<A> c) {
    c.accept(get());
}

    Using this method, our last example can be rewritten as:

    public static void main(String... args) {
    Lazy<String> message = lazyGreetings
        .flatMap(greetings -> lazyFirstName
            .flatMap(firstName -> lazyLastName
                .map(lastName -> String.format(
                        "%s, %s %s!", greetings, firstName, lastName))));
    System.out.println("Message has been composed but nothing has been evaluated yet");
    message.forEach(System.out::println);
}

    Note that our forEach method takes a Consumer that is applied to each value in context. The fact that for Lazy it can’t be anything but a single value is irrelevant. What is important is to clearly see that it is exactly the same concept as forEach in a Java 8 Stream. This is (among other things) what Optional is doing wrong: calling this method ifPresent fools the user by making him believe it’s something different from the forEach method of Stream, when what they have in common is much more important than what differentiates them.

    Memoizing the Result of the Evaluation

    Our interface allows deferred evaluation, but it does not allow reusing the value once it has been evaluated. This means that if we want to use the value twice without recomputing it, we have to store it somewhere. It would be more practical to have the Lazy type handle this for us.

    But an interface can’t store a value, so we have to choose another design. Instead of creating an interface extending Supplier, we may create a class containing a Supplier. This class will store both a Supplier<A> and an A, using the same technique we used in the first example:

    public class Lazy<A> {

    private final Supplier<A> sValue;

    private A value;

    private Lazy(Supplier<A> value) {
        this.sValue = value;
    }

    public A get() {
        // Note that the following code is not thread safe. Thread safety
        // is not implemented here to keep the code simple, but can be
        // added easily.
        if (value == null) {
            value = sValue.get();
        }
        return value;
    }

    public <B> Lazy<B> map(Function<A, B> f) {
        return new Lazy<>(() -> f.apply(this.get()));
    }

    public <B> Lazy<B> map(Function<A, B> f, B defaultValue) {
        return new Lazy<>(() -> {
            try {
                return f.apply(this.get());
            } catch (Exception e) {
                return defaultValue;
            }
        });
    }

    public <B> Lazy<Optional<B>> mapOption(Function<A, B> f) {
        return new Lazy<>(() -> {
            try {
                return Optional.of(f.apply(this.get()));
            } catch (Exception e) {
                return Optional.empty();
            }
        });
    }

    public <B> Lazy<B> flatMap(Function<A, Lazy<B>> f) {
        return new Lazy<>(() -> f.apply(get()).get());
    }

    public void forEach(Consumer<A> c) {
        c.accept(get());
    }

    public static <A> Lazy<A> of(Supplier<A> a) {
        return new Lazy<>(a);
    }

    public static <A> Lazy<A> of(A a) {
        return new Lazy<>(() -> a);
    }

}

    Note the presence of two static factory methods in order to allow creation of a Lazy<A> from a Supplier<A> or from an already evaluated A. Running the following test shows the benefits of memoization:

    static Lazy<String> name1 = Lazy.of(() -> {
    System.out.println("Evaluating name1");
    return "Bob";
});

static Lazy<String> name2 = Lazy.of(() -> {
    System.out.println("Evaluating name2");
    throw new RuntimeException();
});

static Function<String, String> constructMessage =
        name -> String.format("Hello, %s!", name);

public static void main(String... args) {
    String defaultValue = "Sorry, but I don't talk to anonymous people.";
    name1.map(constructMessage, defaultValue).forEach(System.out::println);
    System.out.println("----");
    name2.map(constructMessage, defaultValue).forEach(System.out::println);
    System.out.println("----");
    name1.mapOption(constructMessage).forEach(System.out::println);
    System.out.println("----");
    name2.mapOption(constructMessage).forEach(System.out::println);
}

    The result shows that the successful evaluation occurs only once:

    Evaluating name1
Hello, Bob!
----
Evaluating name2
Sorry, but I don't talk to anonymous people.
----
Optional[Hello, Bob!]
----
Evaluating name2
Optional.empty

    Here, the result of a failing evaluation is not memoized. This gives us the opportunity to retry on the next call, which may or may not be useful, depending on the reason of the failure. If we want the failure to be memoized, we may just store an Optional as the result of the call.

    Summary

    We learned how to effectively implement type laziness:

    • Using Supplier to represent laziness
    • Composing lazy types to get a lazy result
    • Mapping a function returning an evaluated value to a lazy type
    • Mapping a function returning a lazy value to a lazy type
    • Applying effect to lazy types
    • Memoizing lazy types

    While learning these techniques, we have discovered how laziness is a computational context. We have learned how to

    • Put an expression in context
    • Combine values in context
    • Apply effect to values in context

    Distinguishing between various types of contexts and abstracting these context types into elements that can be combined at a higher level of computation is a main part of functional programming.

    CSS Master, 3rd Edition