Функциональный стиль программирования

Основные принципы программирования: функциональное программирование

Переводы, 23 января 2017 в 13:43

Если вы такой же разработчик, как и я, то наверняка сперва изучали парадигму ООП. Первым вашим яыком были Java или C++ — или, если вам повезло, Ruby, Python или C# — поэтому вы наверняка знаете, что такое классы, объекты, экземпляры и т.д. В чём вы точно не особо разбираетесь, так это в основах той странной парадигмы, называющейся функциональным программированием, которая существенно отличается не только от ООП, но и от процедурного, прототипно-ориентированного и других видов программирования.

Функциональное программирование становится популярным — и на то есть причины. Сама парадигма не нова: Haskell, пожалуй, является самым функциональным языком, а возник он в 90-ых. Такие языки, как Erlang, Scala, Clojure также попадают под определение функциональных. Одним из основных преимуществ функционального программирования является возможность написания программ, работающих конкурентно (если вы уже забыли, что это — освежите память прочтением статьи о конкурентности), причём без ошибок — то есть взаимные блокировки и потокобезопасность вас не побеспокоят.

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

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

1. Все функции — чистые

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

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

Первое правило понятно — если я вызываю функцию sum(2, 3) , то ожидаю, что результат всегда будет равен 5. Как только вы вызываете функцию rand() , или обращаетесь к переменной, не определённой в функции, чистота функции нарушается, а это в функциональном программировании недопустимо.

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

2. Все функции — первого класса и высшего порядка

Эта концепция — не особенность ФП (она используется в Javascript, PHP и других языках) — но его обязательное требование. На самом деле, на Википедии есть целая статья, посвящённая функциям первого класса. Для того, чтобы функция была первоклассной, у неё должна быть возможность быть объявленной в виде переменной. Это позволяет управлять функцией как обычным типом данных и в то же время исполнять её.

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

3. Переменные неизменяемы

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

4. Относительная прозрачность функций

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

Пусть у нас есть Java-функция, которая складывает 3 и 5:

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

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

5. Функциональное программирование основано на лямбда-исчислении

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

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

Как я уже говорил, лямбда-исчисление на этом не заканчивается — но мы рассмотрели лишь ключевые аспекты, связанные с ФП. Теперь, в разговоре о функциональном программировании вы сможете блеснуть словечком “лямбда-исчисление”, и все подумают, что вы шарите 🙂

Заключение

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

Если вы хотите узнать о функциональном программировании побольше, то советуем вам ознакомиться с примерами использования принципов ФП в JavaScript (часть 1, часть 2), а также с циклом статей, посвящённым функциональному C#.

Функциональный стиль программирования

Процедурное (императивное) программирование является отражением архитектуры традиционных ЭВМ, которая была предложена фон Нейманом в 40-х годах. Теоретической моделью процедурного программирования служит алгоритмическая система под названием «машина Тьюринга».

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

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

Процедурные языки характеризуются следующими особенностями:

@ необходимостью явного управления памятью, в частности, описанием переменных;

@ малой пригодностью для символьных вычислений;

@ отсутствием строгой математической основы;

@ высокой эффективностью реализации па традиционных ЭВМ.

Одним из важнейших классификационных признаков процедурного языка является его уровень. Уровень языка программирования определяется семантической (смысловой) емкостью его конструкций и степенью его ориентации на программиста. Язык программирования частично ликвидирует разрыв между методами решения различного рода задач человеком и вычислительной машиной. Чем более язык ориентирован на человека, тем выше его уровень. Дадим краткую характеристику реализованным на ПЭВМ языкам программирования в порядке возрастания их уровня.

Двоичный язык является непосредственно машинным языком. В настоящее время такие языки программистами практически не применяются.

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

Язык Макроассемблера является расширением языка Ассемблера путем включения в него макросредств. С их помощью в программе можно описывать последовательности инструкций с параметрами — макроопределения. После этого программист может использовать снабженные аргументами макрокоманды, которые в процессе ассемблирования программы автоматически замещаются макрорасширениями. Макрорасширение представляет собой макроопределение с подставленными вместо параметров аргументами.

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

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

Язык программирования С (Си) первоначально был разработан для реализации операционной системы UNIX в начале 70-х годов. В последующем приобрел высокую популярность среди системных и прикладных программистов. В настоящее время этот язык реализован па большинстве ЭВМ.

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

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

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

Basic ( Beginners All — purpose Symbolic Instruction Code ) — многоцелевой язык символических инструкций для начинающих) представляет собой простой язык программирования, разработанный в 1964 году для использования новичками. Он был разработан как простейший язык для непосредственного общения человека с вычислительной машиной. Поэтому первоначально работа велась в интерактивном режиме с использованием интерпретаторов. В настоящее время для этого языка имеются также и компиляторы.

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

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

Pascal является одним из наиболее популярных среди прикладных программистов процедурным языком программирования, особенно для ПЭВМ. Разработанный в 1970 году швейцарским специалистом в области вычислительной техники профессором Н. Виртом, язык назван в честь французского математика и по замыслу автора предназначался для обучения программированию. Однако язык получился настолько удачным, что стал одним из основных инструментов прикладных и системных программистов при решении задач вычислительного и информационно-логического характера. В 1979 году был подготовлен проект описания языка — Британский стандарт языка программирования Pascal BS 6192, который стал также и международным стандартом ISO 7185.

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

? стройностью, простотой и краткостью;

? строгостью, способствующей написанию эффективных и надежных программ;

? высокой эффективностью реализации на ЭВМ.

Pascal реализован на ЭВМ различных типов, но наиболее распространен и развит для ПЭВМ. В настоящее время широко используются такие версии этого языка для ПЭВМ, как Borland Pascal и Turbo Pascal .

ЗАЧЕМ НУЖНО ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

В результате изучения материала главы 1 студент должен:

• • особенности функционального стиля программирования;
• • недостатки и преимущества функционального стиля по отношению к императивному стилю программирования;

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

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

Особенности функционального стиля

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

Рис. 1.1. Схема простой функциональной программы

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

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

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

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

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

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

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

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

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

Листинг 1.1. Функция вычисления суммы элементов числового списка

double sumList(List list) < double sum = 0;

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

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

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

Листинг 1.2. Рекурсивная функция вычисления суммы элементов списка

size == 1 ? list.get(O) :

sumList(list.subList(0, mid)) + sumList(list.subList(mid, size));

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

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

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

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

Рассмотрим следующую простую задачу. Пусть требуется определить функцию, с помощью которой можно создавать суперпозицию двух вещественных функций одного вещественного аргумента. Другими словами, нужно описать инструмент, с помощью которого из двух произвольных функций f (х) и g (х) можно было бы получить новую функцию fg (х), результат работы которой определялся бы уравнением fg(x) = f (g (х) ). Конечно, решение этой задачи было бы очень полезным в ситуации, когда практически единственным инструментом программирования является определение и вызов различных функций. В последних версиях языка Java, начиная с версии Java 8, имеется довольно широкий набор средств функционального программирования, так что поставленную задачу можно решить довольно просто (функция образования суперпозиции двух других функций включена в стандартную библиотеку программ этой версии Java). В листинге 1.3 приведена искомая функция.

Листинг 1.3. Реализация суперпозиции на Java static FunctiorKT,V>

compose (FunctionctJ, V> f, FunctiorKT, U> g) < return x ->f.apply(g.apply (x));

Даже если вы не очень хорошо разбираетесь во всех деталях записи, общий смысл написанного понять можно. Результатом работы этой функции является новая функция с аргументом х, результат работы которой — последовательное применение (apply) функций g и f к этому аргументу. Видно, впрочем, что на самом деле аргументы f ид — это не совсем функции: запись f (д (х) ) синтаксически неверна. Объекты типа Function — это сложно устроенные объекты, внутри которых и спрятана исполняемая функция. Несмотря на внешнюю простоту записи, в приведенной реализации имеется много скрытых деталей, которые необходимы для того, чтобы весьма сложно организованный объект имел вид обычной функции. Например, если подумать, то становится непонятно, почему аргументы функции comp — переданные ей функции f и g — не пропадают после выхода из этой функции, а остаются «жить» внутри возвращаемого результата.

Немного странным выглядит и использование функции compose в довольно простой ситуации. Естественная на первый взгляд запись compose (Math. sin, Math.cos) (3.14) оказывается синтаксически неверной. Правильной будет запись compose (Math: :sin, Math: :cos) . apply (3.14). Очень хорошо видно, что используемые нами «функции» — это не совсем функции в традиционном понимании, и в язык Java пришлось добавить много нового синтаксиса для того, чтобы выразить такие манипуляции с функциями, которые в функциональных языках выглядят очень просто и естественно, да и реализуются просто.

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

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

Программирование на C++ в функциональном стиле

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

Под программированием в функциональном стиле я не имею в виду, что оно является строго функциональным, а лишь то, что в C++ легко использовать многие из функциональных строительных блоков. В данной статье основное внимание уделяется одной из важнейших конструкций функционального программирования: работе со значениями (values) в противоположность идентификациям (identities). Я рассмотрю мощную поддержку, которая всегда была в C++ для работы со значениями, потом покажу, как в новом стандарте C++ 11 эта поддержка расширена с помощью лямбд. Наконец, я дам введение по методу работы с неизменяемыми (immutable) структурами данных, который обеспечивает не только свойственное C++ быстродействие, но и защиту, уже достаточно давно реализованную в функциональных языках.

Значения в сравнении с идентификациями

Сначала позвольте мне пояснить, что я имею в виду под работой со значениями по сравнению с идентификациями. Простые значения вроде 1, 2 и 3 легко идентифицировать. Я мог бы также сказать, что 1, 2 и 3 являются константными целочисленными значениями. Однако это было бы избыточно, так как все значения — на самом деле константы, и сами значения никогда не изменяются (т. е. 1 — всегда 1, и 1 никогда не превратится в 2). С другой стороны, значение, сопоставленное с идентификацией, измениться может (x может быть сейчас равно 1, но позднее стать равным 2).

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

Код на рис. 1 демонстрирует простое использование значимого типа.

Рис. 1. Использование значимого типа

Небольшое изменение, и переменная y может стать ссылочным типом (reference type), что кардинально меняет взаимосвязь между x и y, как показано на рис. 2.

Рис. 2. Использование ссылочного типа

Как видно на рис. 3, C++ также поддерживает модификатор const, который не дает программисту вносить изменения в переменную и тем самым еще больше защищает концепцию значения. (Однако, как и в большинстве других случаев, в C++ есть минимум один способ разрушить эту защиту. Подробнее на эту тему ищите описание const_cast, предназначенной для работы с более старым кодом, который не является «const-корректным».)

Рис. 3. Модификатор const

Заметьте, хотя на рис. 3 переменная y передается по ссылке, значение y защищено на этапе компиляции модификатором const. Это дает программистам на C++ эффективный способ передачи больших объектов и в то же время позволяет работать с их значениями, а не идентификациями.

Благодаря модификатору const в C++ есть неизменяемые типы данных, напоминающие таковые в большинстве языков функциональность программирования. Однако иметь дело с этими типами данных трудно. Более того, создавать детальные (deep) (полные) копии больших объектов при каждом незначительном изменении неэффективно. Тем не менее, должно быть ясно, что в стандартном C++ всегда была концепция работы со значениями (даже если ее чистота выдерживалась не полностью).

Заметьте, что поддержка значимых типов расширяется до охвата пользовательских типов через конструкторы копий и операторы присваивания. Конструкторы копий и операторы присваивания в C++ позволяют создавать детальную копию экземпляра пользовательского типа. Учитывайте, что хотя в C++ можно реализовать конструкторы копий для создания поверхностной копии (shallow copy), вы должны заботиться о сохранении семантики значений.

Поддержка программирования в функциональном стиле в C++ 11

В C++ 11 появилось целый ряд новых средств для программирования в функциональном стиле. Возможно, самое важное, что C++ теперь поддерживает лямбды (также называемые замыканиями [closures] и анонимными функциями). Лямбды позволяют структурировать код такими способами, которые ранее были бы непрактичными. Эта функциональность и раньше была доступна через функторы — мощные, но не столь удобные в использовании средства. (На самом деле «за кулисами» лямбды C++ записывают анонимные функторы.) На рис. 4 показано, как лямбды позволили улучшить наш код на простом примере, использующем STL-библиотеку (C++ standard library).

Рис. 4. Использование лямбд

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

Хотя C++ — лишь один из многих императивных языков, в которых теперь появились лямбды, изюминка лямбд в C++ в том, что (по аналогии с лямбдами в языках функционального программирования) они позволяют защищать концепцию работы со значениями в противоположность идентификациям. Тогда как языки функционального программирования достигают этой цели за счет неизменяемости переменных, C++ делает это, предоставляя контроль над захватом (capture). Рассмотрим код на рис. 5.

Рис. 5. Захват по ссылке

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

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

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

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

Табл. 1. Синтаксис C++ для управления захватом лямбды

Ничего не захватывается

(как раз то, что мне было нужно в первом примере с лямбдой)

Захват всего по ссылке

(традиционное поведение лямбды, но противоречащее акценту функционального программирования на работе со значениями)

Захват всего по значению

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

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

Неизменяемые типы данных

Чего не хватает, так это эффективных неизменяемых структур данных, имеющихся в некоторых языках функционального программирования. В этих языках неизменяемые структуры данных эффективны, даже когда они очень большие, потому что используют общие данные. Создание в C++ структур данных, совместно использующих данных, — дело тривиальное: вы просто динамически выделяете память под данные, и у каждой структуры есть указатели на эти данные. Увы, управлять жизненным циклом общих переменных труднее (именно поэтому, кстати, сборщики мусора стали такими популярными). К счастью, C++ 11 предоставляет элегантное решение для работы с общими переменными через класс шаблона std::shared_ptr, как показано на рис. 6.

Рис. 6. Общие переменные

Код на рис. 6 иллюстрирует простое использование std::shared_ptr и его вспомогательной функции std::make_shared. С помощью std::shared_ptr можно легко разделять данные между структурами, не боясь утечки памяти (при условии, что вы избегаете круговых ссылок). Заметьте, что std::shared_ptr предоставляет базовые гарантии безопасности в многопоточной среде (thread-safety) и выполняется быстро, так как использует архитектуру без блокировок. Однако учитывайте, что эти базовые гарантии не распространяются автоматически на объект, на который указывает std::shared_ptr. Тем не менее, std::shared_ptr гарантирует, что он не уменьшит степень безопасности этого объекта в многопоточной среде. Неизменяемые объекты по своей сути обеспечивают серьезные гарантии безопасности в многопоточной среде, поскольку они никогда не изменяются после создания. Так что, когда вы используете std::shared_ptr с неизменяемым объектом, эта комбинация сохраняет все гарантии безопасности неизменяемого объекта в многопоточной среде.

Теперь я могу легко создать неизменяемый класс, потенциально способный разделять данные (рис. 7).

Рис. 7. Неизменяемый класс для разделения данных

Код на рис. 7 довольно длинный, но большая его часть для конструкторов и операторов присваивания стереотипна. Последние две функции являются ключевыми для того, чтобы сделать объект неизменяемым. Заметьте, что методы SetS и SetD возвращают новый объект, что оставляет исходный объект неизменным. (Хотя включение методов SetS и SetD в виде членов класса удобно, это немного вводит в заблуждение, поскольку на самом деле они не изменяют исходный объект. Более четкое решение см. в ImmutableVector рис. 8 и 9.) Класс Immutable в действии показан на рис. 10.

Рис. 8. Использование «интеллектуального» класса шаблона ImmutableVector

Рис. 9. Методы для операций с ImmutableVector

Рис. 10. Класс Immutable в действии

Заметьте, что объект b использует ту же строку, что и объект a (обе строки находятся по одинаковому адресу). Включение дополнительных полей с сопоставленными get- и set-аксессорами осуществляется тривиальным образом. Хотя этот код вполне хорош, его масштабирование до контейнеров немного затруднительно. Например, «наивная» реализация ImmutableVector могла бы поддерживать список общих указателей, представляющих каждый элемент массива. Если «наивный» ImmutableVector изменяется, вам придется продублировать весь массив общих указателей, что повлечет за собой дополнительные издержки, так как каждый элемент shared_ptr массива потребует увеличения своего счетчика ссылок.

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

Рис. 11. Сравнение «наивной» и «интеллектуальной» реализаций ImmutableVector

Знакомьтесь: функциональное программирование

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

«Подобно ООП, функциональное программирование — это множество идей, но не множество жёстких правил»

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

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

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

Но, пожалуй, самое важное преимущество программ, написанных в функциональном стиле — это, конечно же, их логическая связность и краткость. Программы на функциональных языках программирования могут быть в десятки раз короче тех же самых программ, написанных на традиционных языках. Когда я говорю о традиционных языках здесь, то подразумеваю под ними императивные языки программирования — то есть такие, в которых для выполнения некой операции нужно пошагово описать её выполнение. Примеры таких языков — знакомые всем Basic, Pascal, C.

«В сравнении с пользователями С, «никто» — достаточно точная оценка числа пользователей функциональных языков»

Сразу после рассказа о бочке мёда я расскажу о ложке дёгтя. Действительно, как же так получается, что функциональным программированием, которое решает огромное количество наболевших программистских проблем, пользуются, мягко скажем, не все программисты? Тому есть множество причин. Часть из них я почерпнул из замечательной статьи Филипа Вадлера «Почему никто не использует функциональные языки?» (её можно найти по адресу www.softcraft.ru/paradigm/fp/whynotfp.shtml). Главными недостатками функциональных языков программирования он считает плохую совместимость с самыми популярными из императивных языков программирования, на которых сейчас написано подавляющее большинство широко используемого программного обеспечения, плохую переносимость программ на функциональных языках на различные платформы и низкую популярность этих языков (то есть, получается рекурсия — языки не популярны из-за того, что все опасаются серьёзно их использовать из-за их низкой популярности). Есть ещё ряд причин, но все они также, в большинстве своём, упираются в инерционность индустрии программного обеспечения, в том числе и в инерционность людей, которые работают в ней.

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

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

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

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

Теперь ещё одна возможность, которая, вероятно, покажется вам даже более интересной, так как её аналоги напрочь отсутствуют в императивных языках. Это так называемые ленивые вычисления, называемые также отложенными. Ленится при этом, правда, не программист (программисты и так существа невероятно ленивые в своём подавляющем большинстве), а сама программа. Что это значит? Это значит, что она откладывает все вычисления до тех пор, пока не понадобится их результат. Программист только описывает зависимости функций друг от друга (не забывая при этом, конечно же, использовать такую замечательную вещь, как функции высших порядков), а программа уже сама будет решать, когда вычислять значение той или иной функции. Таким образом, увеличивается производительность программы и, опять-таки, улучшается потенциальная возможность её грамотно распараллелить. Впрочем, ленивые вычисления поддерживаются не всеми функциональными языками (но самый популярный из них, Haskell, их поддерживает) и при этом поддерживаются многими языками программирования, не относящимися к функциональным (например, Python — но там они организованы несколько иначе).

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

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

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