Учебник по Haskell

нам придётся накопить! В этом недостаток второй стратегии. Но есть и ещё один недостаток, рассмотрим

выражение:

(\x -> add (add x x) x) (add Zero two)

Первая стратегия сначала редуцирует выражение add Zero two в то время как вторая подставит это

выражение в функцию и утроит свою работу!

Но у второй стратегии есть одно очень веское преимущество, она может вычислять больше выражений

чем вторая. Определим значение бесконечность:

infinity

:: Nat

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, часто рисуют как ⊥), когда известно, что значение не определено.