Общеизвестной методогией программирования является императивная (предписывающая) методология, в которой программа представляет собой заданную программистом цепочку действий, выполняемых в определенном порядке. Иными словами, в этой парадигме мы записываем на языке программирования строго детерминированный алгоритм ее решения. Класс императивных языков программирования охватывает как классические процедурные, так и современные объектно-ориентированные языки.
Однако, наряду с императивной существует и иная методогия — декларативная (описательная). В декларативной парадигме программа представляет собой описание задачи, а не способ ее решения. Наиболее развитыми из декларативных подходов являются функциональный и логический. Они различаются способом формального описания задачи: функциональная программа представляет собой список определений функций, а логическая — список известных фактов и логических правил вывода новых фактов.
В этих лекциях мы будем рассматривать функциональную методогию программирования.
Императивное программирование основано на модели абстрактного вычислителя, сформулированной Аланом Тьюрингом и уточненной Джоном фон Нейманом. Теоретические основы функционального программирования (далее ФП) были сформулированы в работах по математической логике, в первую очередь:
В начале 50-х годов прошлого века Джон МакКарти разработал первый функциональный язык Lisp, который в виде различных диалектов используется по сей день. С сегодняшней точки зрения Lisp имеет ряд серьезных недостатков, прежде всего, отсутствие типизации данных. Поэтому в дальнейшем был разработан довольно широкий круг новых функциональных языков (назовем, например, языки ML, Scheme, Miranda, Clean и Objective Caml). К концу 80-х годов сложилась ситуация, в которой практическая каждая группа исследователей, занимавшаяся ФП, использовала свой собственный язык или диалект.
Для преодоления такой раздробленности несколько ведущих специалистов в области ФП сформировали группу по созданию универсального функционального языка, которым стал язык Haskell, названный по имени Хаскелла Карри (как мы увидим дальше, в языке увековечены не только его имя, но фамилия).
Первая версия языка Haskell появилась в начале 90-х годов. В настоящее время действующим стандартом является Haskell-98. По заявлению разработчиков, этот стандарт пересматриваться не будет; все предлагаемые расширения и изменения языка будут учтены при разработке новой версии Haskell 2.
В литературе, посвященной ФП, описание его особенностей и преимуществ очень часто формулируется как набор негативных формулировок: в ФП нет присваиваний, побочных эффектов, потоков управления и т. п. Из такого описания невольно складывается впечатление, что функциональные программисты произошли от Рахметова и добровольно предпочитают спать на гвоздях, а не на перине.
Обычно за подобным списком отрицаний следует утверждение, что функциональные программы на порядок короче и надежнее, чем императивные. Это уже повергает читателя в полное недоумение: как, выбросив из языка программирования массу возможностей, можно получить более короткий код?
Мы попытаемся в этих лекциях проследить, в первую очередь, те особенности, которые делают ФП действительно мощной и надежной средой для разработки серьезных приложений. Забегая вперед, скажем, что мы выделяем три таких особенности: наличие функционалов (т. е. функций, аргументами которых являются другие функции), ленивые (отложенные) вычисления и развитый полиморфизм типов. Эта мысль не оригинальна, см., например, статью Джона Хьюза.
Языку Haskell посвящен сайт www.haskell.org, на котором представлены бесплатные программные средства, разработанные международным сообществом специалистов по ФП. Оптимальным средством для освоения языка является интерпретатор Hugs98 (все приведенные ниже примеры проверялись именно в нем). Для создания серьезных приложений можно рекомендовать компилятор GHC (Glasgow Haskell Compiler) Оба эти средства существуют и для Unix-систем, и для Windows.