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

м
орфография, викификатор
м (орфография, викификатор)
 
== Общие слова ==
 
{{Эпиграф|Функциональное программирование ставит своей целью придать каждой программе простое математическое толкование. Это толкование должно быть независимо от деталей исполнения и понятно людям, не имеющим научной степени в предметной области.|Лоренс Паулсон}}
 
Перед началом описания непосредственно [[w:Функциональное программирование|функционального программирования]] следует обратиться к истории [[w:Программирование|программирования]] вообще. В 1940-х годах появились первые цифровые [[w:Компьютер|компьютеры]], которые программировались переключением различного рода тумблеров, проводков и кнопок. Число таких переключений достигало порядка нескольких сотен и росло с усложнением программ. Потому следующим шагом развития программирования стало создание всевозможных [[w:Язык ассемблера|ассемблерных языков]] с простой [[w:Мнемоника|мнемоникой]].
 
Но даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться многие люди, поскольку мнемокоды всё ещё оставались слишком сложными, а всякий ассемблер был жёстко связан с архитектурой, на которой исполнялся. Шагом после ассемблера стали так называемые [[w:Императивное программирование|императивные языки]] [[w:Высокоуровневый язык программирования|высокого уровня]]: [[w:BASIC|Бейсик]], [[w:Паскаль (язык программирования)|Паскаль]], [[w:Си (язык программирования)|Си]], [[w:Ада (язык программирования)|Ада]] и прочие, включая [[w:Объектно-ориентированное программирование|объектно-ориентированные]]. Императивными («предписывающими») такие языки названы потому, что ориентированы на последовательное исполнение инструкций, работающих с памятью (т. е.то есть [[w:Присваивание (программирование)|присваиваний]]), и итеративные [[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:Лисп|Лисп]], который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется (также как и [[w:Фортран|Фортран]]), после многих лет эволюции он удовлетворяет современным запросам, которые заставляют разработчиков программ взваливать как можно бо́льшую но́шу на [[w:Компилятор|компилятор]], облегчив так свой труд. Нужда в этом возникла из-за всё более возрастающей сложности [[w:Программное обеспечение|программного обеспечения]].
Как известно, теоретические основы императивного программирования были заложены ещё в [[w:1930-е|1930-х]] годах [[w:Тьюринг, Алан Матисон|Аланом Тьюрингом]] и [[w:Нейман, Джон фон|Джоном фон Нейманом]]. Теория, положенная в основу функционального подхода, также родилась в 20-х — 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать [[w:Шейнфинкель, Моисей|Моисея Шейнфинкеля]] и [[w:Карри, Хаскелл|Хаскелла Карри]], разработавших [[w:Комбинаторная логика|комбинаторную логику]], и [[w:Чёрч, Алонзо|Алонзо Чёрча]], создателя [[w:Лямбда-исчисление|λ-исчисления]].
 
В связи с этим обстоятельством всё бо́льшую роль начинает играть [[w:Типизация|типизация]]. В конце 70-х    начале 80-х  годов XX  века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как [[w:Абстракция данных|абстракция данных]] и [[w:Полиморфизм в языках программирования|полиморфизм]]. Появляется множество типизированных функциональных языков: [[w:ML|ML]], [[w:Scheme|Scheme]], [[w:Hope|Hope]], [[w:Миранда (язык программирования)|Miranda]], [[w:Clean|Clean]] и многие другие. Вдобавок постоянно увеличивается число диалектов.
Теория так и оставалась теорией, пока в конце 1950-х годов [[w:Маккарти, Джон|Джон Маккарти]] не разработал язык [[w:Лисп|Лисп]], который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется (также как и [[w:Фортран|Фортран]]), после многих лет эволюции он удовлетворяет современным запросам, которые заставляют разработчиков программ взваливать как можно бо́льшую но́шу на [[w:Компилятор|компилятор]], облегчив так свой труд. Нужда в этом возникла из-за всё более возрастающей сложности [[w:Программное обеспечение|программного обеспечения]].
 
В результате вышло так, что практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного [[w:Haskell|Haskell]] в честь Хаскелла Карри, была создана в начале 90-х  годов. Ныне действителен стандарт Haskell-98.
В связи с этим обстоятельством всё бо́льшую роль начинает играть [[w:Типизация|типизация]]. В конце 70-х — начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как [[w:Абстракция данных|абстракция данных]] и [[w:Полиморфизм в языках программирования|полиморфизм]]. Появляется множество типизированных функциональных языков: [[w:ML|ML]], [[w:Scheme|Scheme]], [[w:Hope|Hope]], [[w:Миранда (язык программирования)|Miranda]], [[w:Clean|Clean]] и многие другие. Вдобавок постоянно увеличивается число диалектов.
 
В результате вышло так, что практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного [[w:Haskell|Haskell]] в честь Хаскелла Карри, была создана в начале 90-х годов. Ныне действителен стандарт Haskell-98.
 
Большинство функциональных языков программирования реализуются как [[w:Интерпретация (информатика)|интерпретируемые]], следуя традициям Лиспа (примечание: большая часть современных реализаций Лиспа содержат компиляторы в [[w:Машинный код|машинный код]]). Таковые удобны для быстрой отладки программ, исключая длительную фазу компиляции, укорачивая обычный [[w:Разработка программного обеспечения|цикл разработки]]. С другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например, [[w:OCaml|Objective Caml]]) или код на Си/[[w:C++|Си++]] (например, [[w:Glasgow Haskell Compiler|Glasgow Haskell Compiler]]). Что показательно, практически каждый компилятор с функционального языка реализован на этом же са́мом языке. Это же характерно и для современных реализаций Лиспа, кроме того среда разработки Лиспа позволяет выполнять компиляцию отдельных частей программы без остановки программы (вплоть до добавления методов и изменения определений [[w:Класс (программирование)|классов]]).
 
== Свойства функциональных языков ==
 
Как основные свойства функциональных языков кратко рассмотрим следующие:
* краткость и простота;
* строгая типизация;
* [[w:Модульность (программирование)|модульность]];
*функции функции — это значения;
* [[w:Чистота функции|чистота]] (отсутствие [[w:Побочный эффект (программирование)|побочных эффектов]]);
* [[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 ругается на эту правильную формулу TeX...TeX…
<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>
-->
Это читается так:
 
# Если список пуст, то результатом также будет пустой список.
# Иначе выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет [[w:Конкатенация|конкатенация]] (сращивание) отсортированного списка из всех элементов хвоста меньших головы, списка из самой головы и списка из всех элементов хвоста бо́льших либо равных голове.
 
'''Пример 3. Быстрая сортировка Хоара на языке Haskell'''
quickSort [y | y <- xs, y >= x]</code>
 
Как видно на этом примере, функциональная формулировка алгоритма короче и яснее чем императивная, хоть последняя в данном случае и выигрывает в эффективности исполнения, сортируя массив "«на месте"», внутри себя, в то время как версия на Хаскеле создает новые списки в ходе работы.
 
Кроме того, все операции с [[w:Компьютерная память|памятью]] выполняются автоматически. При создании какого-либо объекта под него автоматически выделяется память. Когда объект выполнит своё предназначение, он вскоре будет также автоматически уничтожен [[w:Сборка мусора|сборщиком мусора]], который имеется в любом функциональном языке.
 
Ещё одно средство, позволяющее сократить программу,  — встроенный механизм сопоставления с образцом. С ним можно описывать функции как [[w:Математическая индукция|индуктивные]] определения.
 
'''Пример 4. Определение N-ого [[w:Числа Фибоначчи|числа́ Фибоначчи]]'''
 
=== Строгая типизация ===
Из современных языков программирования многие суть строго типизированные. Строгая типизация позволяет компилятору [[w:Оптимизация компилятора|оптимизировать]] программы, использовать конкретные типы и [[w:Контейнер (программирование)|контейнеры]] конкретных типов вместо [[w:Шаблон (программирование)|шаблонных]], вариантных типов, более громоздких в реализации. Кроме того, строгая типизация позволяет оградиться от части ошибок, связанных с неожидаемым «видом» входных (и выходных) данных, причем это происходит на стадии компиляции, не отнимая на такие проверки время при работе программы. Система типов также способствует «документированию» программы: любая [[w:Подпрограмма|подпрограмма]] является функцией в математическом смысле слова, отображая одно множество (входное) на другое (выходное), и типы определяют эти множества. Читабельность программ повышается, если используются псевдонимы типов или сложные типы, собранные на основе простых, вместо базовых элементарных ''целых'', ''строк'' и  т.&nbsp; п.
 
В примере с быстрой сортировкой Хоара видно, что есть ещё одно важное отличие между вариантом на Си и вариантом на Хаскеле: функция на Си сортирует список значений типа <code>int</code> ([[w:Целое число|целых чисел]]), а функция на абстрактном функциональном языке  — список значений любого типа, принадлежащего к классу упорядоченных величин. Последняя функция может сортировать и список целых чисел, и список [[w:Вещественное число|чисел с плавающей точкой]], и список [[w:Строковый тип|строк]]. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать функцию <tt>quickSort</tt> и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным [[w:Полиморфизм в языках программирования|полиморфизмом]], и поддерживается большинством функциональных языков.
Из современных языков программирования многие суть строго типизированные. Строгая типизация позволяет компилятору [[w:Оптимизация компилятора|оптимизировать]] программы, использовать конкретные типы и [[w:Контейнер (программирование)|контейнеры]] конкретных типов вместо [[w:Шаблон (программирование)|шаблонных]], вариантных типов, более громоздких в реализации. Кроме того, строгая типизация позволяет оградиться от части ошибок, связанных с неожидаемым «видом» входных (и выходных) данных, причем это происходит на стадии компиляции, не отнимая на такие проверки время при работе программы. Система типов также способствует «документированию» программы: любая [[w:Подпрограмма|подпрограмма]] является функцией в математическом смысле слова, отображая одно множество (входное) на другое (выходное), и типы определяют эти множества. Читабельность программ повышается, если используются псевдонимы типов или сложные типы, собранные на основе простых, вместо базовых элементарных ''целых'', ''строк'' и т.&nbsp;п.
 
Ещё одно проявление полиморфизма  — [[w:Перегрузка функции|перегрузка функций]], позволяющая давать разным, но подобным функциям одинаковые имена. Типичный пример перегруженной операции  — обычная [[w:Сложение (математика)|операция сложения]]. Функции сложения для целых чисел и чисел с плавающей точкой различны, но для удобства они носят одно имя. Некоторые функциональные языки помимо параметрического полиморфизма поддерживают и перегрузку операций.
В примере с быстрой сортировкой Хоара видно, что есть ещё одно важное отличие между вариантом на Си и вариантом на Хаскеле: функция на Си сортирует список значений типа <code>int</code> ([[w:Целое число|целых чисел]]), а функция на абстрактном функциональном языке — список значений любого типа, принадлежащего к классу упорядоченных величин. Последняя функция может сортировать и список целых чисел, и список [[w:Вещественное число|чисел с плавающей точкой]], и список [[w:Строковый тип|строк]]. Можно описать какой-нибудь новый тип. Определив для этого типа операции сравнения, возможно без перекомпиляции использовать функцию <tt>quickSort</tt> и со списками значений этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным [[w:Полиморфизм в языках программирования|полиморфизмом]], и поддерживается большинством функциональных языков.
 
В языке Си++ имеется такое понятие, как шаблон, которое позволяет программисту определять полиморфные функции, подобные <tt>quickSort</tt>. В стандартную библиотеку Си++  — [[w:Standard Template Library|STL]]  — входит такая функция и множество других полиморфных функций. Но шаблоны Си++, как и родовые функции Ады, на самом деле порождают множество перегруженных функций, которые, кстати, нужно каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере [[w:Машинный код|кода]]. А в функциональных языках полиморфная функция <tt>quickSort</tt>  — это одна единственная функция. С другой стороны, функциональные языки в этом плане проигрывают по скорости выполнения.
Ещё одно проявление полиморфизма — [[w:Перегрузка функции|перегрузка функций]], позволяющая давать разным, но подобным функциям одинаковые имена. Типичный пример перегруженной операции — обычная [[w:Сложение (математика)|операция сложения]]. Функции сложения для целых чисел и чисел с плавающей точкой различны, но для удобства они носят одно имя. Некоторые функциональные языки помимо параметрического полиморфизма поддерживают и перегрузку операций.
 
В некоторых языках, например в Аде, строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Для избежания этого, в строго типизированные функциональные языки встроен механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста,  — механизм автоматического [[w:Вывод типов|вывода типов]]. Известно несколько таких механизмов, однако большинство из них суть разновидности модели типизации [[w:Хиндли, Роджер|Хиндли]]  — [[w:Милнер, Робин|Милнера]], разработанной в начале 1980-х. Поэтому в большинстве случаев можно не указывать типы функций.
В языке Си++ имеется такое понятие, как шаблон, которое позволяет программисту определять полиморфные функции, подобные <tt>quickSort</tt>. В стандартную библиотеку Си++ — [[w:Standard Template Library|STL]] — входит такая функция и множество других полиморфных функций. Но шаблоны Си++, как и родовые функции Ады, на самом деле порождают множество перегруженных функций, которые, кстати, нужно каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере [[w:Машинный код|кода]]. А в функциональных языках полиморфная функция <tt>quickSort</tt> — это одна единственная функция. С другой стороны, функциональные языки в этом плане проигрывают по скорости выполнения.
 
В некоторых языках, например в Аде, строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Для избежания этого, в строго типизированные функциональные языки встроен механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста, — механизм автоматического [[w:Вывод типов|вывода типов]]. Известно несколько таких механизмов, однако большинство из них суть разновидности модели типизации [[w:Хиндли, Роджер|Хиндли]] — [[w:Милнер, Робин|Милнера]], разработанной в начале 1980-х. Поэтому в большинстве случаев можно не указывать типы функций.
 
=== Модульность ===
 
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (модулей) с чётко определёнными связями между ними. Так облегчается процесс проектирования и последующей поддержки больши́х программных систем. Поддержка модульности не есть свойство именно функциональных языков программирования, но поддерживается большинством таких языков. Существуют очень развитые модульные императивные языки. Примеры: [[w:Модула-2|Modula-2]] и [[w:Ада (язык программирования)|Ada-95]].
 
=== Функции суть значения ===
В функциональных языках, равно как и вообще в языках программирования и математике, функции могут быть переданы другим функциям в качестве [[w:Аргумент (программирование)|аргумента]] или возвращены в качестве результата. Функции, принимающие функциональные аргументы, называются [[w:Функция высшего порядка|функциями высших порядков]] или [[w:Функционал|функционалами]]. Самый, пожалуй, известный функционал  — функция <tt>map</tt>. Она применяет некоторую функцию ко всем элементам списка, формируя из результатов заданной функции другой список. Например, определив функцию возведения целого числа в квадрат как:
 
В функциональных языках, равно как и вообще в языках программирования и математике, функции могут быть переданы другим функциям в качестве [[w:Аргумент (программирование)|аргумента]] или возвращены в качестве результата. Функции, принимающие функциональные аргументы, называются [[w:Функция высшего порядка|функциями высших порядков]] или [[w:Функционал|функционалами]]. Самый, пожалуй, известный функционал — функция <tt>map</tt>. Она применяет некоторую функцию ко всем элементам списка, формируя из результатов заданной функции другой список. Например, определив функцию возведения целого числа в квадрат как:
 
<code>square n = n * n</code>
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путём разбора и сбора существующих. О ненужных объектах позаботится встроенный в язык сборщик мусора. Благодаря этому в чистых функциональных языках все функции свободны от побочных эффектов. Однако это не мешает этим языкам имитировать некоторые полезные императивные свойства, такие как [[w:Обработка исключений|исключения]] и изменяемые [[w:Индексный массив|массивы]].
 
Каковы же преимущества чистых функциональных языков? Помимо упрощения анализа программ есть ещё одно  — [[w:Параллельные вычислительные системы|параллелизм]]. Раз все функции для вычислений используют только свои параметры, мы можем вычислять независимые функции в произвольном порядке или параллельно, на результат вычислений это не повлияет. Причём параллелизм этот может быть организован не только на уровне компилятора языка, но и на уровне архитектуры. В нескольких научных лабораториях уже разработаны и используются экспериментальные компьютеры, основанные на подобных архитектурах. В качестве примера можно привести [[w:Lisp-машина|Lisp-машину]].
 
=== Отложенные вычисления ===
 
В традиционных языках программирования (например, Си++) вызов функции приводит к вычислению всех аргументов. Этот метод вызова функции называется '''вызов по значению'''. Если какой-либо аргумент не использовался в функции, то результат вычислений пропадает, следовательно, вычисления были произведены впустую. В каком-то смысле противоположностью вызова по значению является '''вызов по необходимости'''. В этом случае аргумент вычисляется, только если он нужен для вычисления результата. Примером такого поведения можно взять оператор [[w:конъюнкция|конъюнкции]] всё из того же Си++ (<tt>&&</tt>), который не вычисляет значение второго аргумента, если первый аргумент имеет ложное значение.
 
Если функциональный язык не поддерживает отложенные вычисления, то он называется строгим. На самом деле, в таких языках порядок вычисления строго определён. В качестве примера строгих языков можно привести Scheme, [[w:SML|Standard ML]] и [[w:Caml Light|Caml]]. Языки, использующие отложенные вычисления, называются нестрогими. Haskell  — нестрогий язык, так же как, например, [[w:Gofer|Gofer]] и Miranda. Нестрогие языки зачастую являются чистыми.
 
Очень часто строгие языки включают в себя средства поддержки некоторых полезных возможностей, присущих нестрогим языкам, например бесконечных списков. В поставке Standard ML присутствует специальный модуль для поддержки отложенных вычислений. А Objective Caml помимо этого поддерживает дополнительное специальное слово <tt>lazy</tt> и конструкцию для списков значений, вычисляемых по необходимости.
 
== Решаемые задачи ==
 
В качестве задач, традиционно рассматриваемых в курсах функционального программирования, можно выделить следующие:
 
'''1.&nbsp; Получение остаточной процедуры.'''
 
Если даны следующие объекты:
 
* <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.&nbsp; Построение математического описания функций.'''
 
Пусть имеется программа <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>
 
'''3.&nbsp; Определение формальной семантики языка программирования.'''
 
'''4.&nbsp; Описание динамических структур данных.'''
 
'''5.&nbsp; Автоматическое построение «значительной» части программы по описанию структур данных, которые обрабатываются создаваемой программой.'''
 
'''6.&nbsp; Доказательство наличия некоторого свойства программы.'''
 
'''7.&nbsp; Эквивалентная трансформация программ.'''
 
Все эти задачи достаточно легко решаются средствами функционального программирования, но практически неразрешимы в императивных языках.
 
=== Языки функционального программирования ===
 
В этом разделе приведено краткое описание некоторых языков функционального программирования (очень немногих). Дополнительную информацию можно почерпнуть, просмотрев ресурсы, перечисленные в следующем разделе.
 
# '''Лисп''' (List processor). Считается первым функциональным языком программирования. Поддерживает [[w:Динамическая типизация|динамическую]] и факультативно [[w:Статическая типизация|статическую типизацию]]. Содержит массу императивных свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов-по-значению. В стандарт [[w:Common Lisp|Common Lisp]] входит [[w:CLOS|Common Lisp Object System (CLOS)]]  — объектная система Common Lisp, которая по многим параметрам превосходит объектные системы в других языках (поддерживает метаобъектный протокол, [[w:Мультиметод|мультиметоды]] и  т.&nbsp; д.).
# '''[[w:ISWIM|ISWIM]]''' (If you See What I Mean). Функциональный язык-прототип. Разработан Питером Ландиным в 60-х&nbsp; годах XX&nbsp; ве́ка для демонстрации того, каким может быть язык функционального программирования. Вместе с языком П.&nbsp; Ландин разработал и специальную [[w:Виртуальная машина|виртуальную машину]] для исполнения программ на ISWIM’е. Эта виртуальная машина, основанная на вызове-по-значению, получила название [[w:SECD-машина|SECD-машины]]. На синтаксисе языка ISWIM базируется синтаксис многих функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.
# '''Scheme'''. Диалект Lisp’а, предназначенный для научных исследований в области computer science. При разработке Scheme был сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем Common Lisp.
# '''ML''' (Meta Language). Семейство строгих языков с развитой полиморфной системой типов и параметризуемыми модулями. ML преподаётся во многих западных университетах (в некоторых даже как первый язык программирования).
# '''Standard ML'''. Один из первых типизированных языков функционального программирования. Содержит некоторые императивные свойства, такие как ссылки на изменяемые значения и поэтому не является чистым. При вычислениях использует вызов-по-значению. Очень интересная реализация модульности. Мощная полиморфная система типов. Последний стандарт языка  — Standard ML-97, для которого существует формальные математические определения синтаксиса, а также статической и динамической семантик языка.
# '''[[w:Caml Light|Caml Light]]''' и '''Objective Caml'''. Как и Standard ML принадлежит к семейству ML. Objective Caml отличается от Caml Light в основном поддержкой классического объектно-ориентированного программирования. Также как и Standard ML строгий, но имеет некоторую встроенную поддержку отложенных вычислений.
# '''Miranda'''. Разработан [[w:Тёрнер, Дэвид|Дэвидом Тёрнером]], в качестве стандартного функционального языка, использовавшего отложенные вычисления. Имеет строгую полиморфную систему типов. Как и ML преподаётся во многих университетах. Оказал большое влияние на разработчиков языка Haskell.
# '''Haskell'''. Один из самых распространённых не строгих языков. Имеет очень развитую систему типизации. Несколько хуже разработана система модулей. Последний стандарт языка  — Haskell-98.
# '''Gofer''' (GOod For Equational Reasoning). Упрощённый диалект Haskell’а. Предназначен для обучения функциональному программированию.
# '''Clean'''. Специально предназначен для параллельного и распределённого программирования. По синтаксису напоминает Haskell. Чистый. Использует отложенные вычисления. С компилятором поставляется набор библиотек (I/O libraries), позволяющих программировать графический пользовательский интерфейс под [[w:Windows API|Win32]] или [[w:Mac OS|Mac OS]].
 
=== Сайты о функциональном программировании ===
# [http://www.haskell.org/ http://www.haskell.org/]  — очень насыщенный сайт, посвящённый функциональному программированию в общем и языку Haskell в частности. Содержит различные справочные материалы, список интерпретаторов и компиляторов Haskell’а (в настоящий момент все интерпретаторы и компиляторы бесплатны). Кроме того, имеется обширный список интересных ссылок на ресурсы по теории функционального программирования и другим языкам (Standard ML, Clean).
 
# [http://cm.bell-labs.com/cm/cs/what/smlnj/ http://cm.bell-labs.com/cm/cs/what/smlnj/]  — Standard ML of New Jersey. Очень хороший компилятор. В бесплатный дистрибутив помимо компилятора входят утилиты MLYacc и MLLex и библиотека Standard ML Basis Library. Отдельно можно взять документацию по компилятору и библиотеке.
#[http://www.haskell.org/ http://www.haskell.org/] — очень насыщенный сайт, посвящённый функциональному программированию в общем и языку Haskell в частности. Содержит различные справочные материалы, список интерпретаторов и компиляторов Haskell’а (в настоящий момент все интерпретаторы и компиляторы бесплатны). Кроме того, имеется обширный список интересных ссылок на ресурсы по теории функционального программирования и другим языкам (Standard ML, Clean).
# [http://replay.waybackmachine.org/19971013225217/http://www.harlequin.com/products/ads/ml/ http://www.harlequin.com/products/ads/ml/] ''(dead link)'' - — Harlequin MLWorks, коммерческий компилятор Standard ML. Однако в некоммерческих целях можно бесплатно пользоваться версией с несколько ограниченными возможностями.
#[http://cm.bell-labs.com/cm/cs/what/smlnj/ http://cm.bell-labs.com/cm/cs/what/smlnj/] — Standard ML of New Jersey. Очень хороший компилятор. В бесплатный дистрибутив помимо компилятора входят утилиты MLYacc и MLLex и библиотека Standard ML Basis Library. Отдельно можно взять документацию по компилятору и библиотеке.
# [http://caml.inria.fr/ http://caml.inria.fr/]  — институт INRIA. Домашний сайт команды разработчиков языков Caml Light и Objective Caml. Можно бесплатно скачать дистрибутив Objective Caml, содержащий интерпретатор, компиляторы [[w:Байт-код|байт-кода]] и машинного кода, Yacc и Lex для Caml, [[w:Отладчик|отладчик]] и [[w:Профайлер|профайлер]], документацию, примеры. Качество компилированного кода у этого компилятора очень хорошее, по скорости опережает даже Standard ML of New Jersey.
#[http://replay.waybackmachine.org/19971013225217/http://www.harlequin.com/products/ads/ml/ http://www.harlequin.com/products/ads/ml/] ''(dead link)'' - Harlequin MLWorks, коммерческий компилятор Standard ML. Однако в некоммерческих целях можно бесплатно пользоваться версией с несколько ограниченными возможностями.
# [http://www.cs.kun.nl/~clean/ http://www.cs.kun.nl/~clean/]  — содержит дистрибутив компилятора с языка Clean. Компилятор коммерческий, но допускается бесплатное использование в некоммерческих целях. Качественный (очень быстр), в наличии среда разработчика, хорошая документация и стандартная библиотека.
#[http://caml.inria.fr/ http://caml.inria.fr/] — институт INRIA. Домашний сайт команды разработчиков языков Caml Light и Objective Caml. Можно бесплатно скачать дистрибутив Objective Caml, содержащий интерпретатор, компиляторы [[w:Байт-код|байт-кода]] и машинного кода, Yacc и Lex для Caml, [[w:Отладчик|отладчик]] и [[w:Профайлер|профайлер]], документацию, примеры. Качество компилированного кода у этого компилятора очень хорошее, по скорости опережает даже Standard ML of New Jersey.
#[http://www.cs.kun.nl/~clean/ http://www.cs.kun.nl/~clean/] — содержит дистрибутив компилятора с языка Clean. Компилятор коммерческий, но допускается бесплатное использование в некоммерческих целях. Качественный (очень быстр), в наличии среда разработчика, хорошая документация и стандартная библиотека.
 
=== Литература ===
# Хювёнен&nbsp; Э., Сеппенен&nbsp; И. Мир Lisp’а. В 2-х томах. М.: Мир, 1990.
 
# Бёрдж&nbsp; В. Методы рекурсивного программирования. М.: Машиностроение, 1983.
#Хювёнен&nbsp;Э., Сеппенен&nbsp;И. Мир Lisp’а. В 2-х томах. М.: Мир, 1990.
#Хендерсон&nbsp; Филд А., Харрисон П. Функциональное программирование. Применение и реализация. М.: Мир, 19831993.
#Бёрдж&nbsp;В. Методы рекурсивного программирования. М.: Машиностроение, 1983.
#Филд&nbsp;А., Харрисон&nbsp;Хендерсон П. Функциональное программирование. Применение и реализация. М.: Мир, 19931983.
# Джонс&nbsp; С., Лестер&nbsp; Д. Реализация функциональных языков. М.: Мир, 1991.
#Хендерсон&nbsp;П. Функциональное программирование. Применение и реализация. М.: Мир, 1983.
# Henson  M. Elements of functional languages. Dept. of CS. University of Sassex, 1990.
#Джонс&nbsp;С., Лестер&nbsp;Д. Реализация функциональных языков. М.: Мир, 1991.
#Henson&nbsp; MFokker J. ElementsFunctional of functional languagesprogramming. Dept. of CS. Utrecht University of Sassex, 19901995.
# Thompson S. Haskell: The Craft of Functional Programming. 2-nd edition, Addison-Wesley, 1999.
#Fokker&nbsp;J. Functional programming. Dept. of CS. Utrecht University, 1995.
#Thompson&nbsp;S Bird R. Haskell:Introduction The Craft ofto Functional Programming using Haskell. 2-nd edition, Addison-WesleyPrentice Hall Press, 19991998.
#Bird&nbsp;R. Introduction to Functional Programming using Haskell. 2-nd edition, Prentice Hall Press, 1998.
 
== Благодарности ==
 
Благодарю Сергиевского Георгия Максимовича, который в своё время обучил меня основам функционального программирования и помог с организацией этого курса лекций.
 
118

правок