Конспект лекций Рыбинск 2010

Введение 3

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

2 Особенности функциональных языков 5

2.1 Основные свойства 5

2.2 Преимущества 9

2.3 Недостатки 11

3 Обзор существующих языков 13

4 Базовые принципы языка Haskell 16

4.1 Интерактивная среда 16

4.2 Структура программы 18

4.3 Типы функций 22

4.4 Условные вычисления (ветвление) 24

4.5 Сопоставление с образцом 27

4.6 Списки 29

4.7 Локальные определения 33

4.8 Дополнительные возможности интерактивной среды 34

4.9 Функции высшего порядка 35

4.10 Бесконечные структуры данных 37

5 Типы данных и модули 40

5.1 Пользовательские типы и структуры данных 40

5.2 Модули 44

6 Классы и монады 47

6.1 Классы 47

6.2 Ввод-вывод 49

7 Примеры 53

Заключение 54

Список использованных источников 55

Введение

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

Но даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться многие люди, поскольку мнемокоды всё ещё оставались слишком сложными, а всякий ассемблер был жёстко связан с архитектурой, на которой исполнялся. Следующим шагом после ассемблера стали так называемые императивные языки высокого уровня: Бейсик, Паскаль, Си, Ада и прочие, включая объектно-ориентированные. Императивными («предписывающими») такие языки названы потому, что ориентированы на последовательное исполнение инструкций, работающих с памятью (т. е. присваиваний), и итеративные циклы [1]. Вызовы функций и процедур, даже рекурсивные, не избавляли такие языки от явной императивности.

В парадигме функционального программирования краеугольным камнем является функция. Математические функции выражают связь между исходными данными и итоговым продуктом некоторого процесса. Процесс вычисления также имеет вход и выход, поэтому функция — вполне подходящее и адекватное средство описания вычислений [1]. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно через самих себя. На функциональном языке программист должен только описать желаемый результат как систему функций.

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

Как известно, теоретические основы императивного программирования были заложены ещё в 1930-х годах Аланом Тьюрингом и Джоном фон Нейманом [1,2]. Теория, положенная в основу функционального подхода, также родилась в 20-х — 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать Моисея Шейнфинкеля и Хаскелла Карри, разработавших комбинаторную логику, а также Алонзо Чёрча, создателя λ-исчисления (лямбда-исчисления).

Теория так и оставалась теорией, пока в начале 1950-х годов Джон Маккарти не разработал язык Лисп (Lisp), который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется, после многих лет эволюции он удовлетворяет современным запросам [1].

В связи с все возрастающей сложности программного обеспечения всё большую роль начинает играть типизация. В конце 70-х — начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм [1]. Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число диалектов. Практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов.