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?

CodePudding user response：

No, concat isn't magic. It's just a method, and like all methods, all args are evaluated on the spot and in order.

However, the isPrime argument does not lead to executing that closure. Why should it? A large part of the point of closures/lambdas is that you refer to them, not, 'execute them immediately'. It's the notion of wrapping the idea of executing a function in a little envelope, ready to hand off to another method which can run it once, many times, or never.

Argument IntStream.iterate(3, i -> i 2).filter(isPrime) must be evaluated before being applied to IntStream.concat

Yes, but evaluating that does almost nothing. It certainly isn't going to invoke isPrime.

CodePudding user response：

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.