Сильные стороны функционального программирования

Джон Хьюз^*

Перевод И.А. Дехтяренко

Можно скачать текст статьи в формате html (20 кб)

Резюме

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

1. Введение

Эта статья является попыткой демонстрации  "реальному миру" того, что функциональное программирование жизненно важно и призвана помочь программистам полностью использовать его преимущества. В ней также показывается, что это за преимущества.

Функциональное программирование называется так, потому что программа полностью состоит из функций. Сама программа тоже является функцией, которая получает исходные данные в качестве аргумента, а выходные данные выдаёт как результат. Как правило, основная функция определена в терминах других функций, которые в свою очередь определены в терминах еще большего количества функций, вплоть до функций - примитивов языка на самом нижнем уровне. Эти функции очень похожи на обычные математические функции, и в этой статье будут определены обычными уравнениями.  Для демонстрации используется язык программирования Haskell ^** , но примеры должны быть понятны и без знания функциональных языков.

Особенности и преимущества функционального программирования обычно излагаются следующим образом. Функциональные программы не содержат операторов присваивания, а  переменные, получив однажды значение, никогда не изменяются. Более того, функциональные программы вообще не имеют побочных эффектов. Обращение к функции не вызывает иного эффекта кроме вычисления  результата. Это устраняет главный источник ошибок, и делает порядок выполнения функций несущественным: так как побочные эффекты не могут изменять значение выражения, оно может быть вычислено в любое время. Программист освобождается от бремени описания потока управления. Поскольку  выражения могут быть вычислены в любое время, можно свободно заменять переменные их значениями и наоборот, то есть программы "прозрачны по ссылкам". Эта прозрачность ссылок делает функциональные программы более удобными для математической обработки, по сравнению с общепринятыми аналогами.

Приведенный список "преимуществ" очень хорош, но ни для кого не является сюрпризом, что функциональное программироние не воспринимается  всерьез. Он много говорит о том, чего нет в функциональном программировании (нет присваивания, побочных эффектов, потоков управления) но ничего о том, чем же оно является. Функциональный программист смотрится как средневековый монах, отвергающий удовольствия жизни в надежде, что это сделает его добродетельным. Для тех, кто заинтересован в материальных выгодах, эти "преимущества" не очень убедительны.

Сторонники функционального стиля утверждают, что имеются большие материальные выгоды, и что функциональный программист - на порядок более производителен, чем его обычный (императивный) коллега, потому что функциональные программы на порядок короче. Но почему же такое возможно?  Единственная маловероятная причина, которую можно предположить на основе анализа этих "преимуществ"  заключается в том, что обычные программы на 90% состоят из операторов присваивания, а в функциональных программах они могут быть опущены! Но это смешно. Если бы исключение оператора присваивания принесло такие огромные выгоды, то программисты на Фортране  сделали бы это лет двадцать назад^***. Здравый смысл подсказывает, что невозможно сделать язык более мощным, выбрасывая из него некоторые свойства, независимо от того, насколько плохими они могут быть.

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

Ясно, что такая характеристика функционального программирования неадекватна. Мы должны найти, что-то вместо неё - то, что не только объяснит мощь функционального программирования, но и  показывает, к чему программист должен стремиться.

2. Аналогия со структурным программированием.

Полезно провести аналогию между функциональным и структурным программированием. Когда-то характеристики и преимущества структурного программирования излагались  более или менее следующим образом.  Структурные программы не содержат операторов goto. Блоки в структурной программе не имеют несколько входов или выходов.  Структурные программы лучше поддаются математической обработке, чем их неструктурные аналоги. Эти "преимущества" структурного программирования очень похожи по духу на "преимущества"  обсужденные ранее. Они  по существу малозначимы, и чаще всего вели ко многим бесплодным спорам относительно "необходимости goto" и всего остального.

Ясно, что эти свойства структурных программ, хоть и полезны, но не отражают существа вопроса. Наиболее важное различие между структурным и неструктурным подходом в том, что структурные программы, разработаны модульным способом. Модульность ведет к повышению производительности при создании проекта. Прежде всего, маленькие модули могут быть закодированы быстро и легко. Во-вторых, универсальные модули могут многократно использоваться, что приводит к более быстрому построению последующих программ. В-третьих, модули программы могут быть проверены независимо, что помогает уменьшить время, потраченное на отладку.

Отсутствие goto и т.п. немногим помогает этому. Оно помогает "программированию в малом", в то время как модульное проектирование помогает "программированию в большом". Таким образом, можно наслаждаться выгодами от структурного программирования на Фортране или ассемблере, даже если это требует больших усилий.

Сейчас общеизвестно, что модульная разработка  - ключ к успешному программированию, и языки типа Modula-2 [Wir82] , Ada [oD80] и Standard ML [MTH90] включают конструкции, предназначенные для улучшения модульности. Однако имеется очень важный момент, который часто опускают. При создании модульной программы, чтобы решить задачу, мы делим ее на подзадачи, затем решаем подзадачи и объединяем решения. Методы,  которыми можно разделить первоначальную задачу, зависят непосредственно от методов,  которыми можно склеивать решения вместе. Поэтому, чтобы увеличить способность к концептуальному разбиению задачи на модули, нужно обеспечить новые виды клея в языке программирования. Сложные правила формирования контекста, и условия, обеспечивающие раздельную трансляцию, помогают только как дополнительные канцелярские мелочи; они не предлагают никаких концептуально новых инструментальных средств для решения задач декомпозиции.

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

Теперь вернёмся  к функциональному программированию. Мы приведём доводы в пользу того, что функциональные языки предоставляют два новых, очень важных вида клея. Мы дадим примеры программ, которые можно разбить на модули новыми способами, и таким образом очень упростить.

Причина мощи функционального программирования в том, что оно улучшает модульность. Цель, к которой функциональные программисты должны стремиться: меньшие по размеру, более простые и универсальные модули, склеенные  новыми клеями, которые мы опишем ниже.

3. Склеивание функций

Первый из двух новых видов клея позволяет склеивать простые функции в более сложные. Это можно проиллюстрировать на примере простой задачи обработки списков: сложении его элементов. Мы определяем списки следующим образом:

    data [x] = [] | x : [x]

Это означает, что список иксов - это либо пустой список [], либо конструкция из элемента X и другого списка иксов. X:Xs, представляет список, первый элемент которого - X, а последующие - элементы другого списка Xs.

X здесь может замещать любой тип - например, если X "целочисленный", то определение говорит, что список целых чисел является либо пустым, либо составлен из целого числа и другого списка целых чисел. Следуя обычным обозначениям, мы записываем списки, просто перечисляя их элементы в квадратных скобках. Например

[1] означает 1:[]

[1,2,3] означает 1:2:3:[]

Элементы списка могут быть просуммированы рекурсивной функцией sum. Она должна быть определена для двух видов параметра: пустого списка и конструктора. Так как сумма пустого множества чисел равна нулю, мы определяем

    
    sum [] = 0

А так как сумма может быть рассчитана сложением первого элемента списка с суммой  остальных, мы можем определить

    sum num:list = num + sum list

Исследуя это определение, мы видим, что только выделенные части ("0" и "+" ) определяют вычисление суммы. Это значит, что вычисление суммы может быть "модуляризовано" склеиванием общего рекурсивного образца и выделенных частей. Этот рекурсивный образец традиционно называется сверткой (reduce), так что сумма может быть выражена как

    sum = reduce (+) 0

Определение свертки, может быть получено параметризацией определения sum,

    reduce f x [] = x
    reduce f x (a:l) = f a (reduce f x) l

Здесь мы выделили цепочку reduce f x, чтобы прояснить, что она заменяет sum. Функция от 3-х аргументов типа reduce, применяемая только к  2-м, считается функцией 1-го параметра. И вообще, функция от n параметров, применённая к m (m < n), будет функцией n-m  оставшихся аргументов.  Мы будем следовать этим соглашением и в дальнейшем.

"Модуляризовав", таким образом sum, мы можем пожинать плоды,  многократного использования. Наиболее интересная часть функции - это reduce, которая может использоваться, и для функции умножения элементов списка:

    product = reduce (*)1

Или, чтобы проверить, является ли какая-нибудь переменная из списка булевых истинной:

    anytrue = reduce (||) False

Или, что они все истинны:

    alltrue = reduce (&&) True

Один из способов понять использование reduce f a в качестве функции, заключается в мысленной замене всех вхождений ":" в списке на f, и всех вхождений "[]" на a. Например, список 1 : 2 : 3 : []

reduce (+) 0 преобразует в 1 + 2 + 3 + 0 , а

reduce (*) 1 преобразует в 1* 2 * 3 * 1

Теперь очевидно что (reduce (:)[]) просто копирует список. Так как список можно добавить к другому, помещая его элементы спереди,  находим:

    append a b = reduce (:) b a

Функцию для удвоения всех элементов списка можно описать так

    doubleall = reduce doubleandcons []
    doubleandcons num list = 2*num : list

В свою очередь, doubleandcons может быть модуляризована дальше сначала в

    doubleandcons = fandcons double
    double n = 2*n
    fandcons f el list = (f el) : list

и затем

    fandcons f = (:). f

где "." - стандартный оператор функциональной композиции,  определенный как

    (f . g) h = f (g h)

Можно убедиться, что новое определение fandcons правильно,  применяя его к некоторым параметрам:

    fandcons f el list = (f el): list

заключительная  версия

    doubleall = reduce ((:) . double) []

Дальнейшей модуляризацией мы достигаем

    doubleall = map double

    map f = reduce ((:). f) []

Функция map применяет любую функцию f ко всем элементам списка - пример ещё одной общеполезной функции. Мы можем даже написать функцию, для сложения всех элементов матрицы, представленной как список списков.

    summatrix = sum . map sum

Функция summatrix использует (map sum), чтобы просуммировать все строки, затем крайняя левая sum складывает результаты, и выдаёт сумму целой матрицы.

Этих примеров должно быть достаточно, чтобы убедить читателя, что модуляризация может проходить длительный путь. Представляя простую функцию (sum) в виде комбинаций "функций высшего порядка" и некоторых простых параметров, мы получили фрагмент (reduce), который без больших усилий может использоваться для программирования многих других функций обработки списков.

Мы не обязаны ограничиваться только функциями над списками. В качестве другого примера, рассмотрим тип данных "упорядоченное дерево", определенный как

    data Treeof x = Node x [Treeof x]

Это определение говорит, что дерево x-ов - узел, с меткой, которая является x-ом, и список поддеревьев, которые являются также деревьями x-ов. Вместо того, чтобы рассматривать пример и абстрагироваться от него к функции более высокого порядка, мы будем непосредственно строить функцию redtree аналогичную reduce. Напомним, что reduce, получала два параметра, один чтобы заменить ":", и другой, чтобы заменить "[]". Так как деревья формируются с использованием "Node", ":" и "[]", redtree должна получить три параметра, чтобы заменить каждый из них. Деревья и списки имеют различные типы, поэтому мы должны определить две функции, по одной для каждого типа. Мы определяем:

    redtree f g a (Node x subtrees) = f x (redtree' f g a subtrees)
    redtree' f g a (x:rest) = g (redtree f g a x) (redtree' f g a rest)
    redtree' f g a [] = a

Склеивая redtree с другими функциями можно определить много интересных функций. Например, можно сложить все элементы в дереве чисел используя

    sumtree = redtree (+)(+)0

    labels = redtree (:) append []

Наконец, можно определять функцию, аналогичную map, которая применяет функцию f ко всем элементам  дерева:

    maptree f = redtree (Node . f) (:) []

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

4. Склеивание программ

Другой новый вид клея, который используют функциональные языки, допускает склеивать целые программы. Напомним, что функциональная программа - просто функция из входных данных в её выходные данные. Если F и G - такие программы, то (G . F) - программа которая, вычисляет G (F input). Программа F вычисляет свой вывод, который используется как ввод, для программы G. Традиционно,это можно осуществить, сохраняя вывод F во временный файл. Проблема состоит в том, что временный файл может занять так много памяти, что непрактично склеивать программы подобным образом.

Функциональные языки обеспечивают решение этой проблемы. Две программы F и G выполняются вместе строго синхронно. F запускается только тогда, когда G пытается прочитать некоторый ввод, и выполняется ровно столько, чтобы предоставить данные, который пытается читать G. После этого F приостанавливается, и выполняется G, до тех пор, пока вновь не попытается прочитать следующую группу входных данных. Если G заканчивается, не прочитав весь вывод F, то F прерывается. F может даже быть не завершаемой программой, создающей бесконечный вывод, так как она будет остановлена, как только завершится G. Это позволяет отделить условия завершения от тела цикла, что является мощным средство модуляризации.

Этот метод называется "ленивыми вычислениями" так как F выполняется настолько редко, насколько это возможно. Он позволяет осуществить модуляризацию программы как генератора, который создает большое количество возможных ответов, и селектора, который выбирает подходящие. Некоторые другие системы позволяют программам выполнятся вместе подобным способом, но только функциональные языки использует ленивые вычисления однородно при каждом обращении к функции, позволяя модуляризовать таким образом любую часть программы. Ленивые вычисления, возможно, наиболее мощный инструмент для модуляризации в наборе функционального программиста.

4.1. Вычисление квадратного корня методом Ньютона - Рафсона

Мы проиллюстрируем мощь ленивых вычислений,  программируя некоторые численные алгоритмы. Прежде всего, рассмотрим алгоритм Ньютона - Рафсона для вычисления квадратного корня. Этот алгоритм вычисляет квадратный корень числа z, начиная с начального приближения a0. Он уточняет это значение на каждом последующем шаге, используя правило:

Если приближения сходятся к некоторому пределу a, то a = (a + z/a) / 2 , то есть a*a = z или a = squareroot(z)

Фактически сведение к пределу проходит быстро. Программа проводит проверку на точность (eps) и останавливается, когда два последовательных приближения отличаются меньше чем на eps. При императивном подходе алгоритм обычно программируется следующим образом:

  x = a0;
  do{
    y = x;
    x = (x + z/x) / 2;
  } while (abs(x-y) < eps)
  // теперь x = квадратному корню из z

Так как алгоритм Ньютона - Рафсона вычисляет последовательность приближений, естественно представить это в программе явно списком приближений. Каждое приближение получено из предыдущего функцией

    next z x = (x + z/x) / 2

То есть (next z) - функция, отображающая каждое приближение в следующее. Обозначим эту функцию f, тогда последовательность приближений будет: [a0, f a0, f(f a0), f(f(f a0)),...] . Мы можем определить функцию, вычисляющую такую последовательность:

    iterate f x = x : iterate f (f x)

    iterate (next z) a0

Здесь iterate - пример функции с "бесконечным" выводом - но это не проблема, потому что фактически будет вычислено не больше приближений, чем требуется остальным частям программы. Бесконечность - только потенциальная: это означает, что любое число приближений можно вычислить, если потребуется, iterate сама по себе не содержит никаких ограничений.

Остаток программы - функция within, которая берет допуск и список приближений и, просматривая список, ищет два последовательных приближения, отличающихся не более чем на данный допуск.

    within eps (a:b:rest) =
        if abs(a-b) <= eps
            then b
            else within eps (b : rest)

    sqrt a0 eps z = within eps (iterate (next z) a0)

Теперь, когда мы имеем части программы поиска квадратного корня, мы можем попробовать объединить их различными способами. Одна из модификаций, которую мы могли бы пожелать, заключается в использовании относительной погрешности вместо абсолютной. Она  больше подходит как для очень малых чисел (когда различие между последовательными приближениями маленькое), так и для очень больших (при округлении ошибки могут быть намного большими, чем допуск). Необходимо определить только замену для within:

    relative eps (a:b:rest) =
        if abs(a-b) <= eps*abs(b)
            then b
            else relative eps (b:rest)

    relativesqrt a0 eps z = relative eps (iterate (next z) a0)

Нет необходимости переписывать часть, которая генерирует приближения.

4.2. Численное дифференцирование

Мы повторно использовали iterate при генерации последовательности приближений в вычислениях квадратного корня. Конечно же, можно многократно использовать within и relative в любых численных алгоритмах, которые генерирует последовательность приближений. Сделаем это в алгоритме численного дифференцирования.

Производная функции в точке - наклон графика функции в этой точке. Её можно легко найти,  определив значение функции в данной точке и в другой точке поблизости и вычислив наклон прямой линии между двумя точками. Предполагается, что, если две точки находятся достаточно близко, то график функции между ними не будет слишком изгибаться. Это дает определение:

    easydiff f x h = (f(x+h)-f x) / h

Чтобы получить хорошее приближение,  значение h должно быть очень маленьким. К сожалению, если h слишком маленькое, то два значения f (x+h) и f (x) - очень близки друг другу, так что ошибка округления при вычитании может заглушать результат. Как правильно выбрать значение h? Одно решение этой дилеммы - вычислять последовательность приближений со всё меньшими и меньшими значениями h, начиная с разумно большого. Такая последовательность должна сходиться к значению производной, но станет безнадежно неточной в конечном счете из-за ошибок округления.

Если (within eps) используется, чтобы выбрать первое приближение, которое достаточно точно, то риск ошибки округления, воздействующей на результат можно уменьшить. Мы нуждаемся в функции, вычисляющей последовательность:

    differentiate h0 f x = map (easydiff f x) (iterate halve h0)
    halve x = x/2

h0 - начальное значение h, последовательные значения получены повторным делением на два. С помощью этой функции, производная в любой точке может быть вычислена так:

    within eps (differentiate h0 f x)

Но это решение не вполне удовлетворительно, потому что последовательность приближений сходится довольно медленно. Немного простой математики может нам помочь. Элементы последовательности могут быть выражены как

Можно показать теоретически, что член погрешности грубо пропорционален степени h. Пусть A - правильный ответ и B*hⁿ - ошибка. Так как каждое последующее приближение вычислено, используя значение h  вдвое меньшее того, что, было, использовало для предыдущего, любые два последовательных приближения могут быть выражены как a_i = A + B*hⁿ и a_i+1 = A + B*hⁿ/2ⁿ. Теперь член погрешности может быть устранен. /p>

Конечно, ошибка определяется степенью h только при грубом приближении. Поэтому наше заключение также приблизительно, но все равно, это намного лучшее приближение. Подобное усовершенствование может применяться ко всем последовательным парам приближений, с помощью функции

    elimerror n (a:b:rest) = (b*2^n - a)/(2^n-1) : elimerror n (b:rest)

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

Но одна проблема остается. Прежде, чем мы можем использовать elimerror - мы должны знать значение n. Его трудно предсказать, но можно измерить. Нетрудно показать, что следующая оценка правильна, но не будем приводить доказательства.

    order a:b:c:rest = round log2 (a-c)/(b-c) - 1

Теперь можно определить общую функцию, улучшающую последовательность приближений:

    improve s = elimerror (order s) s

Производную функции f можно вычислить более эффективно, используя improve следующим образом

    within eps (improve (differentiate h0 f x))

Отметим что improve подходит только для последовательностей приближений, которые вычислены с использованием параметра h, делимого на два при каждом шаге. Однако, если она применена к такой последовательности, её результат - такая же последовательность! Это означает, что  последовательность приближений может быть улучшена больше чем однажды. Каждый раз погрешность устраняется, и последовательности сходятся всё быстрее и быстрее. Производную можно вычислить очень эффективно используя:

    within eps (improve (improve (improve (differentiate h0 f x))))

В терминах вычислительной математики это, вероятно, будет методом четвертого порядка, и дает точный результат очень быстро. Можно даже определить

    super s = map second (iterate improve s)
    second (a:b:rest) = b

Здесь super использует (iterate improve), чтобы получить последовательность все более улучшенных последовательностей приближений, и строит новую последовательность приближений, беря второе приближение  каждой из улучшенных последовательностей (оказывается, что лучше всего брать второе - оно более точно чем первое и не требует дополнительных вычислений).  Этот алгоритм действительно очень сложный - он использует всё лучший и лучший численный метод, по мере того как всё больше приближений вычислено. Производные можно очень эффективно вычислять программой:

    within eps (super (differentiate h0 f x))

Вероятно, это похоже на использование кувалды, чтобы расколоть орех, но смысл в том, что даже столь сложный алгоритм как super легко выражается путём модуляризации с использованием ленивых вычислений.

4.3. Численное интегрирование.

Последний пример, который мы обсудим в этом разделе - численное интегрирование. Задача может быть поставлена очень просто: для вещественной функции f одного вещественного аргумента, и двух конечных точек a и b, вычислить площадь под кривой описываемой f  между конечными точками. Самый простой способ - предположить, что f - почти прямая линия, тогда область была бы:

    easyintegrate f a b = (f a + f b)*(b-a)/2

К сожалению, эта оценка, вероятно,  будет очень неточна, если a и b не близки друг к другу. Лучшую оценку можно получить,  разделив интервал (a, b) на два, вычислив площадь для каждой половине, и сложив результаты. Мы можем определять последовательность всё лучших и лучших приближений к значению интеграла, используя формулу для первого приближения, и затем, складывая приближения к интегралам на каждой половине вычислять другие. Эта последовательность вычисляется функцией

    integrate f a b =
        easyintegrate f a b :
        map addpair (zip (integrate f a mid) (integrate f mid b))
        where mid = (a+b)/2 
              addpair (a,b) = a+b

zip - еще одна стандартная функция обработки списков. Она получает  два списка и возвращает список пар,  состоящих из соответствующих элементов этих списков. Таким образом, первая пара состоит из первого элемента первого списка и первого элемента второго, и так далее. zip может быть определена:

    zip (a:s) (b:t) = (a,b):(zip s t)

В integrate zip вычисляет список пар соответствующих приближений к интегралам на этих двух подынтервалах, и map addpair складывает элементы пары вместе, выдавая список приближений к интегралу.  Эта версия интегрирует, довольно неэффективно, потому что непрерывно перевычисляет значения f. Как уже сказано, easyintegrate вычисляет значения f в точках a и b, а рекурсивные обращения, перевычисляют каждое из них. К тому же и  (f mid) вычисляется при каждом рекурсивном обращении. Поэтому следует вторая версия, которая никогда не перевычисляет значение f.

    integrate f a b = integ f a b (f a) (f b)
    integ f a b fa fb =
        (fa+fb)*(b-a)/2 :
        map addpair (zip (integ f a m fa fm)(integ f m b fm fb))
        where m = (a+b)/2; fm = f m

integrate вычисляет бесконечный список лучших и лучших приближений к интегралу, также как differentiate, в предыдущем разделе. Можно поэтому написать программу, которая интегрирует до любой требуемой точности, как в:

    within eps (integrate f a b)
    relative eps (integrate f a b)

Этот алгоритм интегрирования страдает от того же самого недостатка, что и первый алгоритм дифференцирования - он сходится довольно медленно. И так же он может быть улучшен. Первое приближение в последовательности вычисленный (easyintegrate) использует только две точки, с расстоянием между ними b-a. Второе приближение использует середину отрезка, так что расстояние между соседними точками - (b-a)/2. Третье приближение использует этот метод на каждой половине интервала, так что расстояние между соседними точками становится (b-a)/4. Ясно, что расстояние между соседними точками делится на два при каждом следующем приближении и наша последовательность - кандидат на усовершенствование, используя "улучшающую" функцию (improve) определенную в предыдущем разделе. Поэтому мы можем теперь создавать быстро сходящиеся последовательности приближений к интегралам, например

    super (integrate sin 0 4)
    improve (integrate f 0 1) where f x = 1 /(1+x*x)

Вторая последовательность - метод восьмого порядка для вычисления pi/4. Второе приближение, которое требует только пяти вычислений f, выдаёт результат с точностью до пятого знака.

В этом разделе мы запрограммировали  несколько числовых алгоритмов. Благодаря ленивым вычислениям  мы смогли разбить их на модули новыми способами, получая общеполезные функции типа  within, relative, improve.  Объединяя эти части различными способами, мы очень легко и просто запрограммировали несколько весьма хороших числовых алгоритмов.

5. Пример из искусственного интеллекта

Мы утверждали, что функциональные языки мощны, прежде всего, потому что они обеспечивают два новых клея: функции более высокого порядка и ленивые вычисления. Возьмём пример из "искусственного интеллекта" и покажем, что его очень просто можно запрограммировать, используя эти два вида клея.

Пример, который мы выбираем - "альфа-бета эвристика", алгоритм для оценки позиции в которой находится игрок. Алгоритм работает просмотривая возможные ходы, чтобы видеть, как игра могла бы развиваться, но избегает анализа невыгодных вариантов.

Пусть позиции в игре представлены объектами типа position.  Это тип изменяется от игры к игре, и мы не предполагаем ничего о нём. Но должен существовать некоторый метод узнать, какие ходы могут быть сделаны в данной позиции. Предположим, что имеется функция

    moves: Position -> [Position]

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

Прежде всего надо сформировать дерево игры. Это дерево, в котором узлы помечены позициями, так что сыновья узла помечены позициями, которые могут быть достигнуты в один ход из этого узла. То есть если узел помечен позицией p, то его сыновья помечены позициями  (moves p). Дерево может быть бесконечным. Игровые деревья подобны деревьям, которые мы обсуждали в разделе 2 - каждый узел имеет метку (т.е. позицию) и список подузлов. Поэтому мы можем использовать для их представления тот же самый тип данных.

Дерево игры формируется повторными применениями moves. Начиная с корневой позиции, moves используются, чтобы генерировать метки для поддеревьев корня. Затем moves используются снова, чтобы генерировать поддеревья поддеревьев и так далее. Этот рекурсивный образец может быть выражен функцией высшего порядка

    reptree f a = Node a (map (reptree f) (f a))

Используя эту функцию можно определить другую функцию, которая создает игровое дерево, начиная со  специфической позиции

    gametree p = reptree moves p

Функция высшего порядка, используемая здесь (reptree) аналогична функции iterate создававшей бесконечные списки в предыдущем разделе.

Алгоритм  просматривает дерево игры, начиная с данной позиции, пытаясь определить насколько благоприятно будет развиваться игра. Но чтобы сделать это, он должен иметь возможность делать грубую оценку  значения позиции без просмотра вперед. Эта "статическая оценка" должна использоваться на границах просмотра вперёд. Результат статической оценки является мерой обещания позиции с точки зрения компьютера (предполагается, что компьютер играет против человека). Чем больше результат, тем лучше позиция для компьютера. В самом простом случае такая функция возвращает  +1 для позиций, где компьютер уже победил, -1 для позиций, где компьютер уже проиграл, и 0 в остальных случаях. В действительности, функция статической оценки измеряет различные вещи, которые делают позицию "хорошей", например, материальное преимущество и контроль центра в шахматах. Предположим, что мы имеем такую функцию.

    static: Position -> Number

Так как  игровое дерево есть Treeof Position, оно может быть преобразовано в Treeof Number функцией (maptree static),  которая статически вычисляет все позиции в дереве (их может быть бесконечно много). Здесь используется функция maptree, определенная в разделе 2.

Как найти "истинные" значения позиций из такого дерева статических оценок? В частности какое значение должно быть приписано корневой позиции? Её статическое значение - только грубое предположение. Значение, приписанное узлу, должно определятся из значений его подузлов. Это может быть сделано в предположении, что каждый игрок делает лучшие ходы. Поскольку высокое значение означает хорошую позицию для компьютера, ясно что,  он выберет ход, ведущий к подузлу с максимальным значением. Точно так же противник выберет ход  к подузлу с минимальным значением. Значение узла вычисляются функцией maximise, если очередь компьютера и minimise, иначе:

    maximise (Node n sub) = maximum (map minimise sub)
    minimise (Node n sub) = minimum (map maximise sub)

Здесь maximum и minimum - функции на списках чисел, которые возвращают максимум и минимум списка соответственно. Эти определения не закончены, потому что они будут зацикливаться  - нет базового случая. Мы должны определить значение узла без преемников, и мы определяем его как  статическую оценку узла. Статическая оценка используется когда игрок уже выиграл, или на границах просмотра. Законченные определения maximise и minimise

    maximise (Node n [])  = n
    maximise (Node n sub) = maximum (map minimise sub)
    minimise (Node n [])  = n
    minimise (Node n sub) = minimum (map maximise sub)

    evaluate = maximise . maptree static . gametree

    prune 0 (Node a x) = Node a []
    prune n (Node a x) = Node a (map (prune (n-1)) x)

Функция  (prune  n) берет дерево и "вырезает" все узлы, расположенные далее, чем на n от корня. Если дерево обрезано,  maximise,  будет  использовать статическую оценку для узлов глубины n.  Поэтому evaluate можно определить так:

    evaluate = maximise . maptree static . prune 5 . gametree

что просматривает (скажем) на 5 шагов вперед.

Уже здесь мы использовали функции высшего порядка и ленивые вычисления. Функции высшего порядка reptree и  maptree позволяют нам с легкостью создавать и  управлять игровыми деревьями. Более важно то, что ленивые вычисления разрешает нам модуляризировать вычисления таким образом.

Поскольку gametree выдаёт потенциально бесконечный результат, эта программа никогда не закончилась бы без ленивых вычислений. Вместо (prune 5 . gametree) мы были бы должны свернуть эти две функции вместе в одну такую, которая создавала бы только первые пять уровней дерева. Но даже дерево первых пяти уровней может быть слишком большим, чтобы разместиться  в памяти. В программе которую мы написали, функция (maptree static . prune 5 . gametree) создает только те части дерева, которые требует maximise. Так как каждая часть может быть удалена (сборщиком мусора), как только maximise покончит с ней, дерево никогда не находится в памяти целиком. Только маленькая часть дерева хранится одновременно. Поэтому  ленивая программа эффективна. Поскольку эта эффективность зависит от взаимодействия между  maximise (последняя функция в цепочке) и gametree (первая), её можно получить без ленивых вычислений только сворачивая все функции  цепочки вместе в одну большую. Это значительно уменьшает модульность, но именно это обычно и делается. Мы можем сделать усовершенствования этого несерьезного алгоритма оценки. Для каждой его части это относительно просто. Обычный программист должен изменить всю программу целиком, что намного сложнее.

Пока мы описали только простой минимаксный алгоритм. Основа альфа-бета алгоритма - наблюдение,  что часто можно вычислить значение maximise или minimise без просмотра целого дерева. Рассмотрим дерево:

max
/\
min min
/\  /\
1 2 0 ?

Нет необходимости знать значение (?), чтобы оценить дерево. Левый минимум равен 1, но правый минимум явно меньше или равен 0. Поэтому максимум из этих двух минимумов должен быть 1. Это наблюдение может быть обобщено  и встроено в maximise и minimise. Первый шаг - выделить применение minimise к списку чисел, то есть мы разлагаем, maximise как

    maximise = maximum . maximise'

(minimise,  разбивается подобным образом. Так как minimise  и maximise полностью симметричны, мы обсудим maximise и предполагаем, что minimise обрабатывается так же). Разделённая таким образом maximise может использоват minimise' а не minimise, чтобы определить, для каких чисел minimise, будет искать минимум. Тогда можно отказаться от некоторых чисел не глядя на них. Благодаря ленивым вычислениям, если maximise не просматривает весь список чисел, некоторые из них не будет вычислены, с потенциальным сохранением времени вычислений.

Несложно  "вынести за скобки"  maximum  из определения  maximise:

    maximise' (Node n []) = n : []
    maximise' (Node n l)
            = map minimise l
            = map (minimum . minimise') l
            = map minimum (map minimise' l)
            = mapmin (map minimise' l) where mapmin = map minimum

Так как minimise' возвращает список чисел, минимум которых - результат minimise, то (map minimise' l) возвращает список списков чисел.  maximise' должна возвратить список минимумов этих списков. Однако, только максимум этого списка имеет значение. Мы определим новую версию mapmin, которая опускает минимумы тех списков, чей минимум не имеет значения.

    mapmin nums : rest = min nums : omit min nums rest

Функция omit  получает "потенциальный максимум" - самый большой, из замеченных на данный момент минимумов - и опускает любые минимумы, которые меньше его.

    omit pot [] = []
    omit pot (nums : rest) =
       if minleq nums pot
            then omit pot rest
            else (minimum nums) : omit (minimum nums) rest

Функция minleq получает список чисел и потенциальный максимум, и возвращает истину если минимум списка чисел  меньше или равен потенциальному максимуму. Чтобы сделать это, не требуется смотреть на весь список! Если имеется любой элемент в список меньше или равный потенциальному максимуму, то это - минимум списка. Все элементы после этого несущественны, они обозначены знаком "?" в примере выше. Поэтому minleq может быть определен следующим образом:

    minleq [] pot = False
    minleq (num:rest) pot =  num <= pot || minleq rest pot

Определив maximise' и  minimise', можно просто записать новую evaluate:

    evaluate = maximum . maximise' . maptree static . prune 8 . gametree

Благодаря ленивым вычислениям, если maximise' просматривает меньшую часть дерева то и вся программа выполняется более эффективно. Тоу, что prune просматривает только часть бесконечного дерева, даёт возможность программе закончиться. Оптимизация maximise' хоть и довольно проста, но может оказать значительное воздействие на быстродействие, и позволяет просматривать намного дальше.

Можно сделать и другие улучшения. Например, альфа-бета алгоритм работает лучше всего, если сначала рассматриваются лучшие ходы, так как, если найден очень хороший ход то,  нет необходимости рассматривать худшие ходы, только для того, чтобы продемонстрировать, что противник имеет по крайней мере один хороший ответ на них. Можно было бы, поэтому, сортировать поддеревья в каждом узле, помещая в начале узлы с самыми высокими значениями оценки, при ходе компьютера, и с самыми низкими в противном случае.  Это может быть сделано  функциями

    lowfirst (Node n sub) = Node n  (sort (map highfirst sub )))
    highfirst (Node n sub) = Node n (reverse (sort (map lowfirst sub ))

где sort - универсальная функция сортировки. Теперь можно определить

    evaluate =
        max . maximise' . highfirst . maptree static . prune 8 . gametree

Может оказаться достаточно рассматривать только три лучших хода компьютера или противника, чтобы ограничить поиск. Чтобы запрограммировать это, надо только заменить highfirst на  (taketree 3 . highfirst), где

    taketree n = redtree (nodett n) (:) []
    nodett n x sub = Node x (take n sub)

Taketree заменяет все узлы в дереве  узлами содержащими не более n подузлов, используя функцию  (take n), которая возвращает первые n элементов списка (или меньшее количество если список короче чем n).

Ещё одно улучшение - усовершенствование отсечений. Программа просматривает на установленную глубину, даже если позиция очень динамическая.  Например в шахматах она может прекратить просмотр в позиции, в которой ферзь находится под боем. Обычно определяются некоторые "динамические" позиции в которых нельзя прерывать просмотр. Предположив что функция dynamic распознает такие позиции, мы должны добавить только одно уравнение для prune:

    prune 0 (Node pos sub) | dynamic pos = Node pos (map (prune 0) sub)

Легко вносить такие изменения если программа столь же модульная как эта. Как мы отмечали выше, эффективность программы кардинально зависит от взаимодействия между  maximise и gametree (то есть между первой и последней функциями в цепочке), без ленивых вычислений она может быть написана только как монолитная программа, которую трудно написать, очень трудно изменять,и чрезвычайно трудно понять.

6. Заключение

В этой статье утверждается, что модульность - ключ к успешному программированию. Языки, которые стремятся улучшить производительность, должны поддерживать модульное программирование. Но новые правила видимости и механизмы раздельной трансляции  недостаточны. Модульность - нечто большее, чем модули. Наша способность расчленять проблему на части зависит непосредственно от нашей способности склеить решения. Чтобы поддерживать модульное программирование, язык должен обеспечить хороший клей. Функциональные языки программирования обеспечивают два новых вида клея - функции высшего порядка и ленивые вычисления. При использовании этих клеев программы могут быть модуляризованы новыми и захватывающими способами, и мы дали много примеров этому. Маленькие и очень общие модули могут широко и многократно использоваться, облегчая последующее программирование. Это объясняет, почему функциональные программы намного меньше и почему их проще писать, чем обычные. Если какая то часть программы беспорядочна или сложна, программист должен попытаться разбить её на модули и обобщить части. Он должен попытаться использовать функции высшего порядка и ленивые вычисления  как инструментальные средства для выполнения этой задачи.

Конечно, мы не первые, кто указывает на мощность и элегантность функций высшего порядка и ленивых вычислений. Например, Тёрнер показывает, они могут использоваться с большой выгодой в программе для порождения химических соединений [Tur81]. Абельсон и Сусман подчеркивают, что потоки (ленивые списки) - мощный инструмент для структурирования программ [AS86]. Хендерсон использовал потоки, чтобы структурировать функциональные операционные системы [P.H82]. Основной вклад этой статьи  -  утверждение, что лучшая организация модульности -  ключ к мощности функциональных языков.

Статья имеет отношение и к существующей полемике по поводу ленивых вычислений. Одни полагают, что функциональные языки должны быть ленивы, другие, что не должны. Некоторые ищут компромисс и предлагают только ленивые списки, со специальным синтаксисом для их построения (как, например, в Scheme [AS86] ). Эта стать даёт дальнейшие основания утверждать, что ленивая вычисления слишком важны, чтобы быть низведенными к гражданам второго сорта. Это, возможно, наиболее мощный клей, которым обладают функциональные программисты. Нельзя затруднять доступ к такому жизненно важному инструменту.

Литература

[Wir82] N. Wirth. Programming in Modula-II. Springer-Verlag, 1982.

[MTH90] R. Milner, M. Tofte, and R. Harper. The Definition of Standard ML.MIT Press, 1990.

[oD80] United States Department of Defense. The Programming Language Ada Reference Manual. Springer-Verlag, 1980.

[P.H82] P.Henderson. Purely Functional Operating Systems. 1982.

[Tur81] D. A. Turner. The Semantic Elegance of Applicative Languages. In Proceedings 1981 Conference on Functional Languages and Computer Architecture, Wentworth-by-the-Sea, Portsmouth, New Hampshire, 1981.

[AS86] H. Abelson and G.J. Sussman. Structure and Interpretation of Computer Programs. MIT Press, Boston, 1986.