Kotlin asSequence

Kotlin is a really amazingly rich language and when I thought I had managed to internalise those of its features that I had never (or very rarely) used before in other languages (lambda expressions with receiver, qualified returns, inline functions, etc) I've just come across again some code that had me scratching my head for a while thinking "what the fuck is that code doing?".

The difference between Iterables and Sequences is very interesting (it's not new, you have lazy collection operations in .Net Linq, in JavaScript lodash, in python map-filter...) but the way kotlin allows you switching from eager to lazy by wrapping your collection in a class implementing the Sequence interface is pretty nice. The typical methods to operate on collections (filter, map, all, any, takeWhile...) are implemented as extension functions in both the Iterable and Sequence interfaces. Those in the Iterable interface work egarly and those in the Sequence interface work lazily. These methods rely on an Iterator to obtain elements from the collection, but they call iterator.next eiter eagerly (those from Iterator) or lazily (those from Sequence). So obtaining a Sequence from a Collection should be just getting an object that implements the Sequence interface and which iterator() method returns the iterator of that Collection. Looking into the implementation of asSequence I came across this (documented as: "Creates a Sequence instance that wraps the original array returning its elements when being iterated"):

public fun  Array.asSequence(): Sequence {
    if (isEmpty()) return emptySequence()
    return Sequence { this.iterator() }
}

So, understanding what's happening there in the return Sequence { this.iterator() } is what motivates this post.

Update 2024/05. When I initially wrote this post I was pretty confused. I was thinking that Sequence was a functional interface, but that does not exist, the interface is the generic Sequence[T]. To my surprise, Sequence (starting by uppercase) is a function!? Yes, oddly enough the Kotlin coding conventions allows a very particular case where functions can start by uppercase: factory functions used to create instances of classes can have the same name as the abstract return type.

So this code is just calling the Sequence function:

val cities = Sequence { cities.iterator() } // Sequence is a factory function

//public inline fun  Sequence(crossinline iterator: () -> Iterator): Sequence = object : Sequence {
//    override fun iterator(): Iterator = iterator()
//}

But this code is doing something different:

val runnable = Runnable { println("This runs in a thread pool")} // Runnable is a functional interface

//@FunctionalInterface 
//public interface Runnable

That line is a "SAM conversion". It's creating an object of an anonymous class that implements the Runnable functional interface (SAM). The Runnable interface has a single non default method, so you can pass a function literal as the implementation of that single method (as explained here). So I'm creating an object of a new anonymous class that implements the Runnable interface, (that has only a method, run). The single method of that class is implemented as a call to the lambda.

I've disassemblied the compiled code (see the next paragraph), and to my surprise in this case the Kotlin compiler is treating the lambda the same way the Java compiler manages lambdas, through the invokedynamic bytecode instruction. This means that the kotlin compiler instead of creating the class that I have just described, it just emits an invokedynamic instruction, and it will be at runtime when the class is created. This is well explained for example here

The Kotlin documentation describes this behaviour:

SAM adapters via invokedynamic

Kotlin 1.5.0 now uses dynamic invocations ( invokedynamic ) for compiling SAM (Single Abstract Method) conversions:

Over any expression if the SAM type is a Java interface
Over lambda if the SAM type is a Kotlin functional interface

The new implementation uses LambdaMetafactory.metafactory() and auxiliary wrapper classes are no longer generated during compilation

As for the disassemblied code, here it is. Notice that I'm using the amazing ByteCode Viewer application, and it directly shows the Bootstrap Method (BSM) code just next to the invokedynamic instruction).

invokedynamic java/lang/invoke/LambdaMetafactory.metafactory(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite; : run(LfunctionalInterfaces/Person;)Ljava/lang/Runnable; ()V functionalInterfaces/Person.runRunnable$lambda$0(LfunctionalInterfaces/Person;)V (6) ()V