| Рассмотрим функцию f = [y]. + y (sqrt 4)
, где sqrt -- функ-
ция извлечения квадратного корня. Каждый раз, когда эта функция
применяется к аргументу, подвыражение (sqrt 4) приходится вычи-
слять заново. Однако независимо от значения аргумента y выраже-
ние (sqrt 4) редуцируется к 2. Следовательно, хотелось бы не выпол-
нять повторных вычислений подобных константных выражений, а,
вычислив его единственный раз, использовать сохраненный резуль-
тат.
Пример 16.11 Рассмотрим программу:
f = g 4
g x y = y + (sqrt x)
(f 1) + (f 2)
Запись в виде ламбда-выражения дает:
letrec f = g 4
g = [x].[y].+ y (sqrt x)
in + (f 1)(f 2)
При вычислении этого выражения получаем следующий результат:
+ (f 1)(f 2) → + (. 1)(. 2)
−→ (([x].[y].+ y (sqrt x))4)
→ + (. 1)(. 2)
−→ ([y].+ y (sqrt 4))
→ + (. 1)(+ 2 (sqrt 4))
−→ ([y].+ y (sqrt 4))
→ + (. 1)4
−→ ([y].+ y (sqrt 4))
→ + (+ 1 (sqrt 4))4
→ + (+ 1 2)4
→ + 3 4
→ 7
В этом примере подвыражение (sqrt 4) вычисляется дважды, при ка-
ждом применении выражение [y].(sqrt 4) считается динамически со-
здаваемым константным подвыражением [y].-абстракции. Точно та-
кой же эффект наблюдается и при переходе к суперкомбинаторам.
Рассмотренное выражение компилируется следующим образом:
$g x y = + y (sqrt x)
$f = $g 4
$P rog = + ($f 1)($f 2)
___________
$P rog
Редукция выглядит следующим образом:
$P rog → + (. 1)(. 2)
−→ ($g 4)
→ + (. 1)(+ 2(sqrt 4))
−→ ($g 4)
→ + (. 1)4
−→ ($g 4)
→ + (+ 1(sqrt 4))4
→ + (+ 1 2)4
→ + 3 4
→ 7
И в этом случае подвыражение (sqrt 4) вычисляется дважды. После
выписывания этих примеров, носящих наводящий характер, сформу-
лируем следующую основную проблему, для преодоления которой
потребуются определенные усилия: после связывания всех его пе-
ременных каждое выражение должно вычисляться максимум один
раз. Такое свойство вычисления выражений считается полной ле-
нивостью вычислений.
Упражнение 16.9 Пусть имеется программа:
f = g 2
g x y = y ×(КВАДРАТ x)
(f 3)×(f 1)
а) Записать программу в виде абстракции и произвести вычисления.
б) Скомпилировать программу и произвести вычисления. |
Главная
Каталог файлов
