М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 47

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 47)

11. Дайте примеры использования CW-объектов.

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

16.3. Составные типы

Списки

Список можно создать из элементов любого предварительно определенного типа, в частности из встроенных типов, например целого или булева. Следую­щие списки:

[2,3,5,7,11 ] [true, false, false]

имеют типы int list и bool list, соответственно. Список можно создать также с помощью конструкторов (constructors); конструкторы списка — это [] для пус­того списка, и element::list для непустого списка, создаваемого добавлением элемента (element) к существующему списку (list). Конструкторы могут ис­пользоваться при определении функций путем сопоставления с образцом:

fun member [] e = false

| member [e :: tail] e = true

j member [e1 :: tail] e = member tail e

Тип функции member (член) определяется как:

member: int list x jnt -> boolean

и это можно прочитать следующим образом:

Когда функция member применяется к списку L, а (затем) к элементу е, вычисление основывается на вариантах выбора в зависимости от аргумен­тов: 1) если L пуст, е не является членом L; 2) если е — первый элемент L, то е является членом L; 3) в противном случае, е1, первый элемент списка L, отличен от е, и мы (рекурсивно) проверяем, является ли е членом остав­шейся части списка L.

В языке ML вам не нужно объявлять тип функции; компилятор автомати­чески выводит тип функции из типов аргументов и типа результата. Если ком­пилятор не может вывести тип, вам придется задать нужное количество объ­явлений типа, чтобы ликвидировать неопределенность выражения. Контроль соответствия типов статический, поэтому, когда функция применяется к значению, проверка соответствия типа функции типу параметра делается во вре­мя компиляции.

Обратите внимание, что эта функция рекурсивная. Рекурсия чрезвычайно важна в функциональных языках программирования; при отсутствии «опера­торов» это единственный способ создания циклов при вычислении выраже­ния.

В качестве заключительного примера покажем, как на языке ML написать алгоритм сортировки вставкой (insertion sort). Вы используете этот алгоритм для сортировки при игре в карты: по очереди берете карты из колоды и кла­дете их в нужное место:

fun insertion_sort [] = []

| insertion_sort head:: tail =

insert_element head insertion_sort tail

and

fun insert_element x [] = [x]

| insert_element x head:: tail =

if x < head then x::head:: tail

else head:: (insert_element x tail)

Эти функции имеют типы:

insertion_sort: int list -> int list

insert_element: int -> int list -> int list

Как только вы привыкнете к этой записи, читать такие программы будет про­сто:

Отсортированный пустой список является пустым. При сортировке непу­стого списка берется первый элемент х, сортируется оставшаяся часть спи­ска tail, а затем х вставляется в подходящее место отсортированного спи­ска.

Элемент х вставляется в пустой список, создавая список из одного элемен­та. Чтобы вставить х в непустой список, нужно сравнить х с первым эле­ментом (head) списка: 1) если х меньше head, сделать х новым первым эле­ментом списка; 2) в противном случае создать новый список, составлен­ный из head, за которым следует остаток списка, в который вставлен х.

Обратите внимание, что -> имеет правую ассоциативность:

insert_element: int -> (int list -> int list)

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

fun insert_4 = insert_element 4

которая вставляет 4 в список целых.

В отличие от процедурной программы для того же самого алгоритма здесь нет никаких индексов и никаких for-циклов. Кроме того, ее можно легко обобщить для сортировки объектов других типов, просто заменяя операцию «<» соответствующей булевой функцией для сравнения двух значений рас­сматриваемого типа. Чтобы создать список, явные указатели не нужны; они заданы неявно в представлении данных. Конечно, сортировка списков в лю­бом языке не так эффективна, как сортировка массива «на своем месте», но для многих приложений, использующих списки, вполне практична.

Определение новых типов

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

datatype int tree =

Empty

| T of (int tree x int x int tree)

Это следует читать так:

int tree является новым типом данных, значения которого: 1) новое кон­стантное значение Empty (пусто) или 2) значение, которое сформировано конструктором Т, примененным к тройке, состоящей из дерева, целого числа и другого дерева.

Определив новый тип, мы можем написать функции, которые обрабатыва­ют дерево.

Например:

fun sumtree Empty = О

| sumtree T(left, value, right) =

(sumtree left) + value + (sumtree right)

суммирует значения, помечающие узлы дерева, и:

fun mintree Empty = maxint

| mintree T(left, value, right) =

min left (min value (mintree right))

вычисляет минимальное из всех значений, помечающих узлы, возвращая наи­большее'целое число maxint для пустого дерева.

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

16.4. Функции более высокого порядка

В функциональном программировании функция является обычным объек­том, имеющим тип, поэтому она может быть аргументом других функций. На­пример, мы можем создать обобщенную (родовую) форму для insert_element (вставить элемент), просто добавляя функцию compare как дополнительный аргумент:

fun general_insert_element compare x [ ] = [х]

| general_insert_element compare x head:: tail =

if compare x head

then x::head::tail

else head:: (general_insert_element compare x tail)

Если string_compare является функцией от string к boolean:

string_compare: (string x string)—> bool

применение general_insert_element к этому аргументу:

fun string_insert = general_insert_element string_compare

дает функцию следующего типа:

string -> string list -> string list

Обратите внимание, что, в отличие от процедурных языков, это обобщение достигается естественно, без какого-либо дополнительного синтаксиса или семантики, наподобие generic или template.

Но какой тип у general_insert_element? Первый аргумент должен иметь тип «функция от пары чего-либо к булеву значению», второй аргумент должен иметь тип этого самого «чего-либо», а третий параметр является списком этих «чего-либо». Типовые переменные (type variables) используются в качестве краткой записи для этого «чего-либо», и, таким образом, тип функции будет следующим:

general_insert_element: (('t x 't) -> bool) -> 't -> 't list

где типовые переменные записаны в языке ML как идентификаторы с пред­шествующим

апострофом

Использование функций более высокого порядка, т. е. функций, аргумента­ми которых являются функции, не ограничено такими статическими конст­рукциями, как обобщения. Чрезвычайно полезная функция — тар:

fun map f [] = [ ]

| mар f head :: tail = (f head):: (map f tail)

Эта функция применяет первый аргумент к списку значений, производя спи­сок результатов. Например:

Характеристики

Список файлов книги