Watch Out For Recursion in Java 8’s [Primitive]Stream.iterate()

An interesting question by Tagir Valeev on Stack Overflow has recently caught my attention. To keep things short (read the question for details), while the following code works:

public static Stream<Long> longs() {
    return Stream.iterate(1L, i ->
        1L + longs().skip(i - 1L)
                    .findFirst()
                    .get());
}

longs().limit(5).forEach(System.out::println);

printing

1
2
3
4
5

The following, similar code won’t work:

public static LongStream longs() {
    return LongStream.iterate(1L, i ->
        1L + longs().skip(i - 1L)
                    .findFirst()
                    .getAsLong());
}

Causing a StackOverflowError.

Sure, this kind of recursive iteration is not optimal. It wasn’t prior to Java 8 and it certainly isn’t with the new APIs either. But one might think it should at least work, right? The reason why it doesn’t work is because of a subtle implementation difference between the two iterate() methods in Java 8. While the reference type stream’s Iterator first returns the seed and only then proceeds with iterating by applying the iteration function on the previous value:

final Iterator<T> iterator = new Iterator<T>() {
    @SuppressWarnings("unchecked")
    T t = (T) Streams.NONE;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public T next() {
        return t = (t == Streams.NONE) ? seed : f.apply(t);
    }
};

This is not the case for the LongStream.iterate() version (and other primitive streams):

final PrimitiveIterator.OfLong iterator = new PrimitiveIterator.OfLong() {
    long t = seed;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public long nextLong() {
        long v = t;
        t = f.applyAsLong(t);
        return v;
    }
};

The iteration function is already pre-fetched one value in advance. This is usually not a problem, but can lead to

  1. Optimisation issues when the iteration function is expensive
  2. Infinite recursions when the iterator is used recursively

As a workaround, it might be best to simply avoid recursion with this method in primitive type streams. Luckily, a fix in JDK 9 is already on its way (as a side effect for a feature enhancement):
https://bugs.openjdk.java.net/browse/JDK-8072727

A Very Peculiar, but Possibly Cunning Kotlin Language Feature

This has caught me by surprise. After studying the Kotlin language to learn about how to best leverage this interesting new language for jOOQ, I stumbled upon this puzzler. What do you think the following program will print?

fun main(args: Array) {
    (1..5).forEach {
        if (it == 3)
            return
        print(it)
    }

    print("done")
}

Well… You might have guessed wrong. The above will print:

12

It will NOT print what most people might expect:

1245done

Note to those of you who are not surprised:

The above is peculiar for someone used to working with Java 8, where the following code will indeed print 1245done:

public static void main(String[] args) {
    IntStream.rangeClosed(1, 5).forEach(it -> {
        if (it == 3)
            return;

        System.out.print(it);
    });

    System.out.print("done");
}

The syntactical reason is explained in this section of the Kotlin manual:
https://kotlinlang.org/docs/reference/returns.html

In lambdas / closures, the return statement will not (necessarily) return from the lambda / closure, but from the immediate enclosing scope of the lambda / closure. The rationale has been kindly given to me by Dmitry Jemerov from JetBrains in two tweets:

Cunningly, the Kotlin language has removed language-based support for Java constructs like try-with-resources, or the synchronized statement. That’s very reasonable, because these language constructs don’t necessarily belong in the language (as we’ve previously claimed in another blog post), but could be moved to libraries instead. For example:

// try-with-resources is emulated using an
// extension function "use"
OutputStreamWriter(r.getOutputStream()).use {
    it.write('a')
}

(criticism here)

Or:

// Synchronized is a function!
val x = synchronized (lock, { computation() })

See also:
https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/synchronized.html

After all, even in Java, the language feature only works because the language depends on library types, like Iterable (foreach), AutoCloseable (try-with-resources), or JVM features (monitor on each reference for synchronized)

So, what’s the deal with return?

Along the lines of the above rationale, when language designers want to avoid language constructs for things that can be implemented with libraries, but still want you to feel like these were language constructs, then the only reasonable meaning of return inside of such a “construct-ish” lambda / closure is to return from the outer scope. So, when you write something like:

fun main(args : Array) {
    val lock = Object()
    val x = synchronized(lock, {
        if (1 == 1)
            return

        "1"
    })

    print(x)
}

The real intention is for this to be the equivalent of the following Java code:

public static void main(String[] args) {
    Object lock = new Object();
    String x;

    synchronized (lock) {
        if (1 == 1)
            return;

        x = "1";
    }

    System.out.println(x);
}

In the Java case, obviously, the return statement exits the main() method, because there is no other reasonable stack frame to return from. Unlike in Kotlin, where one might argue the lambda / closure would produce its own stack frame.

But it really doesn’t. The reason for this is the inline modifier on the synchronized function:

public inline fun <R> synchronized(lock: Any, block: () -> R): R {
    monitorEnter(lock)
    try {
        return block()
    }
    finally {
        monitorExit(lock)
    }
}

See also:
https://kotlinlang.org/docs/reference/inline-functions.html

Which means that the block closure passed as an argument isn’t really a pure lambda expression, but just syntactic sugar embedded in the call-site’s scope.

Weird. Cunning. Clever. But a bit unexpected.

Is this a good idea? Or will the language designers regret this, later on? Are all lambdas / closures potentially “language construct-ish”, where such a return statement is expected to leave the outer scope? Or are there clear cases where this inline behaviour just makes total sense?

We’ll see. In any case, it is very interesting for a language to have chosen this path.

Liked this article?

Stay tuned for a follow-up about the exciting Kotlin language. In the meantime, read

Fast File System Operations with Xtend, Lambdas, and ThreadPools

Recently, I’ve blogged about 10 Subtle Best Practices when Coding Java, and I have mentioned that you should start writing SAMs (Single Abstract Method) now, in order to be prepared for Java 8. But there’s another language gem out there, which comes in handy every once in a while, and that’s Eclipse Xtend. Xtend is a “dialect” of the Java language, compiling into Java source code, which then compiles into byte code.

Here’s a quickie showing how easily recursive file system operations can be done with Xtend, Lambdas, and ThreadPools.

class Transform {

  // This is the thread pool performing
  // all the "hard" work
  static ExecutorService ex;

  def static void main(String[] args) {
    // Initialise the thread pool with
    // something meaningful
    ex = Executors::newFixedThreadPool(4);

    // Pass the root directory to the
    // transform method
    val in = new File(...);

    // Recurse into the file transformation
    transform(in);
  }

  def static transform(File in) {

    // Calculate the target file name
    val out = new File(...);

    // Recurse into directories
    if (in.directory) {

      // Pass a FileFilter in the form of an
      // Xtend lambda expression
      for (file : in.listFiles[path |
             !path.name.endsWith(".class")
          && !path.name.endsWith(".zip")
          && !path.name.endsWith(".jar")
        ]) {
        transform(file);
      }
    }
    else {
      // Pass an Xtend lambda expression to
      // the ExecutorService
      ex.submit[ |
        // Read and write could be implemented
        // in Apache Commons IO
        write(out, transform(read(in)));
      ];
    }
  }

  def static transform(String content) {
    // Do the actual string transformation
  }
}

Granted, with Java 8, we’ll get lambdas as well, and that’s awesome. But Xtend has a couple of other nice features that can be seen above:

  • Passing lambdas to a couple of JDK methods, such as File.listFiles() or ExecutorService.submit()
  • Local variable type inference using valvar, or for
  • Method return type inference using def
  • Ability to omit parentheses when passing a lambda to a method
  • Calling getters and setters by convention, e.g. path.name, instead of path.getName(), or in.directory, instead of in.isDirectory()
  • You could also omit semi-colons, although I don’t personally think that’s a good idea.

Xtend is Java 8 already now, which can be very useful for scripts like the above