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

 

== Общие слова ==

{{Эпиграф|Функциональное программирование ставит своей целью придать каждой программе простое математическое толкование. Это толкование должно быть независимо от деталей исполнения и понятно людям, не имеющим научной степени в предметной области.|Лоренс Паулсон}}

 

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

 

 

 

 

 

== История функционального программирования ==

 

 

 

 

Большинство функциональных языков программирования реализуются как [[w:Интерпретация (информатика)|интерпретируемые]], следуя традициям Лиспа (примечание: большая часть современных реализаций Лиспа содержат компиляторы в [[w:Машинный код|машинный код]]). Таковые удобны для быстрой отладки программ, исключая длительную фазу компиляции, укорачивая обычный [[w:Разработка программного обеспечения|цикл разработки]]. С другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, [[w:OCaml|Objective Caml]]) или код на Си/[[w:C++|Си++]] (например, [[w:Glasgow Haskell Compiler|Glasgow Haskell Compiler]]). Что показательно, практически каждый компилятор с функционального языка реализован на этом же са́мом языке. Это же характерно и для современных реализаций Лиспа, кроме того среда разработки Лиспа позволяет выполнять компиляцию отдельных частей программы без остановки программы (вплоть до добавления методов и изменения определений [[w:Класс (программирование)|классов]]).

 

== Свойства функциональных языков ==

Как основные свойства функциональных языков кратко рассмотрим следующие:

 

=== Краткость и простота ===

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

 

<math>\operatorname{quickSort} ([x:xs]) = \operatorname{quickSort} ([y \mid y \in xs,\, y < x]) + [x] + \operatorname{quickSort} ([y \mid y \in xs,\, y \geq x])</math>

 

<math>quickSort (l) = \begin{cases} [],&\text{если $l = []$}\\quickSort([y \mid y \in tail(l), y \leq head(l)]) + [head(l)] + quickSort([y \mid y \in tail(l), y > head(l)]),&\text{в противном случае} \end{cases}</math>

-->

Это читается так:

 

 

'''Пример 3. Быстрая сортировка Хоара на языке Haskell'''

quickSort [y | y <- xs, y >= x]</code>

 

 

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

 

 

'''Пример 4. Определение N-ого [[w:Числа Фибоначчи|числа́ Фибоначчи]]'''

 

=== Строгая типизация ===

 

 

 

 

 

=== Модульность ===

Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (модулей) с чётко определёнными связями между ними. Так облегчается процесс проектирования и последующей поддержки больши́х программных систем. Поддержка модульности не есть свойство именно функциональных языков программирования, но поддерживается большинством таких языков. Существуют очень развитые модульные императивные языки. Примеры: [[w:Модула-2|Modula-2]] и [[w:Ада (язык программирования)|Ada-95]].

 

=== Функции суть значения ===

 

<code>square n = n * n</code>

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

 

 

=== Отложенные вычисления ===

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

 

 

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

 

== Решаемые задачи ==

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

 

 

Если даны следующие объекты:

 

 

Требуется получить остаточную процедуру <math>P_{1} (x_{3},\, \ldots,\, x_{n})</math>. Эта задача решается только на узком классе программ.

 

 

Пусть имеется программа <math>P</math>. Для неё определены входные значения <math>\langle x_{1},\, \ldots,\, x_{n} \rangle</math> и выходные значения <math>\langle y_{1},\, \ldots,\, y_{m} \rangle</math>. Требуется построить математическое описание функции

<center><math>f : D_{x_{1}} \times \ldots \times D_{x_{n}} \rightarrow D_{y_{1}} \times \ldots \times D_{y_{m}}</math>.</center>

 

 

 

 

 

 

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

 

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

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

 

 

=== Сайты о функциональном программировании ===

 

=== Литература ===

 

== Благодарности ==

Благодарю Сергиевского Георгия Максимовича, который в своё время обучил меня основам функционального программирования и помог с организацией этого курса лекций.