Функциональное программирование — то, что вам (наверно) рассказывали. Если вы слушали16.03.2020 10:03

Мне нравятся разговоры на тему «мне раньше в школе/институте/родители говорили, а теперь я узнал». Если по счастливой случайности я оказываюсь хоть немного компетентен в обсуждаемом вопросе, то такие разговоры обычно сводятся к одному из трех вариантов: «где вообще ты раньше слышал такую чушь?» (если собеседник прав), «а с чего ты взял, что это так?» (если он не прав) и «ты прав, только это не противоречит тому, что тебе говорили раньше» (в подавляющем большинстве случаев). Нравятся такие разговоры мне по следующей причине: обычно их инициатор не обременен излишним предварительным знанием вопроса, что в некоторых случаях позволяет ему указать на некоторые моменты, которые принимались как очевидные, на самом деле таковыми не являясь. И одной из тем для подобных бесед оказалось функциональное программирование.

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

На сколько это соответствует истине?

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

Итак, к сути.

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

Поскольку для понимания явления обычно полезно ознакомиться с историей его происхождения, вспомним рамочно важные для нашего вопроса моменты истории теории вычислений и программирования. В конце девятнадцатого — начале двадцатого века произошла существенная перестройка фундамента математической науки. Это не только решило ряд выявленных проблем и противоречий, закравшихся в самое нутро имевшихся на тот момент представлений о том, что есть математика и математическое доказательство, но и поставило ряд новых вопросов. Одним из них был следующий: что есть алгоритм. Или, что то же самое, какой класс задач может быть разрешен чисто механически. Не буду распространяться, почему этот вопрос оказался важным, лучше сразу перейду к ответу, который на него дал широко известный в не очень узких кругах Алан Тьюринг. Он сформулировал тезис: «вычислимыми являются только такие функции, для которых можно построить машину Тьюринга». Это утверждение бездоказательно. То есть фактически Тьюринг просто дал строгое формальное определение того, что считать вычислимой функцией, согласующееся с теми интуитивными представлениями, которые обычно вкладываются в это понятие. Такое определение оказалось способно удовлетворить прикладников, поскольку они хорошо представляют себе, что такое машина, пусть даже с бесконечной лентой, и как она должна функционировать. А вот многих математиков такое определение не слишком удовлетворило. Видимо, понятия, которыми оперировал Тьюринг, показались им недостаточно… абстрактными. В связи с этим они предпринимали попытки дать иное определение, которое охватывало бы больший класс математических функций и при этом все еще соответствовало нашим интуитивным представлениям. Данные попытки оказались бесплотными. Каждое альтернативное определение, которое было предложено и выдержало критику, оказывалось эквивалентным определению Тьюринга в том смысле, что описывало ровно тот же класс математических функций. Однако данные исследования отнюдь не были бесполезными. Попытки посмотреть на объект исследования с другой точки зрения вообще редко бывают бесполезными. В нашем случае это привело к появлению нескольких теорий, одной из которых было предложенное Алонзо Черчем лямбда-исчисление.

Лень — двигатель прогресса

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

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

fibonachi2 a b = a : (fibonachi2 b (a+b))
fibonachi = fibonachi2 1 1

nfibonachi n = take n fibonachi

def fibonachi2(a, b) :
    return [a] + fibonachi2(b, a+b)

def fibonachi() :
    return fibonachi2(1, 1)

def nfibonachi(n) :
    res = []
    data = fibonachi()
    for i in range(n) :
      res.append( data[i] )
    return res

Функция fibonachi (а это именно функция) порождает бесконечный список чисел. Если бы мы использовали привычную нам модель вычислений, то nfibonachi никогда не могла бы завершиться (что, напомню, вполне допустимо и не противоречит представлениям о ее «вычислимости»). Но если мы используем «ленивую» модель вычислений, то легко заметить, что как только n принимает конкретное значение, для получения значения функции nfibonachi нам требуются только первые n элементов списка, являющегося результатом функции fibonachi. В этом случае мы можем действовать так: получили элемент списка — провели редукцию, следующий элемент — еще шаг редукции, n-й аргумент — редукция привела к получению значения функции. То есть в этом случае мы получаем результат за конечное время не смотря на «зацикленность» процедуры построения списка чисел Фибоначчи.

Здесь особенно рьяный императивно настроенный читатель воскликнет:»Но постойте, только откровенный идиот станет реализовывать построение списка чисел Фибоначчи таким образом! Есть же очевидные решения, не приводящие к зацикливанию». И он, конечно, будет прав. Тупой перенос решения, предполагающего выполнение в рамках модели «ленивых» вычислений, в программу для «жадных» вычислений действительно не является показателем большого ума. Если предложить данную задачку программисту, который всю свою профессиональную жизнь хранил верность, скажем, языку C, то он скорее всего предложит вариант с одним циклом со счетчиком и двумя переменными состояния.

Но ведь дело не в самих числах Фибоначчи. Дело в том, что правило построения последовательности в данном примере отделено от способа обработки его элементов. А это — полезное свойство, которое желательно иметь возможность воспроизводить в более сложных случаях, когда элементы обрабатываемой последовательности порождаются довольно сложным образом и простой перенос решения «в лоб» для последовательности Фибоначчи на данный случай оказывается неэффективным по времени, по памяти, либо просто приводит к коду, понимание которого недоступно для простого смертного. Такое стремление естественно и может быть реализовано, например, через использование итераторов или генераторов. В питоне, например, мы можем сделать так:

def fibonachi() :
    a = 1
    b = 1
    yield a
    yield b
    while True :
      c = a + b
      yield c
      a = b
      b = c
     
def nfibonachi(n) :
    return [e for e in itertools.islice(fibonachi(), n)]

Здесь fibonachi () — генератор, который создает последовательность элемент за элементом. И в данном случае вместо fibonachi может стоять функция-генератор любой сложности. Если привести код полностью, включая подкапотный код генератора, то получим весьма сложную и полностью императивную программную конструкцию. Но окончательный вариант вполне себе «функциональный». В C++ можно было бы провернуть аналогичный трюк, заведя специальный класс Fibonachi и итераторы для него. Решение будет меняться в зависимости от особенностей языка программирования и предпочтений программиста, но цель останется общая — разделить на уровне организации программы способ построения последовательности заранее неизвестной длины и способ обработки ее элементов.

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

Чистота — залог здоровья

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

Причина того, что все функции в функциональной программе должны соблюдать чистоплотность, проста. Если допустить наличие этих самых побочных эффектов, то получится, что порядок, в котором аргументы функции получают свое значение, прямо влияет на результат функции. Можно сказать, что и в рамках императивного подхода это так, но в случае «ленивости» вычислений все намного хуже. Даже если мы допустим, что аргументы функции могут быть вычислены независимо друг от друга в произвольном порядке, то «ленивость» все равно предполагает, что (условно) не весь код функции будет исполнен в один присест. Исполняться он будет по частям в зависимости от двух вещей — собственно, структуры функции, которую нам любезно предоставит условный компилятор, и того порядка, в котором мы будем предъявлять функции ее аргументы.

Для нас естественно ожидать, что если мы сначала определили функцию

def f(x,y) :
  ...

а после нее

def g(x, y) :
  return f(y, x)

то результат вызова g (a, b) окажется равным результату вызова f (b, a) для любых независимо вычислимых значений a и b. Но если f имеет побочные эффекты, влияющие на вычисление значений аргументов, то наши ожидания могут быть жестоко обмануты. Например, при вычислении b происходит чтение из файла — и при вычислении f тоже происходит чтение из того же файла. В «ленивых» вычислениях мы заранее не знаем то, какая часть кода (для b или для f) будет выполнена первой. А значим не знаем и того, какой результат даст программа даже если знаем содержание файла, который она должна прочитать. Такое поведение в принципе недопустимо и потому должно быть категорически исключено. А значит, в рамках модели «ленивых» вычислений (неконтролируемые) побочные эффекты у функции должны быть запрещены.

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

Следовательно, имевший место тезис

Функциональная программа — программа, состоящая из чистых функций

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

Однако есть проблема. Возможность сохранения состояния и даже банальный ввод-вывод — это вещи, напрямую связанные с побочными эффектами. И жизнь без них полна боли и страданий. Возникает вопрос: как поженить побочные эффекты и «ленивые» вычисления? Ответ в общем — никак. Ответ правильный — в каждом частном случае следует искать удовлетворительное частное решение. Вышло так, что многие способы воспроизведения вычислений с побочными эффектами без нарушения концепции «чистоты» вычислений укладываются в общее понятие монады, позаимствованное из теории категорий. Мне бы не хотелось в очередной раз пытаться объяснять, что это такое и с чем его едят хотя бы потому, что в любом случае это не заменит, а по моему опыту даже не упростит, объяснение того, как конкретно можно реализовать переменные состояния, исключения и подобные вещи в «чистых» функциональных языках. Главная мораль в том, что императивное программирование является источником вдохновения для функционального так же, как и функциональное для императивного. Причем иногда идея проходит через конкурирующую концепцию как через фильтр, возвращается назад в измененном виде и приводит к появлению нового инструмента.

Нужны ли монады в императивном мире? У меня нет устоявшегося мнения по данному вопросу. Автор этого поста уверен, что нужны. Я склонен усомниться в данном утверждении, поскольку польза использования понятия монады в функциональных программах обычна связано с тем, что некоторый алгоритм можно сформулировать безотносительно того, какие конкретно побочные эффекты данная монада скрывает. Иными словами, если пользовательский (гипотетический, еще не созданный человечеством) тип данных удовлетворяет требованиям, которые предъявляются к монаде, то записанный алгоритм для него отработает корректно. Это удобно прежде всего в теоретических изысканиях. Но есть пара нюанса. Во первых, не слишком понятно, зачем прятать в обертку побочные эффектны в языках, для которых они являются естественным явлением. Во вторых, при написании конкретных программ с конкретными типами данных и конкретной целевой архитектурой такой обобщенный алгоритм чаще всего вынужденно подвергнется реструктуризации с целью повышения производительности. Написание обощенных алгоритмов с использованием монад в императивном стиле возможно, но целесообразность такого подхода вызывает у меня сомнения. То, что некий аналог Maybe типа std: optional из C++ объявят монадой, вряд ли как-то повлияет на практику его использования.

Кто наблюдает за наблюдателями?

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

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

В качестве функции высшего порядка обычно приводят map или fold. Но мы рассмотрим более тривиальную — любую  — функцию двух аргументов f (x, y). В рамках модели «ленивых» вычислений аргументы данной функции будут вычислены только тогда, когда действительно понадобятся. Допустим, что первым понадобился аргумент x. Вычислим этот аргумент, предоставим его значение f и, кроме того, вычислим все, что можем вычислить без использования значения аргумента y. Тогда остаток вычислений вполне можно представить как новую функцию, уже от x не зависящую — например, g (y). Но в таком случае ничто не мешает нам формально представить f не как функцию двух аргументов, а как функцию одного аргумента f (x), результатом которой будет другая функция g (y). Иными словами, в рамках функционального подхода любая функция N>1 аргументов является функцией высшего порядка, поскольку может быть интерпретирована, как функция одного аргумента, результатом которой является функция N-1 аргументов.

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

def partial(f, x) :
	def g(*args) :
		return f(x, *args)
	return g

Вызвав функцию partial, первым аргументом которой является функция N аргументов, а вторым — значение первого ее аргумента, мы получаем функцию N-1 аргумента. Теперь новую функцию мы можем использовать везде, где можно использовать функцию N-1 аргументов. То есть получили то же самое, что и в функциональной программе. Так? Нет, не так. Если бы мы имели дело с действительно функциональной программой, то при вызове partial произошло бы вычисление всего того, для чего нужно значение первого аргумента. В некоторых случаях вообще бы получилось, что g — константное значение. Что мы имеем в императивном аналоге? Переданное значение аргумента x просто запоминается (добавляется в контекст функции g). Когда мы вызовем g, значение x будет вынуто из закромов и просто подставлено в f. То есть разницы в форме нет, а вот в содержании — существенная.

Использование функций от функций удобно, поскольку позволяет естественным образом описать многие важные алгоритмы. Значит, они обязаны были появиться в императивных языках программирования. И появились. Но поскольку в них используется другая модель вычислений, это должно было потребовать разработки новых концепций. И они были разработаны. Например, описанное выше замыкание. То есть функции высших порядков в императивных языках соответствуют тому, что можно наблюдать в языках функциональных, только внешне. Но содержание совсем иное. Важно ли это программисту? Вероятно нет, но только если он хорошо понимает, как работают те механизмы, которые реализуют такие возможности в его любимом языке программирования. Иначе можно, например, реализовывать «частичное применение» и замкнуть при построении новой функции (ну или того, что в вашем случае будет выглядеть как функция) ссылку вместо значения и получить интересное поведение программы. И после этого кричать об ущербности функционального подхода.

Так кто кого обманывал?

На этом этапе изложения вполне можно поставить точку с запятой и вернутся к основному вопросу. Поскольку теперь можно сформулировать следующие утверждения:

• Основным отличием функционального программирования от императивного является не свойство чистоты функций, не наличие безымянных функций, функций высших порядков, монад, параметрического полиморфизма или чего-бы то ни было еще. Основным отличием является использование иной модели вычислений. Все остальное — не более чем следствия.
• Свойства, которые естественным образом присутствуют у программ на функциональных языках, вполне можно воспроизвести в рамках императивного подхода. Причем очень разными средствами. Иногда даже на уровне компилятора, что сделает не отличимыми по форме «функциональную» и «нефункциональную» программы. Это прямое следствие того, что в рамках функционального и императивного подходов может быть реализовано ровно одно и то же множество математических функций. Тьюринг сказал.
• Полезные свойства программ, являющиеся естественными в рамках императивного подхода, но не являющиеся таковыми в рамках подхода функционального, тем не менее могут и должны быть реализованы в функциональных языках. Для этого вводятся в рассмотрение всякие дополнительные абстракции. В частности — монады.
• ООП не противоречит функциональному программированию просто потому, что никак с ним не связано. Функциональное программирование декларирует способ построения процесса вычислений, из которого проистекают все достоинства и недостатки «функциональных» программ; ООП определяет концепции, в соответствие с которыми должна проектироваться программа. Противопоставление данных терминов совершенно искусственно и всегда основано на сравнении того, как реализованы концепции ООП в каком-то конкретном языке программирования с тем, как записать ООП-программу данного языка на конкретном языке функциональном. Такое сравнение попахивает неадекватностью.
• Изучение функционального программирования необходимо, если вы хотите иметь более полную картину о возможных подходах к построению алгоритмов и организации процесса вычислений. Это как минимум источник решений, совершенно не очевидных в рамках привычных императивных представлений. Если, конечно, вы не обладаете присущим со всей очевидностью автору сего полета мысли сакральным знанием о том, как в каждой представимой ситуации при решении задачи любой сложности оптимальным образом спроектировать программную систему и какие инструменты и подходы следует использовать для реализации каждого ее компонента. Менее просветленным умам избыток подобных знаний вряд ли нанесет урон.

Функциональное программирование — это то, о чем вам (наверно) рассказывали. Это бета-редукция, комбинаторы неподвижной точки, монады, типизация Хиндли-Милнера и многое другое. Не надо путать обертку с содержанием. ФП базируется на не самой простой математике, не может быть освоено в течение пары вечерков за рюмкой чая; оно вряд ли сможет быть непосредственно спроецировано на ваши насущные проблемы и проекты, гарантированный и быстрый профит от этих знаний вы не получите. Но многие элементы того, что есть в функциональном подходе, заимствуются, перерабатываются и в конечном счете реализуются в языках программирования, ориентированных на разработку больших проектов. Да, они устроены иначе, чем их функциональные предки, но это не делает их менее полезными. Только клинический идиот будет на серьезных щах вещать о том, что хаскель — плохой язык, потому что на нем сложно написать программу для какого-нибудь бухучета. Человек, обремененный наличием интеллекта, даже с позиций своей профессиональной деятельности, без глубокого погружения в хитросплетения теории вполне способен понять, какие именно практики из функционального программирования стоит перенять для того, чтобы сделать свой код лучше. За убедительную демонстрацию чего выражаю благодарность PsyHaSTe.

Изучайте функциональное программирование. Во имя себя.

© Habrahabr.ru