Функциональное программирование
Н.Н.Непейвода, Интернет Университет Информационных
Технологий, INTUIT.ru
Функциональное
программирование объясняется на примере диалекта Common Lisp языка LISP. Этот
диалект наиболее распространен и имеет официальный стандарт. Common Lisp может
работать не только в пакетном режиме (когда он запускается как обычная
программа), но и в режиме диалога.
LISP
- вероятно, первый из практически реализованных языков1, который основывался на
серьезном теоретическом фундаменте и пытался поднять практику программирования
до уровня концепций, а не наоборот - опустить концепции до уровня
существовавшей на момент создания языка практики.
В
настоящий момент функциональное программирование представлено целым семейством
языков, но LISP свои позиции не сдает.
λ-абстракции
В
некоторых случаях осознанное усвоение концепций даже на самом низком уровне
нереально без базовых теоретических сведений. А знакомство с таким базисом, в
свою очередь, стимулирует значительно более глубокий интерес к теории и
способствует пониманию того, что на высшие уровни знаний и умений не подняться
без овладения теорией.
Теоретической
основой языка LISP является логика функциональности: комбинаторная логика или
(по наименованию одного из основных понятий в наиболее популярной из нынешних
ее формализаций) λ-исчисление.
В
λ-исчислении выразительные средства, на первый взгляд, крайне скупы.
Имеются две базисные операции: применение функции к аргументу (λx) и
квантор образования функции по выражению λx t[x]. В терминах
λ-исчисления функция возведения числа в квадрат записывается как λx
(sqrx) или, если быть ближе к обычным математическим обозначениям, λx x2.
Основная
операция - символьное вычисление применения функции к аргументу: (λx t[x]
u) преобразуется в t[u]. Но эта операция может применяться в любом месте
выражения, так что никакая конкретная дисциплина вычислений не фиксируется.
Более того, функции могут вычисляться точно так же, как аргументы. Уже эта маленькая
тонкость приводит к принципиальному расширению возможностей λ-исчисления
по сравнению с обычными вызовами процедур. Если мы желаем ограничиться лишь ею,
рассматривается типизированное λ-исчисление, в котором, как принято в
большинстве современных систем программирования, значения строго разделены по
типам. В типизированном λ-исчислении есть только типы функций, но этого
хватает, поскольку функции могут принимать в качестве параметров и выдавать
функции.
Но
в исходной своей форме λ-исчисление является нетипизированным, любой
объект может быть и функцией, и аргументом, и, более того, функция может
применяться к самой себе. Конечно же, при этом появляется возможность
зацикливания, но без нее не обойдется ни одна
алгоритмическая система. Например, выражение
(λx
(xx) λx (xx))
вычисляется
бесконечно, а чуть более сложное выражение
((λx λy x a) (λx (xx) λx (xx)))
может
либо дать a, либо зациклиться, в зависимости от выбора порядка его вычисления.
Но все равно, если мы приходим к результату, то он определяется однозначно. Так
что совместность вычислений не портит однозначности, если язык хорошо
сконструирован.
Дж.
Маккарти перенес идеи λ-исчисления в программирование, не потеряв
практически ничего из исходных концепций. Далее, он заметил, что в рудиментарном
виде в λ-исчислении появилось понятие списка, и перенес списки в качестве
основных структур данных в свой язык. λ-исчислением было навеяно и
соглашение языка LISP о том, что первый член списка трактуется как функция,
применяемая к остальным.
Списки и функциональные выражения
Основной
единицей данных для LISP-системы является список.
Списки задаются следующим индуктивным
определением.
Пустой
список () (обозначаемый также nil) является списком.
Если
l1,. . . , ln, n ≥ 1 - атомы либо списки, то (l1, . . . , ln) - также
список.
Элементами
списка (l1, . . . , ln) называются l1, . . . , ln. Равенство списков задается
следующим индуктивным определением.
l
= nil тогда и только тогда, когда l также есть nil.
(l1,
. . . , ln) = (k1, . . . , km) тогда и только тогда, когда n = m и
соответствующие li = ki.
Пример
8.2.2. Все списки (), (()), ((())) и т. д. различны. Различны также и списки
nil, (nil, nil), (nil, nil, nil) и так далее. Попарно различны и списки ((a,b),
c), (a, (b,c)), (a,b,c), где a, b, c - различные атомы.
Поскольку
понятие, задаваемое индуктивным определением, должно строиться в результате
конечного числа шагов применения определения, мы исключаем списки, ссылающиеся
сами на себя. Списки в нашем рассмотрении изоморфны упорядоченным конечным
деревьям, листьями которых являются nil либо атомы.
Вершины
списка l задаются следующим индуктивным определением.
Элементы
списка являются его вершинами.
Вершины
элементов списка являются его вершинами.
Длиной
списка называется количество элементов в нем. Глубиной списка называется
максимальное количество вложенных пар скобок в нем. Соединением списков (l1, .
. . , ln) и (k1, . . . , km) называется список
(l1,
. . . , ln, k1, . . . , km).
Замена
вершины a списка l на атом либо список m получается заменой поддерева l,
соответствующего a, на дерево для m. Замена обозначается l[a | m]. Через l[a ||
m] будем обозначать результат замены нескольких вхождений вершины a на m.
Атомами
в языке lisp являются числа, имена, истина T. Ложью служит пустой список nil,
который в принципе атомом не является, но в языке lisp при проверке на то,
является ли он атомом, выдается истина. Точно так же выдается истина и при
проверке, является ли он списком. Однако все списковые операции применимы к
nil, а те, которые работают с атомами, часто к нему неприменимы. Например,
попытка присваивания значения выдает ошибку.
Основная
операция для задания списков (list a b . . . z). Она вычисляет свои аргументы и
собирает их в список. Для этой операции без вычисления аргументов есть
скоропись '(a b . . . z). Она является частным случаем функции quote
(сокращенно обозначаемой '), которая запрещает всякие вычисления в своем
аргументе и копирует его в результат так, как он есть.
По
традиции, элементарные операции разбора списков обозначаются именами, которые
начинаются с c и кончаются на r, а в середине идет некоторая последовательность
букв a и d; (car s) выделяет голову (первый член списка), (cdr s) - хвост
(подсписок всех членов, начиная со второго). Буквы a и d применяются, начиная с
конца. Общее число символов в получающемся атоме должно быть не больше шести.
Рассмотрим фрагмент диалога, иллюстрирующий эти операции. Как только в диалоге
вводится законченное выражение, оно вычисляется либо выдается ошибка.
[13]>(setq a '(b c (d e) f g))
(B C (D E) F G)
[14]> (cddr a)
((D E) F G)
[15]> (cddar a)
*** - CDDAR: B is not a list
1. Break [16]> ^Z
[17]> (caaddr a)
D
[18]> (cdaddr a)
(E)
Поле зрения и поле памяти
Если
не применены специальные операции блокирования вычислений, первый аргумент
списка интерпретируется как функция, аргументами которой являются оставшиеся
элементы списка. Это позволяет программу также задавать списком.
Таким
образом, в lisp, так же, как в сентенциальных языках, структура данных
программы и поля памяти, обрабатываемого программой, совпадают. Видимо, это
одна из удачнейших форм поддержания концептуального единства для
высокоуровневых систем.
В поле памяти с каждым атомом-именем могут быть
связаны атрибуты. Стандартный атрибут - значение атома. Для установки этого
атрибута есть функция (setq atom value), аналогичная присваиванию. Эта функция
не вычисляет свой первый аргумент, она рассматривает его как имя, которому
нужно приписать значение.
Значение
в языке lisp может быть локальным. Если мы изменили значение атома внутри
некоторого блока, то такое 'присваивание' действует лишь внутри минимальных
объемлющих его скобок и исчезает снаружи блока. Кроме значения, имена могут
иметь сколько угодно других атрибутов, которые обязательно глобальны. Они
принадлежат самому имени, а не блоку. Способ установки значений этих атрибутов
несколько искусственный. Имеется еще одна функция setf, вычисляющая свой первый
аргумент, дающий ссылку на место, которому можно приписать значение (например,
на атрибут). Функция получения значения атрибута get, даже если атрибута еще
нет, указывает на его место. Следующий пример демонстрирует, как это работает.
[38]>
(setf (get 'b 'weight) '(125 kg))
(125 KG)
[39]> (get 'b 'weight)
(125 KG)
Рассмотрим
подробнее структуру данных языка lisp. Она является двухуровневой. На верхнем
уровне имеется структура списков. На нижнем находится структура информации,
сопоставленной атому. Она изображена на рис. 8.1. Оба этих уровня рекурсивно
ссылаются друг на друга, например, атрибуты атома являются списками.
Типы
данных (в смысле программирования) в lisp есть, но они определяются
динамически. В частности, если действительное число придано атому как значение,
то тип атома становится float.
Модель
вычислений LISP
Для
lisp (как и для любого другого функционального языка) не обязательно2 говорить,
где и как размещаются структуры данных (списки).
Рис.
8.1. Структура информации, сопоставленной атому языка LISP
Их
стоит рассматривать как сугубо математические объекты со сложной структурой,
которая всегда точно указывает на текущие вычислительные элементы:
До
выполнения шага вычисления - это список, включающий имя функции и ее аргументы.
Во
время выполнения шага вычисления - это те фрагменты списочной структуры поля
зрения, которые доступны для использования вычисляемой функцией (в частности,
среди них есть список, связанный с именем функции, который определяет ее
вычислительный процесс).
После
выполнения шага вычислений - это результаты вычислений. Результаты можно
разделить на три группы:
значение,
выдаваемое вызовом функции: оно замещает в поле зрения отработанный вызов
функции;
побочные
эффекты, разбросанные по структуре поля данных;
очередная
функция, которая будет вычисляться далее. В традиционном программировании
обычно возвращаются к вычислениям той функции, которая активизировала
завершаемую. В функциональном программировании может быть и по-другому.
Результат может оказаться функцией, либо описанной в статическом тексте
программы, либо скомпонованной в ходе вычислений.
Общую
структуру данных и программы функционального языка можно рассматривать как
связный нагруженный граф, динамически изменяющийся в ходе вычислений, у
которого имеются активные вершины, т. е. функции, вычисляемые в данный момент,
потенциально активные вершины, соответствующие функциям, которым назначено
вычисление или продолжение вычисления (отложенного, приостановленного и т. п.),
и пассивные вершины, участие которых в вычислениях в данный момент не
запланировано. Дуги графа отмечают связи по управлению или по данным между
функциями. Такой граф далее называется абстрактным графом функциональных
вычислений.
Конкретизировать
такой граф и стратегию отработки активных вершин можно разными способами. При
этом могут появляться разные ипостаси функционального программирования.
Для
абстрактного вычислителя граф функциональных зависимостей естественно считать
полем памяти функциональной программы, в котором выделено поле зрения: активные
(либо активные и потенциально активные) вершины-функции со своими аргументами.
В
практике реализации функциональных систем программирования имеется три варианта
конкретизации представления графа:
Списки
lisp, которые связаны с последовательными вычислениями. Структура графа
задается как совокупность линейных списков, объединяющих имена функций и
указатели аргументов. Голова списка трактуется как указание функции, а хвост -
как аргументы.
Коммутационные
схемы, которые строятся на основе разделения функций и данных: функции
представляются вершинами графа, а их аргументы-данные передаются по дугам,
соединяющим вершины. Дуги рассматриваются в качестве каналов связи. Функция
активизируется, когда ее аргументы появляются в каналах.
Ассоциативные
схемы, в которых вершины-функции остаются виртуальными. Они образуются в
результате связывания данных, имеющих одинаковый ключ. Ситуация, когда такие
данные появляются в ассоциативной памяти, трактуется как готовность аргументов
для вычисления функции, идентифицируемой этим ключом.
Коммутационные
и ассоциативные схемы рассмотрены при обсуждении неимперативных моделей
вычислений. Выбор последовательно просматриваемой структуры для первого
функционального языка обусловлен единственной для того времени возможностью
реализации функциональности путем моделирования ее операционными средствами
традиционной модели вычислений. Списочная структура также строится посредством
более или менее стандартного для традиционной модели адресного представления. С
языковой точки зрения именно этот выбор обеспечивает однородность структуры
программы и данных, на базе которой Дж. Маккарти удалось построить систему
средств, достаточную для практического функционального программирования.
Программа
на языке lisp задается как список применений функций, часть из которых может
вычисляться во время исполнения самой программы. Как правило, заданные в
программе списки интерпретируются как применения функций и вычисляются, если
другое не определяют ранее активированные функции (вы видели, что функция quote
запрещает вычисление своего аргумента, функция setq запрещает вычисление лишь
первого из двух аргументов, а функция setf заставляет вычислить первый аргумент
лишь до стадии, когда получена ссылка на его значение). Любое выражение выдает
значение, что используется, в частности, при диалоговой работе с lisp (на
примере которой иллюстрируются понятия).
Основные
управляющие функции концептуально едины и позволяют динамически строить блочную
структуру программы. В частности, функция
(block
name e1 . . . en) (8.1)
вычисляет
свои аргументы, начиная со второго, один за другим, тем самым задавая
последовательность команд. Первый ее аргумент, name, служит именем блока. В
любой момент из любого объемлющего блока можно выйти и выдать значение с
помощью функции
(return-from
name value) (8.2)
Этим
lisp выгодно отличается от большинства языков, где такие структурные переходы
либо неполны, либо некорректно реализованы.
Далее,
блоком считается любое описание функции. Описание функции производится при
помощи функции defun, которая, в свою очередь, определяется через примитивы
function и lambda. Первый из них задает, что имя, являющееся его аргументом,
рассматривается как функция (он часто сокращается в конкретном синтаксисе до
#'), второй образует значение функционального типа. Имя функции является и
именем функционального блока.
Пример
8.4.1. В данном примере иллюстрируются определение факториала, вызов анонимной
функции и возможность вычисления произвольного функционального выражения,
созданного в программе.
[1]> (defun fact (n) (if (= n 0)
1
(* (fact (- n 1)) n)))
FACT
[2]> (fact 40)
815915283247897734345611269596115894272000000000
[3]> ((lambda (x) (fact (* x x)))
5)
15511210043330985984000000
[4]> (setq g '(lambda (x) (fact
(* x x))))
(LAMBDA (X) (FACT (* X X)))
[5]>
(eval (list g 3))
362880
Нужно
заметить, что определение функции с данным именем и значение имени могут
задаваться независимо. Например, мы можем в этом же контексте задать (setq fact
7), хотя, конечно же, это отвратительный способ программирования.
Все
формальные параметры функций являются локальными переменными. Никакие изменения
их значений не выходят наружу. Но все другие свойства остаются глобальными!
Приведем пример.
[23]> (defun f (x) (progn (setf
(get 'x 'weight) '(25 kg)) (+ x 3)))
F
[24]> (setf (get 'x 'weight) '(30
kg))
(30 KG)
[25]> (get 'x 'weight)
(30 KG)
[26]> (setq x 5)
5
[27]> (f 3)
6
[28]> x
5
[29]> (get 'x 'weight)
(25
KG)
В
lisp имеется возможность создать анонимный блок со своими локальными
переменными, не объявляя его функцией. Создание такого блока называется
связыванием переменных и производится функцией let.
Значение
имени, унаследованного извне, все равно будет внешним! Смотрите пример ниже.
[32]>(setq
a '(b c d))
(B C D)
[33]>(setq b 5)
5
[34]> (list (let ((b 6)) (eval
(car a)))
(eval (car a)))
(5 5)
[35]> (list (let ((b 6)) b) (eval
(car a)))
(6 5)
[36]> (list (let ((b 6)) (list b
a))
(eval (car a)))
((6 (B C D)) 5)
[37]> (list (let ((b 6)) (eval
(car
(list 'b a)))) (eval (car a)))
(5
5)
Важнейшей
особенностью функционального программирования как стиля, впервые использованной
в языке lisp, являются функционалы с аргументами-функциями. Рассмотрим пример
возведения всех членов кортежа в квадрат.
[57]>
(setq a (list 1 5 7 9 11 13 15 19 22 28))
(1 5 7 9 11 13 15 19 22 28)
[58]> (mapcar (function (lambda
(x) (* x x))) a)
(1
25 49 81 121 169 225 361 484 784)
Функционал
mapcar применяет свой первый аргумент ко всем членам второго.
Такие
функционалы, в частности, делают циклы практически ненужными. Тем не менее в
языке lisp есть конструкции циклов как дань программистской традиции.
Чужеродность циклов подчеркивается тем, что они всегда выдают значение nil.
И,
наконец, приведем пример3.
Пример
8.4.2. Данная программа строит автомат для нахождения всех вхождений некоторой
системы слов во входной поток. Позже она анализируется с точки зрения
автоматного программирования.
Листинг 8.4.1. Автомат для нахождения всех вхождений
некоторой системы слов во входной поток (html, txt)
Прагматические добавления и динамическое порождение
программ
Разберем
возможности языка lisp в комплексе.
Выразительные
средства конкретно-синтаксического представления общей структуры данных и
программ языка lisp крайне скупы. Но это представление позволяет практически
однозначно связать синтаксис и реализационную структуру.
Реализационное
представление как нельзя лучше соответствует соглашению об общности
функциональной структуры и структуры данных: в каждом списке голова
рассматривается как указание (имя, ссылка или что-то подобное) на функцию, а
хвост - как последовательность указаний на аргументы. Задание свойства списка
не быть функцией, т. е. отмена выделенного статуса головы, обозначающей
функцию, достигается с помощью блокировок. Это удачное решение в условиях
принятого соглашения, позволяющее трактовать нефункциональный список как
константную функцию, свое изображение (представление). Еще
более важно то, что оно обеспечивает гибкость представления: функцию eval,
заставляющую список принудительно вычисляться, естественно трактовать просто
как снятие блокировок. Заметим, что на уровне абстрактного синтаксиса функция
eval обязана быть универсально применимой к любому списку.
К
сожалению, такой универсализм провоцирует крайне ненадежное и неэффективное
программирование, поэтому это решение нельзя считать удачным. Справедливости
ради заметим, что в те времена, когда разрабатывался язык, задача надежности
еще не была поставлена, но плохо то, что сформировался стихийный стандарт, не
способствующий качеству программирования.
Для
обеспечения практической пользы функции eval следовало бы предусмотреть
компенсирующие регламенты ее корректного применения на уровне конкретного
синтаксиса, режимов вычислений и системных механизмов.
Внимание!
На
уровне абстрактного и конкретного синтаксиса разные семантические возможности
имеют разный статус, поэтому в конкретном представлении необходимо
предусматривать механизм скрытия и даже полного запрета тех возможностей,
которые концептуально разумны лишь на уровне абстрактного синтаксиса4.
Структура
списков lisp идеальна для представления абстрактного синтаксиса языка. И хотя
злые языки называют этот синтаксис ,
он в точности соответствует абстрактному синтаксису. Если даже не учитывать
преимущества указанного соответствия, то остается простота представления
программ и данных в виде линейной текстовой последовательности символов.
Другие
гипотетические кандидаты на роль конкретного синтаксиса по этому критерию явно
проигрывают. Традиционные математические формы задания функций и их применений
являются текстуально избыточными (как префиксная, так и постфиксная записи
требуют обязательного обрамления параметров скобками), а бесскобочная нотация
Лукасевича (и прямая, и обратная) еще более запутывали бы тексты по сравнению с
. Но за счет внеязыковых
прагматических соглашений о том, как располагать на двумерном носителе (на
бумаге или на экране) скобочную структуру, можно существенно облегчить. Если же
система программирования будет поддерживать (и проверять!) прагматические
соглашения (что характерно для развитых систем), то вид программ станет вполне
читаемым. Таким образом преодолеваются неудобства линейного представления.
Сегодня
можно было бы говорить о других форматах конкретного синтаксиса lisp, в том
числе и не связанных с линейным представлением. Использование развитых средств
графики при экранном наборе программ позволяет на полную мощь подключить
двумерную работу. Однако традиции и стихийно сформировавшиеся стандарты не
оставляют возможности для внедрения таких форматов. Здесь в очередной раз и в
полной мере проявились вредные эффекты ранней стандартизации, мешающие развитию
направления, остающегося одним из самых концептуально богатых и перспективных.
Диктат
линейности укоренился настолько глубоко, что даже в тех случаях, когда он мог
бы быть преодолен безболезненно, языковая система чаще всего все равно строится
как линейная. Это касается не только функционального стиля5.
Объекты и LISP
Стандартная
надстройка над Common Lisp, имитирующая объектно-ориентированный стиль, это
модуль CLOS - Common Lisp Object System. Сама по себе объектность не дает
никакого выигрыша по сравнению с языком lisp, поскольку возможности
динамического вычисления функций в lisp даже шире. Видимо, именно поэтому в
CLOS имеются две интересных модификации, делающие его не совсем похожим на
стандартное ООП.
Начнем
с понятия структуры данных в языке Common Lisp. Структура определяется функцией
defstruct вида
(defstruct pet name (species 'cat)
age weight sex)
Задание
структуры автоматически задает функцию-конструктор структуры make-pet, которая
может принимать ключевые аргументы для каждого из полей:
(make-pet :nick 'viola :age '(3
years) :sex 'femina))
и
функцию доступа для каждого из полей, например pet-nick, использующуюся для
получения значения поля или ссылки на него. Если поле не инициализировано (ни
по умолчанию, ни конструктором), оно получает начальное значение nil. Никакой
дальнейшей спецификации полей структур нет6.
В
объекте для каждого поля могут явно указываться функции доступа и имена
ключевых параметров для инициализации аргументов. Приведем пример класса,
определенного на базе другого класса.
(defclass
pet (animal possession) (
(species :initform 'cat)
(nick :accessor nickof
:inintform 'Pussy
:initarg namepet)
)
Этот класс наследует поля, функции доступа и прочее от
классов animal и possession. Например, поле
cost имеется в значении класса, если оно имеется в одном из этих классов.
Поскольку статических типов у полей нет, нет и конфликтов.
Основная
функция наследования в CLOS - определение упорядочения на классах. С каждым
классом связано свое упорядочение. Наследник меньше своих предков, из предков
меньшим считается тот, который раньше перечислен в списке наследования при
определении класса. CLOS достраивает этот частичный порядок до линейного.
Способ пополнения порядка может быть в любой момент и без оповещения изменен, и
хакерское использование особенностей конкретного пополнения считается грубой
стилистической ошибкой. Если система находит несовместимость в определении
порядка, то она выдает ошибку, как в следующем примере:
[6]> (defclass init () ())
#
[7]> (defclass a (init) ())
#
[8]> (defclass b (init) ())
#
[9]> (defclass c1 (a b) ())
#
[10]> (defclass c2 (b a) ())
#
[11]> (defclass contr (c1 c2) ())
*** - DEFCLASS CONTR:
inconsistent precedence graph,
cycle (#
#)
В
CLOS могут задаваться методы, отличающиеся от функций тем, что их аргументы
специфицированы, например
(defmethod inspectpet ((x pet) (y
float))
(setf
weightofanimal 3.5))
Как
видно из этого примера, методы не обязательно связаны с классами. Они могут
быть связаны с любыми типами. Методы в CLOS могут иметь дополнительные
спецификации. Для того, чтобы разобраться, как эти спецификации взаимодействуют
с упорядочением типов классов, рассмотрим следующую программу и генерируемый
при ее исполнении результат.
Листинг 8.6.1. Взаимодействие дополнительных
спецификаций методов в CLOS с упорядочением типов классов (html, txt)
При
загрузке этого файла происходит следующее:
Пример 8.6.2. Результат загрузки программы 8.6.1
(html, txt)
Видно,
что упорядоченность классов по отношению наследования позволяет выстраивать
целые последовательности действий при вызове одного метода.
Поскольку
в CLOS нет ни механизмов скрытия конкретных представлений, ни механизмов замены
прямого доступа к данным на функции, ни других характерных особенностей ООП, мы
видим еще один пример того, как модным словом (в данном случае ООП)
прикрывается другая, не менее интересная сущность: начатки планирования
действий по структуре типов данных. В связи с этим стоит напомнить блестящий
эксперимент планирования вычислений по структуре данных, в настоящий момент
(судя по всему, временно) забытый: эстонскую систему PRIZ [Тыугу Э.Х.
Концептуальное программирование. М. Наука. 1984. - 256 с.].
Неадекватное
теоретизирование мешает увидеть и развить реальные достоинства системы и
закрепляет слабые места.
Список литературы
Для
подготовки данной работы были использованы материалы с сайта http://www.citforum.ru/