Kotlin ❤ FP

Предлагаю читателям «Хабрахабра» вольный перевод статьи «Functional programming in Kotlin». Автор публикации — Mike Hearn.



Те, кто используют .NET, наверняка слышали про F#, универсальный функциональный язык программирования для CLR. Программисты же вне .NET сообщества скорее всего знают про функциональное программирование в связи с языком Haskell.

Так или иначе, я подозреваю что многим пришелся бы по душе схожий язык, но для JVM, с развитыми инструментами и без необходимости делать все подряд в функциональном стиле.

Язык Kotlin (kotlinlang.org) от JetBrains может показаться всего лишь подслащенной Java: синтаксические конвенции, автовывод типов (type inference) и тому подобные мелочи. Но под незамысловатой оболочкой в нем можно найти все самые популярные и прогрессивные конструкции функциональных языков.

Начнем с несложных примеров типичных функциональных конструкций.

Алгебраические типы данных

Подобный синтаксис весьма типичен для большинства функциональных языков:

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

Это Haskell, и тут определён тип «Maybe», который имеет два конструктора: «Nothing» и «Just». Конструктор Just принимает единственный параметр неопределенного типа. Ключевое слово «deriving» автогенерирует код для сравнения объектов типа и проверки их на равенство.

В Kotlin не нужен класс Maybe, так как возможность вернуть или не вернуть значение уже изначально заложена в его систему типов. Опциональность результата так часто встречается в программах, что ее имеет смысл поддерживать в самой основе языка. Это добавляет как удобства, так и производительности:

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

Здесь не скомпилируется вторая строчка, так как мы пытаемся вычислить длину строки, которой у нас может и не быть. Чинится это несложно:

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

Конструкция «s?.length()» возвратит `null` если строка была `null`, а оператор "?:" вернет свою правую часть когда слева стоит `null`. То есть код распечатает `-1`, если строки вдруг все же нету.

В Kotlin имеется полный набор средств для работы с `null` типами, можете не сомневаться. Но не будем об этом ради краткости изложения.

Вместо этого давайте определим аналог Maybe в Kotlin, просто для иллюстрации.

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

Синтаксис конечно не такой краткий как в Haskell, но тоже вполне приемлем. Модификатор «data» опционален, однако он добавляет несколько полезных плюшек.

Всё работает без сюрпризов:

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

Здесь мы определяем Just, содержащий число (Int) внутри, а потом извлекаем число обратно. Замете, ни один тип ни разу не упомянут: они все выведены автоматически. Если бы в Just было бы несколько полей, можно бы было извлечь их все, что на самом деле и является предназначением этой конструкции:

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

А как же сопоставление образцу (pattern matching)? Это именно то, для чего нам было нужно ключевое слово «sealed». С ним компилятор знает, что других подклассов Maybe кроме Just и None быть не может, и при ветвлении по всем вариантам не требуется ветка «else»:

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")
    }
}

Выше определен простой класс с единственным неизменяемым полем «age». Метод «lookupFromDB» имитирует доступ к базе данных и возвращает `Maybe`. В нашем случае всегда None, но это не более чем пример.

После этого возвращенное значение сопоставляется с типами при помощи оператора «when». Конструкция `when` позволяет делать множество вещей. В частности, после успешного сопоставления аргумента с типом, внутри правой части аргумент меняет свой тип соответственным образом. Именно поэтому в правой части второй ветки мы можем использовать поле «t» класса `User` без лишних церемоний.

Неизменяемость данных (Immutability)

Kotlin не является чисто-функциональным языком, поэтому неизменяемые объекты сосуществуют с изменяемыми на равных правах. Дизайн ненавязчиво подталкивает программиста к использованию неизменяемых объектов, но в целом выбор каждый раз остается за разработчиком.

Например как тут:

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

Здесь «p» это неизменяемое значение (value). Похоже на `final variable` в Java, или `let` в Haskell/F#. Но вот содержимое этого объекта состоит из изменяемых переменных (variable), поэтому их можно переприсваивать. Подсветка в IDE помогает различать изменяемые и неизменяемые поля.

Тот же пример, но теперь все ссылки неизменяемые:

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

Копирующий метод для `data` классов создается автоматически. На каждое поле класса он имеет именованный параметр, по умолчанию равный текущему значению. В результате его удобно использовать для создания новых «подправленных» объектов.

Списки по умолчанию неизменяемы:

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()

Вторая строка не скомпилируется: `listOf()` возвращает неизменяемый список. А вот в четвертой строке все в порядке, так как мы специально попросили `ArrayList`, который можно менять. Разумеется, любой список всегда можно привести к неизменяемуму интерфейсу `List` и создать «read-only view».

На данный момент в языке нету встроенного синтаксиса для списков, поэтому для их создания используются функции с переменным числом аргументов.

Mapping, filtering, reducing и прочие вкусности

Kotlin поддерживает лямбда-выражения и расширяет стандартные JDK коллекции популярными методами из функционального мира. Это можно использовать вплоть до Java 6, а значит и на любом Android устройстве:

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

Обратите внимание что «it» это автоматическое имя для параметра лябмды, которое появляется если лямбда принимает ровно один аргумент. Разумеется, всегда можно задать более информативное имя самостоятельно. Так например рекомендуется делать во вложенных лямбдах.

Тут `map` является функцией-расширением (extension function). Kotlin позволяет добавлять такие функции к произвольному классу, улучшая внешние API. Это похоже на java-вские `FooUtils` со статическими методами, но гораздо удобнее. Функции-расширения активно используются в стандартной библиотеке, добавляя функциональность классам из Java и уменьшая объем интерфейсов самого Kotlin.

Более продвинутый пример:

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}

Рекурсия

В функциональной парадигме программирования циклический код часто удобно выражать в виде рекурсивных вызовов функций. Чтобы не терять в производительности, компиляторы языков типа Haskell используют так называемую оптимизацию хвостовой рекурсии (tail call optimisation). Эта оптимизация может работать только если рекурсивный вызов является последней операцией в функции, и компилятор Kotlin даже проверит это за вас.

Простейший пример: неподвижная точка математической функции это значение, при котором результат функции равен её аргументу. Если вы хотите найти неподвижную точку косинуса, то можно в цикле передавать результат косинуса в него же, пока все не стабилизируется. Процедурная реализация:

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

Очень просто: начиная с 1.0 мы вычисляем косинус пока результат не сравняется с аргументом.

То же самое, но через рекурсию:

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

Или даже в одну строчку:

import java.lang.Math.cos

tailrec fun f(x: Double = 1.0): Double = if (x == cos(x)) x else f(cos(x)))

Эта версия должна работать так же быстро как и остальные две, при условии что JIT догадается оптимизировать повторный вызов `Math.cos(x)`.

Каррирование, частичное применение и композиция

Эти те вещи, которые обязательно есть в любом функциональном языке, хотя я не могу сказать что они очень-то нужны для повседневных задач. Каррирование (currying) разбивает функцию многих переменных в цепочку нескольких функций одного аргумента. Частичное применение (partial application) позволяет зафиксировать некоторые параметры функции и получить функцию с меньшим количеством аргументов.

Kotlin не предоставляет такие изыски «из коробки», но он достаточно гибок, чтобы все это можно было элегантно реализовать в библиотеке funKtionale:

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)

… а также…

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"))

Отложенное исполнение (lazyness)

Kotlin не относится к «ленивым» языкам, то есть вычисления происходят там, где они описаны (опа, а бывает и по другому!). Насколько мне известно, ни один распространенный язык кроме Haskell не использует ленивые вычисления по умолчанию (lazy-by-default).

Разумеется, ленивые вычисления доступны через библиотеу. Рассмотрим реально встречающийся пример: как не компоновать строку лога, если логирование отключено?

val loggingEnabled = System.getProperty("log") != null

fun log(s: String): Unit = if (loggingEnabled) println(s)

fun log(ls: () -> String): Unit = if (loggingEnabled) println(ls())

Здесь функция логирования `log` перегружена — в нее можно передать либо строку, либо функцию, которая вычислит строку по требованию:

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

В функциональном программировании часто удобно иметь списки бесконечной длины, и работать с ними «как можно ленивее и параллельнее». Простота таких операций это одна из ключевых особенностей функционального программирования в целом.

С версии 8 Java тоже так может, а вместе с ней и Kotlin:

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

В Java бесконечные списки называются потоками (streams). Мы конструируем ленивый список всех положительных целых; затем выбираем из них только те, которые просты с вероятностью (1 — (1/4)^16) в соответствии с тестом Миллера — Рабина; после этого мы возвращаем первые `n` из них в виде обычного списка. Классическое функциональное программирование.

Но на сколько быстро это все работает?

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

На моем ноутбуке со второго запуска (с разогретым JIT) вычисления заняли 1.5 секунды.

Но вся соль создания цепочек функций без побочных эффектов таится в легкости их распараллеливания. Легким движение руки брюки превращаются…

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

Все что мы сделали это вставили вызов `parallel()` в наш поток. Благодаря этому все последующие операции запускаются в несколько потоков. Измерения показывают трехкратное увеличение производительности: всего 0.5 секунды. По мне так совсем неплохо!

Software Transactional Memory

Программная транзакционная память (software transactional memory), или STM, это один из способов писать параллельный код. Эта техника хорошо объяснена в статье Саймона Пейтон-Джонса, одного из прародителей Haskell.

Вместо использования блокировок вы пишите что-то вроде:

var account1 = 5
var account2 = 0

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

С точки зрения программиста, все, что происходит внутри блока `atomic`, исполняется мгновенно одной транзакцией, и внутри никогда нету гонки потоков (race condition). Но в тоже время ничего не запрещает нескольким потокам быть в этом блоке одновременно. Весьма элегантно.

Простейшая реализация могла бы использовать одну глобальную блокировку, но это было бы невероятно медленно. Так что в реальности система записывает все изменения данных для одного потока, и ловит конфликтные ситуации. В случае конфликта блок перезапускается. Это неплохо реализовано в Haskell.

Kotlin, опять же, не поддерживает STM напрямую. Но это ни разу не проблема, так как через JVM он имеет в своем распоряжении такие библиотеки как Scala STM, и даже круче: низкоуровневую транзакционную память (hardware transactional memory). Wow.

Современные (очень современные) чипы от Intel поддерживают набор расширений, называемых TSX. TSX позволяют создавать атомарные транзакции на уровне железа. Изменения в RAM записываются в кеш и конфликты между потоками отслеживает сам CPU. В случае конфликта CPU отменяет транзакцию в расчете что программа либо попробует еще раз, или воспользуется обычными блокировками. Если все прошло по плану, то кеши разом синхронизируются с RAM.

Начиная с Java 8 «Update 40», так называемое “RTM locking” включено по умолчанию^[1] для совместимых процессоров. Это волшебно преображает каждый synchronized блок в Java в низкоуровневую транзакцию с TSX. А это значит, что теперь ваш код действительно исполняется параллельно. JVM дополнительно профилирует приложение чтобы найти блоки, которые часто перезапускаются, и преобразует их обратно к стандартным блокировкам. Поскольку Kotlin работает на JVM, в нем все это работает автоматически.

Это позволяет писать весь критический код в одном большом блоке синхронизации и не ощущать значительных проблем со скоростью. Если у вас стоит новейшее железо, разумеется.

Но есть и ограничения — STM предоставляет дополнительные программные возможности, такие как остановка\перезапуск\отмену блока. TSX такого не может, или точнее JVM такое не подерживает на текущий момент. Так что если вам нужно больше контроля, то придется подключить к делу транзакционные переменные (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 есть еще один изящный фокус — его система типов позволяет гарантировать, что транзакционные переменные доступны исключительно внутри блока синхронизации, что не позволит забыть про многопоточность, как бы вам это не хотелось. Нечто подобное можно сделать и в 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» это класс который хранит `private` указатель на произвольный объект «value». Таким образом если на этот объект нету внешних ссылок, он может быть использован только через TreadBox. При объявлении объекта «bank» используется «object-expresion» для создания безымянного объекта и передачи его в конструктор ThreadBox, что гарантирует отсутствие внешних ссылок на объект. А ThreadBox в свою очередь отдает указатель только внутри метода «locked», защищенного аннотацией `@Synchronized`.

Синтаксис Kotlin не даёт способа воспользоваться массивом «accounts» вне блока синхронизации… только если ссылка на него не ушла наружу. Так что это не такая суровая защита как в Haskell, но ведь и занимает она всего три строчки кода.

На Github я выложил более изощренную версию той-же идеи, предотвращающую большее количество ошибок.

Чего в Kotlin нету

На данный момент развития языка (M14) не существует способа контролировать побочные эффекты, что может быть важно при создании некоторых классов приложений.

Так же пока не существует «родной» библиотеки для высокопроизводительных неизменяемых структур данных. Это контрастирует с Clojure и Scala, где такие структуры внедрены в сами языки. Самое интересное, что можно было бы сделать гораздо более производительную реализацию для Kotlin (по сравнению со Scala/Clojure), если воспользоваться недавно опубликованным алгоритмом CHAMP.

UPD 1

Как было замечено grossws, фраза в оригинале статьи

Starting with Java 8 Update 40, so-called “RTM locking” is enabled by default when the CPU supports it.

не согласуется с официальной документацией с сайта Oracle:

-XX:+UseRTMLocking Generate Restricted Transactional Memory (RTM) locking code for all inflated locks, with the normal locking mechanism as the fallback handler. This option is disabled by default.

Я не берусь судить о том, что из этого верно, а что нет, но прошу отнестись к этому моменту с известной долей скептицизма.

docs.oracle.com/javase/8/docs/technotes/tools/unix/java.html
oracle.com/technetwork/java/javase/8u40-relnotes-2389089.html