Всем привет. Последнее время функциональное программирование (далее ФП) стремительно входит в жизнь рядового разработчика. Последние версии даже таких императивных языков как C++ и Java включают механизмы работы с анонимными функциями. Умные люди говорят, что теперь на Java можно писать в функциональном стиле. К сожалению практика показывает, что понимание функционального стиля часто сводится к написанию императивного кода, но с анонимными процедурами. В итоге, с таким “функциональным стилем”, есть риск резко опуститься на дно говнокода.

В этом цикле статей я пробую рассказать что же такое настоящий функциональный стиль и чем он отличается от императивного программирования, в том числе в своей самой распространенной объектно-ориентированном форме. Надеюсь статьи помогут вам решить стоит ли шумиха вокруг ФП того, чтобы начать использовать его у себя в работе, или же наоборот запретить себе и коллегам использовать новомодные “функциональные плюшки”.

Кроме текста будут примеры на Scala. Пока планирую, что статьи будут моим вольным изложением замечательного курса с coursera.org Принципы функционального программирования в Scala, а что получиться на самом деле - покажет время. Надеюсь, будет интересно и полезно. И так, начнем.

Парадигмы программирования

Для начала давайте разберемся что такое парадигма программирования и какие парадигмы бывают. Можно, например, дать такое определение:

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

Очевидно, что парадигма определяет внешний вид и стиль программы, а так же способ мышления программиста. На сегодняшний день широко применяются следующие парадигмы:

  • Императивное программирование
  • Функциональное программирование
  • Логическое программирование

Есть еще всем известное объектно-ориентированное программирование (ООП). Но на мой взгляд парадигмой оно не является, так как по меньшей мере не определяет модель вычислений, хотя включает в себя идеи организации данных и диктует определенный способ мышления (иногда далеко не самый лучший, я считаю). Основные идеи ООП не противоречат идеям перечисленных выше парадигм программирования. Поэтому идеями ООП можно безболезненно дополнить любую из приведенных выше парадигм, например функциональное программирование (как это сделать рассмотрим позже, в следующих статьях).

Давайте теперь осмыслим что из себя представляет всем известное императивное программирование и почему его нам может быть недостаточно.

Старое доброе императивное программирование

Императивное программирование имеет под собой математическую основу в виде расширенной теории автоматов - теории машин Тюринга. Современные языки программирования далеко ушли от машин Тьюринга, но основные принципы никуда не делись. В императивном программировании мы оперируем следующими понятиями:

  • переменные, значения которых можно получить
  • управляющие структуры типа if-then-else, return, циклы
  • присвоение значений переменным

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

Вычисление в императивных программах - это изменение состояния переменных. Работа с переменными, каким бы язык не был, похожа по стилю на работу в самом примитивном императивном языке - ассемблере. Переменные - это ячейки памяти, присвоения и чтения - это сохранение и загрузка значений из памяти, управляющие структуры - переходы (jmp).

В 1978 году Джон Бэкус в своей лекции «Can Programming Be Liberated from the Von Neumann Style?» рассказал миру чем же плох такой подход. Дело оказалось в том, что чистое императивное программирование не позволяет выражать абстрактные понятия. Проектировать, например, интеллект беспилотного автомобиля только в терминах присвоения переменных и условных выражений совсем не просто. В качестве решения этой проблемы Джон Бэкус предложил использовать функциональное программирование. В отличии от других попыток решить проблему, таких как процедуры, структуры и ООП, функциональная парадигма имеет под собой математическое основание и проста логически. Давайте попробуем в этом убедиться.

Функциональная парадигма

В основе ФП лежит лямбда-исчисление А. Черча. Глубоко в теорию лезть не будем, а остановимся на практических следствиях: любое вычисление можно представить как последовательность замен значений аргументов функции на сами аргументы (подстановок). Более формально это выглядит это так:

def f(x1, ... , xn) = B
...
f(v1, ... , vn)

->

def f(x1, ... , xn) = B
...
[v1/x1, ... , vn/xn]B

где

f(x1, ... , xn) - функция от n аргументов,

B - выражение, включающее в себя x1, ... , xn,

[v1/x1, ... , vn/xn]B - выражение B в котором все термы x1, ... , xn заменены на термы v1, ... , vn,

v1, ... , vn - произвольные выражения, в том числе и функции.

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

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

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

Как мы видим ФП проще императивного программирования, но благодаря функциям обладает свойством обобщения (по научному обобщение - это операция лямбда-абстракции). Кроме того теперь понятно, что написание “лямбдочки” в коде на Java 8 не делает код функциональным. Для того, чтобы превратить императивный код в функциональный нужно выразить мысли через совсем другие понятия.

На практике существует мало языков, полностью следующих теории. Одна из причин - практическая сложность применения чисто функциональных языков, например отсутствие возможности сохранить часть вычисления под каким-либо именем (по содержанию это переменная, но не по сути). Но основная проблема заключается в продолжении одного из достоинств ФП - отсутствия у вычислений сайдэффектов. Суть проблемы в том, что обеспечить, например, ввод/вывод только в рамках ФП невозможно. Приходиться либо выносить подобные возможности за рамки языка (как в XSLT), придумывать для ввода/вывода еще одну математическую теорию (Haskell) или забыть про пункт об отсутствии сайдэффектов (Scala, Clojure, Smalltalk, Ruby, JavaScript).

Стратегии вычислений

В предыдущем пункте мы рассмотрели модель подстановки. Но из рассмотрения выпала важная часть - приоритет операций. Предположим у нас есть код:

def loop: Int = loop	// в Scala def - оператор задания функции
                        // после двоеточия указывается тип возвращаемого значения, 
                        // возвращаемое значение иногда можно опускать			

def f(x: Int, y: Int) = x // Функция с аргументами

Теперь мы хотим посчитать значение следующего выражения:

f(1, loop) // вызов функции вернет результат

В Scala возможно две стратегии вычислений, в зависимости от приоритета операции взятия функции (в науке лямбда-абстракции) и подстановки (бэта-редукции):

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

Рассмотрим вызов по значению в нашем примере:

f(1, loop) -> ( 1 остается 1, loop остается loop ) -> f(1, loop) ->
-> ... -> f(1, loop)

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

f(1, loop) -> ( подстановка [1/x] в f(x: Int, y: Int) = x ) -> g() = 1 -> 1

А теперь не зациклилась, такие дела. Теоретически говнокод, зацикливающийся при вызове по значению может дать результат при вызове по имени. Обратное не верно. Как не удивительно на первый взгляд, в Scala по умолчанию используется вызов по значению. Для вызова по имени в объявление типа параметра нужно добавить =>, например def f(x: => Int). Вызов по значению по умолчанию был сделан по соображениям производительности, т.к. авторы посчитали что на Scala будет часто писаться код подобный этому:

def const = 1
def f(x: Int) = x + x + x

f(const)

Очевидно, что при вызове по имени x был бы рассчитан 3 раза:

f(const) -> const + const + const -> 1 + const + const -> 
-> 1 + 1 + const -> 1 + 1 + 1 -> 3

По мнению авторов Scala, вызов по значению производительнее и лучше вызова по имени. Хотя авторы Haskell, например, считают по другому и гордятся своим решением. Я же просто приведу пример кода, в котором вызов по имени быстрее:

def f(x: Int, y: => Int) = x

f(1, verySlowFunction)

Ну вы поняли.

Хвостовая рекурсия

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

Рекурсия - это использование в определении функции своего же имени. На первый взгляд все просто, но для многих, в том числе и для меня когда-то, понимание процессов в рекурсивных программах находится где-то на уровне понимания процессов, происходящих при коллапсе волновой функции в квантовой механике. Для прозрения, на мой взгляд, есть лишь один путь - практика. Поэтому сразу пример:

def gcd(a: Int, b: Int): Int =
        if (b == 0) a else gcd(b, a % b)	// if не оператор, а выражение, 
                                                // возвращающее значение
                                                // % - деление по модулю

Это алгоритм Евклида для нахождения НОД, который уместился в 2 строчки. Давайте посмотрим как он работает.

gcd(14, 21)
-> if (21 == 0) 14 else gcd(21, 14 % 21)
-> if (false) 14 else gcd(21, 14 % 21)
-> gcd(21, 14 % 21)
-> gcd(21, 14)
-> if (14 == 0) 21 else gcd (14, 21 % 14)
->> gcd(14, 7)
->> gcd(7, 0)
-> if (0 == 0) 7 else gcd(0, 7 % 0)
-> 7

Теперь все понятно. Давайте теперь рассмотрим пример нахождения факториала.

def factorial(n: Int): Int =
        if (n == 0) 1 else n * factorial(n - 1)
        
factorial(4)
-> if (4 == 0) 1 else 4 * factorial(4 - 1)
->> 4 * factorial(3)
->> 4 * (3 * factorial(2))
->> 4 * (3 * ( 2 * factorial(1)))
->> 4 * (3 * ( 2 * (1 * factorial(0))))
->> 4 * (3 * ( 2 * (1 * 1)))

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

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

Хвостовая рекурсия - отличный инструмент оптимизации. Давайте попробуем оптимизировать наш пример с факториалом.

def factorial(n: Int) : Int = { 	                // {} - блок кода, любые определения, 
                                                        // сделанные в блоке доступны только в нем
        @tailrec					// Ошибка компиляции, если невозможно оптимизировать
        def loop(n: Int, acc: Int): Int = 
                if (n == 0) acc else loop(n - 1, acc * n)
                
        loop(n, 1)					// результат последнего вычисления равен значению блока
}

Мы просто ввели аргумент-аккумулятор вместо сохранения результата в стековом кадре. Компилятор выполнит оптимизацию автоматически. Полученный байт-код будет принципиально аналогичен коду, полученному из итерации на императивном языке, например на Java (на самом деле это упрощенно, в случае с Java код будет отличаться от цикла, но смысл остается прежним).

Что дальше

На этом можно было бы все закончить, так как фундаментальные концепции ФП мы рассмотрели. Но как известно демон кроется в деталях. В следующих статьях мы рассмотрим функции высшего порядка, ООП, напишем коллекции в функциональном стиле и многое другое. Спасибо за внимание, до новых встреч.