SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


Декларативное программирование


[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]


© 2003 И.А. Дехтяренко

5. Функциональное программирование.

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

Петер Уэнтворт

В программировании мы имеем дело с двумя видами сущностей: данными и операциями. Первые мы рассматриваем как пассивную составляющую вычислительного процесса, материал которым мы хотим управлять. Вторые - как его активную составляющую, описание правил выполнения действий над данными. Поэтому, любой язык программирования должен предоставлять возможность описывать эти сущности. Прежде всего, язык должен содержать элементарные выражения, представляющие примитивные данные и операции над ними. Затем, нам необходимы средства объединения простых объектов (как данных, так и операций) в более сложные. Наконец, язык программирования должен иметь средства абстрагирования, позволяющие отвлечься от конкретного устройства сложных объектов и манипулировать ими как едиными сущностями.

Функциональное программирование использует математическое понятие функции для выражения концепции действия. Подобно обычным математическим функциям, процедуры («функции») функциональных языков отображают одни объекты (аргументы) в другие (значения). Причём, в отличие от процедур (функций) императивных языков, значения функций однозначно определяются их аргументами и не зависят от истории вычислительного процесса. Но имеется важное различие между математическими функциями и процедурами. Процедуры должны быть эффективно определены. Например, в математике мы можем определить квадратный корень из числа a как такое число, которое, будучи возведённым в квадрат, даёт a. Это совершенно законное определение, тем не менее, абсолютно неконструктивно, оно не даёт метода находить этот самый корень. (Однако нельзя сказать, что такое определение совершенно бесполезно, поскольку оно важно в качестве средства спецификации.) В дальнейшем мы будем использовать термины «процедура» и «функция» как синонимы за исключением тех случаев, когда необходимо подчеркнуть эту разницу между математическим понятием функции и её определением на языке программирования.

Это же понятие функции как мы увидим в дальнейшем, используется и для выражения концепции данных. Вообще, изучение функционального программирования - хороший повод убедиться, что разница между «данными» и «операциями» не столь уж принципиальна. Функции в функциональных языках являются объектами «первого класса».

Понятие «первоклассных» элементов языка программирования было введено Кристофером Стрейчи. Он отметил, что языки программирования налагают различные ограничения на методы использования элементов языка. Элементы первого класса - это элементы с наименьшим количеством ограничений. Важные свойства таких первоклассных элементов:

  • На них можно ссылаться посредством переменных.
  • Их можно включать в структуры данных.
  • Их можно передавать как параметры.
  • Они могут быть возвращены в качестве результата.

За небольшими исключениями (например, Алгол-68) императивные языки ограничивают «права и свободы» функций и процедур. В отличие от них, функциональные языки предоставляет функциям статус первого класса. Это создаёт трудности для их эффективной реализации, но приводит к значительному увеличению выразительной силы этих языков.

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

  • 5.1. Введение в Лисп
  • 5.2. Рекурсия
  • 5.3. Функции высшего порядка
  • 5.4. Структуры данных
  • 5.5. Абстракции данных
  • 5.6. Последовательности как стандартные интерфейсы
  • 5.7. Потоки и ленивые вычисления
  • 5.8. Синтаксический сахар: язык Erlang
  • 5.9. Математические свойства функциональных программ

  • [ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]