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

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

Энциклопедичный YouTube

1 / 5

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

Математика и константы / Введение в программирование, урок 4 (JavaScript ES6)

Реактивное программирование и современные веб-интерфейсы

Александр Чирцов о математике в физике

Анна Андреева. Решение олимпиадных задач по математике

Субтитры

Языки функционального программирования

Ещё не полностью функциональные изначальные версии и Лиспа , и APL внесли особый вклад в создание и развитие функционального программирования. Более поздние версии Lisp, такие как Scheme , а также различные варианты APL поддерживали все свойства и концепции функционального языка .

Как правило, интерес к функциональным языкам программирования, особенно чисто функциональным, был скорее научный, нежели коммерческий. Однако, такие примечательные языки как Erlang , OCaml , Haskell , Scheme (после 1986) а также специфические (статистика), Wolfram (символьная математика), и (финансовый анализ), и XSLT (XML) находили применение в индустрии коммерческого программирования. Такие широко распространенные декларативные языки как SQL и Lex /Yacc содержат некоторые элементы функционального программирования, например, они остерегаются использовать переменные. Языки работы с электронными таблицами также можно рассматривать как функциональные, потому что в ячейках электронных таблиц задаётся массив функций, как правило зависящих лишь от других ячеек, а при желании смоделировать переменные приходится прибегать к возможностям императивного языка макросов.

История

Первым функциональным языком был Лисп , созданный Джоном Маккарти в период его работы в в конце пятидесятых и реализованный, первоначально, для IBM 700/7000 (англ.) русск. . В Лиспе впервые введено множество понятий функционального языка, хотя при этом в языке применяется не только парадигма функционального программирования . Дальнейшим развитием Лиспа стали такие языки как Scheme и Dylan .

Концепции

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

Функции высших порядков

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

Функции высших порядков позволяют использовать карринг - преобразование функции от пары аргументов в функцию, берущую свои аргументы по одному. Это преобразование получило своё название в честь Х. Карри .

Чистые функции

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

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

Хотя большинство компиляторов императивных языков программирования распознают чистые функции и удаляют общие подвыражения для вызовов чистых функций, они не могут делать это всегда для предварительно скомпилированных библиотек, которые, как правило, не предоставляют эту информацию. Некоторые компиляторы, такие как gcc , в целях оптимизации предоставляют программисту ключевые слова для обозначения чистых функций . Fortran 95 позволяет обозначать функции как «pure» (чистые) .

Рекурсия

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

Подход к вычислению аргументов

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

print (len ([ 2 + 1 , 3 * 2 , 1 / 0 , 5 - 4 ]))

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

Как правило, нестрогий подход реализуется в виде редукции графа. Нестрогое вычисление используется по умолчанию в нескольких чисто функциональных языках, в том числе Miranda , Clean и Haskell . [ ]

ФП в нефункциональных языках

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

Стили программирования

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

# императивный стиль target = # создать пустой список for item in source_list : # для каждого элемента исходного списка trans1 = G (item ) # применить функцию G() trans2 = F (trans1 ) # применить функцию F() target . append (trans2 ) # добавить преобразованный элемент в список

Функциональная версия выглядит по-другому:

# функциональный стиль # языки ФП часто имеют встроенную функцию compose() compose2 = lambda A , B : lambda x : A (B (x )) target = map (compose2 (F , G ), source_list )

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

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

• Рефал (для этой категории, представленной единственным языком, нет общепринятого названия);
• Аппликативные (Лисп , , Tcl , Rebol);
• Комбинаторные (APL / / , FP /FL );
• Бесточечные (чистые конкатенативные) (Joy , Cat , Factor , подмножество PostScript).

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

Особенности

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

Сильные стороны

Повышение надёжности кода

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

Удобство организации модульного тестирования

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

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

Возможности оптимизации при компиляции

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

Возможности параллелизма

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

Недостатки

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

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

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

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

Языки функционального программирования

• LISP - (Джон МакКарти , ) и множество его диалектов, наиболее современные из которых:
• Erlang - (Joe Armstrong, ) функциональный язык с поддержкой процессов.
• APL - предшественник современных научных вычислительных сред, таких как MATLAB .
• (Робин Милнер , , из ныне используемых диалектов известны Standard ML и Objective CAML).
• - функциональный язык семейства ML для платформы .NET
• Miranda (Дэвид Тёрнер , , который впоследствии дал развитие языку Haskell).
• Nemerle - гибридный функционально/императивный язык.
• Haskell - чистый функциональный. Назван в честь Хаскелла Карри .

Ещё не полностью функциональные изначальные версии и Lisp и APL внесли особый вклад в создание и развитие функционального программирования. Более поздние версии Lisp, такие как Scheme , а также различные варианты APL поддерживали все свойства и концепции функционального языка .

Как правило, интерес к функциональным языкам программирования, особенно чисто функциональным, был скорее научный, нежели коммерческий. Однако, такие примечательные языки как Erlang, OCaml , Haskell , Scheme (после 1986) а также специфические (статистика), Mathematica (символьная математика), и K (финансовый анализ), и XSLT (XML) находили применение в индустрии коммерческого программирования. Такие широко распространенные декларативные языки как SQL и Lex /Yacc содержат некоторые элементы функционального программирования, например, они остерегаются использовать переменные. Языки работы с электронными таблицами также можно рассматривать как функциональные, потому что в ячейках электронных таблиц задаётся массив функций, как правило зависящих лишь от других ячеек, а при желании смоделировать переменные приходится прибегать к возможностям императивного языка макросов.

История

Первым функциональным языком был Lisp , созданный Джоном МакКарти в период его работы в в конце пятидесятых и реализованный, первоначально, для IBM 700/7000 (англ.) русск. . Lisp ввел множество понятий функционального языка, хотя при этом исповедовал не только парадигму функционального программирования . Дальнейшим развитием лиспа стали такие языки как Scheme и Dylan .

Концепции

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

Функции высших порядков

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

Функции высших порядков позволяют использовать карринг - преобразование функции от пары аргументов в функцию, берущую свои аргументы по одному. Это преобразование получило свое название в честь Х. Карри .

Чистые функции

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

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

Хотя большинство компиляторов императивных языков программирования распознают чистые функции и удаляют общие подвыражения для вызовов чистых функций, они не могут делать это всегда для предварительно скомпилированных библиотек, которые, как правило, не предоставляют эту информацию. Некоторые компиляторы, такие как gcc , в целях оптимизации предоставляют программисту ключевые слова для обозначения чистых функций . Fortran 95 позволяет обозначать функции как «pure» (чистые) .

Рекурсия

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

Подход к вычислению аргументов

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

Print (len ([ 2 +1 , 3 *2 , 1 /0 , 5 -4 ] ) )

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

Как правило, нестрогий подход реализуется в виде редукции графа. Нестрогое вычисление используется по умолчанию в нескольких чисто функциональных языках, в том числе Miranda , Clean и Haskell .

ФП в нефункциональных языках

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

Стили программирования

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

# императивный стиль target = # создать пустой список for item in source_list: # для каждого элемента исходного списка trans1 = G(item) # применить функцию G() trans2 = F(trans1) # применить функцию F() target.append (trans2) # добавить преобразованный элемент в список

Функциональная версия выглядит по-другому:

# функциональный стиль # языки ФП часто имеют встроенную функцию compose() compose2 = lambda A, B: lambda x: A(B(x) ) target = map (compose2(F, G) , source_list)

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

Особенности

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

Сильные стороны

Повышение надёжности кода

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

Удобство организации модульного тестирования

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

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

Возможности оптимизации при компиляции

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

Возможности параллелизма

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

Недостатки

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

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

См. также

• Анаморфизм
• Катаморфизм

Примечания

1. А. Филд, П. Харрисон Функциональное программирование: Пер. с англ. - М.: Мир, 1993. - 637 с, ил. ISBN 5-03-001870-0 . Стр. 120 [Глава 6: Математические основы: λ-исчисление].
2. Tiobe Programming Community Index
3. Пол Хьюдак (англ.) русск. (September 1989). «Conception, evolution, and application of functional programming languages » (PDF). ACM Computing Surveys 21 (3): 359-411. DOI :10.1145/72551.72554 .
4. Роджер Пенроуз Глава 2: Лямбда-исчисление Черча // Новый ум короля. О компьютерах, мышлении и законах физики = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics. - Едиториал УРСС, 2003. - ISBN 5-354-00005-X + переиздание ISBN 978-5-382-01266-7 ; 2011 г.
5. McCarthy, John (June 1978). «History of Lisp ». In ACM SIGPLAN History of Programming Languages Conference : 217–223. DOI :10.1145/800025.808387 .
6. , Гл. 3. λ-исчисление как язык программирования
7. В своих мемуарах Герберт Саймон (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 утверждает, что его, Al. Ньюэлл, и Клифф Шоу которых «часто называют родителями искусственного интеллекта» за написание программы Logic Theorist (англ.) русск. автоматически доказывающей теоремы из Principia Mathematica (англ.) русск. . Для того, чтобы достичь этого, они должны были придумать язык и парадигму, которую, ретроспективно, можно рассматривать как функциональное программирование.
8. History of Programming Languages: IPL
9. XIV. APL Session // History of Programming Language / Richard L. Wexelbblat. - Academic Press, 1981. - С. 661-693. - 749 с.
10. Скачать PDF: «Техники функционального программирования, В. А. Потапенко» стр. 8 «Функции высших порядков» .
11. GCC, Declaring Attributes of Functions
12. XL Fortran for AIX, V13.1 > Language Reference, Pure procedures (Fortran 95)
13. Tail call optimization

String reverse(String arg) { if(arg.length == 0) { return arg; } else { return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1); } }
Эта функция довольно медленная, потому что она повторно вызывает сама себя . Здесь возможна утечка памяти, так как множество раз создаются временные объекты. Но это функциональный стиль. Вам может показать странным, как люди могут так программировать. Ну, я как раз собирался вам рассказать.

Преимущества функционального программирования

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

Unit тестирование

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

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

Отладка

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

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

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

Многопоточность

Функциональная программа сразу готова к распараллеливанию без каких-либо изменений. Вам не придётся задумываться о deadlock-ах или состояниях гонки (race conditions) потому что вам не нужны блокировки! Ни один кусочек данных в функциональной программе не меняется дважды одним и тем же потоком или разными. Это означает, что вы можете легко добавить потоков к вашей программе даже не задумываясь при этом о проблемах, присущих императивным языкам.

Если дела обстоят подобным образом, то почему так редко функциональные языки программирования используются в многопоточных приложениях? На самом деле чаще, чем вы думаете. Компания Ericsson разработала функциональный язык под названием Erlang для использования на отказоустойчивых и масштабируемых телекоммуникационных коммутаторах. Многие отметили преимущества Erlang-а и стали его использовать . Мы говорим о телекоммуникациях и системах контроля трафика, которые далеко не так просто масштабируются, как типичные системы, разработанные на Wall Street. Вообще-то, системы написанные на Erlang, не такие масштабируемые и надёжные, как Java системы. Erlang системы просто сверхнадёжные.

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

Компилятор функционального языка может проанализировать код, классифицировать функции, которые создают строки s1 и s2 , как функции потребляющие много времени, и запустить их параллельно. Это невозможно сделать в императивном языке, потому что каждая функция может изменять внешнее состояние и код, идущий непосредственно после вызова, может зависеть от неё. В ФП автоматический анализ функций и поиск подходящих кандидатов для распараллеливания - это тривиальнейшая задача, как автоматический inline ! В этом смысле функциональный стиль программирования соответствует требованиям завтрашнего дня. Разработчики железа уже не могут заставить CPU работать быстрее. Вместо этого они наращивают количество ядер и заявляют о четырёхкратном увеличении скорости многопоточных вычислений. Конечно они очень вовремя забывают сказать, что ваш новый процессор покажет прирост только в программах, разработанных с учётом распараллеливания. Среди императивного ПО таких очень мало. Зато 100% функциональных программ готовы к многопоточности из коробки.

Развёртывание по горячему

В старые времена для установки обновлений Windows приходилось перезагружать компьютер. Много раз. После установки новой версии медиа проигрывателя. В Windows XP произошли значительные изменения, но ситуация всё ещё далека от идеальной (сегодня я запустил Windows Update на работе и теперь надоедливое напоминание не оставит меня в покое, пока не перезагружусь). В Unix системах модель обновления была получше. Для установки обновлений приходилось останавливать некоторые компоненты, но не всю ОС. Хотя ситуация выглядит лучше, но для большого класса серверных приложений это всё ещё не приемлемо. Телекоммуникационные системы должны быть включены 100% времени, ведь если из-за обновления человек не сможет вызвать скорую, то жизни могут быть потеряны. Фирмы с Wall Streets тоже не желают останавливать сервера на выходных, чтобы установить обновления.

В идеале нужно обновить все нужные участки кода не останавливая систему в принципе. В императивном мире это невозможно [пер. в Smalltalk-е очень даже возможно]. Представьте себе выгрузку Java класса на лету и перезагрузка новой версии. Если бы мы так сделали, то все экземпляры класса стали бы нерабочими, потому что потерялось бы состояние, которое они хранили. Нам пришлось бы писать хитрый код, для контроля версий. Пришлось бы серриализовать все созданные экземпляры класса, потом уничтожить их, создать экземпляры нового класса, попытаться загрузить серриализованные данные в надежде, что миграция пройдёт нормально и новые экземпляры будут валидными. И кроме того, миграционный код необходимо писать каждый раз вручную. И ещё миграционный код должен сохранять ссылки между объектами. В теории ещё куда ни шло, но на практике это никогда не заработает.

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

Доказательные вычисления и оптимизация (Machine Assisted Proofs and Optimizations)

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

Дополнительно вы можете использовать математический аппарат, чтобы доказать корректность участков ваших программ. При желании можно написать инструменты, которые анализируют код и автоматически создают Unit-тесты для граничных случаев! Такая функциональность бесценна для сверхнадёжных систем (rock solid systems). При разработке систем контроля кардиостимуляторов или управления воздушным трафиком такие инструменты просто необходимы. Если же ваши разработки не находятся в сфере критически важных приложений, то инструменты автоматической проверки всё равно дадут вам гигантское преимущество перед вашими конкурентами.

Функции высшего порядка

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

В ФП функция - это не тоже самое, что функция в Java или C. Это надмножество - они могут тоже самое, что Java функции и даже больше. Пусть у нас есть функция на C:

Int add(int i, int j) { return i + j; }
В ФП это не тоже самое, что обычная C функция. Давайте расширим наш Java компилятор, чтобы он поддерживал такую запись. Компилятор должен превратить объявление функции в следующий Java код (не забывайте, что везде присутствует неявный final):

Class add_function_t { int add(int i, int j) { return i + j; } } add_function_t add = new add_function_t();
Символ add не совсем функция. Это маленький класс с одним методом. Теперь мы можем передавать add в качестве аргумента в другие функции. Мы можем записать его в другой символ. Мы можем создавать экземпляры add_function_t в runtime и они будут уничтожены сборщиком мусора, если станут ненужными. Функции становятся базовыми объектами, как числа и строки. Функции, которые оперируют функциями (принимают их в качестве аргументов) называются функциями высшего порядка. Пусть это вас не пугает. Понятие функций высшего порядка почти не отличается от понятия Java классов, которые оперируют друг другом (мы можем передавать классы в другие классы). Мы можем называть их «классы высшего порядка», но никто этим не заморачивается, потому что за Java не стоит строгое академическое сообщество.

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

Предположим, что у нас есть участок Java кода, который получает сообщение, преобразует его различными способами и передаёт на другой сервер.

Void handleMessage(Message msg) { // ... msg.setClientCode("ABCD_123"); // ... sendMessage(msg); } // ... }
Теперь представьте себе, что система поменялась, и теперь нужно распределять сообщения между двумя серверами вместо одного. Всё остаётся неизменным, кроме кода клиента - второй сервер хочет получать этот код в другом формате. Как нам справиться с этой ситуацией? Мы можем проверять, куда должно попасть сообщение, и в зависимости от этого устанавливать правильный код клиента. Например так:

Class MessageHandler { void handleMessage(Message msg) { // ... if(msg.getDestination().equals("server1") { msg.setClientCode("ABCD_123"); } else { msg.setClientCode("123_ABC"); } // ... sendMessage(msg); } // ... }
Но такой подход плохо масштабируется. При добавлении новых серверов функция будет расти линейно, и внесение изменений превратится в кошмар. Объектно ориентированный подход заключается в выделении общего суперкласса MessageHandler и вынесение логики определения кода клиента в подклассы:

Abstract class MessageHandler { void handleMessage(Message msg) { // ... msg.setClientCode(getClientCode()); // ... sendMessage(msg); } abstract String getClientCode(); // ... } class MessageHandlerOne extends MessageHandler { String getClientCode() { return "ABCD_123"; } } class MessageHandlerTwo extends MessageHandler { String getClientCode() { return "123_ABCD"; } }
Теперь для каждого сервера мы можем создать экземпляр соответствующего класса. Добавление новых сервером становится более удобным. Но для такого небольшого изменения многовато текста. Пришлось создать два новых типа чтобы просто добавить поддержку различного кода клиента! Теперь сделаем тоже самое в нашем языке с поддержкой функций высшего порядка:

Class MessageHandler { void handleMessage(Message msg, Function getClientCode) { // ... Message msg1 = msg.setClientCode(getClientCode()); // ... sendMessage(msg1); } // ... } String getClientCodeOne() { return "ABCD_123"; } String getClientCodeTwo() { return "123_ABCD"; } MessageHandler handler = new MessageHandler(); handler.handleMessage(someMsg, getClientCodeOne);
Мы не создавали новых типов и не усложняли иерархию классов. Мы просто передали функцию в качестве параметра. Мы достигли того же эффекта, как и в объектно-ориентированном аналоге, только с некоторыми преимуществами. Мы не привязывали себя к какой-либо иерархии классов: мы можем передавать любые другие функции в runtime и менять их в любой момент, сохраняя при этом высокий уровень модульности меньшим количеством кода. По сути компилятор создал объектно-ориентированный «клей» вместо нас! При этом сохраняются все остальные преимущества ФП. Конечно абстракции, предлагаемые функциональными языками на этом не заканчиваются. Функции высшего порядка это только начало

Каррирование

Большинство людей, с которыми я встречаюсь, прочли книгу «Паттерны проектирования» Банды Четырёх. Любой уважающий себя программист будет говорить, что книга не привязана к какому-либо конкретному языку программирования, а паттерны применимы к разработке ПО в целом. Это благородное заявление. Но к сожалению оно далеко от истины.

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

Паттерн Адаптер наиболее часто применяется к «стандартной» единице абстракции в Java - классу. В функциональных языках паттерн применяется к функциям. Паттерн берёт интерфейс и преобразует его в другой интерфейс, согласно определённым требованиям. Вот пример паттерна Адаптер:

Int pow(int i, int j); int square(int i) { return pow(i, 2); }
Этот код адаптирует интерфейс функции, возводящей число в произвольную степень, к интерфейсу функции, которая возводит число в квадрат. В аккадемических кругах этот простейший приём называется каррирование (в честь специалиста по логике Хаскелла Карри (Haskell Curry), который провёл ряд математических трюков, чтобы всё это формализовать). Так как в ФП функции используются повсеместно в качестве аргументов, каррирование используется очень часто, чтобы привести функции к интерфейсу, необходимому в том или ином месте. Так как интерфейс функции - это её аргументы, то каррирование используется для уменьшения количества аргументов (как в примере выше).

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

Square = int pow(int i, 2);
Этой строкой мы автоматически создаём функцию возведения в квадрат с одним аргументом. Новая функция будет вызывать функцию pow , подставляя 2 в качестве второго аргумента. С точки зрения Java, это будет выглядеть следующим образом:

Class square_function_t { int square(int i) { return pow(i, 2); } } square_function_t square = new square_function_t();
Как видите, мы просто написали обёртку над оригинальной функцией. В ФП каррирование как раз и представляет из себя простой и удобный способ создания обёрток. Вы сосредотачиваетесь на задаче, а компилятор пишет необходимый код за вас! Всё очень просто, и происходит каждый раз, когда вы хотите использовать паттерн Адаптер (обёртку).

Ленивые вычисления

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

String s1 = somewhatLongOperation1(); String s2 = somewhatLongOperation2(); String s3 = concatenate(s1, s2);
В императивных языках программирования очерёдность вычисления не вызывает никаких вопросов. Поскольку каждая функция может повлиять или зависеть от внешнего состояния, то необходимо соблюдать чёткую очерёдность вызовов: сначала somewhatLongOperation1 , затем somewhatLongOperation2 , и concatenate в конце. Но не всё так просто в функциональных языках.

Как мы уже видели ранее somewhatLongOperation1 и somewhatLongOperation2 могут быть запущены одновременно, потому что функции гарантированно не влияют и не зависят от глобального состояния. Но что, если мы не хотим выполнять их одновременно, нужно ли вызывать их последовательно? Ответ - нет. Эти вычисления должны быть запущены, только если какая-либо другая функция зависит от s1 и s2 . Нам даже не нужно выполнять их до тех пор, пока они понадобятся внутри concatenate . Если вместо concatenate мы подставим функцию, которая в зависимости от условия использует один аргумент из двух, то второй аргумент можно даже не вычислять! Haskell - это пример языка с отложенными вычислениями. В Haskell отсутствует гарантия какой-либо очередности вызовов (вообще!), потому что Haskell выполняет код по мере необходимости.

Ленивые вычисления обладают рядом достоинств как и некоторыми недостатками. В следующем разделе мы обсудим достоинства и я объясню как уживаться с недостатками.

Оптимизация

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

Абстрагирование структур управления

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

Unless(stock.isEuropean()) { sendToSEC(stock); }
Мы хотим, чтобы функция sendToSEC выполнялась только если фонд (stock) не европейский. Как можно реализовать unless ? Без ленивый вычислений нам бы понадобилась система макросов, но в языках, подобных Haskell, это не обязательно. Мы можем объявить unless в виде функции!

Void unless(boolean condition, List code) { if(!condition) code; }
Заметьте, что code не будет выполняться, если condition == true . В строгих языках такое поведение невозможно повторить, так как аргументы будут вычислены прежде, чем unless будет вызвана.

Бесконечные структуры данных

Ленивые языки позволяют создавать бесконечные структуры данных, создание которых в строгих языках гораздо сложнее [пер. - только не в Python]. Например представьте себе последовательность Фибоначи. Очевидно, что мы не можем вычислить бесконечный список за конечное время и при этом сохранить его в памяти. В строгих языках, таких как Java, мы просто написали бы функцию, которая возвращает произвольный член последовательности. В языках подобных Haskell мы можем абстрагироваться и просто объявить бесконечный список чисел Фибоначи. Так как язык ленивый, то будут вычислены лишь необходимые части списка, которые реально используются в программе. Это позволяет абстрагироваться от большого числа проблем и посмотреть на них с более высокого уровня (например можно использовать функции обработки списков на бесконечных последовательностях).

Недостатки

Конечно бесплатный сыр бывает только в мышеловке. Ленивые вычисления тянут за собой ряд недостатков. В основном это недостатки от лени. В реальности очень часто нужен прямой порядок вычислений. Возьмём, например, следующий код:

В ленивом языке никто не гарантирует, что первая строка выполнится раньше второй! Это означает, что мы не можем делать ввод-вывод, не можем нормально использовать нативные функции (ведь их нужно вызывать в определённом порядке, чтобы учитывать их побочные эффекты), и не можем взаимодействовать с внешним миром! Если мы введём механизм для упорядочивания выполнения кода, то потеряем преимущество математической строгости кода (а следом потеряем все плюшки функционального программирования). К счастью ещё не всё потеряно. Математики взялись за работу и придумали несколько приёмов для того, чтобы убедится в правильном порядке выполняемых инструкций не потеряв функционального духа. Мы получили лучшее от двух миров! Такие приёмы включают в себя продолжения (continuation), монады (monads) и однозначная типизация (uniqueness typing). В данной статье мы поработаем с продолжениями, а монады и однозначную типизацию отложим до следующего раза. Занятно, что продолжения очень полезная штука, которая используется не только для задания строгого порядка вычислений. Об этом мы тоже поговорим.

Продолжения

Продолжения в программировании играют такую же роль, как «Код да Винчи» в человеческой истории: удивительное разоблачение величайшей тайны человечества. Ну, может не совсем так, но они точно срывают покровы, как в своё время вы научились брать корень из -1.

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

Int i = add(5, 10); int j = square(i);
Функция add возвращает число 15, которое записывается в i , в том месте, где функция и была вызвана. Затем значение i используется при вызове square . Заметьте, что ленивый компилятор не может поменять очередность вычислений, ведь вторая строка зависит от результата первой. Мы можем переписать этот код с использованием Стиль Передачи Продолжения (Continuation Passing Style или CPS), когда add возвращает значение в функцию square .

Int j = add(5, 10, square);
В таком случае add получает дополнительный аргумент - функцию, которая будет вызвана после того, как add закончит работать. В обоих примерах j будет равен 225.

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

System.out.println("Please enter your name: "); System.in.readLine();
Эти две строки не зависят друг от друга, и компилятор волен поменять их порядок по своему хотению. Но если мы перепишем в CPS, то тем самым добавим нужную зависимость, и компилятору придётся проводить вычисления одно за другим!

System.out.println("Please enter your name: ", System.in.readLine);
В таком случае println должен будет вызвать readLine , передав ему свой результат, и вернуть результат readLine в конце. В таком виде мы можем быть уверены, что эти функции будут вызваны по очереди, и что readLine вообще вызовется (ведь компилятор ожидает получить результат последней операции). В случае Java println возвращает void . Но если бы возвращалось какое-либо абстрактное значение (которое может служить аргументом readLine), то это решило бы нашу проблему! Конечно выстраивание таких цепочек функций сильно ухудшает читаемость кода, но с этим можно бороться. Мы можем добавить в наш язык синтаксических плюшек, которые позволят нам писать выражения как обычно, а компилятор автоматически выстраивал бы вычисления в цепочки. Теперь мы можем проводить вычисления в любом порядке, не потеряв при этом достоинств ФП (включая возможность исследовать программу математическими методами)! Если вас это сбивает с толку, то помните, что функции - это всего лишь экземпляры класса с единственным членом. Перепишите наш пример так, чтобы println и readLine были экземплярами классов, так вам станет понятней.

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

Как только мы переведём программу к CPS виду, становится ясно, что у каждой инструкции есть продолжение, функция в которую будет передаваться результат, что в обычной программе было бы точкой вызова. Возьмём любую инструкцию из последнего примера, например add(5,10) . В программе, написанной в CPS виде, понятно что будет являться продолжением - это функция, которую add вызовет по окончанию работы. Но что будет продолжением в случае не-CPS программы? Мы, конечно, можем конвертировать программу в CPS, но нужно ли это?

Оказывается, что в этом нет необходимости. Посмотрите внимательно на наше CPS преобразование. Если вы начнёте писать компилятор для него, то обнаружите, что для CPS версии не нужен стек! Функции никогда ничего не возвращают, в традиционном понимании слова «return», они просто вызывают другую функцию, подставляя результат вычислений. Отпадает необходимость проталкивать (push) аргументы в стек перед каждым вызовом, а потом извлекать (pop) их обратно. Мы можем просто хранить аргументы в каком-либо фиксированном участке памяти и использовать jump вместо обычного вызова. Нам нет нужны хранить первоначальные аргументы, ведь они больше никогда не понадобятся, ведь функции ничего не возвращают!

Таким образом, программы в CPS стиле не нуждаются в стеке, но содержат дополнительный аргумент, в виде функции, которую нужно вызвать. Программы в не-CPS стиле лишены дополнительного аргумента, но используют стек. Что же хранится в стеке? Просто аргументы и указатель на участок памяти, куда должна вернуться функция. Ну как, вы уже догадались? В стеке храниться информация о продолжениях! Указатель на точку возврата в стеке - это то же самое, что и функция, которую нужно вызвать, в CPS программах! Чтобы выяснить, какое продолжение у add(5,10) , достаточно взять из стека точку возврата.

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

Хорошо, теперь мы уяснили, что же такое текущее продолжение. Что это значит? Если мы возьмём текущее продолжение и сохраним его где-нибудь, мы тем самым сохраним текущее состояние программы - заморозим её. Это похоже на режим гибернации ОС. В объекте продолжения хранится информация, необходимая для возобновления выполнения программы с той точки, когда был запрошен объект продолжения. Операционная система постоянно так делает с вашими программами, когда переключает контекст между потоками. Разница лишь в том, что всё находится под контролем ОС. Если вы запросите объект продолжения (в Scheme это делается вызовом функции call-with-current-continuation), то вы получите объект с текущим продолжением - стеком (или в случае CPS - функцией следующего вызова). Вы можете сохранить этот объект в переменную (или даже на диск). Если вы решите «перезапустить» программу с этим продолжением, то состояние вашей программы «преобразуется» к состоянию на момент взятия объекта продолжения. Это то же самое, как переключение к приостановленному потоку, или пробуждение ОС после гибернации. С тем исключением, что вы можете проделывать это много раз подряд. После пробуждения ОС информация о гибернации уничтожается. Если этого не делать, то можно было бы восстанавливать состояние ОС с одной и той же точки. Это почти как путешествие по времени. С продолжениями вы можете себе такое позволить!

В каких ситуациях продолжения будут полезны? Обычно если вы пытаетесь эмулировать состояние в системах лишенных такового по сути. Отличное применение продолжения нашли в Web-приложениях (например во фреймворке Seaside для языка Smalltalk). ASP.NET от Microsoft прикладывает огромные усилия, чтобы сохранять состояние между запросами, и облегчить вам жизнь. Если бы C# поддерживал продолжения, то сложность ASP.NET можно было бы уменьшить в два раза - достаточно было бы сохранять продолжение и восстанавливать его при следующем запросе. С точки зрения Web-программиста не было бы ни единого разрыва - программа продолжала бы свою работу со следующей строки! Продолжения - невероятно полезная абстракция для решения некоторых проблем. Учитывая то, что всё больше и больше традиционных толстых клиентов перемещаются в Web, важность продолжений будет со временем только расти.

Сопоставление с образцом (Pattern matching)

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

Давайте начнём наше знакомство с Pattern matching следующим примером. Вот функция вычисления чисел Фибоначи на Java:

Int fib(int n) { if(n == 0) return 1; if(n == 1) return 1; return fib(n - 2) + fib(n - 1); }
А вот пример на Java-подобном языке с поддержкой Pattern matching-а

Int fib(0) { return 1; } int fib(1) { return 1; } int fib(int n) { return fib(n - 2) + fib(n - 1); }
В чём разница? Компилятор реализует ветвление за нас.

Подумаешь, велика важность! Действительно важность не велика. Было подмечено, что большое количество функций содержат сложные switch конструкции (это отчасти верно для функциональных программ), и было принято решение выделить этот момент. Определение функции разбивается на несколько вариантов, и устанавливается паттерн на месте аргументов функции (это напоминает перегрузку методов). Когда происходит вызов функции, компилятор на лету сравнивает аргументы со всеми определениями и выбирает наиболее подходящий. Обычно выбор падает на самое специализированное определение функции. Например int fib(int n) может быть вызвана при n равном 1, но не будет, ведь int fib(1) - более специализированное определение.

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

Int f(int n < 10) { ... } int f(int n) { ... }
Когда сопоставление с образцом может быть полезно? Список таких случаев на удивление очень большой! Каждый раз, когда вы используете сложные конструкции вложенных if , pattern matching может справиться лучше с меньшим количеством кода. В голову приходит хороший пример с функцией WndProc , которая реализуется в каждой Win32 программе (даже если она спрятана от программиста за высоким забором абстракций). Обычно сопоставление с образцом может даже проверять содержимое коллекций. Например, если вы передаёте массив в функцию, то вы можете отбирать все массивы, у которых первый элемент равен 1, а третий элемент больше 3.

Ещё одним преимуществом Pattern matching является то, что в случае внесения изменений вам не придётся копаться в одной огромной функции. Вам достаточно будет добавить (или изменить) некоторые определения функций. Тем самым мы избавляется от целого пласта паттернов из знаменитой книги Банды Четырёх. Чем сложнее и ветвистее условия, тем полезнее будет использовать Pattern matching. Как только вы начнёте их использовать, то удивитесь, как вы могли раньше без них обходится.

Замыкания

До сих пор мы обсуждали особенности ФП в контексте «чисто» функциональных языков - языков, которые являются реализацией лямбда исчисления и не содержат особенностей, противоречащих формальной системе Чёрча. Тем не менее, многие черты функциональных языков используются за пределами лямбда исчисления. Хотя реализация аксиоматической системы интересна с точки зрения программирования в терминах математических выражений, это не всегда может быть применимо на практике. Многие языки предпочитают использовать элементы функциональных языков не придерживаясь строгой функциональной доктрины. Некоторые такие языки (например Common Lisp) не требуют от переменных быть final - их значения можно менять. Они даже не требуют, чтобы функции зависели только от своих аргументов - функциям дозволенно обращаться к состоянию за пределом своей области видимости. Но при этом они включают в себя такие особенности, как функции высшего порядка. Передача функции в не-чистом языке немного отличается от аналогичной операции в пределах лямбда исчисления и требует наличия интересной особенности под названием: лексическое замыкание. Давайте взглянем на следующий пример. Помните, что в данном случае переменные не final и функция может обращаться к переменным за пределом своей области видимости:

Function makePowerFn(int power) { int powerFn(int base) { return pow(base, power); } return powerFn; } Function square = makePowerFn(2); square(3); // returns 9
Функция make-power-fn возвращает функцию, которая принимает один аргумент и возводит его в определённую степень. Что произойдёт, когда мы попробуем вычислить square(3) ? Переменная power находится вне области видимости powerFn , потому что makePowerFn уже завершилась, и её стек уничтожен. Как же тогда работает square ? Язык должен каким-либо образом сохранить значение power , чтобы функция square могла работать. А что если мы создадим ещё одну функцию cube , которая возводит число в третью степень? Язык должен будет сохранять два значения power для каждой созданной в make-power-fn функции. Феномен хранения этих значений и называется замыканием. Замыкание не только сохраняет аргументы верхней функции. Например замыкание может выглядеть следующим образом:

Function makeIncrementer() { int n = 0; int increment() { return ++n; } } Function inc1 = makeIncrementer(); Function inc2 = makeIncrementer(); inc1(); // returns 1; inc1(); // returns 2; inc1(); // returns 3; inc2(); // returns 1; inc2(); // returns 2; inc2(); // returns 3;
В процессе выполнения значения n сохраняются, и счётчики имеют доступ к ним. Более того у каждого счётчика своя копия n , не смотря на то, что они должны были исчезнуть после того, как функция makeIncrementer отработает. Как же компилятор умудряется это скомпилировать? Что происходит за кулисами замыканий? К счастью у нас есть волшебный пропуск.

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

Class some_function_t { SymbolTable parentScope; // ... }
Если замыкание обращается к переменной, которой нет в локальной области видимости, тогда оно принимает во внимание родительскую область. Вот и всё! Замыкание связывает функциональный мир с миром ООП. Каждый раз, когда вы создаёте класс, который хранит некоторое состояние, и передаёте его куда-то, вспомните про замыкания. Замыкание - это всего лишь объект, который создаёт «атрибуты» на лету, забирая их из области видимости, чтобы вам не пришлось делать это самим.

Что теперь?

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

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

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

К функциональным языкам программирования относят: Lisp, Miranda, Gofel, ML, Standard ML, Objective CAML, F#, Scala, Пифагор и др.

Процедурные языки программирования

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

Процедурные языки программирования: Ada, Basic, Си, КОБОЛ, Pascal, ПЛ/1, Рапира и др.

Стековые языки программирования

Стековый язык программирования − это язык программирования, в котором для передачи параметров используется машинная модель стека. Стековые языки программирования: Forth, PostScript, Java, C# и др. При использовании стека, в качестве основного канала передачи параметров между словами, элементы языка, естественным образом, образуют фразы (последовательное сцепление). Это свойство сближает данные языки с естественными языками.

Аспектно-ориентированные языки программирования 5) Декларативные языки программирования 6) Динамические языки программирования 7) Учебные языки программирования 8) Языки описания интерфейсов 9) Языки прототипного программирования 10) Объектно-ориентированные языки программирования 11) Логические языки программирования 12) Сценарные языки программирования 13) Эзотерические языки программирования

Стандартизация языков программирования. Парадигма программирования

Концепция языка программирования неотрывно связана с его реализацией. Для того чтобы компиляция одной и той же программы различными компиляторами всегда давала одинаковый результат, разрабатываются стандарты языков программирования. Организации, занимающиеся вопросами стандартизации: Американский национальный институт стандартов ANSI, Институт инженеров по электротехнике и электронике IEEE, Организация международных стандартов ISO.

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

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

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

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

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

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

Программирование – процесс создания компьютерных программ. В более широком смысле: спектр деят-сти, связ-ый с созданием и поддержанием в раб. состоянии программ - ПО ЭВМ.

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

Технология программир-я представляет собой набор технологических инструкций, включающих:

· указание последоват-сти выполнения технологич-х операций;

· перечисление условий, при кот-х выполняется та или иная операция;

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

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

Важным этапом создания прогр-го продукта явл. тестирование и отладка.

Отладка − это деятельность, направленная на обнаружение и исправление ошибок в программном продукте с использованием процессов выполнения его программ.

Тестирование − это процесс выполнения его программ на некотором наборе данных, для которого заранее известен результат применения или известны правила поведения этих программ.

Существуют следующие методы тестирования ПС:

1) Статическое тестирование – ручная проверка программы за столом.

2) Детерминированное тестир-е – при разл-х комбинациях исх-х данных.

3) Стохастическое – исх. данные выбир-ся произвольно, на выходе определяется качеств-е совпадение результатов или примерная оценка.

Стили программирования.

Стиль программирования - набор приемов или методов программирования, которые используют программисты, чтобы получить правильные, эффективные, удобные для применения и легкочитаемые программы.

Существует несколько стилей программирования:

1. Процедурное программирование – это программирование, при котором программа представляет собой последовательность операторов. Используется в языках высокого уровня Basic, Fortran и др.
2. Функциональное программирование – это программирование, при котором программа представляет собой последовательность вызовов функций. Используется в языках Lisp и др.
3. Логическоепрограммирование – это программирование, при котором программа представляет собой совокупность определения соотношений между объектами. Используется в языках Prolog и др.

Объектно-ориентированноепрограммирование – это программирование, при котором основой программы является объект представляющий собой совокупность данных и правил их преобразования. Используется в языках Turbo-Pascal, C++ и др.

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

Основные концепции

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

Чистые функции

Чистая функция максимально проста. Она должна всегда возвращать один и тот же результат. Посмотрите на эту JavaScript-функцию:

var z = 10; function add(x, y) { return x + y; }

var z = 10 ; function add (x , y ) { return x + y ;

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

Изменяемые данные и побочные эффекты

Вернемся к примеру кода. Если мы добавим в качестве аргумента функции add() , переменную z , которая объявлена выше, наша функция перестанет быть чистой и предсказуемой. Почему? Потому что z объявлена как обычная переменная: она доступна для изменения из любого места программы.

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

Корректный код чистой функции с z должен выглядеть так:

const x = 10; const z = 10; add (x, z); // вернет 20

const x = 10 ; const z = 10 ; add (x , z ) ; // вернет 20

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

Еще один пример не функционального кода – классические циклы. Вспомним, как выглядит типичный цикл for в JavaScript:

var acc = 0; for (var i = 1; i <= 10; ++i) { acc += i; } console.log(acc); // выведет 55

var acc = 0 ; for (var i = 1 ; i <= 10 ; ++ i ) { acc += i ; console . log (acc ) ; // выведет 55

Первое, на что нужно обратить внимание, – то, что цикл использует var i для подсчета шагов. В функциональном программировании использование такого цикла неприемлемо, так как это может привести к непредсказуемому поведению цикла.

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

function sumRange(start, end, acc) { if (start > end) { return acc; } else { return sumRange(start + 1, end, acc + start); } } console.log(sumRange(1, 10, 0)); // выведет 55

function sumRange (start , end , acc ) { if (start > end ) { return acc ; } else { return sumRange (start + 1 , end , acc + start ) ; console . log (sumRange (1 , 10 , 0 ) ) ; // выведет 55

Такая конструкция позволяет использовать константы для определения начала, конца цикла и шага. В основе такого типа цикла лежит идея вызова функции внутри себя, или рекурсивного вызова. В примере выше функция sumRange() с заданными аргументами делает проверку условия, и в случае ложного результата вызывает саму себя с измененными аргументами.

Композиция функций

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

function addOne(x) { return x + 1; } function timesTwo(x) { return x * 2; } console.log(addOne(timesTwo(3))); // выведет 7 console.log(timesTwo(addOne(3))); // выведет 8

function addOne (x ) { return x + 1 ; function timesTwo (x ) {

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

Польза функционального программирования

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

Недостатки функционального программирования

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

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

Функциональное программирование в языках

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

Более современные функциональные языки, такие как Elm и Elixir, по данным GitHub и Stack Overflow постепенно и уверенно набирают популярность. Рост популярности JavaScript также привел к повышенному интересу к концепциям функционального программирования для применения в этом языке.