Вступление
Я хочу вас познакомить с функциональным программированием и языком Haskell. Даже если вы не будете его использовать, знание поможет изменить стиль написания программ на любом языке в лучшую сторону.
О языках
Есть два класса языков программирования - императивные и декларативные. Программа на императивных языках представляет собой последовательность шагов, которые должен выполнить компьютер для получения результата. Программа на декларативном языке является описанием результата. При написании программы на языке любого класса необходимо описать, хотя бы для себя, что желаем получить от программы. Императивный подход также нуждается в том чтобы мы еще указали путь достижения результата, а это дополнительная сложность.
Декларативные языки делятся на логические и функциональные. В логических языках программа задается набором предикатов (утверждений), на их основе вычисляется результат. В функциональных - объектом вычисления является функция, то есть программа представляет собой функцию, зависящую от других функций. Наиболее популярны функциональные языки, логические применяются в узких областях. Все задачи, которые можно решить на императивном языке программирования, решаются и на функциональном.
В функциональных языках программирования есть особенность, которая больше всего удивляет программиста, переходящего на них. Это отсутствие переменных. У функций нет побочных эффектов, то есть они не могут изменять какие-либо внешние объекты, и имеют доступ только к своим аргументам. Благодаря этому ошибка, если она есть, ограничена рамками функции, где она находится и там же выявляется. Поэтому отладка занимает минимум времени.
В языках этого класса есть и другие преимущества такие, как высокая надежность и защищенность, масштабируемость, возможность горячей замены кода, короткий выразительный код и высокая степень параллелизма программы.
О многих функциональных языках можно сказать, что если программа компилируется, она почти наверняка работает правильно.
Перспективы
Ранее, на одноядерных машинах, параллельные программы требовались достаточно редко, поэтому императивное программирование было довольно эффективно. Теперь для того, чтобы использовать мощь современных процессоров, программа должна быть многопоточной. Она будет работать наиболее эффективно, если число потоков совпадает с числом доступных ядер. Императивные языки, даже поддерживающие параллельное программирование, заставляют разработчика заботиться о сохранности общих данных, разграничении доступа, бороться с клинчами и конкуренцией за ресурсы, используя для этого различные механизмы, вручную заниматься распределением на потоки нагрузки. Кроме того, сейчас нужно управлять количеством потоков в зависимости от количества ядер. Создать потоки "на вырост" нельзя, затраты на создание лишних потоков и переключение между ними будут слишком большими, к тому же рано или поздно количество ядер превысит количество потоков. Написание такого механизма вручную возможно, но оно требует большого труда и профессионализма разработчиков, к тому же этот подход чреват ошибками. Такая ситуация сейчас, когда все больше механической работы перекладывается на плечи компилятора - сборка мусора, контроль границ массива, выглядит архаизмом. Эффективно реализовать автоматическое распараллеливание в императивных языках с их побочными эффектами не представляется возможным. В функциональных языках оно уже реализовано - среда исполнения создает необходимое количество потоков, распределяет по ним функции, порядок исполнения которых не важен, и исполняет их параллельно.
Хотя программы на функциональных языках исполняются несколько медленнее, чем на императивных, их можно легко распараллеливать, поэтому на многоядерных процессорах они должны работать быстрее.
Что выбрать
Из современных функциональных языков программирования можно выделить Erlang, который имеет большую коллекцию библиотек и применяется в телекоммуникационной индустрии для создания систем реального времени, программы, написанные на нем, обладают высокой степенью параллелизма; Lisp - первый функциональный язык, он до сих пор используется в задачах искусственного интеллекта, и популярный среди энтузиастов Haskell.
Эти языки во многом похожи друг на друга. Нельзя однозначно сказать какой из них лучше, выбор языка зависит от поставленной цели. Для серьезного программирования на любом функциональном языке полезно знать комбинаторную логику и лямбда-исчисление, но это необязательно, так же как для программирования на императивных языках необязательно читать Кнута и Дейкстру. Понимая идею функционального программирования и освоив один язык, можно легко перейти на другой. Если у вас уже есть проект на императивном языке, в него легко можно интегрировать код почти на любом функциональном языке. В сети есть довольно много руководств и примеров по Haskell, у него простой синтаксис, поэтому остальная часть статьи будет именно о нем.
Haskell
Haskell был назван по имени Хаскелла Карри, разработавшего комбинаторную логику - упрощение лямбда-исчисления. Последний стандарт языка датируется 98 годом.
Для работы с Haskell нужен компилятор GHC или интерпретатор HUGS 98, который больше подходит для начинающих. У компилятора GHC есть интересная особенность - он может генерировать код на языке C.
Для начала немного о синтаксисе. Haskell, как и C, чувствителен к регистру символов, то есть идентификаторы SOMETHING, SoMeThInG и something имеют различные имена. Имена функций и переменных типа должны начинаться с маленькой буквы, классов и конструкторов данных с большой. При определении функции указывается ее имя и знак "=", дальше идет само определение. Тип указывается через "::". Файлы исходников имеют расширение *.hs.
Первый пример. Быстрая сортировка массива - сортировка, при которой берется первый элемент массива, остальные элементы упорядочиваются относительно него, затем рекурсивно этим же методом сортируются левая и правая части массива.
qSort::(Ord a)=>[a]->[a] qSort [] = [] qSort (x:xs) = qSort [y | y <- xs, y<x] ++ [x] ++ qSort [y | y <- xs, y>=x]
Хотя программа выглядит довольно непривычно, в ней легко разобраться, если вспомнить, что в декларативном программировании мы описываем только требуемый результат.
Первая строка необязательна, в ней определяется тип функции. Хотя Haskell обладает строгой системой типизации, тип может быть выведен транслятором автоматически. В строке записано, что qSort имеет тип функции, которая принимает список произвольного типа a (a - это переменная типа), причем тип a должен быть экземпляром класса Ord, где определены операторы сравнения величин (<) и (>=), а затем возвращает список того же типа. Списки заключаются в скобки [], между которыми расположены его элементы, разделяемые запятой. Если список пустой, между скобками ничего не должно быть. Как видно из определения, функция qSort может принимать значения любого типа, где определены операторы сравнения, то есть Haskell поддерживает полиморфизм. В языке Haskell классы похожи на абстрактные классы С++ или интерфейсы Java. Во второй строке идет определение функции qSort для того случая, если ей передали пустой список [] - она возвращает также пустой список. Это необходимо для прекращения рекурсии.
Если же ей передали непустой список, вызовется реализация функции qSort из третьей строки. Список можно представить как кортеж из двух элементов, состоящий из первого элемента списка и его хвоста. Кортеж это составной тип, в котором может храниться фиксированное число разнородных данных. Кортежи заключаются в скобки (). Он близок к структуре в C. Функция возвратит отсортированный список, состоящий из трех объединенных операцией (++) подсписков - отсортированного списка, состоящего из элементов, взятых из xs и меньших x, списка из одного элемента x и списка из отсортированных элементов больших или равных x. Нужно заметить, вместо x и xs могут быть любые другие имена. При создании списков для передачи рекурсивно вызываемым функциям qSort используются определители списка. Рассмотрим первый определитель [y | y <- xs, y<x] Это выражение можно прочитать как список всех y, взятых из xs, для которых выполняется условие y<x. Могут быть более сложные определители списков, такие, например, как [a+b-1 | a<-[1..5], b<-[a,a+1,3], a==1, f b] где f - функция, возвращающая значение типа Bool. Для того чтобы лучше понять, как работать с определителями списков стоит поэкспериментировать с ними на компьютере. Вторую и третью строки можно поменять местами, результат от этого не изменится.
В Haskell нет побочных эффектов, поэтому функция qSort не изменяет переданный ей массив, а создает новый. Хотя при каждом последующем вызове qSort выделяется память для ее результата, сборщик мусора вскоре ее освобождает и ресурсы расходуются экономно.
Теперь сохраняем программу в файле sort.hs и открываем его в HUGS 98. Если все сделано правильно, появится приглашение интерпретатора Main>.
Вызываем функцию и передаем ей параметр через пробел без скобок и видим результат.
Main> qSort [2,1,3] [1,2,3] Main> qSort [9,8..1] [1,2,3,4,5,6,7,8,9] Main> qSort ['d','a','c','b'] "abcd"
Если вас заинтересовал Haskell, все необходимое можно найти на сайтах www.haskell.org и www.haskell.ru. Удачи!