Мне нравятся разговоры на тему «Мне раньше в школе/институте/родителях говорили, а теперь я узнал».
Если по счастливой случайности я оказываюсь хоть сколько-нибудь компетентным в обсуждаемом вопросе, то такие разговоры обычно сводятся к одному из трех вариантов: «где вы раньше слышали такую чушьЭ» (если собеседник прав), «почему ты решил, что это такЭ» (если он не прав) и «вы правы, но это не противоречит тому, что вам говорили раньше» (в подавляющем большинстве случаев).
Мне нравятся такие разговоры по следующей причине: обычно их инициатор не отягощен чрезмерными предварительным знанием вопроса, что в ряде случаев позволяет ему указать на некоторые моменты, которые считались очевидными, но на самом деле таковыми не являются.
И одной из тем таких разговоров оказалось функциональное программирование.
Вообще про ФП столько написано и сказано, что кажется, что все вопросы о его применимости, крутости, производительности и т. д. изъедены до мозга костей.
И тем не менее, такого рода вопросы поднимаются снова и снова, и всегда находится кто-то, кто хочет сказать тебе, что ты все неправильно понял, а на самом деле это вроде ничего.
Пожалуй, сегодня я примерю на себя эту неблагодарную роль, поскольку недавно мне попалось несколько постов на эту многострадальную тему.
В первый И второй В очередной раз сказано, что ФП – это ерунда и изучение его только испортит вашу карму как будущего специалиста.
Другой ( один раз И два ) гораздо более адекватны, в них автор стремится объяснить, что все эти лямбды, комбинаторы, категории — не более чем пыль в глазах, а сам ФП — простая, понятная и приятная вещь в повседневной жизни.
Насколько это правда? Прежде чем перейти к сути вопроса, сделаю небольшое отступление и расставлю акценты.
Содержание первых двух упомянутых постов я считаю откровенным бредом безграмотного.
специалиста, который, растопырив пальцы, как козёл, рассказывает о вещах, на изучение которых не потратил и доли своего драгоценного времени.
Добрые люди из числа комментаторов уже отметили, что это не более чем стеб.
Проблема в том, что тезисы, выдвинутые в этих переводах, я, как оказалось, не смог воспринять как стеб, поскольку большую часть из них мне приходилось слышать вживую.
По-видимому, можно диагностировать наличие психологической травмы, вызванной переизбытком ерунды, прошедшей через мозг.
Две вторые вызвали скорее положительные эмоции, так как в них автор применяет практики ФП к задачам, понятным ООП-разработчику.
Несмотря на несогласие с основным посылом его первой публикации, отраженным в названии, и сомнения относительно разумности реализации понятия монады в столь явном виде на ООП-ориентированном языке, нельзя упрекнуть автора в недостаточной проработанности.
материала.
Но есть один принципиальный аспект, который я не мог игнорировать.
Это своего рода вульгаризация функционального программирования, попытка рассматривать его как простой набор инструментов и подходов к проектированию программ.
Что, на мой взгляд, не совсем верно.
Поэтому в данной статье делается попытка показать, что те свойства функциональных программ, которые автор пытается воспроизвести в своем коде, не являются основой функционального программирования, заложенными не мудрыми создателями Haskell и ему подобных, а либо прямым следствием тех концепций и моделей, которые действительно заложены в ее основу, или, как ни странно, попытка компенсировать те недостатки, которые эти основы порождают.
Итак, к делу
В науке довольно часто можно наблюдать следующую метаморфозу.Сначала в рамках рассмотрения определенного процесса/феномена/теории появляется некий объект, обладающий какими-то важными и полезными свойствами.
Но он также обычно оказывается достаточно сложным по своей структуре, что ограничивает его практическую полезность.
Поэтому они часто поступают так: берут за основу свойства данного объекта и на этой основе строят новую теорию/модель/описание, в рамках которой искомый объект становится простым или даже тривиальным, или необходимые внутренние свойства проявляются в гораздо более простых объектах.
Примерно так соотносятся друг с другом «настоящее» функциональное программирование и «элементы функционального программирования», встречающиеся в современных языках высокого уровня.
Поскольку для понимания явления обычно полезно ознакомиться с историей его возникновения, напомним принципиально важные для нашего вопроса моменты истории вычислений и теории программирования.
В конце XIX — начале XX веков произошла значительная перестройка основ математической науки.
Это не только решило ряд выявленных проблем и противоречий, закравшихся в самую суть существовавших в то время представлений о том, что такое математика и математическое доказательство, но и поставило ряд новых вопросов.
Один из них был следующий: что такое алгоритм? Или, что то же самое, какой класс задач можно решить чисто механически.
Я не буду вдаваться в подробности, почему этот вопрос оказался важным; лучше сразу перейти к ответу, данному Аланом Тьюрингом, широко известным в не очень узких кругах.
Он сформулировал тезис: «вычислимы только те функции, для которых можно построить машину Тьюринга».
Это заявление необоснованно.
То есть, по сути, Тьюринг просто дал строгое формальное определение того, что считать вычислимой функцией, согласующееся с интуитивными идеями, которые обычно закладываются в это понятие.
Это определение оказалось способным удовлетворить учёных-прикладников, поскольку они хорошо представляют себе, что такое машина, даже с бесконечной лентой, и как она должна функционировать.
Но многих математиков это определение не очень удовлетворило.
Судя по всему, концепции, которыми оперировал Тьюринг, показались им недостаточно.
абстрактными.
В связи с этим они не оставили попытки дать иное определение, которое охватывало бы более широкий класс математических функций и в то же время все же соответствовало бы нашим интуитивным представлениям.
Эти попытки оказались безрезультатными.
Каждое альтернативное определение, которое было предложено и выдержало критику, оказалось эквивалентным определению Тьюринга в том смысле, что оно описывает точно тот же класс математических функций.
Однако эти исследования ни в коем случае не были бесполезными.
Попытки взглянуть на объект исследования с иной точки зрения редко оказываются бесполезными.
В нашем случае это привело к появлению нескольких теорий, одной из которых стало лямбда-исчисление, предложенное Алонзо Чёрчем.
Лень — двигатель прогресса
Что такого полезного в лямбда-исчислении и почему все вокруг него так суетятся? Это просто.В модели, предложенной Тьюрингом, алгоритм представляет собой знакомую нам последовательность инструкций, которую должен выполнить опять-таки знакомый нам исполнитель.
Это интуитивно понятно.
Но в определении Чёрча всё иначе.
Основным (и по сути единственным) механизмом построения в рамках этой теории являются так называемые лямбда-термы, которые в наших сегодняшних терминах можно (условно) назвать безымянными функциями.
Программа (алгоритм) в данном случае представляет собой комбинацию этих самых термов, построенную по определенным правилам, исходными данными являются значения свободных переменных лямбда-терма, а процесс расчета представляет собой не что иное, как редукцию (упрощение ) лямбда-терма (функции), который может быть выполнен, как только какая-либо свободная переменная получит значение.
Неожиданным здесь оказался следующий факт: как только переменная получит значение - то есть как только мы представим программе часть исходных данных - мы сможем провести приведение, но не за один, а за один раз.
два пути.
В первом случае процесс вычислений оказывается эквивалентным тому, который воспроизводят типичные механические калькуляторы типа машины Тьюринга.
Это соответствует правилу: аргументы функции должны быть вычислены до того, как будет вычислена сама функция.
Но есть и другой вариант – так называемый частичный расчет. При этом, если вычислена только часть аргументов, мы все равно можем вычислить (сократить) ту часть функции, которая использует только эти аргументы.
Этот подход обычно называют моделью «ленивых» вычислений.
Напротив, модель вычислений «Тьюринга» иногда называют «энергичной» или «жадной»; языки программирования, построенные на его основе, будут называться императивными.
Важная особенность «ленивых» вычислений заключается в том, что если некая подпрограмма написана как функция, скажем, трёх аргументов, а по факту использует только два, то нет необходимости вычислять этот самый третий аргумент, чтобы вычислить значение функции.
И это дает нам интересные практические возможности.
Например, возможность работы с бесконечными последовательностями.
Любой, кто начал знакомство с функциональным программированием вообще и языком Haskell в частности, не составит труда понять этот метод получения первых н Числа Фибоначчи:
Пояснения для тех, кто не знаком с Haskell. Фибоначчи2 для двух аргументов рекурсивно строит список, первый элемент которого является первым аргументом функции, а остальная часть списка является результатом рекурсивного применения Фибоначчи2 ко второму аргументу b и значению (a+b).fibonacci2 a b = a : (fibonacci2 b (a+b)) fibonacci = fibonacci2 1 1 nfibonacci n = take n fibonacci
Ээквивалентный (по форме!) код для Python выглядит так: def fibonacci2(a, b) :
return [a] + fibonacci2(b, a+b)
def fibonacci() :
return fibonacci2(1, 1)
def nfibonacci(n) :
res = []
data = fibonacci()
for i in range(n) :
res.append( data[i] )
return res
Я не рекомендую звонить Нфибоначчи.
Функция Фибоначчи (а это именно функция) генерирует бесконечный список чисел.
Если бы мы использовали знакомую нам модель расчета, то нфибоначчи никогда бы не смог завершить (что, напомню, вполне приемлемо и не противоречит идее его «вычислимости»).
Но если мы воспользуемся «ленивой» моделью вычислений, то легко увидеть, что как только н принимает определенное значение, чтобы получить значение функции Нфибоначчи нам нужны только первые n элементов списка, который является результатом функции Фибоначчи .
В этом случае мы можем поступить так: получили элемент списка — провели сокращение, следующий элемент — еще один шаг сокращения, н аргумент - сокращение привело к получению значения функции.
То есть в этом случае мы получаем результат за конечное время, несмотря на «циклический» характер процедуры построения списка чисел Фибоначчи.
Здесь особо рьяный, повелительно настроенный читатель воскликнет: « Но подождите, только полный идиот сможет реализовать построение списка чисел Фибоначчи таким способом! Существуют очевидные решения, которые не приводят к зацикливанию И он, конечно, будет прав.
Глупый перенос решения, предполагающего выполнение в рамках модели «ленивых» вычислений, в программу для «жадных» вычислений действительно не является показателем большого ума.
Если вы предлагаете эту задачу программисту, который придерживается.
Если вы верны, скажем, C, он, скорее всего, предложит одноконтурный вариант со счетчиком и двумя переменными состояния.
Но дело не в самих числах Фибоначчи.
Дело в том, что правило построения последовательности в этом примере отделено от способа обработки ее элементов.
И это полезное свойство, которое желательно иметь возможность воспроизвести в более сложных случаях, когда элементы обрабатываемой последовательности генерируются достаточно сложным способом и простым переносом решения «в лоб» для последовательности Фибоначчи.
в этом случае оказывается неэффективным по времени, по памяти или просто приводит к коду, понимание которого недоступно простым смертным.
Это желание естественно и может быть реализовано, например, за счет использования итераторов или генераторов.
В Python, например, мы можем сделать это: def fibonacci() :
a = 1
b = 1
yield a
yield b
while True :
c = a + b
yield c
a = b
b = c
def nfibonacci(n) :
return [e for e in itertools.islice(fibonacci(), n)]
Здесь Фибоначчи() — генератор, создающий последовательность элемент за элементом.
И в этом случае вместо Фибоначчи Может быть функция-генератор любой сложности.
Если представить код полностью, включая код генератора под капотом, мы получим очень сложную и совершенно императивную структуру программного обеспечения.
Но финальная версия вполне «функциональна».
В C++ вы можете провернуть аналогичный трюк, создав специальный класс.
Фибоначи и итераторы для него.
Решение будет варьироваться в зависимости от особенностей языка программирования и предпочтений программиста, но цель останется общей — разделить на уровне организации программы метод построения последовательности заранее неизвестной длины и метод обработки.
его элементы.
Разница в том, что в рамках функционального подхода такая организация программы естественна и навязана самим способом ее выполнения, а в рамках императивного подхода она требует дополнительной творческой работы, в том числе создания дополнительных концепций и шаблонов проектирования.
Чистота – залог здоровья
Еще одно свойство, наличие которого говорит о функциональном подходе к программированию, — «чистота» функций.Это также означает отсутствие побочных эффектов.
То есть вызов функции с тем же набором аргументов должен привести к одному и тому же результату.
Автор цитируется В посте достаточно подробно описано, почему это свойство желательно и в программах, написанных в императивном стиле.
Однако это не более чем следствие используемой модели расчета.
Причина, по которой все функции функциональной программы должны быть чистыми, проста.
Если допустить наличие этих самых побочных эффектов, то окажется, что порядок, в котором аргументы функции получают свое значение, напрямую влияет на результат работы функции.
Можно сказать, что это верно в рамках императивного подхода, но в случае «ленивых» расчетов все гораздо хуже.
Даже если предположить, что аргументы функции могут вычисляться независимо друг от друга в любом порядке, то «лень» всё равно подразумевает, что (условно) не весь код функции будет выполнен за один присест. Она будет выполняться по частям, в зависимости от двух вещей — собственно структуры функции, которую нам любезно предоставит условный компилятор, и порядка, в котором мы представим аргументы функции.
Для нас естественно ожидать, что если мы сначала определим функцию def f(x,y) :
.
и после этого def g(x, y) :
return f(y, x)
затем результат вызова г(а, б) будет равен результату вызова е(б, а) для любых независимо вычислимых значений а И б .
Но если ж имеет побочные эффекты, влияющие на вычисление значений аргументов, то наши ожидания могут быть сильно обмануты .
Например, при расчете б чтение происходит из файла - и при вычислении ж также читает из того же файла.
При ленивых вычислениях мы заранее не знаем, какая часть кода (для б или для ж ) будет выполнен первым.
Это значит, что мы не знаем, какой результат выдаст программа, даже если знаем содержимое файла, который она должна прочитать.
Подобное поведение в принципе неприемлемо и поэтому должно быть категорически исключено.
Что означает в в рамках «ленивой» модели расчета (неконтролируемой) должны быть запрещены побочные эффекты функции .
Если используется жадный порядок вычислений, побочные эффекты гораздо более предсказуемы.
По этой и только этой причине они разрешены в императивном программировании.
Но если ими злоупотреблять, функция превратится в ошибку.
Это означает, что вы не должны злоупотреблять ими.
Это означает, что понятие «чистоты», естественное для функционального программирования, вновь востребовано в императивном мире.
Следовательно, диссертация, состоявшаяся
Функциональная программа – программа, состоящая из чистых функций.неверно, если рассматривать его как определение.
Да, функциональная программа состоит из «чистых» функций, но программа, состоящая из чистых функций, не обязательно должна быть «функциональной».
Это его свойство, но это не определяющее свойство.
Однако есть проблема.
Возможность сохранения состояния и даже банальный ввод-вывод — вещи, которые напрямую связаны с побочными эффектами.
А жизнь без них полна боли и страданий.
Возникает вопрос: как совместить побочные эффекты и ленивые расчеты? В целом ответ — нет. Ответ правильный – в каждом конкретном случае следует искать удовлетворительное частное решение.
Оказалось, что многие способы воспроизведения вычислений с побочными эффектами без нарушения концепции «чистоты» вычислений укладываются в общую концепцию монады, заимствованную из теории категорий.
Мне бы не хотелось лишний раз пытаться объяснить, что это такое и с чем его едят, хотя бы потому, что это в любом случае не заменит (а по моему опыту даже не упростит) объяснение того, как конкретно могут быть состояния переменных и исключений.
быть реализованы и подобные вещи на «чистых» функциональных языках.
Мораль в том, что императивное программирование является таким же источником вдохновения для функционального программирования, как и функциональное для императивного программирования.
Более того, иногда идея проходит через конкурирующую концепцию как через фильтр, возвращается обратно в измененном виде и приводит к появлению нового инструмента.
Нужны ли монады в императивном мире? У меня нет однозначного мнения по этому вопросу.
Автор этот post Я уверен, что они нужны.
Я склонен усомниться в этом утверждении, поскольку польза от использования понятия монады в функциональных программах обычно связана с тем, что алгоритм можно сформулировать без учета того, какие конкретные побочные эффекты скрывает монада.
Другими словами, если собственный (гипотетический, еще не созданный человечеством) тип данных соответствует требованиям, предъявляемым к монаде, то написанный для него алгоритм будет работать корректно.
Это удобно прежде всего в теоретических исследованиях.
Но есть пара нюансов.
Во-первых, не очень понятно, зачем прятать побочные эффекты в обертке в языках, для которых они являются естественным явлением.
Во-вторых, при написании конкретных программ с конкретными типами данных и конкретной целевой архитектурой такой обобщенный алгоритм чаще всего будет вынужден подвергаться реструктуризации с целью повышения производительности.
Написание универсальных алгоритмов с использованием монад в императивном стиле возможно, но у меня есть сомнения в осуществимости такого подхода.
Тот факт, что некоторый аналог типа Maybe std::optional из C++ объявлен монадой, вряд ли окажет какое-либо влияние на практику его использования.
Кто наблюдает за наблюдателями?
Функции высшего порядка настолько широко используются в функциональных программах, что одного факта поддержки чего-то подобного в языке программирования достаточно, чтобы некоторые странные люди признали этот язык функциональным.Что такое «функции высшего порядка»? Это функция, которая работает с другими функциями в качестве аргументов или возвращает функцию в результате.
Казалось бы, что здесь может вызвать дискуссию? Оказывается, это очень много.
Начнем с того, что обычно понимают под термином «функция».
Программисты обычно думают просто: если что-то можно вызвать как функцию, то это можно и рассматривать как функцию.
В рамках императивного подхода это имеет смысл, поскольку интуитивно функция — это нечто, что при заданном наборе аргументов дает определенный результат. Если принять наличие побочных эффектов, то в практическом смысле действительно нет разницы между «обычной» языковой функцией и, скажем, объектом класса, имеющим перегруженный оператор().
Но в функциональном программировании такое определение функции недостаточно конструктивно, так как не позволяет интерпретировать понятие частичного вычисления этой самой функции.
В функциональном программировании функция не является «одним из» структурных элементов программы, а в определенном смысле наоборот: все элементы программы являются функциями.
Поэтому, по сути, это «функциональное программирование».
И опять же, если все является функцией, то есть любой аргумент любой функции является функцией, то любая функция с аргументами является функцией высшего порядка.
Это означает, что функции высшего порядка являются естественным элементом функциональной программы.
Настолько, что даже выделять их в отдельный класс не имеет особого смысла.
Функция высшего порядка обычно задается как карта или складывать .
Но мы рассмотрим более тривиальный вариант – любой - функция двух аргументов е(х, у) .
В модели ленивого вычисления аргументы данной функции будут оцениваться только тогда, когда они действительно необходимы.
Допустим, сначала нужен был аргумент Икс .
Давайте посчитаем этот аргумент и предоставим его значение.
ж и, кроме того, мы вычисляем все, что можем вычислить, не используя значение аргумента й .
Тогда остальные вычисления можно будет полностью представить в виде новой функции, уже из Икс независимый – например, г(у) .
Но в данном случае ничто не мешает нам формально представлять ж не как функция двух аргументов, а как функция одного аргумента е(х) , результатом которого будет другая функция г(у) .
Другими словами, в рамках функционального подхода любая функция Н> 1 аргументы — это функция более высокого порядка, поскольку ее можно интерпретировать как функцию одного аргумента, результатом которого является функция Н-1 аргументы.
Можем ли мы реализовать такое поведение в рамках императивного подхода? Конечно можем.
В Python мы бы написали что-то вроде следующего: def partial(f, x) :
Теги: #python #программирование #Функциональное программирование #Идеальный код #монады #чистые функции #ссылочная прозрачность
-
Уничтожить И Безвозвратно Удалить Файлы
19 Oct, 24
