В этой статье предпринята попытка простым и понятным языком рассказать о функциональном программировании. Несмотря на то, что языки функционального программирования еще не получили широкого распространения в кругах программистов, есть факты свидетельствующие о некоторых преимуществах функционального программирования перед традиционным, императивным.
Функциональное
программирование ставит своей
целью придать каждой
программе простую математическую
интерпретацию. Эта интерпретация
должна быть независима от деталей
исполнения и понятна людям,
которые не имеют научной степени в
предметной области.
Паулсон, Лоренс
В 40-х годах нашего века были построены первые цифровые компьютеры. Самые первые модели этих компьютеров 'программировались' на машинных языках, посредством соединения плат проводками вручную или, в лучшем случае, путем установки в нужное положение сотен переключателей. Машинные языки плохо воспринимаются человеком, поэтому следующим шагом стало создание различных ассемблеров. В ассемблере машинные команды получают компактные мнемокоды типа LOAD, STORE, ADD и т.п.
В конце 50-х годов сотрудник IBM Джон Бэкус решил, что записывать формулы вида
A = B + C
не только проще, чем
LOAD B ADD C STORE A
но к тому же эти формулы могут быть выполнены на любой машине для которой есть специальная программа, которую назвали компилятором. Первый компилятор был создан для языка FORTRAN (FORmula TRANslator - Транслятор Формул).
В те дни компьютеры были очень дороги. Поэтому создатели первых языков программирования высокого уровня в погоне за эффективностью пошли по наиболее простому пути. Архитектура языков программирования должна была быть максимально приближена к архитектуре компьютера. Компьютер состоит из центрального процессора и памяти. Поэтому программа должна была состоять из последовательности инструкций, выполняемых процессором и модифицирующих память. На основе этого принципа был разработан так называемый императивный стиль программирования.
Основными признаками императивных языков программирования являются ориентированность, в первую очередь, на последовательное исполнение инструкций оперирующих с памятью (присваиваний) и итеративные циклы. Но не это главное. Со времен возникновения FORTRAN-а прошло почти 50 лет. За это время были разработаны сотни намного более развитых императивных языков, таких как Pascal, C++, Ada, Java и т.д. Значительно усовершенствованы механизмы и методы императивного программирования. Однако идея, лежащая в его основе, остается прежней. Программы на этих языках описывают процесс последовательного, пошагового решения задачи. Как следствие, полученные программы слабо напоминают оригинальную спецификацию задачи, которая, как правило, не содержат никаких упоминаний о различных массивах, указателях и счетчиках.
На протяжении последних 400 лет, центральным понятием математики является понятие функции. Математические функции выражают связь между параметрами (входом) и результатом (выходом) некоторого процесса. Так как вычисление это тоже процесс, имеющий вход и выход, функция - вполне подходящее средство задания вычислений. Именно этот простой принцип положен в основу функционального стиля программирования. Функциональная программа представляет собой определения функций. Функции определяются через другие функции или рекурсивно - через себя. В процессе выполнения программы, функции получают параметры, вычисляют и возвращают результат, в случае необходимости вычисляя значения других функций. Программируя на функциональном языке, программист не должен описывать порядок вычислений. Ему необходимо просто описать желаемый результат в виде системы функций.
Почти каждый из нас так или иначе использовал функциональный подход к программированию. Возьмем к примеру всем известный Microsoft Excel. Записывая содержимое ячейки в виде, похожем на обычную математическую формулу, мы не задумываемся о действительном порядке вычислений этой формулы, возлагая эти функции на встроенный в Excel интерпретатор. А этот интерпретатор построен так, что правильный порядок вычисления этого выражения и, следовательно, правильный результат гарантированы. Фактически, вся таблица представляет собой набор функций и констант (которые, в общем, тоже функции), определенных друг через друга.
Другим простым примером могут послужить языки запросов к базам данных. В большинстве своем эти языки используют один из двух подходов. В языках, основанных на реляционной алгебре, результат записывается в терминах операций над таблицами, демонстрируя тем самым явно императивный подход. Языки же, основанные на реляционном исчислении (например всем известный SQL или QBE), напротив, описывают только результат, являясь тем самым по сути функциональными.
По мере развития вычислительной техники, компьютерное время удешевляется, поэтому особую важность приобретает вопрос "Как описывать вычисления на языке более близком человеку, чем компьютеру?". На этот вопрос призваны ответить универсальные функциональные языки программирования, программы на которых гораздо больше напоминают изначальную спецификацию задачи, чем программы, написанные с помощью императивных языков программирования.
Теоретические основы императивного программирования были заложены в 30-х годах Аланом Тьюрингом и Джоном фон Нейманом. Теория положенная в основу функционального подхода, также родилась в 20-х - 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать Мозеса Шёнфинкеля (Германия и Россия) и Хаскелла Карри (Англия), разработавших теорию комбинаторов, а также Алонзо Чёрча (США), создателя лямбда исчисления.
Теория так и оставалась теорией, пока в начале 50-х Джон МакКарти не разработал язык Lisp, который стал первым почти функциональным языком программирования и на протяжении многих лет оставался единственным таковым. Хотя Lisp все еще используется (как и FORTRAN), он уже не удовлетворяет некоторым современным запросам, которые заставляют нас взваливать как можно большую ношу на компилятор, облегчив тем самым непосильный труд программиста. Необходимость в этом, конечно же, возникла из-за все возрастающей сложности программного обеспечения.
В связи с этим обстоятельством все большую роль начинает играть типизация. В конце 70-х - начале 80-х интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм. Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число диалектов.
В результате вышло так, что практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многочисленные более мелкие проблемы. Чтобы исправить ситуацию, объединенная группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов. В настоящее время действителен стандарт Haskell 98. Большинство примеров в этой статье будут приводиться именно на этом языке.
В первую очередь большинство функциональных языков программирования реализуются как интерпретаторы, следуя традициям Lisp-а. Интерпретаторы удобны для быстрой отладки программ, исключая длительную фазу компиляции, тем самым укорачивая обычный цикл разработки. Однако с другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения в несколько раз. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие неплохой машинный код (например Objective Caml) или код на C/C++ (например Glasgow Haskell Compiler). Что показательно, практически каждый компилятор с функционального языка реализован на этом же самом языке.
Программы на функциональных языках обычно намного короче и проще, чем те же самые программы на императивных языках. Как стандартный пример, рассмотрим алгоритм быстрой сортировки Хоара. На C этот алгоритм описывается примерно так:
void qsort (int a[], int l, int r)
{
int i = l, j = r, x = a[(l + r) / 2];
do
{
while (a[i] < x) i++;
while (x < a[j]) j--;
if (i <= j)
{
int temp = a[i];
a[i++] = a[j];
a[j--] = temp;
}
}
while (i <= j);
if (l < j) qsort (a, l, j);
if (i < r) qsort (a, i, r);
}
Сравним этот код с кодом на Haskell:
qsort :: (Ord a) => [a] -> [a]
-- если список пустой, то сортировать его не нужно...
qsort [] = []
-- ...иначе разобьем его на голову - x и хвост - xs
qsort (x : xs) =
-- конкатенация отсортированного списка элементов хвоста меньших или равных x...
qsort [n | n <- xs, n <= x] ++
-- ...и списка элементов хвоста больших x
qsort [n | n <- xs, n > x]
Что может быть проще?
Кроме того, все операции с памятью выполняются автоматически. При создании объекта для него автоматически выделяется память. После того как объект выполнит свои функции, он вскоре будет также автоматически уничтожен сборщиком мусора, который является частью любого функционального языка.
Еще одним полезным свойством позволяющим сократить программу является встроенный механизм сопоставления с образцом. Это позволяет описывать функции как индуктивные определения. Например:
-- Функция, возвращающая n-е число Фибоначчи fib :: Int -> Int fib 0 = 1 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1)
или
-- Функция, возвращающая число n в целой степени m
pow :: Int -> Int -> Int
pow n 0 = 1
pow n m | even m = pow (n * n) (m `div` 2)
| otherwise = n * pow n (m - 1)
Практически все современные языки функционального программирования являются строго типизированными языками. Строгая типизация обеспечивает безопасность. Программа, прошедшая проверку типов просто не может выпасть в OS с сообщением подобным "segmentation violation". Большая часть ошибок может быть исправлена на стадии компиляции, поэтому стадия отладки и общее время разработки программ сокращаются. Вдобавок к этому строгая типизация позволяет компилятору генерировать более эффективный код и тем самым ускорять выполнение программ.
Вернемся к примеру с быстрой сортировкой Хоара. Помимо уже упомянутых отличий между вариантом на языке C и вариантом на Haskell есть еще одно важное отличие: функция на C сортирует список значений типа int (целых чисел), а функция на Haskell - список значений любого типа, который принадлежит к классу упорядоченных величин Ord. Поэтому функция на Haskell может сортировать и список целых чисел, и список чисел с плавающей запятой, и список строк. Мы можем описать какой-нибудь новый тип. Определив для этого типа операции сравнения и cделав его тем самым экземпляром класса Ord, мы без перекомпиляции сможем использовать qsort и со списками этого нового типа. Это полезное свойство системы типов называется параметрическим или истинным полиморфизмом, и поддерживается большинством функциональных языков.
Еще одной разновидностью полиморфизма является перегрузка операций (overloading), позволяющая давать различным, но в чем-то схожим функциям одинаковые имена. Типичным примером перегруженной операции является обычная операция сложения. Функции сложения для целых чисел и чисел с плавающей запятой различны, однако для удобства они носят одно и то же имя. Некоторые функциональные языки, например все тот же Haskell, помимо параметрического полиморфизма, поддерживают и перегрузку операций.
Программист, знакомый с C++, может возразить: "Да, все это хорошо, но я могу легко определить такую же полиморфную функцию qsort и на C++, воспользовавшись механизмом шаблонов". Да, это так. В стандартную библиотеку C++ STL входит такая функция и множество других полиморфных функций. Но шаблоны C++, как и родовые функции Ada, на самом деле порождают множество перегруженных функций, которые, кстати, компилятор должен каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в Haskell полиморфная функция qsort это одна функция.
В некоторых языках, например в Ada, строгая типизация вынуждает программиста явно описывать тип всех значений и функций. Чтобы избежать этого, в строго типизированные функциональные языки встроен специальный механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста. Этот механизм называется механизмом вывода типов (type inference). Известно несколько таких механизмов, однако большинство из них являются разновидностями модели типизации Хиндли-Милнера, разработанной в начале 80-х.
Таким образом в большинстве случаев можно не указывать типы функций. Однако в примерах, приводимых в этой статье, типы функций указаны явно. Это позволяет компилятору дополнительно контролировать корректность типов определяемых функций.
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (модулей) с четко определенными связями между ними. Тем самым облегчается процесс проектирования и последующей поддержки больших программных систем.
Поддержка модульности не является свойством именно функциональных языков программирования. Существуют очень развитые модульные императивные языки. В качестве примеров подобных языков можно привести Modula-2 и Ada-95.
В этой статье, однако, речь идет о языках функционального программирования. Поэтому для примера рассмотрим систему модулей функционального языка Standard ML. Standard ML - строго типизированный язык, это накладывает свой отпечаток и на систему модулей. Поэтому каждый модуль (в терминах языка - структура) имеет тип (сигнатуру). Сигнатура определяет часть структуры доступную извне. Именно так в Standard ML реализуется механизм абстракции данных.
По аналогии с соответствиями сигнатура = тип и структура = значение, должно быть определено и какое-нибудь соответствие понятию функции. В самом деле, в Standard ML существует возможность определять функции над структурами. Такие функции называются функторами, по аналогии с термином из общей алгебры. Функторы позволяют преобразовывать структуры, соответствующие одной сигнатуре, в структуры, соответствующие другой, тем самым одновременно являя собой механизм реализующий наследование и параметрический полиморфизм на уровне целых модулей.
Standard ML является одним из немногих функциональных языков с такой интересной системой модулей. В Haskell, например, реализована намного более простая система, сходная с системой модулей в языке Modula-2.
В функциональных языках функции могут быть переданы другим функциям в качестве аргумента или возвращены в качестве результата. Функции, принимающие функциональные аргументы, называются функциями высших порядков или функционалами. Самый, пожалуй, известный функционал, это map. map применяет некоторую функцию ко всем элементам списка, формируя из результатов другой список. Например определив функцию возведения целого числа в квадрат как:
square :: Int -> Int square n = n * n
мы можем воспользоваться этой функцией для возведения в квадрат всех элементов списка
l2 = map square [1, 2, 3, 4] -- результат - список [1, 4, 9, 16]
Каждый тип имеет литералы, например тип Boolean имеет литералы True и False, а тип Char имеет 256 литералов представляющих ASCII символы. Функциональный тип также имеет свои литералы, которые являются ничем иным, как безымянными функциями. Функциональные литералы называются лямбда-абстракциями (это название появилось из лямбда-исчисления Чёрча) или просто лямбдами. Например для получения списка кубов можно воспользоваться записью
l3 = map (\x -> x * x * x) [1, 2, 3, 4] -- результат - список [1, 8, 27, 64]
Функции, возвращающие другие функции, кажутся на первый взгляд несколько более специфичными. В самом деле, куда это можно применять? В функциональных языках они применяются повсеместно. Для примера определим два варианта функции сложения:
sum1 :: (Int, Int) -> Int sum1 (n, m) = n + msum2 :: Int -> Int -> Int sum2 n m = n + m
Вопреки первому впечатлению функция sum1 принимает всего один аргумент - пару чисел, и возвращает результат - их сумму. Функция sum2 (эквивалентная стандартному оператору (+)) - пример частично вычисляемой функции. Эта функция принимает в качестве аргумента число (типа Int) и возвращает функцию прибавляющую это число к своему аргументу. Зачем это нужно? Функция sum2 позволяет легко определять свои частные случаи. Например - функция инкремент, увеличивающая свой аргумент на 1 определяется как частный случай sum2 следующим образом:
inc :: Int -> Int inc = sum2 1
Функция map - тоже пример частично-вычисляемой функции. Эта функция принимает в качестве аргумента функцию и возвращает функцию принимающую список и возвращающую другой список. Это легко понять если взглянуть на пример:
-- sins принимает список действительных чисел (типа Double) -- и возвращает список их синусов sins :: [Double] -> [Double] sins = map sin
В императивных языках функция в процессе своего выполнения может читать и модифицировать значения глобальных переменных и осуществлять ввод/вывод. Поэтому, если мы вызовем одну и ту же функцию дважды с одним и тем же аргументом, может случиться так, что мы получим два различных результата. Такая функция называется функцией с побочными эффектами.
Описывать функции без побочных эффектов позволяет практически любой язык. Однако некоторые языки поощряют или даже требуют от функции побочных эффектов. Например во многих объектно-ориентированных языках в функцию передается скрытый параметр (чаще он называется this или self), который функция неявно модифицирует.
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путем декомпозиции и синтеза существующих. О ненужных объектах позаботится встроенный в язык сборщик мусора. Благодаря этому в чистых функциональных языках все функции свободны от побочных эффектов. Однако это не мешает этим языкам имитировать некоторые полезные императивные свойства, такие как исключения и изменяемые массивы. Для этого существуют специальные методы.
Каковы же преимущества чистых функциональных языков? Помимо упрощения анализа программ есть еще одно весомое преимущество - параллелизм. Раз все функции для вычислений используют только свои параметры, мы можем вычислять независимые функции в произвольном порядке или, скажем, параллельно, на результат вычислений это не повлияет. Причем параллелизм этот может быть организован не только на уровне компилятора с языка, но и на уровне архитектуры. В нескольких университетах уже разработаны и используются экспериментальные компьютеры, основанные на подобных архитектурах.
Далеко не все функциональные языки являются чистыми. В некоторых случаях побочные эффекты намного упрощают программирование. Однако преимущества чистых языков постепенно перевешивают, и наиболее современные функциональные языки являются, как правило, чистыми.
В традиционных языках программирования (например C++) вызов функции приводит к вычислению всех аргументов. Этот метод вызова функции называется вызов-по-значению (call-by-value). Если какой-либо аргумент не использовался в функции, то результат вычислений пропадает, следовательно вычисления были произведены впустую. В каком-то смысле противоположностью вызова-по-значению является вызов-по-необходимости (call-by-need). В этом случае аргумент вычисляется, только если он нужен для вычисления результата. Предположим, что мы хотим определить оператор конъюнкции (логическое и). На C мы можем прибегнуть к следующему определению (намеренно не используя оператор &&):
int and (int x, int y) { if (x) return y; else return 0; }Мы не сможем пользоваться этим оператором также как предопределенным оператором, потому что даже если x == FALSE, y все равно будет вычислен перед вызовом функции, так что простой оператор
if (and (y != 0.0, 1.0 / y > 2.0)) printf ("y = %g\n", y);в случае если y окажется равным 0.0 произойдет деление на 0, а это совсем не то, что нам нужно.
Если же мы определим подобную функцию на Haskell (который поддерживает отложенные вычисления), то все будет работать как должно:
-- возвращает True, если оба аргумента истинны and :: Bool -> Bool -> Bool and x y = cond (x, y, False) cond :: Bool -> a -> a cond True result _ = result cond False _ result = result
обратите внимание на функцию cond, которая представляет собой не что иное как аналог конструкции if-then-else в традиционных языках программирования. В языках использующих вызов-по-значению определить такую функцию невозможно, т.к. вне зависимости от логического условия будут вычислены оба других аргумента, хотя в каждом случае вычислять нужно только один.
Одним из самых полезных свойств отложенного вычисления является пожалуй возможность определения потенциально бесконечных структур данных, чаще всего - списков (lazy lists). Например, Haskell позволяет очень просто определить список всех простых чисел.
-- возвращает список делителей аргумента divisors :: Int -> [Int] divisors n = [m | m <- [1 .. n], n `mod` m == 0] -- предикат, возвращает True, если аргумент - простое число -- число является простым, если оно делится только на 1 и на себя isPrime :: Int -> Bool isPrime n = (divisors n) == [1, n] -- возвращает список всех простых чисел, получая его фильтрацией -- множества натуральных чисел предикатом isPrime primes :: [Int] primes = filter isPrime [1 ..]
Разумеется, это далеко не самый быстрый способ вычисления простых чисел, однако один из самых простых.
Если функциональный язык не поддерживает отложенные вычисления, то он называется строгим (strict). В самом деле, в таких языках порядок вычисления строго определен. В качестве примера строгих языков можно привести Scheme, Standard ML и Caml.
Языки использующие отложенные вычисления называются нестрогими (non-strict или lazy). Haskell - нестрогий язык, так же как, например, Gofer и Miranda. Нестрогие языки зачастую являются чистыми.
Зачастую строгие языки включают в себя средства поддержки некоторых полезных элементов, присущих нестрогим языкам, например бесконечных списков. В поставке Standard ML присутствует специальный модуль для поддержки отложенных вычислений. А Objective Caml помимо этого поддерживает дополнительное зарезервированное слово lazy и конструкцию для списков значений, вычисляемых по необходимости.
В этом разделе приведено краткое описание некоторых языков функционального программирования (очень немногих). Дополнительную информацию можно почерпнуть просмотрев сайты, перечисленные в следующем разделе.
Евгений Нонко, cm@iclub.nsu.ru или cm@liceum.secna.ru