infinity
= Succ infinity
Это рекурсивное определение, если мы попытаемся его распечатать мы получим бесконечную последо-
вательность Succ. Чем не бесконечность? Теперь посмотрим на выражение:
isZero infinity
Первая стратегия захлебнётся, вычисляя аргумент функции isZero, в то время как вторая найдёт решение
за два шага.
Подведём итоги. Плюсы вычисления по значению:
• Эффективный расход памяти в том случае если все
составляющие выражения участвуют в вычислении.
• Она не может дублировать вычисления, как стратегия вычисления по имени.
Плюсы вычисления по имени:
• Меньше вычислений в том случае, если при вычислении выражения
участвует лишь часть составляющих.
• Большая выразительность. Мы можем вычислить больше значений.
Какую из них выбрать? В Haskell пошли по второму пути. Всё-таки преимущество выразительности языка
оказалось самым существенным. Но для того чтобы избежать недостатков стратегии вычисления по имени
оно было модифицировано. Давайте посмотрим как.
9.2 Вычисление по необходимости
Вернёмся к выражению:
(x -> add (add x x) x) (add Zero two)
Нам нужно как-то рассказать функции о том, что имя x в её теле указывает на одно и то же значение. И
если в одном из x значение будет вычислено переиспользовать эти результаты в других x. Вместо значения мы
будем передовать в функцию ссылку на область памяти, которая содержит рецепт получения этого значения.
Напомню, что мы по-прежнему вычисляем значение сверху вниз, сейчас мы просто хотим избавиться от
проблемы дублирования. Вернитесь к примеру с вычислением по имени и просмотрите его ещё раз. Обратите
внимание на то, что значения вычислялись лишь при сопоставлении с образцом. Мы вычисляем верхний
конструктор аргумента лишь для того, чтобы понять какое уравнение для foldNat выбрать. Теперь мы будем
хранить ссылку на (add Zero two) в памяти и как только, внешняя функция запросит верхний конструктор
мы обновим значение в памяти новым вычисленным до корневого конструктора значением. Если в любом
другом месте функции мы вновь обратимся к значению, мы не будем его перевычислять, а сразу вернём
конструктор. Посмотрим как это происходит на примере:
Вычисление по необходимости | 145
—
выражение
| память:
———————————————|————————-
(x -> add (add x x) x) M
| M = (add Zero two)
— подставим ссылку в тело функции
|
=>
add (add M M) M
|
— раскроем самый верхний синоним
|
=>
foldNat (add M M) Succ M
|
— для foldNat узнаем верхний конструктор
|
— последнего аргумента (пропуская
|
— промежуточные шаги, такие же как выше)
|
=>
| M
= Succ M1
| M1 = foldNat Succ Zero one
— по M выбираем второе уравнение
|
=> Succ (foldNat (add M M) Succ M1)
|
— запросим следующий верхний конструктор:
|
=>
| M
= Succ M1
| M1 = Succ M2
| M2 = foldNat Succ Zero zero
— по M1 выбираем второе уравнение
|
=> Succ (Succ (foldNat (add M M) Succ M2))
|
— теперь для определения уравнения foldNat |
— раскроем M2
|
=>
| M
= Succ M1
| M1 = Succ M2
| M2 = Zero
— выбираем первое уравнение для foldNat:
|
=> Succ (Succ (add M M))
|
— раскрываем самый верхний синоним:
|
=> Succ (Succ (foldNat M Succ M))
|
— теперь, поскольку M уже вычислялось, в
|
— памяти уже записан верхний конструктор,
|
— мы знаем, что это Succ и выбираем второе |
— уравнение:
|
=> Succ (Succ (Succ (foldNat M Succ M1)))
|
— и M1 тоже уже вычислялось, сразу
|
— выбираем второе уравнение
|—-+
=> Succ (Succ (Succ (Succ (foldNat M Succ M2)))) |
— M2 вычислено, идём на первое уравнение
|—-+
=> Succ (Succ (Succ (Succ (Succ M))))
|
— далее остаётся только подставить уже
|
— вычисленные значения M
|
— и вернуть значение.
|
Итак подставляется не значение а ссылка на него, вычисленная часть значения используется сразу в
нескольких местах. Эта стратегия редукции называется вычислением по необходимости (call by need) или
ленивой стратегией вычислений (lazy evaluation).
Теперь немного терминологии. Значение может находится в четырёх состояниях:
• Нормальная форма (normal form, далее НФ), когда оно полностью вычислено (нет синонимов);
• Слабая заголовочная НФ (weak head NF, далее СЗНФ), когда известен хотя бы один верхний конструк-
тор;
• Отложенное вычисление (thunk), когда известен лишь рецепт вычисления;
• Дно (bottom, часто рисуют как ?), когда известно, что значение не определено.
Вы могли понаблюдать за значением в первых трёх состояниях на примере выше. Но что такое ?? Вспом-
ним определение для функции извлечения головы списка head:
head :: [a] -> a
head (a:_)
= a
head []
= error ”error: empty list”
Второе уравнение возвращает ?. У нас есть две функции, которые возвращают это “значение”:
undefined
:: a
error
:: String -> a
146 | Глава 9: Редукция выражений
Первая – это ? в чистом виде, а вторая не только возвращает неопределённое значение, но и приводит
к выводу на экран сообщения об ошибке. Обратите внимание на тип этих функций, результат может быть
значением любого типа. Это наблюдение приводит нас к ещё одной тонкости. Когда мы определяем тип:
data Bool
= False | True
data Maybe a
= Nothing | Just a
На самом деле мы пишем:
data Bool
= undefined | False | True
data Maybe a
= undefined | Nothing | Just a