Categories
Kotlin

Fibonacci in Kotlin

I didn’t realize it until I noticed the trending topic on Twitter, but Saturday, November 23 was Fibonacci Day. That gave me an opportunity to drag out one of my favorite old jokes:

For those unaware or who don’t remember, the Fibonacci series starts with 0 and 1, and then each subsequent number is the sum of the previous two. The Fibonacci numbers are thus 0, 1, 1, 2, 3, 5, 8, 13, …. By the definition, the “zeroth” Fibonacci number F0 = 0, the first F1 = 1, the second F2 = 1, the third F3 = 2, and so on.

(Note the gag only works in the U.S., because we express our dates as month/day/year rather than day/month/year like the rest of the world. For us, November 23 is 11/23, thus Fibonacci day, ha ha. Sorry about the US-centric approach. On the other hand, there’s no 23rd month, so the rest of the world would miss out on Fibonacci day, and that would be sad.)

Naive Recursive Implementation

The Fibonacci algorithm is a classic example of a recursive function, expressed as Fn = Fn-1 + Fn-2:

fib(n) = fib(n - 1) + fib(n - 2)

The problem with a naive implementation of that algorithm is that the amount of duplicated work grows exponentially. For example,

fib(5) = fib(4) + fib(3) 
       = fib(3) + fib(2) + fib(2) + fib(1) 
       = fib(2) + fib(1) + fib(1) + fib(0) 
                + fib(1) + fib(0) + 1
       = fib(1) + fib(0) + 1 + 1 + 0 + 1 + 0 + 1 
       = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
       = 5

Yikes, and that’s just for the fifth Fibonacci number. The problem is that intermediate results aren’t being saved, so each number is recalculated over and over again, and the higher you go, the more duplicated work there is.

Tail Call Optimization

In Kotlin, there are several ways to fix this. One is to use tail recursion, which involves replacing recursion with iteration. An implementation in Kotlin can take advantage of the tailrec keyword:

@JvmOverloads
tailrec fun fibonacci(n: Int, a: Int = 0, b: Int = 1): Int =
    when (n) {
        0 -> a
        1 -> b
        else -> fibonacci(n - 1, b, a + b)
    }

There’s a fair amount going on here. First, in order to write a recursive function as a tail call, the recursive call itself has to come last in the implementation. In this example, the last evaluated expression is the else clause in the when loop, which calls the function again.

Also, when you write your function to be called recursively, you need to use an additional parameter to act as the accumulator. Here, n is the nth desired Fibonacci number, the value of b is the previous value, and the value of a is the one before that. In the recursive call, the new value of b is the current value of b plus the value of a, so that is effectively the accumulator.

The next interesting part is that the return type is specified explicitly. Normally in Kotlin when you implement a function as a single expression (using an = sign at the end of the signature) you can leave out the return type. If you do that in this case, however, IntelliJ IDEA complains with “Type checking has run into a recursive problem. Easiest workaround: specify types of your declarations explicitly.” Yeah, okay, I can do that, thus the a : Int at the end of the signature.

The next good part is using default values for the second and third arguments in the function. By initializing a to 0 and b to 1, the function can be invoked as fibonacci(10) without giving values for the other two parameters. That’s the way you want to call the function anyway, so that’s helpful. Unfortunately, Java doesn’t support default parameters, so to make sure the compiler generates overloads that Java can see, the JmvOverloads annotation is added. Now the fibonacci function can be called from Java with only a single argument.

That leads to the best part, which is the tailrec modifier. You could write this tail call algorithm directly in Java, but it wouldn’t save any memory. In Kotlin, however, this page in the reference guide says that compiler will automatically “optimize out the recursion, leaving behind and fast and efficient loop version instead.”

If you play the game in IntelliJ where you “Show Kotlin Bytecodes” and the hit the Decompile button, the resulting Java code looks like:

@JvmOverloads
public static final int fibonacci(int n, int a, int b) {
    while(true) {
        int var10000;
        switch(n) {
        case 0:
            var10000 = a;
            break;
        case 1:
            var10000 = b;
            break;
        default:
            var10000 = n - 1;
            int var10001 = b;
            b += a;
            a = var10001;
            n = var10000;
            continue;
        }

        return var10000;
    }
}

The recursive call has been implemented as a while(true) loop with the accumulator in the default section.

Kotlin fold and reduce

That’s all well and good, and normally I’d go on to discuss ways to test this function, but there are a couple of alternative ways to implement the algorithm. One is this particularly interesting version:

fun fibonacciFold(n: Int) =
    (2 until n).fold(1 to 1) { (prev, curr), _ -> 
        curr to (prev + curr) 
    }.second

Now that’s poetry, in that it’s simple, elegant, and really needs to be explained before it makes any sense. First of all, credit where credit is due. This is from Marcin Moskala (@marcinmoskala on Twitter). He included it in a blog post at Kotlin Academy, based on one of his tweets.

His first example, fib1, is the inefficient recursive algorithm. His second, fib2, is an iterative version of the same. The third one, fib3, is like the tail-call version described above. Finally, the last one, fib4, is the one I want to talk about, repeated in the syntax block prior to the tweet.

First, the expression (2 until n) is a range that runs from 2 to n - 1. An inclusive range would be 2..n.

Next comes the fold function. Kotlin has both fold and reduce functions. The fold function takes two parameters, while reduce only takes one:

inline fun <T, R> Iterable<T>.fold(
    initial: R,
    operation: (acc: R, T) -> R
): R

inline fun <S, T : S> Iterable<T>.reduce(
    operation: (acc: S, T) -> S
): S

Each of them applies the provided operation to each element of the Iterable, and the last evaluated expression from the operation becomes the new value of the acc (accumulator) argument on the next iteration. The difference is that fold takes an initial value for the accumulator, while reduce uses the first element from the sequence to initialize the accumulator.

For those more familiar with Java, the reduce function on Java streams behaves the same way, except that it is overloaded to take either a single BinaryOperator (like Kotlin’s reduce) or two values, where the first is an initial value called identityand the second is a BinaryOperator (like Kotlin’s fold). Note that in Java they refer to the first argument as identity rather than initial, which is more in keeping with the theory of functional programming. In either case the first argument is used as the initial value of the provided operation accumulator, but it’s supposed to be the identity value for the binary operator. The Kotlin implementation works the same way, but doesn’t stress that distinction.

Returning to the Fibonacci calculation, the fold function uses the Pair of 1 to 1 as its initial value, so the operation needs to return a new instance of Pair each time. There are two arguments to the lambda provided as the operation. The first argument is also a Pair, which acts as the accumulator, and the second argument would be each value in the range from 2 to n - 1. The algorithm doesn’t actually need those values, so the implementation just uses an underscore to indicate they’re ignored.

The implementation of the operation creates a new Pair whose first element is the current value and whose second element is the sum of the previous value and the current value. Finally, when the limit of the range is reached, the function returns the second element from the Pair as the desired value.

As usual with a fold function, it’s easiest to understand if you see it in action. Here is a version of it with the previous and current values written out each time:

fun fibonacciFoldDebug(n: Int) =
    (2 until n).fold(1 to 1) { (prev, curr), _ ->
        println("prev=$prev, curr=$curr")
        curr to (prev + curr)
    }.second

Here is the output of F(10):

prev=1, curr=1
prev=1, curr=2
prev=2, curr=3
prev=3, curr=5
prev=5, curr=8
prev=8, curr=13
prev=13, curr=21
prev=21, curr=34
Fib(10) == 55

The initial Pair of 1 to 1 initialized the prev and curr variables, which take new values as described in the fold operation. Once again, a recursive problem has been transformed into an iterative one, but this time in a really beautiful way. You can comfortably compute Fibonacci numbers as far as Int values work, and if you need something higher just reimplement this with BigInteger (and replace + with add) and keep going.

Sequences

There’s one more fundamentally different approach to the same problem, this time using sequences. A sequence in Kotlin is just like a stream in Java, in that values go through a series of intermediate operations followed by a terminal operation, and no data is pulled through the sequence until there is a terminal operation.

There are several ways to create a sequence in Kotlin, from the asSequence function on collections to the generateSequence function that takes a lambda to evaluate for each element. There is also, however, the basic function called sequence:

fun <T> sequence(
    block: suspend SequenceScope<T>.() -> Unit
): Sequence<T>

The sequence function is a suspend function (so it can be used with coroutines) that takes a lambda with a receiver. The lambda takes no arguments and returns nothing (i.e., Unit), and the receiver is an instance of SequenceScope. The documentation says the function returns a sequence by lazily yielding values one by one.

In fact, that documentation page actually contains a Fibonacci example, repeated here:

fun fibonacci() = sequence {
    var terms = Pair(0, 1)

    // this sequence is infinite
    while (true) {
        yield(terms.first)
        terms = Pair(terms.second, terms.first + terms.second)
    }
}

Look familiar? The iteration occurs over Pair instances, as before, in an infinite loop. The yield function “yields a value to the Iterator being built and suspends until the next value is requested.” Note that this returns a sequence, so to invoke it you need to add a terminal operation. The way the code in the documentation example calls this function is:

println(fibonacci().take(10).toList())

The take function is another intermediate operation that requests ten elements, and toList is, at long last, a terminal operation which converts the sequence into a List. The code prints the first 10 Fibonacci numbers in a list, [0, 1, 1, 2, 3, 5, 8, 13, 21, 34].

Wow, right? Lots of ways to solve the same problem. Of course, any functions like this need to be tested. That, too, can be an interesting story, which I’ll leave for the next blog post in this series.

As always, all the code (including extensive JUnit 5 tests) from this post can be found in this GitHub repository for my new book, the Kotlin Cookbook.

Categories
Kotlin

Annotated TOC for Kotlin Cookbook

Last week I received an email asking about a table Of contents for my new Kotlin Cookbook, saying they couldn’t find one either on the O’Reilly Media site or on Amazon. It’s a lot easier to make a decision about buying a recipe book if you have a list of recipes.

When I checked last week, no table of contents was available. Fortunately that’s no longer the case. If you go to the Amazon listing and click on the “Look Inside” link, the table of contents is included, along with the preface, which includes a description of each chapter.

It couldn’t hurt, however, to repeat both of those here as well. That way if anyone asks I can just give them this link, plus you can add whatever comments you like to this post and I’ll see them and potentially be able to respond.

Cover for my Kotlin Cookbook
Cover for my Kotlin Cookbook

Here is the list of chapter descriptions from the Preface.

  • Chapter 1, Installing and Running Kotlin, covers the basic process of installing and running Kotlin, including using the REPL, working with build tools like Maven and Gradle, and employing the native image generator in Graal.
  • Chapter 2, Basic Kotlin, covers some fundamental features of Kotlin—such as nullable types, overloading operators, and converting between types—before examining some more esoteric issues including working with bitwise shift operators or the to extension function on the Pair class.
  • Chapter 3, Object Oriented Programming in Kotlin, focuses on object-oriented features of the language that developers from other languages might find surprising or unusual. It includes how to use the const keyword, how Kotlin handles backing properties, delayed initialization, and the dreaded Nothing class, which is guaranteed to confuse existing Java developers.
  • Chapter 4, Functional Programming, has only a few recipes, which involve functional features that need their own explanations. Functional programming concepts are covered throughout the book, especially when talking about collections, sequences, and coroutines, but there are a handful of techniques included in this chapter that you may find unusual or particularly interesting.
  • Chapter 5, Collections, covers arrays and collections, dealing mostly with non-obvious methods like destructing collections, sorting by multiple properties, building a window on a collection, and creating progressions.
  • Chapter 6, Sequences, shows how Kotlin handles sequences of items lazily, similar to the way Java uses streams. Recipes cover generating sequences, yielding from them, and working with infinite sequences.
  • Chapter 7, Scope Functions, covers another topic unique to Kotlin: functions that execute a block of code in the context of an object. Functions like let, apply, and also are quite useful in Kotlin, and this chapter illustrates why and how to use them.
  • Chapter 8, Kotlin Delegates, discusses a convenient feature of Kotlin: how it implements delegation. Delegation lets you employ composition rather than inheritance, and Kotlin includes several delegates in the standard library, like lazy, observable, and vetoable.
  • Chapter 9, Testing, covers the important topic of testing, with a particular focus on JUnit 5. In its current version, JUnit is designed to work well with Kotlin, and that includes both its regular usage and employing it in Spring Framework applications. This chapter discusses several approaches that make writing and executing tests easier.
  • Chapter 10, Input/Output, includes a couple of recipes specifically for managing resources. File I/O is covered, as is the use function, which has broad applicability in several contexts.
  • Chapter 11, Miscellaneous, covers topics that do not fit easily in any other category. Topics such as how to get the current Kotlin version, how to force the when statement to be exhaustive even when it doesn’t return a value, and how to use the replace function with regular expressions are covered. In addition, the TODO function and the Random class are discussed, as well as how to integrate with Java exception handling.
  • Chapter 12, The Spring Framework, involves the Spring Framework along with Spring Boot, which is very friendly to Kotlin. A few recipes are included to show how to use Kotlin classes as managed beans, how to implement JPA persistence, and how to inject dependencies when needed.
  • Chapter 13, Coroutines and Structured Concurrency, covers the subject of coroutines, one of the most popular features of Kotlin and the basis of concurrent and parallel programming in the language. Recipes cover the basics, like builders and dispatchers, along with how to cancel and debug coroutines, and how to run them on your own custom Java thread pool.

Hopefully those descriptions will be helpful. For the actual recipes, the following list has been (slightly) enhanced by using code formatting for Kotlin functions or keywords.

  1. Installing and Running Kotlin
    1.1 Running Kotlin Without a Local Compiler
    1.2 Installing Kotlin Locally
    1.3 Compiling and Running Kotlin from the Command Line
    1.4 Using the Kotlin REPL
    1.5 Executing a Kotlin Script
    1.6 Building a Standalone Application Using GraalVM
    1.7 Adding the Kotlin Plugin for Gradle (Groovy Syntax)
    1.8 Adding the Kotlin Plugin for Gradle (Kotlin Syntax)
    1.9 Using Gradle to Build Kotlin Projects
    1.10 Using Maven with Kotlin
  2. Basic Kotlin
    2.1 Using Nullable Types in Kotlin
    2.2 Adding Nullability Indicators to Java
    2.3 Adding Overloaded Methods for Java
    2.4 Converting Between Types Explicitly
    2.5 Printing to Different Bases
    2.6 Raising a Number to a Power
    2.7 Using Bitwise Shift Operators
    2.8 Using Bitwise Boolean Operators
    2.9 Creating Pair Instances with to
  3. Object-Oriented Programming in Kotlin
    3.1 Understanding the Difference Between const and val
    3.2 Creating Custom Getters and Setters
    3.3 Defining Data Classes
    3.4 The Backing Property Technique
    3.5 Overloading Operators
    3.6 Using lateinit for Delayed Initialization
    3.7 Using Safe Casting, Reference Equality, and Elvis to Override equals
    3.8 Creating a Singleton
    3.9 Much Ado About Nothing
  4. Functional Programming
    4.1 Using fold in Algorithms
    4.2 Using the reduce Function for Reductions
    4.3 Applying Tail Recursion
  5. Collections
    5.1 Working with Arrays
    5.2 Creating Collections
    5.3 Creating Read-Only Views from Existing Collections
    5.4 Building a Map from a Collection
    5.5 Returning a Default When a Collection Is Empty
    5.6 Restricting a Value to a Given Range
    5.7 Processing a Window on a Collection
    5.8 Destructuring Lists
    5.9 Sorting by Multiple Properties
    5.10 Defining Your Own Iterator
    5.11 Filtering a Collection by Type
    5.12 Making a Range into a Progression
  6. Sequences
    6.1 Using Lazy Sequences
    6.2 Generating Sequences
    6.3 Managing Infinite Sequences
    6.4 Yielding from a Sequence
  7. Scope Functions
    7.1 Initializing Objects After Construction with apply
    7.2 Using also for Side Effects
    7.3 Using the let Function and Elvis
    7.4 Using let with a Temporary Variable
  8. Kotlin Delegates
    8.1 Implementing Composition by Delegation
    8.2 Using the lazy Delegate
    8.3 Ensuring That a Value Is Not Null
    8.4 Using the observable and vetoable Delegates
    8.5 Supplying Maps as Delegates
    8.6 Creating Your Own Delegates
  9. Testing
    9.1 Setting the Test Class Life Cycle
    9.2 Using Data Classes for Tests
    9.3 Using Helper Functions with Default Arguments
    9.4 Repeating JUnit 5 Tests with Different Data
    9.5 Using Data Classes for Parameterized Tests
  10. Input/Output
    10.1 Managing Resources with use
    10.2 Writing to a File
  11. Miscellaneous
    11.1 Working with the Kotlin Version
    11.2 Executing a Lambda Repeatedly
    11.3 Forcing when to Be Exhaustive
    11.4 Using the replace Function with Regular Expressions
    11.5 Converting to Binary String and Back
    11.6 Making a Class Executable
    11.7 Measuring Elapsed Time
    11.8 Starting Threads
    11.9 Forcing Completion with TODO
    11.10 Understanding the Random Behavior of Random
    11.11 Using Special Characters in Function Names
    11.12 Telling Java About Exceptions
  12. The Spring Framework
    12.1 Opening Spring-Managed Bean Classes for Extension
    12.2 Persisting Kotlin Data Classes
    12.3 Injecting Dependencies
  13. Coroutines and Structured Concurrency
    13.1 Choosing Coroutine Builders
    13.2 Replacing async/await with withContext
    13.3 Working with Dispatchers
    13.4 Running Coroutines on a Java Thread Pool
    13.5 Cancelling Coroutines
    13.6 Debugging Coroutines

I believe that’s 87 recipes total. I could have added at least a dozen more, but as Katie Mack (@AstroKatie on Twitter) once said, “the hardest thing about writing a book is that eventually you have to stop writing the book.” My book is done and I believe what’s there is solid. If I ever get to revisit it for a second edition, I’m sure I’ll have much more to say, but this hopefully will give you a good cross-section of what Kotlin can do and how to do it.

Categories
Kotlin

Kotlin Palindrome Checker

This post, based on code from my new Kotlin Cookbook, shows how to write a palindrome checker in Kotlin. Along the way it discusses raw strings and regular expressions, writing functions as single statements, and creating an extension function on String.

First, a quick definition. A palindrome is a string whose characters are the same forwards and backwards, ignoring case and with punctuation removed. Here are a few palindromes, which can serve as test cases later:

  • racecar
  • Madam, in Eden, I’m Adam.
  • Flee to me, remote elf!
  • Sex at noon taxes.
  • A Santa pets rats, as Pat taps a star step at NASA.

Make of them what you will. 🙂

To make a palindrome checker, you need to remove case sensitivity and replace all the punctuation with empty strings. The first task is trivial: just use the String functions toLowerCase or toUpperCase, whichever you prefer.

To handle regular expressions, Kotlin has a few mechanisms, but one is to use a raw string with the regex in it and then invoke the toRegex function on it.

In the case of a palindrome, a decent regex would be """[\W+]""". The square brackets represent a choice. The expression is a predefined character class \W, meaning the opposite of \w, where the lowercase version represents any word character. Word characters are lowercase a-z, uppercase A-Z, the numbers 0-9, and an underscore, _. Therefore \W represents all non-word characters, which can be used to get rid of all punctuation (other than underscores, but if that’s important, that can always be added later). The plus sign means one or more, so the overall effect is to look for one or more non-word characters. Since this post (and the book) is written for the JVM version of Kotlin, you can see the JavaDocs for java.util.regex.Pattern class for details.

The triple quotes surrounding the regex represent a “raw” string in Kotlin, so you don’t have to escape the backslash on the W when writing a regular expression. Raw strings can be written over several lines, too, but that’s not necessary here. To make the raw string into a regular expression, invoke the toRegex function on it.

"""[\W+]""".toRegex()

The tricky “replace” function

To use the regular expression, String has a function called replace, but it’s a bit tricky. There are two overloaded versions of replace, one whose first argument is a string and one whose first argument is a regex. The signatures are:

// First arg is String, last arg has default value "false"
public fun String.replace(
    oldValue: String,
    newValue: String,
    ignoreCase: Boolean
): String

and

// First arg is a regular expression
public inline fun CharSequence.replace(
    regex: Regex,
    replacement: String
): String

For the first version of replace, the library implementation shows that the ignoreCase parameter has a default value of false, so invoking the function without that parameter is legal. That, unfortunately, makes it easy to confuse with the second version, as the following test case shows.

@Test
fun `demonstrate replace with a string vs regex`() {
    assertAll(
        { assertEquals("one*two*", "one.two.".replace(".", "*")) },
        { assertEquals("********", 
              "one.two.".replace(".".toRegex(), "*")) }
    )
}

The first assertion replaces the single dots in “one.two.” with a single star, *, because it’s using the version of replace that takes a string as the first argument. That means it looks for literal dots in the string and replaces them with a star.

The second assertion uses the version of replace that takes a regular expression as the first argument. In regular expressions, a single dot represents any single character, so the result is to replace all the letters in “one.two.” with stars, as shown.

I should mention that I didn’t come up with that example on my own. I saw it in a slide found here, which is one of the presentations, hosted at SpeakerDeck, provided by the Kotlin core team members. The slides are a little dated, but still useful. You can find all of them linked from this GitHub repository.

isPalindrome Function

Returning to the palindrome checker, version 1 is shown as a function called isPalindrome that takes a string argument and returns a boolean:

fun isPalindrome(string: String): Boolean {
    val testString = string.toLowerCase()
        .replace("""[\W+]""".toRegex(), "")
    return testString == testString.reversed()
}

This works by converting the supplied string to lower case, then using the replace function with the needed regex, and then using == to see if it is equivalent to its reverse. It’s notable that in Kotlin String has a reverse function, and that operator overloading means that the == sign invokes the equals function.

While this works, it’s arguably not idiomatic. Kotlin favors single statement functions, where you can just assign a statement implementation to the function signature. The hard part in this particular function is that it is currently two statements — one to create the test string, and one to do the equality check. This is where the convenient scope function called let comes in, as you can see in version 2 of the palindrome function:

fun isPalindrome(string: String) =
    string.toLowerCase()
          .replace("""[\W+]""".toRegex(), "")
          .let { it == it.reversed() }

The replace function returns the new string, so you can chain another function call to it. Then, according to the documentation, the let function “calls the specified function block with this value as its argument and returns its result”. The provided block is a lambda with a single argument, referred to as it, and returns the last evaluated expression, which is the boolean that results from the equivalence check.

To really bring this home, this top-level function seems to be a natural extension function on the String class (or CharSequence interface) , so here is the final version of the function:

fun String.isPalindrome() =
    this.toLowerCase()
        .replace("""[\W+]""".toRegex(), "")
        .let { it == it.reversed() }

Inside the extension function, the current instance is referenced as this, but the rest of the implementation is the same.

Finally, here are a couple of tests to demonstrate that the function works correctly:

@Test
fun `these are palindromes`() {
    assertAll(
        { assertTrue("Madam, in Eden, I'm Adam".isPalindrome()) },
        { assertTrue("Flee to me, remote elf!".isPalindrome()) },
        { assertTrue("Sex at noon taxes".isPalindrome()) },
        { assertTrue("A Santa pets rats, as Pat taps a star step at NASA".isPalindrome()) }
    )
}

@Test
fun `check isPalindrome is not just returning true`() {
    assertFalse("this is not a palindrome.isPalindrome())
}

The result is a simple function that can be used for any string, and the implementation shows how to use replace, reverse, regular expressions, the let function, and how to implement a simple extension function.

As usual, the source code can be found in the GitHub repository for my Kotlin Cookbook. The tests there include one for the massive 543-word palindrome, written as a multi-line string, from the Gigantic List of Palindromes. Just being able to verify that palindrome was entertaining enough to do this entire exercise. 🙂

Categories
Kotlin

A Deep Dive into the KotlinVersion Class

Getting the current Kotlin version is easy, but the actual KotlinVersion class is much more interesting. This post shows how to get the Kotlin version programmatically, but then looks at the details of the KotlinVersion class, including how it demonstrates a great way to write an equals method and more.

Note that this demo is part of my new book, Kotlin Cookbook, from O’Reilly Media.

Book cover for Kotlin Cookbook
The Kotlin Cookbook, coming this Fall from O’Reilly Media

Also, I was lucky enough to be interviewed by Hadi Harriri on his Talking Kotlin podcast, and this class came up. That episode has not yet been released, but should be out soon depending on his current backlog.

To start, here is the trivial one-liner to find out which version of Kotlin is executing your code:

fun main() {
    println("The current Kotlin version is ${KotlinVersion.CURRENT}")
}

At the time of this writing, the current release version of Kotlin is 1.3.50, and when you run this script on that version that’s what you get.

Where life gets interesting is when you look at how the KotlinVersion class is implemented. The next series of snippets will examine that in some detail. The KotlinVersion class in the standard library is in the kotlin package, and begins:

public class KotlinVersion(val major: Int, 
                           val minor: Int, 
                           val patch: Int
) : Comparable<KotlinVersion> {

The class is marked public, which isn’t necessary (public is the default) but is typical of library classes. Then follows the primary constructor, which takes three integer values, labeled major, minor, and patch. After the colon after the signature shows that the class implements the Comparable interface for instances of itself, which is already pretty interesting. The Comparable interface in Kotlin is just like its counterpart in Java. It establishes a “natural ordering” on instances of the class.

The Comparable interface in the standard library consists of:

public interface Comparable<in T> {
    public operator fun compareTo(other: T): Int
}

Again, the word public is not necessary either on the class or the function, but doesn’t hurt anything. The compareTo function is labeled an operator function. In this case, the function is used whenever you use <, >, ==, or one of the combination comparison functions, <=, >=, or !=. The function returns an integer whose value doesn’t matter, but should be negative, zero, or positive if the current object is less than, equal to, or greater than its argument.

Returning to the KotlinVersion class, the implementation of compareTo is:

override fun compareTo(other: KotlinVersion): Int = version - other.version

This assumes that the KotlinVersion class has a version property. The primary constructor didn’t show one, so the implementation provides a private property of that name and the function to compute it:

private val version = versionOf(major, minor, patch)

private fun versionOf(major: Int, minor: Int, patch: Int): Int {
    require(major in 0..MAX_COMPONENT_VALUE && 
            minor in 0..MAX_COMPONENT_VALUE && 
            patch in 0..MAX_COMPONENT_VALUE) {
        "Version components are out of range: $major.$minor.$patch"
     }
     return major.shl(16) + minor.shl(8) + patch
}

So the version property is computed from the major, minor, and patch values. The require statement is a pre-condition that verifies the individual values fall within the required range. For all three, the minimum is zero and the maximum is MAX_COMPONENT_VALUE. Like most constants, MAX_COMPONENT_VALUE is found in the companion object:

companion object {
    public const val MAX_COMPONENT_VALUE = 255

    @kotlin.jvm.JvmField
    public val CURRENT: KotlinVersion = KotlinVersion(1, 3, 50)
}

Note the use of both const and val together. From a Java perspective, the properties inside the companion object are effectively static, and the val keyword indicates they’re both final as well. The const modifier means the value is a compile-time constant, rather than being specified at runtime. The max value is therefore hard-wired to 255, and on this version of Kotlin the CURRENT value is an instance of the KotlinVersion class where major, minor, and patch values are 1, 3, and 50, respectively.

That takes care of the require block in the versionOf function. What about the actual value it returns? That’s computed using the shift-left (or left-shift, but the other way reads better) operator function, shl. That is an infix function that shifts the current value by the specified number of bits. Its signature is given by:

public final infix fun shl(
    bitCount: Int
): Int

This is an infix function, so the idiomatic way to invoke it would be major shl 16, minor shl 8, etc, but the form used here works anyway. Basically, the function shifts by two bytes for major and one byte for minor, which gives them enough of an offset that it is very unlikely a different set of major/minor/patch values will result in the same version. For the record, using 1, 3, and 50 gives 65,536 for 1 shl 16 and 768 for 3 shl 8, and the sum from the versionOf function is 66,354:

@Test
fun `left-shift for major, minor, and patch of 1, 3, and 50`() {
    assertEquals(65536, 1 shl 16)
    assertEquals(768, 3 shl 8)
    assertEquals(66354, (1 shl 16) + (3 shl 8) + 50)
}

The major, minor, and patch values are therefore combined into a single integer, which is used for the ordering. The next interesting part is how the KotlinVersion class implements the standard overrides of toString, equals, and hashCode:

override fun toString(): String = "$major.$minor.$patch"

override fun equals(other: Any?): Boolean {
    if (this === other) return true
    val otherVersion = (other as? KotlinVersion) ?: return false
    return this.version == otherVersion.version
}

override fun hashCode(): Int = version

There’s nothing terribly surprising about the overrides of toString or hashCode. The former is just formatting, and the latter reuses that version calculation just discussed, which is pretty convenient since the left-shifted offset mechanism described above is exactly how Josh Bloch recommended creating a decent hashCode function in his Effective Java book for the last twenty-some-odd years. 🙂

The real fun is in the override of the equals function. The KotlinVersion class, like all Kotlin classes, extends Any. As a reminder, the Any class looks like:

package kotlin

public open class Any {
    public open operator fun equals(other: Any?): Boolean
    public open fun hashCode(): Int
    public open fun toString(): String
}

Returning to the implementation of equals in KotlinVersion, the first check uses the triple equals operator === to see if the current reference and the argument are both pointing to the same instance. If so, the result is equal and no further checking is necessary.

If the two objects are different, the code needs to check the version property. Because the argument to the equals function is nullable, you can’t simply access the version property without checking for null first. The safe cast operator, as?, is used to check that. If the argument is not null, this casts it to an instance of KotlinVersion. If the argument is null, the safe cast operator returns null, so the Elvis operator, ?:, is used to simply return false rather than continue.

That’s really interesting, actually. The “return false” statement aborts the assignment of the otherVersion property. The results is Nothing, a class almost guaranteed to confuse Java developers, but beyond the scope of this discussion. Suffice it to say that because Nothing is a subclass of every other class, the resulting type of otherVersion is KotlinVersion, as desired.

Assuming we make it to the last line in the equals method, now there is a value for otherVersion and a value for the current version. The comparison then checks version == otherVersion.version for equality (since they’re both Int values) and returns the result.

That’s quite a lot of power for three lines of code, and is a great example of how to implement an equivalence check for a nullable property (which happens to be another recipe in the book).

To complete the story, the class has a secondary constructor that can be used when the patch value is unknown.

public constructor(major: Int, minor: Int) : this(major, minor, 0)

Then there are two overloads of the isAtLeast function:

public fun isAtLeast(major: Int, minor: Int): Boolean =
    this.major > major || 
        (this.major == major && this.minor >= minor)

public fun isAtLeast(major: Int, minor: Int, patch: Int): Boolean =
    this.major > major || 
        (this.major == major &&
            (this.minor > minor || 
                 this.minor == minor && this.patch >= patch))

A couple of tests show how the basic comparisons work:

@Test
fun `comparison of KotlinVersion instances work`() {
    val v12 = KotlinVersion(major = 1, minor = 2)
    val v1341 = KotlinVersion(1, 3, 41)
    assertAll(
        { assertTrue(v12 < KotlinVersion.CURRENT) },
        { assertTrue(v1341 <= KotlinVersion.CURRENT) },
        { assertEquals(KotlinVersion(1, 3, 41),
            KotlinVersion(major = 1, minor = 3, patch = 41)) }
    )
}

@Test
fun `versions are Ints less than max`() {
    val max = KotlinVersion.MAX_COMPONENT_VALUE
    assertAll(
        { assertTrue(KotlinVersion.CURRENT.major < max) },
        { assertTrue(KotlinVersion.CURRENT.minor < max) },
        { assertTrue(KotlinVersion.CURRENT.patch < max) }
    )
}

Because the KotlinVersion class implements Comparable, it can be used in a range and has a contains method. In other words, you can write:

@Test
fun `check current version inside range`() {
    assertTrue(KotlinVersion.CURRENT in 
        KotlinVersion(1,2)..KotlinVersion(1,4))
}

What you can not do, however, is to iterate over that range, because ranges are not progressions, but that’s a post for another day.

I hope you enjoyed this deep dive into what is arguably a trivial, but highly instructive, class in the Kotlin library. The GitHub repository for the book is located here and contains this example as well as many, many others.