Evaluation strategy in Java

Question

I'm used to believing that functions in Java are always applicatively evaluated, that is, all the function arguments are evaluated before being applied to the function; until today when I was playing with prime numbers and wrote this function to generate an infinite sequence of prime numbers:

public static IntStream primes() 
{
    final IntPredicate isPrime = (n) ->
    {
        final int isqrt = (int)Math.sqrt(n);
        return primes().takeWhile(i -> i <= isqrt).allMatch(i -> n % i != 0);
    };
    
    return IntStream.concat(
            IntStream.of(2), 
            IntStream.iterate(3, i -> i + 2).filter(isPrime));
}

I expected the program to throw a StackOverflowError when primes() is called, with the following understanding:

• Evaluating return statement of primes()
  • Evaluating IntStream.concat(...)
    • Argument IntStream.iterate(3, i -> i + 2).filter(isPrime) must be evaluated before being applied to IntStream.concat
    • Testing isPrime on 3
      • isqrt evaluated as 1
      • Evaluating return statement of isPrime

        • Calling primes()

        • Evaluating return statement of primes()

          ...

And eventually lead to StackOverflowError.

Whereas the program actually runs and does produce an infinite sequence of prime numbers. What's wrong with my thinking, or is IntStream.concat actually lazily evaluated?

Answer 1

IntStream.concat evaluates its arguments applicatively, of course.

But Streams aren't collections of values, they're recipes for generating a sequence of values, and those recipes are only run when the stream has a terminal operation run on it, like collect, sum, to list, and the like.

For a simpler example of a lazy data structure like streams, consider:

class MyIterator implements Iterator<Integer> {
  int x = 0;
  public boolean hasNext() { return true; }
  public Integer next() { return x++; }
}

This represents an infinite sequence 0, 1, 2... You can create an instance of this Iterator, though, and it doesn't use infinite memory. It's just a recipe for that infinite sequence. Streams are implemented something like this, and IntStream.concat certainly doesn't try to go through the entire sequence of results -- it just produces a recipe that goes through the first stream first, then the second. It applicatively produces that recipe, which then gets evaluated later lazily when you actually do something with the stream.