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

Функциональное программирование — это ветвь программирования, при котором программирование ведется с помощью определения функций. Вы можете сказать, что любой программист давно уже программирует с помощью функций, а также процедур, циклов, модулей, объектов… Что же нового в функциональном программировании по сравнению с тем, что мы уже давно знаем?

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

Традиционное программирование родилось в 1940;х гг., когда велась разработка первых электронно-вычислительных машин (ЭВМ). Его основой послужила концепция Джона фон Неймана о хранимой программе автоматических вычислений по заданному алгоритму. Существенными чертами такой программы служили, во-первых, строгая последовательность в выполнении ее элементарных шагов и, во-вторых, возможность хранения и изменения программы наряду с данными для вычислений в общей с ними памяти. Таким образом, программа сама становилась объектом обработки вместе с арифметическими значениями, над которыми, собственно, и должны были производиться все действия.

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

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

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

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

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

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

Тем не менее оказалось, что опыт написания программ, не имеющих строго последовательной структуры, имеется. Почти одновременно с первым «традиционным» языком программирования — Фортраном — появился еще один совершенно непохожий на него язык программирования — Лисп, для которого последовательность выполнения отдельных частей написанной программы была несущественной. Ветвь программирования, начатая созданием Лиспа, понемногу развивалась с начала 1960;х гг. и привела к появлению целой плеяды очень своеобразных языков программирования, которые удовлетворяли всем требованиям, необходимым для исполнения программ несколькими параллельными процессорами. Во-первых, алгоритмы, записанные с помощью этих языков, допускают сравнительно простой анализ и формальные преобразования программ; во-вторых, отдельные части программ могут исполняться независимо друг от друга. Языки, обладающие такими замечательными свойствами, — это и есть языки функционального программирования.

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

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

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