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

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

C

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, который использует жадные вы­числения, придется применять специальные приемы.

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