Основы функционального программирования/Вводная лекция: различия между версиями

Перед началом описания непосредственно [[w:Функциональное программирование|функционального программирования]] следует обратиться к истории [[w:Программирование|программирования]] вообще. В 1940-х годах появились первые цифровые [[w:Компьютер|компьютеры]], которые, программировались переключением различного рода тумблеров, проводков и кнопок. Число таких переключений достигало порядка нескольких сотен и росло с усложнением программ. Потому следующим шагом развития программирования стало создание всевозможных [[w:Язык ассемблера|ассемблерных языков]] с простой [[w:Мнемоника|мнемоникой]].

Но даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться многие люди, поскольку мнемокоды всё ещё оставались слишком сложными, тем более чтоа всякий ассемблер был жёстко связан с архитектурой, на которой исполнялся. Шагом после ассемблера стали так называемые [[w:Процедурное программирование|императивные языки]] [[w:Высокоуровневый язык программирования|высокого уровня]]: [[w:Бейсик|BASICБейсик]], [[w:Паскаль|PascalПаскаль]], [[w:Си (язык программирования)|CСи]], [[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:Лисп|LispЛисп]], который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Хотя Лисп всё ещё используется (как, например, и [[w:Фортран|FORTRANФортран]]), он уже́ не удовлетворяет некоторым современным запросам, которые заставляют разработчиков программ взваливать как можно бо́льшую но́шу на [[w:Компилятор|компилятор]], облегчив так свой труд. Нужда в этом, конечно же, возникла из-за всё более возрастающей сложности [[w:Программное обеспечение|программного обеспечения]].

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

Программы на функциональных языках обычно короче и проще, чем те же самые программы на императивных языках. Сравним программы на [[w:Си (язык программирования)|CСи]] и на абстрактном функциональном языке на примере [[w:Алгоритм сортировки|сортировки]] списка [[w:Быстрая сортировка|быстрым методом]] [[w:Хоар, Чарльз Энтони Ричард|Хоара]] (пример, уже́ ставший классическим при описании преимуществ функциональных языков).

Ещё одно средство, позволяющее сократить программу, --— встроенный механизм сопоставления с образцом. С ним можно описывать функции как [[w:Математическая индукция|индуктивные]] определения.

В примере с быстрой сортировкой Хоара можно увидетьвидно, что помимоесть уже́ещё упомянутыходно отличийважное отличие между вариантом на языке [[w:Си (язык программирования)|Си]] и вариантом на абстрактном функциональном языке, есть ещё одно важное отличиеХаскеле: функция на Си сортирует список значений типа <code>int</code> ([[w:Целое число|целых чисел]]), а функция на абстрактном функциональном языке — список значений любого типа, принадлежащего к классу упорядоченных величин. Последняя функция может сортировать и список целых чисел, и список [[w:Вещественное число|чисел с плавающей точкой]], и список [[w:Строковый тип|строк]]. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать функцию <tt>quickSort</tt> и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным [[w:Полиморфизм в языках программирования|полиморфизмом]], и поддерживается большинством функциональных языков.

В некоторых языках, например в [[w:АдаAda|Аде]], строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Для избежания этого, в строго типизированные функциональные языки встроен специальный механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста, — механизм [[w:Приведение типа|вывода типов]]. Известно несколько таких механизмов, однако большинство из них суть разновидности модели типизации [[w:Хиндли, Роджер|Хиндли]]- — [[w:Милнер, Робин|Милнера]], разработанной в начале 1980-х. Поэтому в большинстве случаев можно не указывать типы функций.

В функциональных языках, равно как и вообще в языках программирования и [[w:Математика|математике]], функции могут быть переданы другим функциям в качестве [[w:Аргумент|аргумента]] или возвращены в качестве результата. Функции, принимающие функциональные аргументы, называются [[w:Функция высшего порядка|функциями высших порядков]] или [[w:Функционал|функционалами]]. Самый, пожалуй, известный функционал, это— функция <tt>map</tt>. Эта функцияОна применяет некоторую функцию ко всем элементам списка, формируя из результатов заданной функции другой список. Например, определив функцию возведения целого числа в квадрат как:

=== Чистота ===
(отсутствие побочных эффектов) ===

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

Описывать функции без побочных эффектов позволяет практически любой язык. Однако некоторые языки поощряют или даже требуют от функции побочных эффектов. Например, во многих объектно-ориентированных языках в функцию-член класса передаётся скрытый параметр (чаще он называется <tt>this</tt> или <tt>self</tt>), который эта функция неявно модифицируетизменяет.

В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путём декомпозицииразбора и синтезасбора существующих. О ненужных объектах позаботится встроенный в язык [[w:Сборка мусора|сборщик мусора]]. Благодаря этому в чистых функциональных языках все функции свободны от побочных эффектов. Однако это не мешает этим языкам имитировать некоторые полезные императивные свойства, такие как [[w:Обработка исключений|исключения]] и изменяемые [[w:Индексный массив|массивы]]. Для этого существуют специальные методы.

Каковы же преимущества чистых функциональных языков? Помимо упрощения анализа программ есть ещё одно весомое преимущество — [[w:Параллельные вычисления|параллелизм]]. Раз все функции для вычислений используют только свои параметры, мы можем вычислять независимые функции в произвольном порядке или параллельно, на результат вычислений это не повлияет. Причём параллелизм этот может быть организован не только на уровне компилятора языка, но и на уровне архитектуры. В нескольких научных лабораториях уже разработаны и используются экспериментальные [[w:Компьютер|компьютеры]], основанные на подобных архитектурах. В качестве примера можно привести Lisp-машину.

В традиционных языках программирования (например, [[w:C++|CСи++]]) вызов функции приводит к вычислению всех аргументов. Этот метод вызова функции называется вызов- по- значению. Если какой-либо аргумент не использовался в функции, то результат вычислений пропадает, следовательно, вычисления были произведены впустую. В каком-то смысле противоположностью вызова- по- значению является вызов- по- необходимости. В этом случае аргумент вычисляется, только если он нужен для вычисления результата. Примером такого поведения можно взять оператор [[w:конъюнкция|конъюнкции]] всё из того же [[w:C++|CСи++]] (<tt>&&</tt>), который не вычисляет значение второго аргумента, если первый аргумент имеет ложное значение.

Очень часто строгие языки включают в себя средства поддержки некоторых полезных возможностей, присущих нестрогим языкам, например бесконечных списков. В поставке [[w:Standard ML|Standard ML]] присутствует специальный модуль для поддержки отложенных вычислений. А [[w:OCaml|Objective Caml]] помимо этого поддерживает дополнительное зарезервированноеспециальное слово <tt>lazy</tt> и конструкцию для списков значений, вычисляемых по необходимости.