=>
Succ (foldNat Succ Zero one)
— В корне м ыполучили конструктор, можем спуститься ниже.
— Там мы видим foldNat, для того чтобы раскрыть его нам
— снова нужно понять какой конструктор в корне у второго аргумента:
=>
Succ (foldNat Succ Zero (Succ zero))
— Это опять Succ переходим ко второму уравнению для foldNat
Стратегии вычислений | 143
=>
Succ (Succ (foldNat Succ Zero zero))
— Снова раскрываем второй аргумент у foldNat
=>
Succ (Succ (foldNat Succ Zero Zero))
— Ага это Zero, выбираем первое уравнение
=>
Succ (Succ Zero)
— Синонимов больше нет можно вернуть значение
— результат:
Succ (Succ Zero)
В этой стратегии мы всегда раскрываем самый верхний уровень выражения, можно представить как мы
вытягиваем конструкторы от корня по цепочке. У этих стратегий есть специальные имена:
• вычисление по значению (call by value), когда мы идём от листьев к корню.
• вычисление по имени (call by name), когда мы идём от корня к листьям.
Отметим, что стратегию вычисления по значению также принято называть энергичными вычислениями
(eqger evaluation) или аппликативной (applicative) стратегией редукции. Вычисление по имени также принято
называть нормальной (normal) стратегией редукции.
Преимущества и недостатки стратегий
В чём преимущества, той и другой стратегии.
Если выражение вычисляется полностью, первая стратегия более эффективна по расходу памяти.
Вычисляется полностью означает все компоненты выражения участвуют в вычислении. Например то вы-
ражении, которое мы рассмотрели так подробно, вычисляется полностью. Приведём пример выражения, при
вычислении которого нужна лишь часть аргументов, для этого определим функцию:
isZero :: Nat -> Bool
isZero Zero
= True
isZero _
= False
Она проверяет является ли нулём данное число, теперь представим как будет вычисляться выражение, в
той и другой стратегии:
isZero (add Zero two)
Первая стратегия сначала вычислит все аргументы у add потом расшифрует add и только в самом конце
доберётся до isZero. На это уйдёт восемь шагов (семь на вычисление add Zero two). В то время как вто-
рая стратегия начнёт с isZero. Для вычисления isZero ей потребуется узнать какой конструктор в корне у
выражения add Zero two. Она узнает это за два шага. Итого три шага. Налицо экономия усилий.
Почему вторая стратегия экономит память? Поскольку мы всегда вычисляем аргументы функции, мы
можем не хранить описания в памяти а сразу при подстановке в функцию начинать редукцию. Эту ситуацию
можно понять на таком примере, посчитаем сумму чисел от одного до четырёх с помощью такой функции:
sum :: Int -> [Int] -> Int
sum []
res = res
sum (x:xs)
res = sum xs (res + x)
Посмотрим на то как вычисляет первая стратегия, с учётом того что мы вычисляем значения при подста-
новке:
sum [1,2,3,4] 0
=>
sum [2,3,4]
(0 + 1)
=>
sum [2,3,4]
1
=>
sum [3,4]
(1 + 2)
=>
sum [3,4]
3
=>
sum [4]
(3+3)
=>
sum [4]
6
=>
sum []
(6+4)
=>
sum []
10
=>
10
144 | Глава 9: Редукция выражений
Теперь посмотрим на вторую стратегию:
sum [1,2,3,4] 0
=>
sum [2,3,4]
0+1
=>
sum [3,4]
(0+1)+2
=>
sum [4]
((0+1)+2)+3
=>
sum []
(((0+1)+2)+3)+4
=>
(((0+1)+2)+3)+4
=>
((1+2)+3)+4
=>
(3+3)+4
=>
6+4
=>
10
А теперь представьте, что мы решили посчитать сумму чисел от 1 до миллиона. Сколько вычислений
нам придётся накопить! В этом недостаток второй стратегии. Но есть и ещё один недостаток, рассмотрим
выражение:
(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 вычислено, идём на первое уравнение
