Функциональное программирование
Функциональное программирование - это парадигма программирования, в которой выполнение программы представляет собой вычисление некоторого выражения, описывающего применение функций (в математическом понимании) ко входным данным.
В отличие от традиционного подхода к программированию (императивное программирование), где выполнение программы рассматривается как последовательная смена состояний в памяти компьютера (т.е. изменение значений переменных), в функциональном программировании нет понятия переменной и присваивания, функция не имеет явного внутреннего состояния, а оперирует только над входными данными. Из-за этого отсутствуют побочные эффекты, программа становится более простой в отладке, а также допускает более естественное распараллеливание на многоядерных процессорах.
Также, использование функций высшего порядка позволяет в большей степени использовать функциональную абстракцию, а автоматический вывод типов делает код существенно более компактным. Познакомившись поближе с функциональным программированием вы сами почувствуете, что функциональный подход заставляет вас больше думать и меньше писать.
Почему важно изучать функциональное программирование?
В последнее время программные системы становятся всё сложнее. Возникает потребность в параллельном программировании, которое при использовании императивного подхода является очень сложной задачей. Из-за этого интерес к функциональному программированию быстро растёт, и оно начинает всё больше использоваться в индустрии разработки ПО.
В частности, Майкрософт включила язык функционального программирования F# в состав Visual Studio 2010. Много функциональных возможностей вошло в язык C#, включая целое функциональное ядро в виде LINQ.
Какие продукты и языки использовать?
Функциональное программирование очень удобно изучать на базе Visual Studio и F#. Для этого можно установить Visual Studio 2010 Beta (куда уже входит F#), либо установить F# CTP поверх Visual Studio 2008. Подробности установки описаны тут.
С чего начать?
Введение в функциональное программирование на F# содержится в блоге Дмитрия Сошникова. Слайды его курса "Функциональное программирования на F#", прочитанного на ФИВТ МФТИ в 2008-09 уч. году, содержатся в репозитории учебных курсов Майкрософт.
Пример функциональной программы
Рассмотрим программу, которая будет строить множество Мандельброта - примерно такое. Подробнее про то, что такое множество Мандельброта и как его визуализировать на F#, можно прочитать в этой статье.
Для начала, опишем функцию f(z,c) = z2+c, определённую на комплексных числах:
let mandelf (c:Complex) (z:Complex) = z*z+c;;
let - это ключевое слово для определения имён. Эта функция имеет тип Complex -> Complex -> Complex, т.е. её можно применить к одному аргументу с, получив при этом функцию из Complex в Complex. Такое представление функций типично для функционального программирования, и называется каррированием.
Для определения того, принадлежит ли точка c множеству надо проверить, будет ли сходиться ряд, задаваемый функцией f = mandelf c, т.е. ряд f(0), f(f(0)) и т.д. Мы для простоты проверим, что f(20)(0) будут по модулю меньше 1. Для этого используем функцию rpt, так что rpt 20 f будет представлять собой 20-кратное применение функции f, а функция принадлежности запишется как
let ismandel c = Complex.Abs(rpt 20 (mandelf c) (Complex.zero))<1.0;;
При этом функция rpt может быть описана следующим образом:
let rec rpt n f =
if n=0 then (fun x->x)
else f >> (rpt (n-1) f);;
Здесь let rec означает рекурсивное определение, fun x-> ... - конструкция, позволяющая описать функциональную константу (или т.н. лямбда-выражение), >> - композицию функций. Определение означает, что для возведения в нулевую степень надо взять тождественную функцию, а для возведения в n-ю - надо посчитать композицию f и (n-1)-ой степени. Обратите внимание, что при описании функции мы нигде не указывали типов данных, а при этом правильный полиморфный тип функции rpt: int -> ('a -> 'a) -> ('a -> 'a) будет выведен автоматически.
После этого построения множества на консоли - дело техники! Более подробно о том, как построить множество в графическом окне WinForms - читайте в блоге.
let scale (x:float,y:float) (u,v) n = float(n-u)/float(v-u)*(y-x)+x
for i = 1 to 60 do
for j = 1 to 60 do
let lscale = scale (-1.2,1.2) (1,60) in
let t = complex (lscale j) (lscale i) in
System.Console.Write(if ismandel t then "*" else " ");
System.Console.WriteLine("")
Литература по функциональному программированию:
- R.Pickering, Foundations of F#, A-Press, 2008.
- D.Syme, A.Granicz, A.Cisternio. Expert F#. A-Press, 2008
- E. Chailloux, P. Manoury, B.Pagano. Разработка программ с помощью Objective Caml. O’Reilly. Русский перевод: http://shamil.free.fr/comp/ocaml/
- Филд А., Харрисон П. Функциональное программирование. – М.: Мир, 1993.
- J.Harrop, F# for Scientists, Wiley, 2008.