1.2. Функциональность

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

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

Пример нефункциональности Паскаля:

var flag: boolean;

function f (n:integer):integer;

begin

if flag then f:=n

else f:= 2*n;

flag:=not flag

end;

begin

flag:=true;

writeln(f(1)+f(2)); ==> 5

writeln(f(2)+f(1)); ==> 4

end.

Функция f не является математической (“чистой”) функцией. Операции, подобные этой, в математике не разрешены, поскольку математические рассуждения базируются на идее равенства и возможности замены одного выражения другим, означающим то же самое, т. е. определяющим ту же величину. Вместо представления о переменной как о величине, которая может периодически изменяться путем присваивания ей различных значений, переменные в функциональной программе рассматриваются как переменные в математике: если они существуют, то, следовательно, имеют какую-то величину, и эта величина не может изменяться. Вместо программы, являющейся последовательностью императивов, описывающих, как компьютер должен решать задачу, основываясь на состоянии, изменяемом шаг за шагом (т. е. на изменении переменных в результате присваивания), функциональная программа описывает, что должно быть вычислено, т. е. является просто выражением, определенным в терминах заранее заданных функций и функций, определенных пользователем. Величина этого выражения является результатом программы. Таким образом, тут отсутствует понятие состояния программы и предыстория её вычислений.

2. Введение в функциональное программирование

2.1. О языке Лисп

Лисп (LISP) был первым чисто функциональным языком. Он был разработан Джоном Маккарти в 1961 году. Хотя оригинальный Лисп был чисто функциональным в смысле прозрачности ссылок, появившиеся в последующие годы диалекты включили в себя многие императивные особенности, в частности конструкции для выполнения разрушающего присваивания, уничтожавшие простоту и элегантность, присущие оригинальному языку. Существует, однако, “чистое” подмножество языка Лисп, встроенное во все диалекты, которое само по себе можно использовать для написания функциональных программ в нашем понимании этого термина. Хотя различные реализации Лиспа отличаются довольно значительно по выбору ключевых слов, имен примитивных функций и структуре программы в целом, в их основе лежат одни и те же принципы.

Мы будем строить наше обсуждение на синтаксисе диалекта Лиспа, называемого XLisp (David Betz, Великобритания, 1988), практически согласованного со стандартом Common Lisp.