История функционального программирования - Основные свойства функциональных языков программирования

Широко известно, что теоретические основы императивного программирования были заложены еще в 30-х годах XX века учеными Аланом Тьюрингом и Джоном фон Нейманом. Теория, положенная в основу функционального подхода, также родилась в 20-х-30-х годах XX столетия. В числе разработчиков математических основ функционального программирования можно назвать Мозеса Шенфинкеля (Германия и Россия) и Хаскелла Карри (Англия), разработавших комбинаторную логику, а также Алонзо Черча (США), создателя - исчисления.

Теория так и оставалась теорией, пока в начале 50-х годах XX века Джон МакКарти не разработал язык Lisp, который стал первым почти функциональным языком программирования и на протяжении многих лет оставался единственным. Хотя Lisp все еще используется (как, например, и FORTRAN), он уже не удовлетворяет некоторым современным запросам, которые заставляют разработчиков программ взваливать как можно большую ношу на компилятор, облегчив тем самым свой непосильный труд. Необходимость в этом, конечно же, возникла из-за все более возрастающей сложности программного обеспечения.

В связи с этим все большую роль начинает играть типизация. В конце 70-х-начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов, как абстракция данных и полиморфизм. Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число их диалектов, применяемых для решения конкретных задач.

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

В первую очередь, большинство функциональных языков программирования реализуются как интерпретаторы, следуя традициям языка Lisp. Интерпретаторы удобны для быстрой отладки программ, исключая длительную фазу компиляции, тем самым укорачивая обычный цикл разработки. Однако с другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения в несколько раз. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, Objective Caml) или код на C/C++ (например, Glasgow Haskell Compiler). Практически каждый компилятор с функционального языка реализован на этом же языке.

Концепции

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

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

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

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

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

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

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

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

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

Рекурсия

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

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

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

Функциональные языки можно классифицировать по тому, как обрабатываются аргументы функции в процессе ее вычисления. Технически различие заключается в денотационной семантике выражения. К примеру, при строгом подходе к вычислению выражения <source lang="python"> print(len([2+1, 3*2, 1/0, 5-4])) </source> на выходе будет ошибка, так как в третьем элементе списка присутствует деление на ноль. При нестрогом подходе значением выражения будет 4, поскольку для вычисления длины списка значения его элементов, строго говоря, не важны и могут вообще не вычисляться. При строгом (аппликативном) порядке вычисления заранее подсчитываются значения всех аргументов перед вычислением самой функции. При нестрогом подходе (нормальный порядок вычисления) значения аргументов не вычисляются до тех пор, пока их значение не понадобится при вычислении функции.

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

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

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

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

В языке C# версии 3.0 и выше можно использовать ?-функции для написания программы в функциональном стиле.

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

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

Простой пример двух решений одной задачи (используется один и тот же язык Python) иллюстрирует это. <source lang="python">

1. императивный стиль

Target = [] # создать пустой список for item in source_list: # для каждого элемента исходного списка

</source> Функциональная версия выглядит по-другому: <source lang="python">

    1. функциональный стиль 2. языки ФП часто имеют встроенную функцию compose()

Compose2 = lambda A, B: lambda x: A(B(x)) target = map(compose2(F, G), source_list) </source>

Язык программирование интерпретатор haskell

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

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

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

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

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

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

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

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

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

Рекурсия

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

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

Функциональные языки можно классифицировать по тому, как обрабатываются аргументы функции в процессе ее вычисления. Технически различие заключается в денотационной семантике выражения. К примеру, при строгом подходе к вычислению выражения <source lang="python"> print(len([2+1, 3*2, 1/0, 5-4])) </source> на выходе будет ошибка, так как в третьем элементе списка присутствует деление на ноль. При нестрогом подходе значением выражения будет 4, поскольку для вычисления длины списка значения его элементов, строго говоря, не важны и могут вообще не вычисляться. При строгом (аппликативном) порядке вычисления заранее подсчитываются значения всех аргументов перед вычислением самой функции. При нестрогом подходе (нормальный порядок вычисления) значения аргументов не вычисляются до тех пор, пока их значение не понадобится при вычислении функции.

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

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

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

Похожие статьи




История функционального программирования - Основные свойства функциональных языков программирования

Предыдущая | Следующая