Kotlin ❤ FP

I offer the readers of "Habrakhabr" a free translation of the article "Functional programming in Kotlin" . Publication author - Mike Hearn.



Those who use .NET have probably heard about F #, the universal functional programming language for CLR. Programmers outside the .NET community are most likely aware of functional programming in connection with the Haskell language.
')
Anyway, I suspect that many would have liked a similar language, but for JVM, with advanced tools and without having to do everything in a functional style.

The Kotlin language ( kotlinlang.org ) from JetBrains may seem like only sweetened Java: syntax conventions, type inference, and similar trivialities. But under the plain shell in it you can find all the most popular and progressive constructions of functional languages.

Let's start with simple examples of typical functional structures.

Algebraic data types

This syntax is quite typical for most functional languages:

data Maybe a = Nothing | Just a deriving (Eq, Ord) 

This is Haskell, and there is defined the type “Maybe”, which has two constructors: “Nothing” and “Just”. The Just constructor takes a single parameter of undefined type. The keyword "deriving" autogenerates the code to compare type objects and check them for equality.

In Kotlin, the Maybe class is not needed, since the ability to return or not return a value is initially incorporated into its type system. Optionality of the result is so often found in programs that it makes sense to support it at the very core of the language. This adds both convenience and performance:

 val s: String? = if (Math.random() < 0.5) "Yay!" else null println("length of string is .... ${ s.length() }") 

It does not compile the second line, since we are trying to calculate the length of the line, which we may not have. It is easy to repair:

 val s: String? = if (Math.random() < 0.5) "Yay!" else null println("length of string is .... ${ s?.length() ?: -1 }") 

The "s? .Length ()" construction will return `null` if the string was` null`, and the "?:" Operator will return its right-hand side when `null` is on the left. That is, the code prints `-1`, if the line suddenly does not exist.

Kotlin has a full set of tools for working with `null` types, you can be sure. But let's not talk about this for the sake of brevity.

Instead, let's define the equivalent of Maybe in Kotlin, just for illustration.

 sealed class Maybe<out T> { object None : Maybe<Nothing>() data class Just<T>(val t: T) : Maybe<T>() } 

The syntax is certainly not as short as in Haskell, but also quite acceptable. The “data” modifier is optional, but it adds some useful buns.

Everything works without surprises:

 val j = Maybe.Just(1) val (i) = j 

Here we define Just containing the number (Int) inside, and then retrieve the number back. Note, no type is ever mentioned: they are all output automatically. If there were just a few fields in Just, it would be possible to extract them all, which is in fact the purpose of this construction:

 data class Pet(val name: String, val age: Int) val alice = Pet("Alice", 6) val (name, age) = alice 

But what about pattern matching? This is exactly what we needed the keyword "sealed". With it, the compiler knows that there are no other Maybe subclasses except Just and None, and branching all options does not require the “else” branch:

 class User(val age: Int) fun lookupFromDB(s: String): Maybe<User> = Maybe.None fun printUser(username: String) { val rec = lookupFromDB(username) when (rec) { is Maybe.None -> println("not found") is Maybe.Just<User> -> println("${rec.t.age} years old") } } 

Above is defined a simple class with a single immutable field «age». The “lookupFromDB” method simulates database access and returns `Maybe`. In our case, always None, but this is nothing more than an example.

After that, the returned value is compared with the types using the "when" operator. The `when` construct allows you to do many things. In particular, after successfully matching an argument with a type, inside the right-hand side, the argument changes its type accordingly. That is why in the right part of the second branch we can use the “t” field of the `User` class without unnecessary ceremonies.

Immutability data (Immutability)

Kotlin is not a purely functional language, therefore immutable objects coexist with mutable on equal rights. The design unobtrusively pushes the programmer to use immutable objects, but in general, the choice is always left to the developer.

For example, like this:

 data class Person(var name: String, var age: Int) val p = Person("Mike", 31) p.name = "Bob" 

Here "p" is the immutable value ( val ue). Similar to `final variable` in Java, or` let` in Haskell / F #. But the contents of this object consist of variable variables ( var iable), so they can be reassigned. Highlighting in the IDE helps distinguish between changeable and immutable fields.

The same example, but now all links are unchangeable:

 data class Person(val name: String, val age: Int) val mike = Person("Mike", 31) val olderMike = mike.copy(age = 32) 

The copy method for the `data` classes is created automatically. For each class field it has a named parameter, by default equal to the current value. As a result, it is convenient to use it to create new "corrected" objects.

Default lists are immutable:

 val people = listOf(mike, olderMike) people.add(Person("Bob", 50)) // ERROR val peopleDB = arrayListOf(mike, olderMike) peopleDB.add(Person("Bob", 50)) val view: List<Person> = peopleDB val snapshot = peopleDB.toList() 

The second line will not compile: `listOf ()` returns an immutable list. But in the fourth line, everything is in order, since we specifically asked for `ArrayList`, which can be changed. Of course, any list can always be made unchangeable by the `List` interface and create a“ read-only view ”.

At the moment, there is no built-in syntax for lists in the language, so functions with a variable number of arguments are used to create them.

Mapping, filtering, reducing and other goodies

Kotlin supports lambda expressions and extends standard JDK collections with popular methods from the functional world. This can be used up to Java 6, and therefore on any Android device:

 val nums = listOf(1, 2, 3, 4) val r = nums.map { it * 2 }.sum() // r == 20 

Note that “it” is the automatic name for the lyabmda parameter, which appears if lambda takes exactly one argument. Of course, you can always set a more informative name yourself. So for example it is recommended to do in nested lambdas.

Here `map` is an extension function. Kotlin allows you to add such functions to an arbitrary class, improving the external API. This is similar to the java-based `FooUtils` with static methods, but much more convenient. Function extensions are actively used in the standard library, adding functionality to classes from Java and reducing the amount of interfaces of Kotlin itself.

More advanced example:

 val strs = listOf("fish", "tree", "dog", "tree", "fish", "fish") val freqs = strs.groupBy { it }.mapValues { it.value.size() } println(freqs) // {fish=3, tree=2, dog=1} 

Recursion

In the functional programming paradigm, cyclic code is often conveniently expressed as recursive function calls. In order not to lose in performance, compilers of languages ​​like Haskell use the so-called tail recursion optimization (tail call optimization). This optimization can only work if the recursive call is the last operation in the function, and the Kotlin compiler will even check it for you.

The simplest example: a fixed point of a mathematical function is a value at which the result of a function is equal to its argument. If you want to find a fixed cosine point, then you can transfer the result of the cosine to it in the loop until everything is stabilized. Procedural implementation:

 private fun cosFixpoint(): Double { var x = 1.0 while (true) { val y = Math.cos(x) if (x == y) return y x = y } } 

Very simple: starting from 1.0, we calculate the cosine until the result is equal to the argument.

The same, but through recursion:

 tailrec fun cosFixpoint(x: Double = 1.0): Double { val r = Math.cos(x) return if (x == r) x else cosFixpoint(r) } 

Or even in one line:

 import java.lang.Math.cos tailrec fun f(x: Double = 1.0): Double = if (x == cos(x)) x else f(cos(x))) 

This version should work as fast as the other two, provided that the JIT will guess to optimize the re-call of `Math.cos (x)`.

Currying, partial application and composition

These are the things that necessarily exist in any functional language, although I cannot say that they are very necessary for everyday tasks. Currying splits the function of many variables into a chain of several functions of the same argument. Partial application (partial application) allows you to fix some parameters of the function and get the function with a smaller number of arguments.

Kotlin does not provide such delights “out of the box”, but it is flexible enough so that all this can be elegantly implemented in the funKtionale library:

 import org.funktionale.currying.* val sum2ints = { x: Int, y: Int -> x + y } val curried: (Int) -> (Int) -> Int = sum2ints.curried() assertEquals(curried(2)(4), 6) val add5 = curried(5) assertEquals(add5(7), 12) 

… and…

 import org.funktionale.partials.* val format = { prefix: String, x: String, postfix: String -> "${prefix}${x}${postfix}" } val prefixAndBang = format(p3 = "!") // Passing just the first parameter will return a new function val hello = prefixAndBang(p1 = "Hello, ") println(hello("world")) 

Delayed execution (lazyness)

Kotlin does not belong to the "lazy" languages, that is, the calculations occur where they are described (oops, but it happens in another way!). As far as I know, no common language other than Haskell uses lazy computations by default (lazy-by-default).

Of course, lazy calculations are available through the library. Consider a real example: how not to build a log line, if logging is disabled?

 val loggingEnabled = System.getProperty("log") != null fun log(s: String): Unit = if (loggingEnabled) println(s) fun log(ls: () -> String): Unit = if (loggingEnabled) println(ls()) 

Here the logging function `log` is overloaded - either a string or a function that calculates the string on demand can be passed to it:

 log("now!") log { "calculate me later" } 

In functional programming, it is often convenient to have lists of infinite length, and to work with them "as lazier as possible and parallel". The simplicity of such operations is one of the key features of functional programming in general.

From version 8, Java can also do this, and with it Kotlin:

 val ONE = BigInteger.ONE fun primes(n: Long) = Stream .iterate(ONE) { it + ONE } .filter { it.isProbablePrime(16) } .limit(n) .toList() 

In Java, endless lists are called streams. We construct a lazy list of all positive integers; then choose from them only those that are simple with probability (1 - (1/4) ^ 16) in accordance with the Miller-Rabin test; after that we return the first `n` of them in the form of a regular list. Classic functional programming.

But how fast does it all work?

 repeat(3) { val t = measureTimeMillis { primes(100000) } println("Took $t msec") } 

On my laptop from the second run (with a heated JIT) the calculations took 1.5 seconds.

But the whole point of creating chains of functions without side effects lies in the ease of parallelizing them. Easy movement of the arm pants are turning ...

 fun primes(n: Long) = Stream .iterate(ONE) { it + ONE } .parallel() .filter { it.isProbablePrime(16) } .limit(n) .toArray() 

All we did was put a call to `parallel ()` in our stream. Due to this, all subsequent operations are launched in several threads. Measurements show a threefold increase in performance: just 0.5 seconds. It's not so bad for me!

Software Transactional Memory

Software transactional memory (software transactional memory), or STM, is one way to write parallel code. This technique is well explained in the article by Simon Peyton-Jones, one of the progenitors of Haskell.

Instead of using locks, you write something like:

 var account1 = 5 var account2 = 0 fun transfer(amount: Int) { atomic { account1 -= amount account2 += amount } } 

From the programmer's point of view, everything that happens inside the `atomic` block is executed instantly in one transaction, and there is never a race condition inside. But at the same time, nothing prohibits multiple threads from being in this block at the same time. Very elegant.

The simplest implementation could use one global lock, but that would be incredibly slow. So in reality, the system records all data changes for one stream, and catches conflict situations. In the event of a conflict, the block is restarted. This is well implemented in Haskell.

Kotlin, again, does not directly support STM. But this is never a problem, because through the JVM it has at its disposal such libraries as Scala STM, and even cooler: low-level transaction memory (hardware transactional memory). Wow.

Modern (very modern) Intel chips support a set of extensions called TSX. TSX allows you to create atomic transactions at the level of iron. Changes in RAM are recorded in the cache and the conflicts between threads are monitored by the CPU itself. In the event of a conflict, the CPU cancels the transaction in the calculation that the program will either try again, or use the usual locks. If everything went according to plan, then the caches are synchronized with RAM at once.

Starting with Java 8 “Update 40”, the so-called “RTM locking” is enabled by default ^[1] for compatible processors. It magically transforms every synchronized block in Java into a low-level transaction with TSX. And this means that now your code is actually executed in parallel. The JVM additionally profiles the application to find blocks that are often restarted, and converts them back to standard locks. Since Kotlin works on the JVM, it all works automatically.

This allows you to write all the critical code in one large block of synchronization and not feel significant problems with speed. If you have the latest iron, of course.

But there are limitations - STM provides additional software features, such as stopping / restarting / canceling a block. TSX cannot, or more precisely, the JVM doesn’t support it at the moment. So if you need more control, you will have to connect transactional variables:

 import scala.concurrent.stm.japi.STM.* val counter = newRef(10) try { atomic { increment(counter, 1) println("counter is ${counter.get()}") // -> 11 throw Exception("roll back!!") } } catch(e: Exception) { println("counter is ${counter.get()}") // -> 10 } 

Haskell has another elegant focus - its type system ensures that transaction variables are available exclusively inside the synchronization block, which will not let you forget about multithreading, no matter how much you want it. Something similar can be done in Kotlin:

 class ThreadBox<T>(v: T) { private val value = v @Synchronized fun locked<R>(f: T.() -> R): R = value.f() } val bank = ThreadBox(object { val accounts = intArrayOf(10, 0, 0, 0) }) fun transfer(from: Int, to: Int, amount: Int) { bank.locked { accounts[from] -= amount accounts[to] += amount } } 

"ThreadBox" is a class that stores a `private` pointer to an arbitrary object" value ". Thus, if there are no external links to this object, it can only be used via the TreadBox. When declaring the object “bank”, “object-expresion” is used to create a nameless object and transfer it to the ThreadBox constructor, which guarantees the absence of external references to the object. And ThreadBox, in turn, returns a pointer only inside the “locked” method, protected by the `@ Synchronized` annotation.

Kotlin syntax does not provide a way to use the “accounts” array outside the synchronization block ... only if the link to it has not gone out. So this is not such a harsh defense as in Haskell, but after all, it only takes three lines of code.

On Github, I laid out a more sophisticated version of the same idea, preventing more errors.

What is not in Kotlin

At the moment the development of the language (M14) there is no way to control the side effects, which may be important when creating some classes of applications.

Also, there is still no “native” library for high-performance, immutable data structures. This contrasts with Clojure and Scala, where such structures are embedded in the languages ​​themselves. The most interesting thing would be to make a much more productive implementation for Kotlin (compared to Scala / Clojure), if we use the recently published CHAMP algorithm.