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

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

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

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

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

λ-исчисления являются основой для функционального программирования, многие функциональные языки можно рассматривать как «надстройку» над ними^[1].

Содержание

1 Языки функционального программирования
2 История
3 Концепции
4 Стили программирования
5 Особенности
- 5.1 Сильные стороны
- 5.2 Недостатки
6 Практическое применение
7 См. также
8 Примечания
9 Литература
10 Ссылки

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

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

Наиболее известными языками функционального программирования являются^[2]:

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

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

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

[править] История

Лямбда-исчисление стало теоретической базой для описания и вычисления функций. Являясь математической абстракцией, а не языком программирования, оно составило базис почти всех языков функционального программирования на сегодняшний день. Сходное теоретическое понятие, комбинаторная логика, является более абстрактным, нежели λ-исчисления и было создано раньше. Эта логика используется в некоторых эзотерических языках, например в Unlambda. И λ-исчисление, и комбинаторная логика были разработаны для более ясного и точного описания принципов и основ математики^[4].

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

Язык обработки информации (Information Processing Language (англ.)русск., IPL) иногда определяется как самый первый машинный функциональный язык^[7]. Это язык ассемблерного типа для работы со списком символов. В нём было понятие «генератора», который использовал функцию в качестве аргумента, а также, поскольку это язык ассемблерного уровня, он может позиционироваться как язык, имеющий функции высшего порядка. Однако, в целом IPL акцентирован на использование императивных понятий^[8].

Кеннет Е. Айверсон разработал язык APL в начале шестидесятых, документировав его в своей книге A Programming Language (ISBN 9780471430148)^[9]. APL оказал значительное влияние на язык FP (англ.)русск., созданный Джоном Бэкусом. В начале девяностых Айверсон и Роджер Хуэй (англ.)русск. создали преемника APL в язык программирования J. В середине девяностых Артур Витни (англ.)русск., ранее работавший с Айверсоном, создал язык K, который впоследствии использовался в финансовой индустрии на коммерческой основе.

В семидесятых в университете Эдинбурга Робин Милнер создал язык ML, а Дэвид Тернер начинал разработку языка SASL в университете Сент-Эндрюса и, впоследствии, язык Miranda в университете города Кент. В конечном итоге на основе ML были созданы несколько языков, среди которых наиболее известные Objective Caml и Standard ML. Также в семидесятых осуществлялась разработка языка программирования, построенного по принципу Scheme (реализация не только функциональной парадигмы), получившего описание в известной работе «Lambda Papers», а также в книге восемьдесят пятого года «Structure and Interpretation of Computer Programs», в которой принципы функционального программирования были донесены до более широкой аудитории.^{[источник не указан 1089 дней]}

В восьмидесятых Пер Мартин-Лёф создал интуиционистскую теорию типов (также называемую конструктивной). В этой теории функциональное программирование получило конструктивное доказательство того, что ранее было известно как зависимый тип. Это дало мощный толчок к развитию диалогового доказательства теорем и к последующему созданию множества функциональных языков. Haskell был создан в конце восьмидесятых в попытке соединить множество идей, полученных в ходе исследования функционального программирования.^[3]

[править] Концепции

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

[править] Функции высших порядков

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

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

Функции высших порядков весьма схожи с функциями первого класса, оба типа позволяют иметь на выходе и в качестве аргумента функцию. Грань между этими типами функций довольно тонкая: функции высших порядков - это математическая концепция функций, оперирующих другими функциями, а функции первого класса в термин компьютерных наук, описывающий конструкцию языка, не имеющую ограничений на свое использование (функция первого порядка может использоваться всюду в программе, как и другие сущности первого класса, к примеру число, включая возможность быть аргументом других функций и быть на выходе у них).^{[источник не указан 1089 дней]}

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

[править] Чистые функции

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

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

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

Если нет никакой зависимости по данным между двумя чистыми функциями, то порядок их вычисления можно поменять или распараллелить (говоря иначе вычисление чистых функций удовлетворяет принципам thread-safe)

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

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

[править] Рекурсия

Основная статья: Рекурсия

В функциональных языках цикл обычно реализуется в виде рекурсии. Строго говоря, в функциональной парадигме программирования нет такого понятия, как цикл. Рекурсивные функции вызывают сами себя, позволяя операции выполняться снова и снова. Для использования рекурсии может потребоваться большой паллетный стек, но этого можно избежать в случае хвостовой рекурсии. Хвостовая рекурсия может быть распознана и оптимизирована компилятором в код, получаемый после компиляции аналогичной итерации в императивном языке программирования. Стандарты языка Scheme требуют распознавать и оптимизировать хвостовую рекурсию. Оптимизировать хвостовую рекурсию можно путём преобразования программы в стиле использования продолжений при её компиляции, как один из способов.^{[источник не указан 1089 дней]}

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

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

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

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

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

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

[править] ФП в нефункциональных языках

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

В языке C указатели на функцию в качестве типов аргументов могут быть использованы для создания функций высшего порядка. Функции высшего порядка и отложенная списковая структура реализованы в библиотеках С++. В языке C# версии 3.0 и выше можно использовать λ-функции для написания программы в функциональном стиле. В сложных языках, типа Алгол-68, имеющиеся средства метапрограммирования (фактически, дополнения языка новыми конструкциями) позволяют создать специфичные для функционального стиля объекты данных и программные конструкции, после чего можно писать функциональные программы с их использованием.^{[источник не указан 1089 дней]}

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

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

# imperative style
target = [] # create empty list
for item in source_list: # iterate over each thing in source
    trans1 = G(item) # transform the item with the G() function
    trans2 = F(trans1) # second transform with the F() function
    target.append(trans2) # add transformed item to target

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

# functional style
# FP-oriented languages often have standard compose()
compose2 = lambda A, B: lambda x: A(B(x))
target = map(compose2(F, G), source_list)

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

[править] Особенности

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

[править] Сильные стороны

[править] Повышение надёжности кода

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

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

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

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

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

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

[править] Возможности параллелизма

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

[править] Недостатки

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

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

[править] Практическое применение

Летом 2009 года в МинЖКХ внедрена система сбора и анализа статистической отчетности о подготовке муниципалитетов Московской области к осенне-зимнему периоду исключительно на языке ФП (XQuery), без использования традиционных языков программирования^{[источник не указан 875 дней]}.

[править] См. также

[править] Примечания

в‘ А. Филд, П. Харрисон Функциональное программирование: Пер. с англ. в М.: Мир, 1993. в 637 с, ил. ISBN 5-03-001870-0. Стр. 120 [Глава 6: Математические основы: λ-исчисление].
в‘ Tiobe Programming Community Index
в‘ ¹ ² Пол Хьюдак (англ.)русск. (September 1989). «Conception, evolution, and application of functional programming languages» (PDF). ACM Computing Surveys 21 (3): 359в411. DOI:10.1145/72551.72554.
в‘ Роджер Пенроуз Глава 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 г.
в‘ McCarthy, John (June 1978). «History of Lisp». In ACM SIGPLAN History of Programming Languages Conference: 217223. DOI:10.1145/800025.808387.
в‘ J. Harrison, 1997, Гл. 3. λ-исчисление как язык программирования
в‘ В своих мемуарах Герберт Саймон (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 утверждает, что его, Al. Ньюэлл, и Клифф Шоу которых «часто называют родителями искусственного интеллекта» за написание программы Logic Theorist (англ.)русск. автоматически доказывающей теоремы из Principia Mathematica (англ.)русск.. Для того, чтобы достичь этого, они должны были придумать язык и парадигму, которую, ретроспективно, можно рассматривать как функциональное программирование.
в‘ History of Programming Languages: IPL
в‘ XIV. APL Session // History of Programming Language / Richard L. Wexelbblat. в Academic Press, 1981. в С. 661-693. в 749 с.
в‘ Скачать PDF: «Техники функционального программирования, В. А. Потапенко» стр. 8 «Функции высших порядков».
в‘ Н. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений в М.: ГИНФО, 2002. в 260 с. Стр. 14 п. 3.1. Ленивые и энергичные вычисления
в‘ Ахмечет В. «Функциональное программирование для всех»

[править] Литература

Городняя Л. В. Основы функционального программирования. Курс лекций в М.: Интернет-университет информационных технологий, 2004. С. 280. ISBN 5-9556-0008-6
Душкин Р. В. Функциональное программирование на языке Haskell. в М.: ДМК Пресс, 2006. С. 608. ISBN 5-94074-335-8
А. Филд, П. Харрисон Функциональное программирование: Пер. с англ. в М.: Мир, 1993. в 637 с, ил. ISBN 5-03-001870-0
Н. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений в М.: ГИНФО, 2002. в 260 с.
John Harrison. Функциональное программирование. Курс лекций = Functional Programming. в 1997.

[править] Ссылки

[lambda-0] в‘ А. Филд, П. Харрисон Функциональное программирование: Пер. с англ. в М.: Мир, 1993. в 637 с, ил. ISBN 5-03-001870-0. Стр. 120 [Глава 6: Математические основы: λ-исчисление].

[top-fp-langs-1] в‘ Tiobe Programming Community Index

[hudak1989-2] в‘ ¹ ² Пол Хьюдак (англ.)русск. (September 1989). «Conception, evolution, and application of functional programming languages» (PDF). ACM Computing Surveys 21 (3): 359в411. DOI:10.1145/72551.72554.

[3] в‘ Роджер Пенроуз Глава 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 г.

[4] в‘ McCarthy, John (June 1978). «History of Lisp». In ACM SIGPLAN History of Programming Languages Conference: 217223. DOI:10.1145/800025.808387.

[J._Harrison.E2.80.941997.E2.80.94.D0.93.D0.BB._3._.CE.BB-.D0.B8.D1.81.D1.87.D0.B8.D1.81.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.B0.D0.BA_.D1.8F.D0.B7.D1.8B.D0.BA_.D0.BF.D1.80.D0.BE.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D1.8F.E2.80.94-5] в‘ J. Harrison, 1997, Гл. 3. λ-исчисление как язык программирования

[6] в‘ В своих мемуарах Герберт Саймон (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 утверждает, что его, Al. Ньюэлл, и Клифф Шоу которых «часто называют родителями искусственного интеллекта» за написание программы Logic Theorist (англ.)русск. автоматически доказывающей теоремы из Principia Mathematica (англ.)русск.. Для того, чтобы достичь этого, они должны были придумать язык и парадигму, которую, ретроспективно, можно рассматривать как функциональное программирование.

[7] в‘ History of Programming Languages: IPL

[8] в‘ XIV. APL Session // History of Programming Language / Richard L. Wexelbblat. в Academic Press, 1981. в С. 661-693. в 749 с.

[functional-9] в‘ Скачать PDF: «Техники функционального программирования, В. А. Потапенко» стр. 8 «Функции высших порядков».

[lenivie-10] в‘ Н. А. Роганова Функциональное программирование: Учебное пособие для студентов высших учебных заведений в М.: ГИНФО, 2002. в 260 с. Стр. 14 п. 3.1. Ленивые и энергичные вычисления

[11] в‘ Ахмечет В. «Функциональное программирование для всех»

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

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

Содержание

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

[править] История

[править] Концепции

[править] Функции высших порядков

[править] Чистые функции

[править] Рекурсия

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

[править] ФП в нефункциональных языках

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

[править] Особенности

[править] Сильные стороны

[править] Повышение надёжности кода

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

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

[править] Возможности параллелизма

[править] Недостатки

[править] Практическое применение

[править] См. также

[править] Примечания

[править] Литература

[править] Ссылки

Личные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Участие

Печать/экспорт

Инструменты

На других языках