5Непроцедурные

языки

программирования

Глава 16

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

16.1. Почему именно функциональное программирование?

В разделе 1.8 мы упоминали, что и Черч и Тьюринг предложили модели для вычислений задолго до того, как появились первые компьютеры. Машины Тьюринга очень похожи на современные компьютеры тем, что они основаны на обновляемой памяти, т. е. наборе ячеек памяти, содержимое которых изме­няется при выполнении команд. Это также известно как архитектура фон Ней­мана.

Формулировка модели вычислений Черча (названная лямбда-исчислением) совершенно другая — она основана на математическом понятии функции. Эта формулировка полностью эквивалентна формулировке Тьюринга в смысле представления вычислений, которые могут быть точно описаны, но в качестве формализма, применяемого для вычислений на практике, функцио­нальный подход всегда был менее популярен. В языке Lisp, разработанном в 1956 г., для вычислений используется функциональный подход, подобный модели лямбда-исчисления, хотя многие его особенности поощряют стиль процедурного программирования.

В 1980-е годы дальнейшие исследования в области функционального про­граммирования привели к разработке языков на чисто теоретических основаниях, которые тем не менее могут быть эффективно реализованы. Ос­новное различие между современными функциональными языками програм­мирования и языком Lisp состоит в том, что в них типы и контроль соответст­вия типов являются базисными понятиями, поэтому значительно возросли и надежность, и эффективность программ.

Многие проблемы, с которыми мы сталкиваемся при написании надежной программы, возникают непосредственно из-за использования обновляемой памяти:

• Память может быть «затерта», потому что мы непосредственно изменяем ячейки памяти (используя индексы массива или указатели), а не просто вычисляем значения.

• Трудно создавать сложные программы из компонентов, потому что под­программы могут иметь побочные эффекты. Поэтому может оказаться, что даже осознать все последствия работы подпрограммы нельзя в отрыве от всей остальной программы.

Строгий контроль соответствия типов и методы инкапсуляции объектно-ориентированного программирования могут смягчить эти проблемы, но не могут устранить их полностью. При функциональном подходе обе эти про­блемы исчезают.

Дальнейшее обсуждение будет базироваться на популярном языке Standart ML, хотя эти понятия справедливы и для других языков.

16.2. Функции

Функции определяются в языке ML заданием равенства между именем функ­ции с формальным параметром и выражением:

fun even n = (n mod 2 = 0)

Различие состоит в том, что здесь нет никаких глобальных переменных, ника­кого присваивания, никаких указателей и, следовательно, никаких побочных эффектов. После того как функция была определена, она может быть применена (applied), и вычисление (evaluation) ее применения и дает результат:

even 4 = true

even 5 = false

С каждой функцией связан тип, точно так же, как в языках программирова­ния типы связаны с переменными. Тип функции even (четное) задается сле­дующим образом:

even: int -> bool

Это означает, что она отображает значение целочисленного типа в значение булева типа.

В языке ML выражения могут содержать условия:

fun min (x,y) = if x < у then x else у

Приведем пример вычисления при применении функции:

min (4,5) =

(if x < у then x else у) (4,5) =

if 4 < 5 then 4 else 5 =

if true then 4 else 5 =

4

Обратите внимание, что это не if-оператор, а условное выражение, аналогич­ное имеющемуся в языке С:

х< у?х:у

Какой тип у min? В функциональном программировании считается, что фун­кция имеет в точности один аргумент, если же вам требуется большее число аргументов, вы должны создать кортеж (двойной, тройной и т.д.), используя функцию декартова произведения. Таким образом, (4,5) имеет тип int x int, a функция min имеет тип:

min: (int x int) -> int

Вместо кортежей вы можете определить функцию, которая будет применять­ся к каждому аргументу по очереди:

fun min_c x у = if x < у then x else у

Это карризованная функция (curriedfunction, от имени математика Н.В. Сипу). Когда эта функция применяется к последовательности аргументов, при пер­вом обращении создается другая функция, которая затем применяется ко вто­рому аргументу.

Функция min_c берет один целочисленный аргумент и создает новую фун­кцию, также с одним аргументом:

min_c 4 = if 4 < у then 4 else у

Эта функция может затем применяться к другому одиночному аргументу:

min_c 4 5 =

(if 4 < у then 4 else у) 5 =

if 4 < 5 then 4 else 5 =

if true then 4 else 5 =

4

Карризованные функции могут использоваться в частичных вычислениях для определения новых функций:

fun min_4 = min_c 4

min_4 5 =

(if 4 < у then 4 else y) 5 =

if 4 < 5 then 4 else 5 =

if true then 4 else 5 =

4