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

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

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

map even [1, 3, 5, 2, 4, 6] = [false, false, false, true, true, true]

map min [(1,5), (4,2), (8,1)] = [1,2,1]

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

Обратите внимание, что эта конструкция надежная. Тип тар следующий:

mар: (t1 -> t2) -> 't1 list -> t2 list

Это означает, что элементы списка аргументов t1 list все должны быть совме­стимы с аргументом функции t1, а список результата t2 list будет состоять только из элементов, имеющих тип результата функции t2.

Функции более высокого порядка абстрагируются от большинства управ­ляющих структур, которые необходимы в процедурных языках. В другом при­мере функция accumulate реализует «составное» применение функции, а не создает список результатов, подобно mар:

fun accumulate f initial [] = initial

| accumulate f initial head::tail - accumulate f (f initial head) tail

Функция accumulate может использоваться для создания ряда полезных фун­кций. Функции

fun minlist = accumulate min maxint

fun sumlist = accumulate "+" 0

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

minlist [3, 1,2] =

accumulate min maxint [3, 1,2] =

accumulate min (min maxint 3) [1,2] =

accumulate min 3 [1, 2] =

accumulate min (min 3 1) [2] =

accumulate min 1 [2] =

accumulate min (min 1 2) [] =

accumulate min 1 [] =

1

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

16.5. Ленивые и жадные вычисления

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

n = min (j + k, (i + 4) /m);

Для обозначения такой методики используется термин — жадные вычисле­ния. Однако жадные вычисления имеют свои собственные проблемы, с кото­рыми мы столкнулись в if-операторах (см. раздел 6.2), когда пришлось опре­делить специальную конструкцию для укороченного вычисления:

if (N > 0) and then ((Sum / N) > M) then . . .

Как должно быть определено условное выражение

if с then e1 else e2

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

if list = [] then [] else hd list

Чтобы решить эту проблему, в язык ML введено специальное правило для вы­числения if-функции: сначала вычисляется условие с, и только после этого вычисляется один из двух вариантов.

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

Например, мы могли бы определить if как обычную функцию:

fun if true х у = х

| if false х у = у

Когда применяется if, функция просто применяется к первому аргументу, производя следующее:

(if list = [] [] hd list) [] =

if [] = [] [] hd [] =

if true [] hd [] =

[]

и мы не пытаемся вычислить hd [].

Ленивое вычисление аналогично механизму вызова параметра по имени (call-by-name) в процедурных языках, где фактический параметр вычисляется каждый раз заново, когда используется формальный параметр. Этот механизм в процедурных языках сомнителен из-за возможности побочных эффектов, которые не позволяют сделать оптимизацию путем вычисления и сохранения результата для многократного использования. В функциональном програм­мировании, свободном от побочных эффектов, такой проблемы нет, и языки, использующие ленивые вычисления (например, Miranda), были реализова­ны. Ленивые вычисления могут быть менее эффективными, чем жадные, но у них есть значительные преимущества.

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

fun equal_nodes t1 t2 = compare_lists (tree_to_list t1) (tree_to_list t2)

Функция tree_to_list обходит дерево и создает список значений в узлах; соm-pare_lists проверяет, равны ли два списка. При жадных вычислениях оба дере­ва полностью преобразуются в списки до того, как будет выполнено сравне­ние, даже если при обходе выяснится, что первые узлы не равны! При лени­вых вычислениях функции нужно вычислять только в том объеме, который необходим для ответа на поставленный вопрос.

Функции compare_lists и tree_to_list определены следующим образом:

fun compare_lists [] [] = true

| compare_lists head::tail1 head::tail2 = compare_lists tail1 tail2

| compare_lists list1 Iist2 = false

fun tree_to_list Empty = []

| tree_to_listT(left, value, right) =

value :: append (tree_to_list left) (tree_to_list right)

Ленивые вычисления, например, могли бы происходить следующим образом (мы использовали сокращенные имена функций сmp и ttl, а многоточием обозначили очень большое поддерево):

cmp ttl T(T(Empty,4,Empty), 5, . . .)

ttl T(T(Empty,6,Empty), 5,...) =

cmp 5:: append (ttl T(Empty,4,Empty)) (ttl.. .)

5:: append (ttl T(Empty,6,Empty)) (ttl.. .) =

cmp append (ttl T(Empty,4,Empty)) (ttl.. .)

append (ttl T(Empty,6,Empty)) (ttl. ..) =

…

cmp 4:: append [] (ttl. . .)

6:: append [] (ttl. ..) =

false

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

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

16.6. Исключения

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

exception BadParameter of int;

После этого может возникнуть исключение, которое можно обработать:

fun only_positive n =

if n <= 0 then raise BadParameter n

else...

val i = ...;

val j = only_positive i

handle

BadParameter 0 => 1;

BadParameter n => abs n;

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

16.7. Среда

Помимо определений функций и вычисления выражений программа на язы­ке ML может содержать объявления:

val i = 20

val'S = "Hello world"

Таким образом, в языке ML есть память, но, в отличие от процедурных язы­ков, эта память необновляемая; в данном примере нельзя «присвоить» другое значение i или s. Если мы теперь выполним:

val i = 35

будет создано новое именованное значение, скрывающее старое значение, но не заменяющее содержимое i новым значением. Объявления в языке ML ана­логичны объявлениям const в языке С в том смысле, что создается объект, который нельзя изменить; однако повторное определение в языке ML скры­вает предыдущее, в то время как в языке С запрещено повторно объявлять объект в той же самой области действия.

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

val а = 1.0 and b = 2.0 and с = 1.0

let

D = b*b-4.0*a*c

in

((- b + D)/2.0*a, (- b - D)/2.0*a )

end

Каждое объявление связывает (binds) значение с именем. Набор всех таких связей, действующих в какой-либо момент времени, называется средой (envi­ronment), и мы говорим, что выражение вычислено в контексте среды. Мы фактически обсуждали среды детально в контексте областей действия и види­мости в процедурных языках; различие состоит в том, что связывания не мо­гут изменяться в среде функционального программирования.

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

abstype int tree =

Empty

| Т of (int tree x int x int tree)

with

fun sumtree t = . . .

fun equal_nodes t1 t2 = .. .

end

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

abstype 't tree = . . .

что аналогично созданию родовых абстрактных типов данных в языке Ada.

Язык ML включает очень гибкую систему для определения и управления модулями. Основное понятие — это структура (structure), которая инкапсули­рует среду, состоящую из объявлений (типов и функций), аналогично классу в языке C++ или пакету в языке Ada, определяющему абстрактный тип дан­ных. Однако в языке ML структура сама является объектом, который имеет тип, названный сигнатурой (signature). Структурами можно управлять, ис­пользуя функторы (functors), которые являются функциями, отображающими одну структуру в другую. Это — обобщение родового понятия, которое ото­бражает пакет или шаблоны класса в конкретные типы. Функторы можно ис­пользовать, чтобы скрыть или совместно использовать информацию в струк­турах. Детали этих понятий выходят за рамки данной книги, и заинтересован­ного читателя мы отсылаем к руководствам по языку ML.

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

16.8. Упражнения

1. Какой тип у карризованной функции min_c?

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

2. Выведите типы sumtree и mintree.

3. Опишите словами определение general_insert_element.

4. Напишите функцию для конкатенации списков, а затем покажите, как ту же самую функцию можно определить с помощью accumulate.

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

6. Выведите типы compare_lists и tree_to_list.

7. Что делает следующая программа? Какой тип у функции?

fun filter f[] = []

| filter f h ::t = h:: (filter f t), if f h = true

| filter f h :: t = filter f t, otherwise

8. Стандартное отклонение последовательности чисел (х\, . .. , х„) опреде­ляется как квадратный корень из среднего значения квадратов чисел ми­нус квадрат среднего значения. Напишите программу на языке ML, ко­торая вычисляет стандартное отклонение списка чисел. Подсказка: ис­пользуйте тар и accumulate.

9. Напишите программу на языке ML для поиска совершенных чисел; п > 2 — совершенное число, если множители я (не включая п) в сумме дают п. Например, 1 +2 + 4 + 7+ 14 = 28.В общих чертах программа будет вы­глядеть как:

fun isperfect n =

let fun addfactors...

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

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