Общеизвестно, что в жизненном цикле разработки программного обеспечения львиную долю занимает не написание кода, а его сопровождение. Поэтому, начиная большой проект, стоит задуматься, удастся ли сохранить строгое разделение функциональности между модулями, достаточной ли будет первоначально планируемая параметризация функций, и не появятся ли, в конце концов, в проекте разномастные реализации одной и той же структуры данных. С этой точки зрения основным требованием к языкам разработки оказывается полноценная поддержка полиморфизма и абстрактных типов данных. Между тем, широко используемые в практике языки программирования C++ и Java, в недостаточной мере предоставляют эти средства, рассматривая их через призму объектности. В то же время функциональные языки в своем развитии достигли результатов, которые позволяют рассматривать их в качестве реальной альтернативы для традиционных языков программирования.
Расхожий аргумент против использования языков функциональной группы — утверждение о невозможности их эффективной реализации. Однако это верно лишь в отношении функциональных языков первого поколения, которые были основаны на интерпретации и динамическом контроле типов. К современным функциональным языкам этот аргумент не применим. Перечислим основные черты современных функциональных языков.
- Параметрический полиморфизм, не связанный с иерархией наследования объектов.
- Поддержка абстрактных типов данных в полном объеме.
- Статическая типизация.
- Поддержка раздельной трансляции.
- Автоматическое управление динамической памятью (сборка мусора).
- Поддержка вложенных функций и функций высших порядков, получающих в качестве параметров функцию и возвращающих новую функцию.
Необходимость языковых средств, обладающих подобными чертами, осознается повсеместно. Об этом, в частности, свидетельствует набирающий популярность термин generic programming, означающий использование параметрического полиморфизма. Увы, большинство специалистов обходит тему функциональных языков, поэтому попытаемся продемонстрировать основные черты и приемы программирования на функциональном языке последнего поколения, разобрав на примерах основные конструкции и парадигмы. В качестве базового избран язык Objective Caml, разрабатывающийся в INRIA (Институт информатики и Автоматизации, Франция).
Основной пример
Излюбленный пример для демонстрации функциональных программ — вычисление чисел Фибоначчи и факториала. Мы начнем с другого примера, с программы вычисления значения многочлена в данной точке по схеме Горнера. На языке Си эта программа может выглядеть как:
# include
typedef struct {int degree; float * coeff;}
polynomial;
float Horner (polynomial p, float x) {
float px = 0; int i;
for (i=0; i<=p.degree; i++) px = px * x
+ p.coeff [p.degree-i];
return px;
}
main () {
polynomial p;
p.degree = 2; p.coeff = (float *) malloc
(3 * sizeof (float));
p.coeff [0] = 1; p.coeff [1] = 2; p.coeff [2]
= 3;
printf ("p(1)=%f
", Horner (p, 1));
printf ("p(2)=%f
", Horner (p, 2));
printf ("p(0)=%f
", Horner (p, 0));
}
Ничего не стоит написать «кальку» на языке Objective Caml:
type polynomial = {mutable degree: int; coeff:
float array}
let horner p x =
let px = ref 0. in
for i=0 to p.degree do
px := !px *. x +. p.coeff.(p.degree-i)
done;
!px ;;
Printf.printf "p(1)=%f
" (horner {degree=2;
coeff=[|1.; 2.; 3.|]} 1.);
Printf.printf "p(2)=%f
" (horner {degree=2;
coeff=[|1.; 2.; 3.|]} 2.);
Printf.printf "p(0)=%f
" (horner {degree=2;
coeff=[|1.; 2.; 3.|]} 0.)
Objective Caml обладает конструкциями аналогичными конструкциям Cи. Описание типа выглядит вполне традиционно. Слово mutable обозначает, что значение данного поля можно изменить присваиванием. float array — тип массива вещественных чисел. (В действительности, float array является типовым выражением, конкретизирующим полиморфный тип ?a array типом float.) Конструкция let <что-то> = <чему-то> может служить аналогом описания, а конструкция let <что-то> = <чему-то> in <где-то> является выражением. Выражением является и конструкция последовательного исполнения, а точка с запятой — знаком соответствующей ей операции; значением последовательного выражения является значение его последнего члена.
То, что в Objective Caml имя функции horner начинается со строчной буквы, имеет синтаксические причины. Можно обратить внимание на то, что для этой функции не указаны типы параметров и тип результата: дело в том, что компилятор в состоянии определить их самостоятельно. Действительно, из параметра p берется поле coeff — следовательно, его тип есть polynomial. Параметр x используется в операции +., которая описана в стандартном вступлении как получающая параметры типа float, — следовательно, тип x есть float. Наконец, тип результата функции есть тип значения, именуемого px, т.е. тоже float. Правда, закономерен вопрос: верно ли, что тело функции всегда содержит достаточно информации для установления окончательного ее типа? Ответ на этот вопрос отрицательный — и это хорошо.
Слово ref указывает на то, что заведенное значение является переменной. Конструкция цикла также довольно прозрачна. Разыменование выражено явно с помощью операции «!». Поскольку в Objective Caml нет приведений и перегрузки, арифметические операции над вещественными числами обозначаются другими значками, нежели над целыми. Наконец, точка необходима для указания вырезки из массива и выборки поля структуры. Результатом функции является значение ее последнего выражения. Символ «;;» используется для обозначения конца выражения или let-определения. Его можно вставлять в конец каждой подобной конструкции, однако стоит это делать только там, где в противном случае возникла бы ошибка.
Printf.printf есть упоминание функции printf из модуля Printf (имена модулей должны начинаться с прописной буквы). Форматная строка выглядит привычно за исключением того, что в Objective Caml принято сопоставление аргументов формату type-safe. При вызове функции ее аргументы не окружаются скобками и не разделяются запятыми. Посредством так называемого конструктора можно задать значение структуры или массива; в данном примере использованы конструкторы структуры в виде {поле=значение;...; поле=значение} и массива в виде [|значение1;...; значениеN|]. Поскольку в Objective Caml нет приведений, все начальные значения вещественных переменных должны быть изображены как вещественные константы.
Таким образом, Objective Caml обладает многими хорошо известными чертами традиционных императивных языков.
Полученная программа содержит «лишние» детали. Так, для значения типа аrray с помощью библиотечной функции Array.length можно узнать число элементов. Поэтому для хранения значения коэффициентов многочлена достаточно массива. К тому же, стиль функционального программирования отличен от императивного. Сделаем первый шаг к функциональной реализации обсуждаемого алгоритма, избавившись от переменной:
let horner p x =
let n = (Array.length p) - 1 in
let rec inner px i =
if i > n then px
else inner (px *. x +. p.(n-i)) (i+1)
in
inner 0. 0;;
Printf.printf "p(1)=%f
" (horner {degree=2;
coeff=[|1.; 2.; 3.|]} 1.);
Printf.printf "p(2)=%f
" (horner {degree=2;
coeff=[|1.; 2.; 3.|]} 2.);
Printf.printf "p(0)=%f
" (horner {degree=2;
coeff=[|1.; 2.; 3.|]} 0.)
Конструкция if-then-else появилась на правах выражения. Невозможность присваивания приводит к свертыванию цикла в рекурсивную функцию с параметрами, которые представляют собой контекст цикла. В этом преобразовании опять-таки нет ничего выдающегося — связь рекурсии с итерацией общеизвестна. Слово rec указывает на рекурсивное определение: inner внутри inner обозначает самое себя (в противном случае это не так; каждое вхождение let-определения как бы вводит вложенную область видимости, перекрывая предыдущее определение того же имени). Внутри функции inner использованы имена, связанные в теле объемлющей функции. Вложенные функции в Objective Caml обладают всей полнотой доступа к объемлющему контексту.
Частичное применение, карринг и замыкание
В предыдущем варианте программы создается три массива, содержащих одни и те же данные. Свяжем значение с каким-нибудь именем:
let p = [|1.; 2.; 3.|] Printf.printf "p(1)=%f " (horner p 1.); Printf.printf "p(2)=%f " (horner p 2.); Printf.printf "p(0)=%f " (horner p 0.)
Однако идентификатор p попал в глобальную область видимости, а потому значение именуемого им массива стало доступно для непредусмотренного изменения. В Objective Caml лучше написать так:
let p = horner [|1.; 2.; 3.|] Printf.printf "p(1)=%f " (p 1.); Printf.printf "p(2)=%f " (p 2.); Printf.printf "p(0)=%f " (p 0.)
Функцию от нескольких аргументов можно применить к неполному их списку; такую конструкцию называют частичным применением. Возможно применение функции и к пустому списку аргументов, возвращающее саму эту функцию. В общем случае частичное применение возвращает функцию, которая получает остаточный список параметров и выдает то, что выдавала исходная функция. Естественно, частичное применение можно подвергнуть частичному применению, например:
let s3 a b c = a+b+c (* функция сложения трех целых *) let s2 = s3 1 (* функция сложения двух целых *) (*с единицей *) let s1 = s2 2 (* функция сложения одного целого с *) (* единицей и двойкой *) let s1' = s3 1 2 (* она же *) let s0 = s1 3 (* сумма единицы, двойки и тройки *)
Как и во всех предыдущих примерах, никакого указания типов здесь не требуется; окончательный тип будет выведен из контекста. Разбирая последний пример, можно заметить, что для сложения трех чисел достаточно трехкратного применения функции к одному аргументу:
s0 = (s1 3) = ((s2 2) 3) = (((s3 1) 2) 3) (1)
Это наводит на мысль трактовать все функции как функции одного аргумента. Такая трактовка, равно как и соответствующее формальное преобразование, называется каррингом (currying). В Objective Caml именно такой способ записи вызова является каноническим. Фактические параметры функции в Objective Caml не окружаются скобками и не разделяются запятыми — в этом нет необходимости, поскольку параметр всегда один. Если все-таки хочется написать функцию без параметров, то ей надо передать один параметр «пустого» типа unit, значения которого создаются конструктором (). Несколько выписанных подряд выражений группируются слева направо (т.е. e1 e2 ... en = (... (e1 e2 ) e3 )...en )...)) и трактуются как последовательность применения частичных применений функции, являющейся значением выражения e1, к значениям выражений e2,...,en. Отсюда вытекает необходимость поставить ;; между определением функции horner и ее использованием; в противном случае выражение !px трактуется как функция, применяемая к Printf.printf. Теперь наш пример будет выглядеть так:
let horner p x = let n = (Array.length p) - 1 in let rec inner px i = if i > n then px else inner (px *. x +. p.(n-i)) (i+1) in inner 0. 0;; let p = horner [|1.; 2.; 3.|] Printf.printf "p(1)=%f " (p 1.); Printf.printf "p(2)=%f " (p 2.); Printf.printf "p(0)=%f " (p 0.)
Идентификатор horner использован лишь однажды, так что без него вполне можно обойтись. Внесем определение horner внутрь определения p, а затем применим функцию horner к аргументу без связывания ее с каким-либо именем:
let p = (fun p x -> let n = (Array.length p) - 1 in let rec inner px i = if i > n then px else inner (px *. x +. p.(n-i)) (i+1) in inner 0. 0 ) [|1.; 2.; 3.|]
Последний пример демонстрирует функциональность Objective Caml в полном смысле этого слова: p возвращает частичное применение своей локальной функции. Более того, эта локальная функция может быть частично применена не только к локальным данным объемлющей функции, но и к ее параметру:
let p coeffs = (fun p x -> let n = (Array.length p) - 1 in let rec inner px i = if i > n then px else inner (px *. x +. p.(n-i)) (i+1) in inner 0. 0 ) coeffs
Итак, мы написали функцию, которая по набору коэффициентов возвращает функцию, вычисляющую значение многочлена с данными коэффициентами.
Частичное применение в некотором смысле есть конкретизация исходной функции для значений некоторых ее параметров. Эти «конкретизирующие» параметры имеют более широкую область действия, нежели обычные параметры в императивном смысле (их область действия была бы ограничена вызовом функции, в данном случае — частичным применением). Каким образом можно было бы «продлить» жизнь таким значениям в императивных языках?
Функцию от нескольких аргументов невозможно применить к одному параметру, и дело тут не в синтаксисе и правилах написания вызовов, а в содержательном толковании функции как таковой. Частичное применение, следовательно, должно быть выражено явно в виде другой функции. Так как возвращаемые функции могут иметь произвольную вложенность, локальные данные всех функций (включая их параметры) должны иметь глобальную область действия.
Далее, ход вычислений вложенной функции зависит от значений локальных данных объемлющих функций (в частности, от глобальных данных) и от значений собственных параметров. Эта совокупность значений целиком определяет исполнение функции. Параметры передаются в явном виде при вызове; что же касается остального, то оно образует некий контекст функции, который можно связать с нею при создании. Необходимый контекст для любой функции определяется статически в процессе идентификации; этот контекст называется замыканием. Замыкание есть обобщение многих хорошо знакомых императивных конструкций. Так, частным случаем замыкания является организация доступа к внешним средам из вложенной функции с использованием статической цепочки.
Наличие замыкания дает возможность реализовывать функции высших порядков, что позволяет выразить многие знакомые конструкции. Например, функция:
let o f g = fun x -> f (g x)
возвращает функцию, которая есть композиция параметров.
Каковы в данном случае типы параметров и результата функции o? Во всех предыдущих примерах тело функции позволяло однозначно определить эти типы, однако здесь зацепиться решительно не за что. Мы подошли к одной из наиболее полезных черт Objective Caml — полиморфизму.
Полиморфизм
Итак, определить точный тип параметров и результата функции o не представляется возможным. Однако, исходя из синтаксического устройства ее тела, можно сделать такие выводы:
- применение функции o к своим аргументам возвращает функцию (так как ее тело есть конструкция fun);
- аргументы функции o есть функции (так как в ее теле встречаются их применения);
- тип результата g есть тип аргумента f (по той же причине и в силу отсутствия приведений);
- тип результата функции, являющейся результатом применения o, есть тип результата f (по тем же соображениям);
- тип аргумента функции, являющейся результатом применения o, есть тип аргумента g (аналогично).
В разобранном примере описанной функции был сопоставлен ее тип, определяемый некоторым типовым выражением. Типовые выражения являются равноправной синтаксической конструкцией Objective Caml. Идентификаторы, начинающиеся с апострофа, называются типовыми переменными, а сами типовые выражения определяются с точностью до переименования типовых переменных. Если в типовом выражении есть хотя бы одна типовая переменная, то тип этот называется полиморфным. Именно поэтому полиморфизм такого рода вида называют параметрическим — тип значения может быть параметризован типами его подзначений. Можно попытаться вывести тип выражения исходя из того, какие его свойства требуются в тех контекстах, в которых оно употребляется в исходной программе. Если желательные свойства объекта в разных контекстах противоречат друг другу, то это значит, что ему не соответствует никакой тип, и, следовательно, с точки зрения языка имеет место семантическая ошибка. Вывод и проверка типов происходят при компиляции программы, т.е. контроль типов — статический.
С точки зрения реализации полиморфизм такого рода не предполагает особенной хитрости. Полиморфные значения представляются указателями в область памяти.
Конструкторы и сопоставление с образцом
Чтобы ввести структурный тип, требуется указать имена и типы его полей. Нигде, кроме как в описании типа структуры, этого сделать нельзя, поэтому несмотря на вывод типов конструкция их описания в некоторых случаях оказывается необходимой. Если описываемый тип полиморфен, то все его типовые параметры должны быть перечислены в описании перед именем:
type (?a, ?b) pair = {first: ?a; second: ?b}
Это описание вводит тип (?a, ?b) pair — структуры из двух полей произвольного типа. При таком описании можно создать значения экземпляров этой структуры с разными типами полей:
let p = {a=3; b=»abc»}
let p? = {a=(fun x -> x); b=1}
Здесь тип p — (int, string) pair, тип p? — (?a->?a, int) pair. Результат подстановки типовых выражений вместо типовых переменных в другое типовое выражение называется конкретизацией. Так, (int, int) pair — это конкретизация полиморфного типа (?a, ?b) pair. Конкретизация, конечно, тоже может приводить к полиморфному типу, как это видно из предыдущего примера. Теперь понятно, что массивы, с которыми мы имели дело раньше, на самом деле просто значения одного из типов стандартного вступления Objective Caml, а именно полиморфного типа ?a array. Еще пример:
type point = {x: int; y:int; z:int}
Это описание вводит структурный тип из трех целых полей x, y и z, которые неизменяемы, поскольку не описаны как mutable. Значение типа point создается с помощью конструктора структуры:
let p = {x=3; y=2; z=0}
Поскольку поля point неизменяемы, любое изменение значения структуры выражается через создание нового экземпляра:
let p? = {x=p.x+3; y=p.y; z=p.z}
На такой случай предусмотрено специальное синтаксическое сокращение:
let p? = {p with x=p.x+3}
Здесь после with перечисляются только те поля, которые изменяются. Выборка поля осуществляется как обычно, указанием его имени после точки; кроме того, в Objective Caml есть дополнительная конструкция, позволяющая выбрать все поля структуры одновременно:
let {x=a; y=b; z=c} = p
Здесь в правой части let-определения стоит структурное значение, а в левой — образец, отличающийся от конструктора структуры тем, что после символов ?=? в нем в свою очередь находятся образцы, которые и связываются со значением соответствующих полей. Частный случай образца — идентификатор. В данном примере идентификатор a связывается со значением p.x, b и c со значениями p.y и p.z соответственно. Если нужны не все поля, можно выбрать только некоторые из них (образец ?_? указывает на то, что значение поля y не требуется связать ни с каким идентификатором):
let {x=a; y=_; z=c} = p
Конструкция, позволяющая раскрыть внутреннюю структуру значения, пользуясь для этих целей образцом, называется сопоставлением. Применять сопоставление с образцом можно не только к структурам, но и к другим значениям; каждому типу соответствует свое синтаксическое устройство образца, в целом соответствующее синтаксическому устройству конструктора. Так, образец для массива выглядит как [|p1; p2; ...; pk|], где p1,...,pk — образцы для элементов. Сопоставление с образцом позволяет определить тип значения, которое ему сопоставляется. Например, образец [|_; _; [|_; a|]|] соответствует типу массива массивов (?a array array).
Образец определяет не только тип сопоставляемого значения, но и некоторые другие его свойства. Так, в приведенном примере он накладывает требования на количество элементов в массиве (он должен состоять из трех элементов, причем последний в свою очередь должен состоять из двух элементов). Это требование в общем случае можно проверить только при исполнении программы: сопоставление с образцом является динамически исполняемой конструкцией, которая может либо успешно завершиться, либо привести к исключению — ошибке сопоставления.
Пара конструктор-образец определяет в некотором смысле взаимообратные преобразования: конструктор создает значение из его компонентов, образец — разбивает значение на компоненты в соответствии с типом. Нам уже известны два вида конструкторов (структуры и массивы) и соответствующие им образцы. Существует еще два вида конструкторов, один из них чрезвычайно удобен, а другой — чрезвычайно важен.
Чрезвычайно удобным является конструктор n-ки (в особенности, его частный случай — конструктор пары):
(1, «abc», fun x y -> x+y)
В n-ку можно свободно объединять разнотипные значения. Типовое выражение, используемое для обозначения типа n-ки, состоит из выражений для типов ее компонентов, разделенных символом ?*?. Тип n-ки в данном примере описывается типовым выражением int * string * (int -> int -> int). Образец, с которым можно сопоставить значение типа n-ки, выглядит очевидным образом: (p1, p2, ..., pk), где p1,..., pk — образцы для компонентов. n-ки чрезвычайно удобны для временного объединения различных значений. Например, посчитать одновременно наибольшее и наименьшее из двух значений можно так:
let maxmin x y = if x >= y then (x, y) else (y, x)
Предположим теперь, что нам требуется найти индекс первого элемента массива, удовлетворяющего определенному условию. Полиморфизм позволит сделать это для массива элементов любого типа:
let lookup a p = let n = Array.length a in let rec inner i = if i>n or (p a.(i)) then i else inner (i+1) in inner 0
Тип этой функции: ?a array -> (?a -> bool) -> int. Единственная неприятность состоит в том, что если искомый элемент не найден, то об этом можно догадаться по тому, что возвращенный индекс указывает за границы массива. Очевидно, правильнее было бы вернуть такую информацию в каком-нибудь более пристойном виде. Для этой цели можно воспользоваться парой, содержащей признак присутствия и сам индекс. Это лучше, но, с другой стороны, если нужного элемента все-таки нет в массиве, второй элемент возвращаемой пары придется «выбросить». Избежать этого позволяет объединение, или, в терминах Objective Caml, алгебраический тип:
type ?a option = None | Some of ?a
Это описание вводит в рассмотрение зависящий от одного параметра (?a) полиморфный тип option. Создать значение типа option можно только с помощью одного из двух конструкторов — None или Some. Значение, созданное с помощью Some, содержит внутри себя подзначение типа ?a. Воспользуемся этим типом option для наших целей:
let lookup a p = let n = Array.length a in let rec inner i = if i=n then None else if p a.(i) then (Some i) else inner (i+1) in inner 1
Тип этой функции: ?a array -> (?a -> bool) -> int option. Теперь если нужный элемент не найден, вернется None; в противном случае индекс найденного элемента будет выдан «завернутым» в значение типа int option с помощью конструктора Some. Конструкторы алгебраических типов — это и есть обещанные чрезвычайно важные конструкторы. Алгебраические типы позволяют выразить огромное разнообразие сущностей. Скажем, массив, каждый элемент которого является целым или строкой, с использованием алгебраических типов задается так:
type e = Str of string | Int of int type a = e array
Здесь e — алгебраический тип, значение которого создается либо конструктором Str (и тогда хранит подзначение-строку), либо конструктором Int (и тогда хранит подзначение-целое); a — тип массива с элементами типа e. Заметим, что тип a можно и не описывать, поскольку его описание в отличие от описаний алгебраических типов и структур не определяет никаких имен.
Конструктор алгебраического типа может принимать не более одного параметра. Если хочется ?завернуть? в алгебраический тип несколько значений, то можно воспользоваться типом n-ки:
type rational = Whole of int | Fraction of int * int
Чтобы создать значение типа rational с помощью конструктора Fraction, надо соорудить пару, а потом «вручить» ее конструктору:
Fraction (1, 2)
Наконец, полезнейшим свойством алгебраических типов является их возможная рекурсивность. Иными словами, значение, «завернутое» с помощью конструктора алгебраического типа, может быть значением того же самого типа:
type ?a list = Nil | Cons of ?a * ?a list
В данном случае конструктор Cons связывает пару, состоящую из значения типа ?a и значения того же типа ?a list, который он конструирует. Списки (а это действительно обычные односвязные списки) настолько распространены в программировании, что стандартное вступление Objective Caml содержит определение такого типа. Кроме того, в целях «экономии чернил» для конструктора Nil введено сокращение ?[]?, а для Cons ?::? в инфиксной нотации (таким образом, ?1 :: 2 :: 3 :: []? список из трех целых). Кроме того, запись ?a :: b :: ... :: []? допускает сокращение в виде ?[a; b; ...]?. С помощью алгебраических типов могут быть описаны структуры данных, имеющие неограниченный размер, но регулярную структуру. Например, конструкция
type ?a tree = Node of ?a * ?a list
задает дерево произвольной степени, хранящее в каждом узле значение типа ?a (рекурсивный алгебраический тип должен обязательно содержать хотя бы один конструктор; в данном случае, несмотря на отсутствие альтернатив, без конструктора Node обойтись нельзя).
Понятно, что описание алгебраического типа открывает возможность использования специальных образцов для сопоставления. Так, для сопоставления со значением типа option можно пользоваться образцами None и Some p, где p — в свою очередь образец для сопоставления со значением, содержащимся «внутри» Some. Однако для того чтобы полноценно пользоваться алгебраическими типами, необходима конструкция условного сопоставления, смысл которой можно выразить фразой «если значение создано таким-то конструктором, делать это, а если таким — то это» и т.д. Например, применив функцию lookup, нужно проверить, вернула ли она значение, созданное конструктором Some, и если вернула, извлечь из него значение индекса. Для этого существует специальная синтаксическая конструкция, называемая «сопоставлением с образцом»:
match lookup [|1; 2; 3|] (fun i -> i mod 2 = 0) with | None -> Printf.printf "Нет четного элемента! " | Some i -> Printf.printf "Элемент номер %d - четный. " i
Здесь после ключевого слова match идет выражение, со значением которого мы хотим разобраться, а далее после ключевого слова with — список альтернатив, разделенных вертикальной чертой. Каждая альтернатива состоит из образца, за которым через знак ?->? следует выражение.
Смысл конструкции сопоставления очевиден: выражение после match вычисляется и сопоставляется последовательно с каждым образцом в левых частях альтернатив. Как только сопоставление прошло удачно, исполняется выражение в правой части этой альтернативы, и после этого выполнение сопоставления завершается. Если значение вычисленного выражения не сопоставилось ни с одним образцом альтернатив, возбуждается исключение.
Наличие полиморфизма и сопоставления с образцом позволяет в широких пределах расширять язык, насыщая его структурами данных и процедурами обработки, имеющими такую же степень общности, что и предопределенные конструкции.
Функциональность против императивности
Вряд ли имеет смысл утверждать, что функциональные языки являются наилучшим выбором в любой ситуации; например, трудно их рекомендовать для написания драйверов. Обычно говорят, что функциональная программа менее эффективна, чем программа на Cи или на Фортране. Однако при этом не учитывают, что по выразительной силе функциональные языки превосходят объектно-ориентированные, а полиморфизм обладает той же степенью общности, что и шаблоны C++, но при этом без таких накладных расходов.
Возможная область применения функциональных языков существенно шире, чем просто упражнения в области разработки языков программирования. Если надо написать небольшую программу в служебных целях («программу на час»), то функциональные языки часто оказываются вне конкуренции — их выразительная сила и достигаемая за ее счет краткость позволяют быстро решить задачу, при этом потеря эффективности не имеет существенного значения. Неудивительно потому, что функциональные языки используются для прототипирования.
С другой стороны, когда размер системы переходит через некоторый порог, накладные расходы на поддержание структур данных, представленных в простом виде, начинают превышать выигрыш в эффективности, полученный за счет этого простого представления. Таким образом, и здесь соображения производительности могут вывести функциональные языки на хорошие позиции.
Отсутствие переменных характеризует основные различия между императивным и функциональным подходами. Одно из кратких определений функционального стиля — программирование без переменных. Говоря в общем, переменные плохи своей расплывчатой семантикой, в императивных языках нет однозначного способа аналитически определить значение переменной в данной точке программы. Семантика имени в императивных языках есть семантика общего вида, в то время как имя в функциональной программе обычно имеет более конкретный смысл. В общем случае значение имени в функциональной программе всегда имеет четкое аналитическое представление — это выражение, с которым оно связано. Именно поэтому let-определение мы назвали лишь аналогом описания, а на самом деле оно ничего не описывает, а лишь вводит имя, которое (в своей области видимости) навсегда связано с выражением в правой части let-определения. Исключение составляют массивы и mutable-поля структур. Эти конструкции, фактически реализующие возможность изменения некоего значения по месту его хранения, не считаются функциональными. Таким образом, Objective Caml не является чистым функциональным языком. Наличие императивных черт (таких, как присваивания и переменные) ничего не добавляет к полноте языка, однако во многих случаях помогает писать программы. Эти конструкции при умеренном употреблении весьма практичны, хотя и создают сложности при анализе, оптимизации и работе программ. В частности, в языках со сборкой мусора присваивание становится дорогой операцией с точки зрения эффективности.
Другим важным отличием является подход к реализации полиморфизма. Легко видеть, что организация полиморфизма с помощью наследования привносит существенные накладные расходы. Во-первых, для его достижения надо написать сравнительно много кода: описать классы, наследование, виртуальные функции-члены. Во-вторых, пространство для маневра ограничено виртуальными функциями — только с их помощью можно достичь нужного эффекта. Иначе говоря, объектно-ориентированный полиморфизм нужно моделировать, а функциональный встроен, а потому более элегантен и эффективен.
В качестве демонстрации этого принципиального различия рассмотрим еще один пример. Функцию, которая применяет функцию, полученную первым аргументом, к параметру, полученному вторым аргументом, на Objective Caml записывается следующим образом:
let apply f x = f x
Умозрительно прокрутив процедуру вывода типов, подобно тому, как это было сделано ранее, получаем следующие типы:
- тип f есть 'a -> 'b;
- тип x есть 'a;
- тип apply есть ('a -> 'b) -> 'a -> 'b.
Такие типы действительно вполне отражают минимальный набор свойств, необходимый для того, чтобы функция apply имела смысл. Написать на традиционном императивном языке текст такой же степени общности не удастся. Требуемое поведение можно эмулировать при помощи объектно-ориентированных конструкций:
class Parameter {...};
class Result {...};
class Function {... public:
Result Invoke (Parameter &);...};
Result apply (Function & f, Parameter & x)
{ return f.Invoke (x); }
Очевидно, что объектная реализация существенно проигрывает функциональной — она менее наглядна (еще надо догадаться, что apply — это функция, из-за которой все затевалось), более громоздка (даже ее «скелет» в несколько раз превышает объем функциональной реализации), и в лучшем случае столь же эффективен (если удастся обойтись абстрактными классами).
В некотором смысле подход, основанный на выводе типов, противоположен по отношению к традиционным системам типов императивных языков, в которых программисту при описании типов и переменных предлагается заранее запастись всеми необходимыми свойствами. Понятно, что это приводит к хорошему результату лишь тогда, когда будущее использование сущностей программы известно с достаточной степенью точности. Увы, такая ситуация — при разработке больших систем большая редкость; чаще приходится сталкиваться с постоянным переписыванием базовых модулей по мере развития системы.
В основе реализации объектного и параметрического полиморфизмов лежит один и тот же принцип — идентичность представления значений разных типов. Интересы проектирования больших систем требуют существенной гибкости структур данных. В результате, в объектных программах стало характерным использование информации времени исполнения о типах и приведение с контролем типов против наследования. Можно без преувеличения сказать, что объектно-ориентированный код сегодня обычно содержит существенно больше динамического контроля типов, нежели функциональный.
Справедливости ради отметим, что недостаточность средств, которые предоставляют современные объектно-ориентированные языки, является следствием не плохого проектирования, а скорее неправильного использования. Взгляд на программу как взаимодействие изолированных объектов, имеющих внутреннее состояние и обменивающихся сообщениями, ни в коей мере не противоречит функциональному подходу. Неприятности возникают тогда, когда необходимые средства (полиморфизм, абстракцию данных и т.д.) начинают рассматривать как свойства объектности. Дополнительной иллюстрацией того, что функциональный и объектно-ориентированный стиль не противоречат друг другу, является реализация традиционного объекта на Objective Caml. Объектом принято считать совокупность совместно инкапсулированных операций и данных, где функция-член помимо своих непосредственных параметров имеет доступ к внутренности объекта. Используем аналогичное свойство замыкания для реализации объектности:
type point =
{
getx: unit -> int;
gety: unit -> int;
setx: int -> point;
sety: int -> point;
}
Это описание содержит «операционную» часть объекта — определены функции-члены (getx, gety, setx, sety). Функции, изменяющие содержимое объекта, в функциональной реализации фактически играют роль дополнительных конструкторов. Остается написать основной конструктор:
let rec create (x, y) =
{ getx = (fun () -> x);
gety = (fun () -> y);
setx = (fun x -> create (x, y));
sety = (fun y -> create (x, y));
}
Определение этого конструктора содержит вторую часть обычного описания объекта — именно, определение атрибутов и собственно тел функций-членов. Как видно, функции, меняющие данные объекта, действительно свелись к вызову конструктора, в силу чего основной конструктор оказался формально-рекурсивным. Данные описания вполне реализуют задуманный объект. Действительно, применение функции create к паре параметров приведет к созданию структуры с нужным набором операций. Параметры create попадут в ее замыкание, и, в силу использования, в замыкания нужных функций-членов. Использование объекта, созданного таким образом, выглядит вполне традиционно:
let p = create (1, 2) in let x = p.getx () in let y = p.gety () in let p = p.setx 10 in let p = p.sety 20 и т.д.
***
Функциональные языки последнего поколения не стали основным инструментом разработки коммерческого программного обеспечения. В известной степени причинами этого является их сравнительная молодость и определенная инерция программной индустрии, которая не спешит расставаться с привычными методами. Как следствие, функциональное программирование не может предложить сегодня такое количество библиотек и готовых функций, как императивное и объектно-ориентированное. Тем не менее идеи, апробированные в области функционального программирования (параметрический полиморфизм и вывод типов), не могут не оказать сильнейшего влияния на разработку языков, подобно тому, как объектно-ориентированная модель коренным образом изменила облик программирования, спустя почти пятнадцать лет после своего появления. Овладевать этими идеями нужно уже сегодня. Даже начальное знакомство с функциональным программированием будет полезно для разработчиков — по крайней мере, незнание подобных средств перестанет быть решающим аргументом против их использования.
Дмитрий Булычев (db@tepkom.ru) — сотрудник кафедры системного программирования Санкт-Петербургского государственного университета.
Полезные ресурсы
- Язык Objective Caml. Полное описание языка, неформальное введение, ответы на часто задаваемые вопросы и т.д. Здесь же можно найти бесплатно распространяемую среду программирования для платформ Linux, Mac OS, Windows. Помимо собственно компилятора система содержит отладчик, систему для расширения синтаксиса базового языка и разнообразные библиотеки.
- Язык Standard Meta Language, который, в отличие от Objective Caml, стандартизован
- Реализация SML, называемая Moscow ML
- Cайт для общего знакомства с функциональным программированием.
