64
правки
м (исправил ударения: больш́их — больши́х) |
м (Кавычки "" -> «», пробелы т.д. -> т. д.) |
||
Перед началом описания непосредственно [[w:Функциональное программирование|функционального программирования]] следует обратиться к истории [[w:Программирование|программирования]] вообще. В 1940-х годах появились первые цифровые [[w:Компьютер|компьютеры]], которые программировались переключением различного рода тумблеров, проводков и кнопок. Число таких переключений достигало порядка нескольких сотен и росло с усложнением программ. Потому следующим шагом развития программирования стало создание всевозможных [[w:Язык ассемблера|ассемблерных языков]] с простой [[w:Мнемоника|мнемоникой]].
Но даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться многие люди, поскольку мнемокоды всё ещё оставались слишком сложными, а всякий ассемблер был жёстко связан с архитектурой, на которой исполнялся. Шагом после ассемблера стали так называемые [[w:Процедурное программирование|императивные языки]] [[w:Высокоуровневый язык программирования|высокого уровня]]: [[w:Бейсик|Бейсик]], [[w:Паскаль|Паскаль]], [[w:Си (язык программирования)|Си]], [[w:Ada|Ada]] и прочие, включая [[w:Объектно-ориентированное программирование|объектно-ориентированные]]. Императивными («предписывающими») такие языки названы потому, что ориентированы на последовательное исполнение инструкций, работающих с памятью (т. е. [[w:Присваивание (программирование)|присваиваний]]), и итеративные [[w:Цикл (программирование)|циклы]]. Вызовы функций и процедур, даже [[w:Рекурсия|рекурсивные]], не избавляли такие языки от явной императивности.
В [[w:Парадигма программирования|парадигме]] функционального программирования краеугольный камень, — это [[w:Функция (программирование)|функция]]. Вспомнив историю [[w:Математика|математики]], можно оценить возраст понятия «функция»: ему уже́ около четырёхсот лет, и математики придумали очень много теоретических и практических аппаратов для оперирования функциями, начиная от обыкновенных операций [[w:Дифференцируемая функция|дифференцирования]] и [[w:Интеграл Римана|интегрирования]], заканчивая заумными [[w:Функциональный анализ|функциональными анализами]], теориями [[w:Нечёткое множество|нечётких множеств]] и функций [[w:Комплексное число|комплексных переменных]].
Математические функции выражают связь между исходными данными и итоговым продуктом некоторого процесса. Процесс [[w:Вычисление|вычисления]] также имеет вход и выход, поэтому функция — вполне подходящее и адекватное средство описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно через самих себя. При выполнении программы функции получают параметры, вычисляют и возвращают результат, при необходимости вычисляя значения других функций. На функциональном языке программист не должен описывать порядок вычислений. Нужно просто описать желаемый результат как систему функций.
Как известно, теоретические основы императивного программирования были заложены ещё в [[w:1930-е|1930-х]] годах [[w:Тьюринг, Алан Матисон|Аланом Тьюрингом]] и [[w:Нейман, Джон фон|Джоном фон Нейманом]]. Теория, положенная в основу функционального подхода, также родилась в 20-х — 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать [[w:Шёнфинкель, Мозес|Мозеса Шёнфинкеля]] и [[w:Карри, Хаскелл|Хаскелла Карри]], разработавших [[w:Комбинаторная логика|комбинаторную логику]], и [[w:Чёрч, Алонзо|Алонзо Чёрча]], создателя [[w:Лямбда-исчисление|λ-исчисления]].
Теория так и оставалась теорией, пока в начале 1950-х годов [[w:
В связи с этим обстоятельством всё бо́льшую роль начинает играть [[w:Типизация|типизация]]. В конце 70-х — начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как [[w:Абстракция данных|абстракция данных]] и [[w:Полиморфизм в языках программирования|полиморфизм]]. Появляется множество типизированных функциональных языков: [[w:ML|ML]], [[w:Scheme|Scheme]], [[w:Hope|Hope]], [[w:
В результате вышло так, что практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного [[w:Haskell|Haskell]] в честь
Большинство функциональных языков программирования реализуются как [[w:Интерпретация (информатика)|интерпретируемые]], следуя традициям Лиспа (примечание: большая часть современных реализаций Лиспа содержат компиляторы в [[w:Машинный код|машинный код]]). Таковые удобны для быстрой отладки программ, исключая длительную фазу
В этом курсе для описания примеров функционального программирования будет использован либо некий абстрактный функциональный язык, приближенный к математической нотации, либо Haskell, бесплатные компиляторы которого можно скачать с сайта [http://www.haskell.org/ haskell.org].
*[[w:Модульность (программирование)|модульность]];
*функции — это значения;
*[[w:Чистота функции|чистота]] (отсутствие [[w:Побочный эффект (программирование)|побочных эффектов]]);
*[[w:Ленивые вычисления|отложенные (ленивые) вычисления]].
=== Краткость и простота ===
Программы на функциональных языках обычно короче и проще, чем те же самые программы на императивных языках. Сравним программы на [[w:Си (язык программирования)|Си]] и на абстрактном функциональном языке на примере [[w:Алгоритм сортировки|сортировки]] [[w:Список (информатика)|списка]] [[w:Быстрая сортировка|быстрым методом]] [[w:Хоар, Чарльз Энтони Ричард|Хоара]] (пример, уже ста́вший классическим при описании преимуществ функциональных языков).
'''Пример 1. Быстрая сортировка Хоара на
<!-- <code>void quickSort (int a[], int l, int r)
}</code> -->
<source lang="C">
void qsort(int *
int vl = *ds, *now = ds, *inl = ss, *ing = ss + (de - ds);
if ( de <= ds + 1 ) return;
for( ; now != de; ++now ){
if ( *now <= vl ) *inl++ = *now;
else *ing-- = *now;
}
*++inl = vl;
qsort(ds, ds + (inl - ss), ss);
qsort(ds + (inl - ss), de, inl + 1);
}
</source>
#Если список пуст, то результатом также будет пустой список.
#Иначе выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет
'''Пример 3. Быстрая сортировка Хоара на языке
<code>quickSort [] = []
=== Строгая типизация ===
Из современных языков программирования многие суть строго типизированные. Строгая типизация позволяет компилятору [[w:Оптимизация компилятора|оптимизировать]] программы, использовать конкретные типы и [[w:Контейнер (программирование)|контейнеры]] конкретных типов вместо [[w:Шаблон (программирование)|шаблонных]], вариантных типов, более громоздких в реализации. Кроме того, строгая типизация позволяет оградиться от части ошибок, связанных с неожидаемым
В примере с быстрой сортировкой Хоара видно, что есть ещё одно важное отличие между вариантом на Си и вариантом на Хаскеле: функция на Си сортирует список значений типа <code>int</code> ([[w:Целое число|целых чисел]]), а функция на абстрактном функциональном языке — список значений любого типа, принадлежащего к классу упорядоченных величин. Последняя функция может сортировать и список целых чисел, и список [[w:Вещественное число|чисел с плавающей точкой]], и список [[w:Строковый тип|строк]]. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать функцию <tt>quickSort</tt> и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным [[w:Полиморфизм в языках программирования|полиморфизмом]], и поддерживается большинством функциональных языков.
Ещё одно проявление полиморфизма — [[w:Перегрузка функции|перегрузка функций]], позволяющая давать разным, но подобным функциям одинаковые имена. Типичный пример перегруженной операции — обычная [[w:Сложение (математика)|операция сложения]]. Функции сложения для целых чисел и чисел с плавающей точкой различны, но для удобства они носят одно имя. Некоторые функциональные языки помимо параметрического полиморфизма поддерживают и перегрузку операций.
В языке
В некоторых языках, например в
=== Модульность ===
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (
=== Функции суть значения ===
В функциональных языках, равно как и вообще в языках программирования и
<code>square (N) = N * N</code>
(отсутствие побочных эффектов)
В императивных языках функция в процессе своего выполнения может читать и изменять значения глобальных [[w:Переменная (программирование)|переменных]] и осуществлять операции [[w:ввод
Описывать функции без побочных эффектов позволяет практически любой язык. Однако некоторые языки поощряют или даже требуют от функции побочных эффектов. Например, во многих объектно-ориентированных языках в функцию-член класса передаётся скрытый параметр (чаще он называется <tt>this</tt> или <tt>self</tt>), который эта функция неявно изменяет.
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путём разбора и сбора существующих. О ненужных объектах позаботится встроенный в язык
Каковы же преимущества чистых функциональных языков? Помимо упрощения анализа программ есть ещё одно — [[w:Параллельные
=== Отложенные вычисления ===
В традиционных языках программирования (например,
Если функциональный язык не поддерживает отложенные вычисления, то он называется строгим. На самом деле, в таких языках порядок вычисления строго определён. В качестве примера строгих языков можно привести
Очень часто строгие языки включают в себя средства поддержки некоторых полезных возможностей, присущих нестрогим языкам, например бесконечных списков. В поставке
== Решаемые задачи ==
Если даны следующие объекты:
*<math>P (x_{1},\, x_{2},\, \ldots, \,x_{n})</math> — некоторая процедура.
*<math>x_{1} = a_{1},\: x_{2} = a_{2}</math> — известные значения параметров.
*<math>x_{3},\, \ldots,\, x_{n}</math> — неизвестные значения параметров.
Требуется получить остаточную процедуру <math>P_{1} (x_{3},\, \ldots,\, x_{n})</math>. Эта задача решается только на узком классе программ.
'''2. Построение математического описания функций.'''
В этом разделе приведено краткое описание некоторых языков функционального программирования (очень немногих). Дополнительную информацию можно почерпнуть, просмотрев ресурсы, перечисленные в следующем разделе.
#'''[[w:Лисп|Лисп]]''' (List processor). Считается первым функциональным языком программирования. Поддерживает динамическую и факультативно статическую типизацию. Содержит массу императивных свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов-по-значению. В стандарт Common Lisp входит Common Lisp Object System (CLOS) - объектная система Common Lisp, которая по многим параметрам превосходит объектные системы в других языках (поддерживает метаобъектный протокол, мультиметоды и т. д.).
#'''ISWIM''' (If you See What I Mean). Функциональный язык-прототип. Разработан Питером Ландиным в 60-х годах XX ве́ка для демонстрации того, каким может быть язык функционального программирования. Вместе с языком П. Ландин разработал и специальную виртуальную машину для исполнения программ на ISWIM’е. Эта виртуальная машина, основанная на вызове-по-значению, получила название SECD-машины. На синтаксисе языка ISWIM базируется синтаксис многих функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.
#'''[[w:Scheme|Scheme]]'''. Диалект Lisp’а, предназначенный для научных исследований в области computer science. При разработке Scheme был сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем Common Lisp.
|
правки