|
== Общие слова́ ==
{{Эпиграф|Функциональное программирование ставит своей целью придать каждой программе простуюпростое математическуюматематическое интерпретациютолкование. ЭтаЭто интерпретациятолкование должнадолжно быть независиманезависимо от деталей исполнения и понятнапонятно людям, которые не имеютимеющим научной степени в предметной области.|Лоренс Паулсон}}
Прежде чем начать описание собственно [[w:Функциональное программирование|функционального программирования]], следует обратиться к истории [[w:Программирование|программирования]] вообще. В 40-х годах XX ве́ка появились первые цифровые [[w:Компьютер|компьютеры]], которые, как известно, программировались переключением различного рода тумблеров, проводков и кнопок. Число таких переключений достигало порядка нескольких сотен и неумолимо росло с усложнением программ. Потому следующим шагом развития программирования стало создание всевозможных [[w:Язык ассемблера|ассемблерных языков]] с простой [[w:Мнемоника|мнемоникой]].
Возвращаясь к функциональному программированию... Краеугольным камнем парадигмы функционального программирования, как будет показано далее, является [[w:Функция|функция]]. Вспомнив историю [[w:Математика|математики]], можно оценить возраст понятия «функция»: ему уже́ около четырёхсот лет, и математики придумали очень много теоретических и практических аппаратов для оперирования функциями, начиная от обыкновенных операций [[w:Дифференцируемая функция|дифференцирования]] и [[w:Интеграл Римана|интегрирования]], заканчивая заумными [[w:Функциональный анализ|функциональными анализами]], теориями [[w:Нечёткое множество|нечётких множеств]] и функций [[w:Комплексное число|комплексных переменных]].
Математические функции выражают связь между параметрами (входом) и результатом (выходом) некоторого процесса. Так какПроцесс [[w:Вычисление|вычислениевычисления]] — это тоже процесс,также имеющийимеет вход и выход, поэтому функция является— вполне подходящимподходящее и адекватнымадекватное средствомсредство описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно — через самих себя. В процессеПри выполнениявыполнении программы функции получают параметры, вычисляют и возвращают результат, в случаепри необходимости вычисляя значения других функций. Программируя на функциональном языке, программист не должен описывать порядок вычислений. Ему необходимо просто описа́тьописать желаемый результат в виде системы функций.
Обращаясь к задачам курса, необходимо в первую очередь подчеркнуть, что функциональноеФункциональное программирование, равно как и [[w:Логическое программирование|логическое программирование]], нашло большое применение в [[w:Искусственный интеллект|искуственном интеллекте]] и его приложениях. Поэтому здесь функциональное программирование рассматривается чрезвычайно скрупулёзно и со всеми возможными подробностями. Далее в этой лекции рассматривается история функционального программирования, свойства функциональных языков, решаемые задачи и некоторые справочные данныесведения.
== История функционального программирования ==
Как известно, теоретические основы императивного программирования были заложены ещё в 30[[w:1930-е|1930-х годах]] XX ве́кагодах [[w:Тьюринг, Алан Матисон|Аланом Тьюрингом]] и [[w:Нейман, Джон фон|Джоном фон Нейманом]]. Теория, положенная в основу функционального подхода, также родилась в 20-х — 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать [[w:Шёнфинкель, Мозес|Мозеса Шёнфинкеля]] (Германия и Россия) и [[w:Карри, Хаскелл|Хаскелла Карри]] (Англия), разработавших [[w:Комбинаторная логика|комбинаторную логику]], а также [[w:Чёрч, Алонзо|Алонзо Чёрча]] (США), создателя [[w:Лямбда-исчисление|λ-исчисления]].
Теория так и оставалась теорией, пока в начале 501950-х годов прошлого ве́ка [[w:МакКарти, Джон|Джон МакКарти]] не разработал язык [[w:Лисп|Lisp]], который стал первым почти функциональным языком программирования и на протяжении многихмногие летгоды оставался единственным таковым. Хотя LispЛисп всё ещё используется (как, например, и [[w:Фортран|FORTRAN]]), он уже́ не удовлетворяет некоторым современным запросам, которые заставляют разработчиков программ взваливать как можно бо́льшую но́шу на [[w:Компилятор|компилятор]], облегчив тем самымтак свой непосильный труд. НеобходимостьНужда в этом, конечно же, возникла из-за всё более возрастающей сложности [[w:Программное обеспечение|программного обеспечения]].
В связи с этим обстоятельством всё бо́льшую роль начинает играть [[w:Типизация|типизация]]. В конце 70-х — начале 80-х годов XX ве́кавека интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как [[w:Абстракция данных|абстракция]] данных]] и [[w:Полиморфизм в языках программирования|полиморфизм]]. Появляется множество типизированных функциональных языков: [[w:ML|ML]], [[w:Scheme|Scheme]], [[w:Hope|Hope]], [[w:Miranda|Miranda]], [[w:Clean|Clean]] и многие другие. Вдобавок постоянно увеличивается число диалектов.
В результате вышло так, что практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многочисленныемногие более мелкие проблемы. Чтобы исправить ситуациюположение, объединеннаяобъединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного [[w:Haskell|Haskell]] в честь [[w:Карии, Хаскелл Брукс|Хаскелла Карри]], была создана в начале 90-х годов. В настоящее времяНыне действителен стандарт Haskell-98.
В первую очередь большинствоБольшинство функциональных языков программирования реализуются как [[w:ИнтерпретаторИнтерпретация|интерпретаторыинтерпретируемые]], следуя традициям Lisp’аЛиспа. ИнтерпретаторыТаковые удобны для быстрой отладки программ, исключая длительную фазу [[w:Компиляция|компиляции]], тем самым укорачивая обычный [[w:Разработка программного обеспечения|цикл разработки]]. Однако сС другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения в несколько раз. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, [[w:OCaml|Objective Caml]]) или код на [[w:Си (язык программирования)|CСи]]/[[w:C++|CСи++]] (например, Glasgow Haskell Compiler). Что показательно, практически каждый компилятор с функционального языка реализован на этом же са́мом языке.
В этом курсе для описания примеров функционального программирования будет использоватьсяиспользован либо некий абстрактный функциональный язык, приближенный к математической нотации, либо Haskell, бесплатные компиляторы которого можно скачать с сайта [http://www.haskell.org/ http://www.haskell.org/].
== Свойства функциональных языков ==
ВКак качествеосновные основных свойствсвойства функциональных языков кратко рассмотрим следующие:
*краткость и простота;
*строгая типизация;
=== Краткость и простота ===
Программы на функциональных языках обычно намного короче и проще, чем те же самые программы на императивных языках. Сравним программы на [[w:Си (язык программирования)|C]] и на абстрактном функциональном языке на примере [[w:Алгоритм сортировки|сортировки]] списка [[w:Быстрая сортировка|быстрым методом]] [[w:Хоар, Чарльз Энтони Ричард|Хоара]] (пример, уже́ ставший классическим при описании преимуществ функциональных языков).
'''Пример 1. Быстрая сортировка Хоара на [[w:Си (язык программирования)|CСи]]'''
void quickSort (int a[], int l, int r)
-->
Это читается так:
Пример 2 следует читать так:
#Если список пуст, то результатом также будет пустой список.
#Иначе (если список не пуст) выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет являться конкатенация (сращивание) отсортированного списка из всех элементов хвоста,хвост которые меньшеменьших либо равныравных голове, списка из самой головы и списка из всех элементов хвоста, которые большебо́льших головы.
'''Пример 3. Быстрая сортировка Хоара на языке [[w:Haskell|Haskell]]'''
<code>quickSort [] = []
quickSort (x:xs) = quickSort [y | y <- xs, y <= x] ++ [x] ++ quickSort [y | y <- xs, y > x]</code>
Как видно, даже на таком простом примере функциональный стиль программирования выигрывает и по количеству написанного кода и по его элегантности.
'''Пример 4. Определение N-ого [[w:Числа Фибоначчи|числа́ Фибоначчи]]'''
<code>fibb (0) = 1
fibb (1) = 1
fibb (N) = fibb (N – 2) + fibb (N – 1)</code>
Механизм сопоставления с образцом будет расмотрен в дальнейших лекциях, однако здесь видно, что функциональные языки выходят на более абстрактный уровень, чем традиционые императивные языки (здесь не рассматривается объектно-ориентированная парадигма и её расширения).
=== Строгая типизация ===
Практически все современные языки программирования являютсясуть строго типизированнымитипизированные языкамиязыки (возможно, за исключением [[w:JavaScript|JavaScript]] и его диалектов, не существует императивных языков без понятия «[[w:Тип данных|тип]]»). Строгая типизация обеспечивает безопасность. Программа, прошедшая проверку типов просто не может выпасть в [[w:Операционная система|операционную систему]] с сообщением, подобным «access violation», особенно это касается таких языков, как [[w:Си (язык программирования)|CСи]]/[[w:C++|CСи++]] и [[w:Паскаль|Object Pascal]], где применение [[w:Указатель|указателей]] является типичным способом использования языка. В функциональных языках бо́льшая часть ошибок может быть исправлена на стадии компиляции, поэтому стадия отладки и общее время разработки программ сокращаются. Вдобавок к этому строгая типизация позволяет компилятору генерироватьсоздавать более эффективный код и тем самымэтим ускорять выполнение программ.
Рассматривая пример с быстрой сортировкой Хоара, можно увидеть, что помимо уже́ упомянутых отличий между вариантом на языке [[w:Си (язык программирования)|CСи]] и вариантом на абстрактном функциональном языке, есть ещё одно важное отличие: функция на [[w:Си (язык программирования)|C]] сортирует список значений типа int ([[w:Целое число|целых чисел]]), а функция на абстрактном функциональном языке — список значений любого типа, который принадлежитпринадлежащего к классу упорядоченных величин. Поэтому последняяПоследняя функция может сортировать и список целых чисел, и список [[w:Вещественное число|чисел с плавающей точкой]], и список [[w:Строковый тип|строк]]. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать функцию <tt>quickSort</tt> и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным [[w:Полиморфизм в языках программирования|полиморфизмом]], и поддерживается большинством функциональных языков.
Ещё однойодно разновидностьюпроявление полиморфизма является— [[w:Перегрузка функции|перегрузка функций]], позволяющая давать различнымразным, но в чём-то схожимподобным функциям одинаковые имена. ТипичнымТипичный примеромпример перегруженной операции является— обычная [[w:Сложение (математика)|операция сложения]]. Функции сложения для целых чисел и чисел с плавающей точкой различны, однаконо для удобства они носят одно и то же имя. Некоторые функциональные языки помимо параметрического полиморфизма, поддерживают и перегрузку операций.
В языке [[w:C++|CСи++]] имеется такое понятие, как шаблон, которое позволяет программисту определять полиморфные функции, подобные <tt>quickSort</tt>. В стандартную библиотеку Си++, — [[w:C++Standard Template Library|C++STL]] STL, входит такая функция и множество других полиморфных функций. Но шаблоны [[w:CСи++|C++]], как и родовые функции [[w:Ада|AdaАды]], на самом деле порождают множество перегруженных функций, которые, кстати, компилятор долженнужно каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в функциональных языках полиморфная функция <tt>quickSort</tt> — это одна единственная функция.
В некоторых языках, например в [[w:Ада|AdaАде]], строгая типизация вынуждает программиста явно описывать тип всех значений и функций. ЧтобыДля избежатьизбежания этого, в строго типизированные функциональные языки встроен специальный механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста., Этот— механизм называется механизмом [[w:Приведение типа|вывода типов]]. Известно несколько таких механизмов, однако большинство из них являютсясуть разновидностямиразновидности модели типизации [[w:Хиндли, Роджер|Хиндли]]-[[w:Милнер, Робин|Милнера]], разработанной в начале 801980-х годов XX ве́ка. Таким образом,Поэтому в большинстве случаев можно не указывать типы функций.
=== Модульность ===
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей ([[w:Модульность (программирование)|модулей]]) с чётко определёнными связями между ними. Тем самымТак облегчается процесс проектирования и последующей поддержки больши́х программных систем. Поддержка модульности не являетсяесть свойствомсвойство именно функциональных языков программирования, однаконо поддерживается большинством таких языков. Существуют очень развитые модульные императивные языки. В качестве примеров подобных языков можно привестиПримеры: [[w:Модула-2 (язык программирования)|Modula-2]] и [[w:Ада (язык программирования)|Ada-95]].
=== Функции — этосуть значения ===
В функциональных языках, (равно как и вообще в языках программирования и [[w:Математика|математике]]), функции могут быть переданы другим функциям в качестве [[w:Аргумент|аргумента]] или возвращены в качестве результата. Функции, принимающие функциональные аргументы, называются [[w:Функция высшего порядка|функциями высших порядков]] или [[w:Функционал|функционалами]]. Самый, пожалуй, известный функционал, это функция <tt>map</tt>. Эта функция применяет некоторую функцию ко всем элементам списка, формируя из результатов заданной функции другой список. Например, определив функцию возведения целого числа в квадрат как:
square (N) = N * N
| 