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

3

4

ВВЕДЕНИЕ

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

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

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

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

Первые три раздела содержат упражнения с решениями для самоконтроля.

Четвертый раздел посвящен перспективам дальнейшего развития языков и сред разработки функционального программирования.

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

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

5

1. ЯЗЫК ФУНКЦИОНАЛЬНОГО ПРОГРАММИРОВАНИЯ LISP

Мышление человека всегда основывается на использовании логики и шаблонов. Если задать вопрос, умный ли человек, который может то́лько складывать и отправлять по адресу в единицу времени, то ответ будет очевиден. Если задать другой вопрос, умный ли человек, который может складывать миллиарды 64-разрядных чисел в единицу времени, то ответ тоже будет очевиден.

Машинный язык сильно отличается от естественного стиля мышления человека. Человек не оперирует теми действиями, которыми совершает вычислительная машина. По этой причине начали проводиться научные исследования по замене машинного языка языком, пригодным и удобным для восприятия человеком. Результатом этих исследований стало создание языков программирования, которые значительно упростили работу человека по описанию программы для машины, но при этом понятных для машины. Основной формой реализации языков программирования служит уровень абстракции.

Вобщем смысле программа – это некая последовательность действий, понятных исполнителю.

Функциональное программирование сильно отличается от шаблона написания императивных программ для ЭВМ. Теория функционального программирования родилась в 20–30-х гг. Основоположниками математических основ функционального программирования являются Мозес Шенфинкель, Хаскелл Карри и Алонзо Чёрч. Мозес Шенфинкель и Хаскелл Карри разработали комбинаторную логику, которая легла в основу записи функциональных шаблонов. Алонзо Чёрч создал λ-исчисление.

В50-х гг. ХХ в. Джон Маккарти разработал первый прототип языка функционального программирования Lisp. Основная идея функционального программирования – применение

6

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

Вконце 70-х гг. XX в. появилось множество типизированных функциональных языков: ML, Miranda, Scheme и др.

Вначале 90-х гг. появилась реализация универсального функционального языка Haskell, в честь Хаскелла Карри.

Наиболее удачными версиями функционального языка программирования, по мнению авторов книги, являются CommonLisp, xLisp, MuLisp, Haskell и VisualLisp. Практически все указанные среды программирования прекрасно подходят для решения задач со сложными структурами данных, таких как графы, деревья, сети

идр. При этом тексты программ в разы меньше, чем у процедурноориентированных языков. Примером могут служить тексты программ решения задачи о восьми ферзях. На языке ObjectPascal текст программы составил 48 ключевых точек (157 строк программного кода), а на языке xLisp всего 14 функций (53 строки программного кода).

Как видно из названия «Функциональное программирование», в нем сделан упор на обработку функций. Сначала разберемся, что же такое функция. Само значение этого слова пришло из математики и определяет некую закономерность выражения между исходными данными, т.е. аргументами, и результатом. По сути, вычисление – это некая последовательность простых действий, т.е. некая процедура. Но процедура и функция – это разные понятия.

Различаются они лишь в конце, а именно процедура – это просто последовательность действий, функция же – это последовательность действий, имеющая некое значение, сопоставляемое с самой функцией. Простыми словами, функция в конце должна получить результат, который будет значением имени этой функции. К этому имени потом можно обратиться.

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

7

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

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

Ярким представителем языка функционального программирования является «Лисп» (Lisp – List Processing – «обработка списков»).

В основу языка положен серьезный математический аппарат:

лямбда-исчисление Чёрча;

алгебра списочных структур;

теория рекурсивных функций.

Основой языка «Лисп» является символьные или знаковые выражения. Эти выражения могут представляться как в виде отдельных символов, так и в виде сложных структур из символов. При этом символ служит для обозначения любой информации и, если провести аналогию с традиционным программированием, то символ в Лиспе – это запись. Символ – это не обязательно конкретно одна буква алфавита. Это некий предмет, объект, действие, представленное в виде набора букв, цифр и специальных знаков.

1.1. Символьные выражения

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

8

символ является аналогом переменной в императивных языках программирования.

Символьные выражения можно разделить на отдельные множества, показанные на рис. 1.

Символьные выражения

Символы

Атомы t nil Списки

Числа

Рис 1. Символьные выражения

Символьные выражения в Лиспесостоятизатомовисписков:

1)атомы – числа, целые и вещественные, специальные константы t и nil, обозначающие логические значения true (истина) и false (ложь);

2)списки, частью которых являются специальные константы t и nil.

Атомы – это простейшие объекты, из которых могут строиться более сложные объекты – списки.

1.2. Программирование с помощью функций

Концепция функций – одно из фундаментальных понятий математики. Функция – правило, сопоставляющее каждому элементу некоторого класса Х соответствующий ему единственный элемент классаY,где Y–областьзначений; Х–областьопределения.

Свойство соответствия (как функций) прообраз x → f (x) образ

(X)(Y)

f (x) – результат применения функции f к аргументу x.

9

Способы описания функций множество пар вида: {(xi, f (xi))} таблично:

ряд равенств: f (x1) = y1, f (x2) = y2, …

Рассмотренные выше способы применимы для функций, у которых мощность области определения конечна и не очень велика. Для остальных функций необходим иной формализм описания – правило (определение).

Функция называется частично определенной над мно-

жеством А, если в множестве А существуют элементы, для которых образ посредством этой функции не определен.

Пример: обратное (х) = 1 / х

Функция называется всюду определенной в А (общая над А), если она не является частично-определенной.

Пример: квадрат(х) = х*х

Методика создания функциональных программ:

определение набора базовых функций;

функция есть программа;

определение новых функций на основе существующих, т.е. создаем иерархию определений функций.

Метод композиции (суперпозиции) функций является одним из фундаментальных способов конструирования новых функций.

Пример:

Степень_4(х) = квадрат (квадрат (х))

Задача: определить иерархию функций для вычисления дискриминанта (D) квадратного уравнения.

1. Базовые функции:

плюс(x, y) = x + y минус(x, y) = x – y умн(x, y) = x*y…

10