Функ­ци­ональ­ное прог­рамми­рова­ние: не­замет­ная ре­волю­ция

25 декабря 2019
Функциональное программирование: незаметная революция

«Будущее – за функциональным программированием!». Такие громкие заявления время от времени звучат в сообществе программистов уже десятки лет. На практике в рейтинге популярности, если взять индекс PYPL* царствуют Java, JS, C/C#/C++, Python. Их сложно назвать функциональными. Erlang, Haskell, Idris, Elm и Clojure остаются за пределами топ-10. Однако, элементы функционального программирования постепенно появляются в императивных языках. Поговорим с Константином Некрасовым, Lead Software Engineer, о том, что такое функциональное программирование, и почему функциональный стиль пригодится любому программисту.


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

Более того, есть еще один процесс, который можно условно назвать «конвергенцией»: мы даже не заметили, как элементы функциональных языков стали нормой в языках императивных. Так, программисты C++ теперь знают, что такое лямбда-функция, любой мало-мальски модный язык обязательно продемонстрирует элегантность Pattern matching’а, а веб-разработчик прочитает вам лекцию о пользе «иммутабельности» при написании UI. В этом свете знакомство с чисто функциональным языком программирования даст вам фору как программисту.

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

Функциональное программирование родилось из математического аппарата Алонзо Чёрча под названием лямбда-исчисление. В основе императивных языков программирования лежит другой математический аппарат – машина Алана Тьюринга. В каком-то смысле это два противоположных подхода: один математичен, но про него известно, что он в любом случае представим в виде набора инструкций ассемблера; второй же показывает, что существует такой ассемблер, с помощью которого можно решать задачи математики. Второй подход интуитивно понятен, но в этом и заключается проблема: на каком-то этапе мы обязательно упираемся в возможности нашего мозга. Например, многопоточное приложение отличается от однопоточной версии кардинально; и количество возможных (в том числе неявных) состояний приложения неизменно растет. Функциональный стиль декларативен, благодаря чему у программиста по крайней мере есть шанс не скатиться в перебор крупинок при создании условного космического корабля.

Выделим 4 ключевых отличия функционального подхода от императивного:

  1. Стилистически мы описываем проблему и изменения, которые ожидаем увидеть, а не даем пошаговые инструкции исполнителю.
  2. У нас нет глобального состояния и нет переменных.
  3. Нет нужды беспокоиться о последовательности выполнения шагов. Всё приложение есть функция, порядок вычисления которой волен определять компилятор.
  4. Мы стремимся использовать чистые функции. Такие функции понятны (в том числе компилятору; при желании он их заменит на table lookup), легко компонуемы, а главное – модульны (т.е. их можно легко протестировать вне остальной системы).

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

Пример: задача из Advent of Code 2019

Рассмотрим в качестве примера решение одной задачи с конкурса Advent of Code 2019 на языке Haskell. Мы не претендуем на элегантность данного решения, но, как нам кажется, на примере гораздо легче оценить функциональный подход к решению задач.

Упрощенно условие задачи выглядит так:

На входе дается последовательность целых чисел, разделенных переносом строки. Каждое число – масса одной из вещей в багаже. Требуется вычислить, сколько единиц топлива потребуется для перевозки каждого из грузов и вывести сумму таких чисел. Правило подсчета количества топлива выглядит следующим образом: массу вещи нужно поделить на 3 с округлением в сторону уменьшения и вычесть 2.

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

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

Приведем решение и разберем, как оно работает.

module Main where

import Lib (getNumbers, toModule, fuelRequirements)

main :: IO ()
main = do 
  contents <- getContents
  let modules = sum $ map fuelRequirements $ getNumbers contents
  putStrLn $ show modules

Файл Main.hs

Функция main в модуле Main, очевидно, является входной точкой в приложение; название этой функции и сигнатура подчиняются «правилам игры» языка Haskell. getContents – это функция стандартной библиотеки, она полностью вычитывает stdin и возвращает весь поток входных символов как строку в «контейнере» IO. Стрелка <- нам в данном случае «распаковывает» строку из контейнера IO и делает contents уже просто строкой (да, автор дает себе отчет, что это очень сильное упрощение, но что на самом деле такое IO и do-нотация, мы обсудим в следующих статьях).

Функция sum возвращает сумму элементов списка, а функция map применяет первый аргумент (функцию) к каждому из элементов списка и возвращает преобразованный список (т.е. семантика аналогична map-ам в JavaScript или в Kotlin). Оператор $ служит для указания приоритета вычислений и его можно понимать как открывающую скобку (на самом деле, это тоже функция, но в данном примере это несущественная деталь).

Все самое интересное нас ждет в модуле Lib.

module Lib
    ( getNumbers
    , toModule
    , moduleSeq
    , fuelRequirements
    ) where

getNumbers :: String -> [Int]
getNumbers s = map toInt $ lines s
  where 
    toInt :: String -> Int
    toInt = read

toModule a = (a `div` 3) - 2
moduleSeq a = b:(moduleSeq b)
  where b = toModule a

fuelRequirements v = sum reqs
  where reqs = takeWhile (\a -> a > 0) t
        t = moduleSeq v

Файл Lib.hs

getNumbers, как нам подсказывает сигнатура, превращает одну строку в список целых чисел. Для этого строка сначала разбивается по символам \n на множество строк (см. функцию lines), и к каждой строке в этом списке применяется «наша» функция toInt, которая есть ничто иное, как функция read, специфицированная для типа Int. Дело в том, что здесь мы имеем дело с параметрическим полиморфизмом: функция read определена сразу для множества типов, т.е. формально одна и та же функция read может служить как для отображения строк в числа (String -> Int), так и в, скажем, булевы значения (String -> Bool). Поскольку из сигнатуры «нашей» функции toInt компилятор может однозначно понять, какая требуется сигнатура read, то и сама функция будет использована правильная.

Тело функции toModule говорит само за себя; отметим, что тип этой функции мы не описываем явно: компилятор сам в состоянии вывести тип аргумента a из тех функций, которые мы используем внутри toModule.

В moduleSeq мы впервые видим функцию «двоеточие». Она конструирует список по принципу «слева элемент, справа хвост списка». То есть 1:[] создаст список [1], 2:1:[0] создаст [2,1,0] и т.д.

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

Например, toModule от 4000 построит список [1331,441,145,46,13…]. Как далее видно в fuelRequirements, из всего этого бесконечного списка нас будут интересовать только неотрицательные элементы (см. takeWhile), которые и будут участвовать в конечном решении.

Бесконечные списки – очень мощный и выразительный инструмент Haskell. Слово «бесконечный» здесь не должно смущать читателя: благодаря «ленивости» языка (т.е. ни одно значение не будет вычислено до тех пор, пока оно не потребовалось), такие структуры доступны и удобны в использовании. Кроме этого, для списков существуют т.н. list comprehensions, с помощью которых можно описывать недетерминированные вычисления. Вкупе с ленивыми вычислениями такие списки позволяют динамически строить последовательности элементов, удовлетворяющие заданным критериям. В этом месте можно прийти к мысли, что граница между структурой данных и функцией (т.е. то, что можно вычислить) становится совсем размытой. Правда, это уже предмет для совсем другого разговора.

*Индекс PYPL

Хотите попробовать свои силы на крупных международных проектах для мировых брендов? Присоединяйтесь к дружной и профессиональной команде разработчиков DSR Corporation.

Что почитать:

Что посмотреть: