Функциональное программирование. Основы (Файлы для подготовки к экзамену)

Функциональное программирование1ВведениеПрограммы на традиционных языках программирования, таких какСи, Паскаль, Java и т.п. состоят их последовательности модификацийзначений некоторого набора переменных, который называется состоянием. Если не рассматривать операции ввода-вывода, а также не учитыватьтого факта, что программа может работать непрерывно (т.е. без остановок, как в случае серверных программ), можно сделать следующуюабстракцию. До начала выполнения программы состояние имеет некоторое начальное значение σ0 , в котором представлены входные значенияпрограммы. После завершения программы состояние имеет новое значение σ 0 , включающее в себя то, что можно рассматривать как «результат»работы программы. Во время исполнения каждая команда изменяет состояние; следовательно, состояние проходит через некоторую конечнуюпоследовательность значений:σ = σ0 → σ1 → σ2 → · · · → σn = σ 0Состояние модифицируется с помощью команд присваивания, записываемых в виде v=E или v:=E, где v — переменная, а E — некотороевыражение.

Эти команды следуют одна за другой; операторы, такие какif и while, позволяют изменить порядок выполнения этих команд взависимости от текущего значения состояния. Такой стиль программирования называют императивным или процедурным.Функциональное программирование представляет парадигму, в корнеотличную от представленной выше модели. Функциональная программапредставляет собой некоторое выражение (в математическом смысле);выполнение программы означает вычисление значения этого выражения.1С учетом приведенных выше обозначений, считая что результат работы1Употребление термина «вычисление» не означает, что программа может оперировать только с числами; результатом вычисления могут оказаться строки, списки ивообще, любые допустимые в языке структуры данных.1императивной программы полностью и однозначно определен ее входом,можно сказать, что финальное состояние (или любое промежуточное)представляет собой некоторую функцию (в математическом смысле) отначального состояния, т.е.

σ 0 = f (σ). В функционально программировании используется именно эта точка зрения: программа представляетсобой выражение, соответствующее функции f . Функциональные языкипрограммирования поддерживают построение таких выражений, предоставляю широкий выбор соответствующих языковых конструкций.При сравнении функционального и императивного подхода к программированию можно заметить следующие свойства функциональныхпрограмм:• Функциональные программы не используют переменные в том смысле, в котором это слово употребляется в императивном программировании. В частности в функциональных программах не используется оператор присваивания.• Как следствие из предыдущего пункта, в функциональных программах нет циклов.• Выполнение последовательности команд в функциональной программе бессмысленно, поскольку одна команда не может повлиятьна выполнение следующей.• Функциональные программы используют функции гораздо болеезамысловатыми способами.

Функции можно передавать в другиефункции в качестве аргументов и возвращать в качестве результата, и даже в общем случае проводить вычисления, результатомкоторого будет функция.• Вместо циклов функциональные программы широко используют рекурсивные функции.На первый взгляд функциональный подход к программированию может показаться странным, непривычным и мало полезным, однако необходимо принять во внимание следующие соображения.Прежде всего, императивный стиль в программировании не являетсяжестко заданной необходимостью. Многие характеристики императивных языков программирования являются результатом абстрагированияот низкоуровневых деталей реализации компьютера, от машинных кодовк языкам ассемблера, а затем к языкам типа Фортрана и т.д. Однако нетпричин полагать, что такие языки отражают наиболее естественный для2человека способ сообщить машине о своих намерениях.

Возможно, более правилен подход, при котором языки программирования рождаютсякак абстрактные системы для записи алгоритмов, а затем происходит ихперевод на императивный язык компьютера.Далее, функциональный подход имеет ряд преимуществ перед императивным. Прежде всего, функциональные программы более непосредственно соответствуют математическим объектам, и следовательно, позволяют проводить строгие рассуждения. Установить значение императивной программы, т.е. той функции, вычисление которой она реализует,может оказаться довольно трудно. Напротив, значение функциональнойпрограммы может быть выведено практически непосредственно.Например, рассмотрим следующую программу на языке Haskell:factorial n = if n == 0 then 1 else n * factorial (n - 1)Практически сразу видно, что эта программа соответствует следующейчастичной функции:(n! n ≥ 0f (n) =⊥ n<0(Здесь символ ⊥ означает неопределенность функции, поскольку приотрицательных значениях аргумента программа не завершается.) Однакодля программы на языке Си это соответствие не очевидно:int f (int n){int x = 1;while (n > 0){x = x * n;n = n - 1;}return x;}Следует также сделать замечание относительно употребления термина «функция» в таких языках как Си, Java и т.п.

В математическомсмысле «функции» языка Си не являются функциями, поскольку:• Их значение может зависеть не только от аргументов;• Результатом их выполнения могут быть разнообразные побочныеэффекты (например, изменение значений глобальных переменных)3• Два вызова одной и той же функции с одними и теми же аргументами могут привести к различным результатам.Вместе с тем функции в функциональных программах действительноявляются функциями в том смысле, в котором это понимается в математике. Соответственно, те замечания, которые были сделаны выше, кним не применимы. Из этого следует, что вычисление любого выражения не может иметь никаких побочных эффектов, и значит, порядок вычисления его подвыражений не оказывает влияния на результат. Такимобразом, функциональные программы легко поддаются распараллеливанию, поскольку отдельные компоненты выражений могут вычислятьсяодновременно.2Основы лямбда-исчисленияПодобно тому, как теория машин Тьюринга является основой императивных языков программирования, лямбда-исчисление служит базисоми математическим «фундаментом», на котором основаны все функциональные языки программирования.Лямбда-исчисление было изобретено в начале 30-х годов логикомА.

Черчем, который надеялся использовать его в качестве формализмадля обоснования математики. Вскоре были обнаружены проблемы, делающие невозможным его использование в этом качестве (сейчас естьоснования полагать, что это не совсем верно) и лямбда-исчисление осталось как один из способов формализации понятия алгоритма.В настоящее время лямбда-исчисление является основной из такихформализаций, применяемой в исследованиях связанных с языками программирования. Связано это, вероятно, со следующими факторами:• Это единственная формализация, которая, хотя и с некоторыминеудобствами, действительно может быть непосредственно использована для написания программ.• Лямбда-исчисление дает простую и естественную модель для такихважных понятий, как рекурсия и вложенные среды.• Большинство конструкций традиционных языков программирования может быть более или менее непосредственно отображено вконструкции лямбда-исчисления.• Функциональные языки являются в основном удобной формой синтаксической записи для конструкций различных вариантов лямбдаисчисления.

Некоторые современные языки (Haskell, Clean) имеют4100% соответствие своей семантики с семантикой подразумеваемых конструкций лямбда-исчисления.В математике, когда необходимо говорить о какой-либо функции,принято давать этой функции некоторое имя и впоследствии использовать его, как, например, в следующем утверждении:Пусть f : R → R определяется следующим выражением:(0,x=0f (x) =22x sin(1/x ), x 6= 0Тогда f 0 (x) не интегрируема на интервале [0, 1].Многие языки программирования также допускают определение функций только с присваиванием им некоторых имен. Например, в языке Сифункция всегда должна иметь имя. Это кажется естественным, однакопоскольку в функциональном программировании функции используютсяповсеместно, такой подход может привести к серьезным затруднениям.Представьте себе, что мы должны всегда оперировать с арифметическими выражениями в подобном стиле:Пусть x = 2 и y = 4.

Тогда xx = y.Лямбда-нотация позволяет определять функции с той же легкостью,что и другие математические объекты. Лямбда-выражением будем называть конструкцию видаλx.Eгде E — некоторое выражение, возможно, использующее переменную x.Пример. λx.x2 представляет собой функцию, возводящую свой аргумент в квадрат.Использование лямбда-нотации позволяет четко разделить случаи,когда под выражением вида f (x) мы понимаем саму функцию f и ее значение в точке x.