-- синонимов больше нет можно вернуть значение
-- результат:
Succ (Succ Zero)
В этой стратегии для каждой функции мы сначала вычисляем до конца все аргументы, потом подставляем
расшифрованные значения в определение функции.
Теперь посмотрим на вычисление от корня к листьям (сверху-вниз):
add Zero two
-- видим два синонима add и two, начинаем с того, что ближе всех к корню
=>
foldNat Succ Zero two
-- теперь выше всех foldNat, раскроем его
Но для того чтобы раскрыть foldNat нам нужно узнать какое уравнение выбрать для этого нам нужно
понять какой конструктор находится в корне у второго аргумента, если это Zero, то мы выберем первое
уравнение, а если это Succ, то второе:
-- в уравнении для foldNat видим декомпозицию по второму
-- аргументу. Узнаем какой конструктор в корне у two
=>
foldNat Succ Zero (Succ one)
-- Это Succ нам нужно второе уравнение:
=>
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) стратегией редукции.
Преимущества и недостатки стратегий
В чём преимущества, той и другой стратегии.
Если выражение вычисляется полностью, первая стратегия более эффективна по расходу памяти.