= THUNK (h x)
in
foldr f gxy hx
У функций появились степени. Что это? Степени указывают на арность функции, то есть на количество
принимаемых аргументов. Количество принимаемых аргументов определяется по левой части функции. По-
скольку в Haskell функции могут возвращать другие функции, очень часто мы не можем знать арность, тогда
мы пишем •.
Отметим два важных принципа вычисления на STG:
• Новые объекты создаются в куче только в let-выражениях
• Выражение приводится к СЗНФ только в case-выражениях
Язык STG | 157
Выражение let a = obj in e означает добавь в кучу объект obj под именем a и затем вычисли e.
Выражение case e of~{alt1; ... ;alt2} означает узнай конструктор в корне e и продолжи вычисления в
соответствующей альтернативе. Обратите внимание на то, что сопоставления с образцом в альтернативах
имеет только один уровень вложенности. Также аргумент case-выражения в отличие от функции не обязан
быть атомарным.
Для тренировки перепишем на STG пример из раздела про ленивые вычисления.
data Nat = Zero | Succ Nat
zero
= Zero
one
= Succ zero
two
= Succ one
foldNat :: a -> (a -> a) -> Nat -> a
foldNat z
s
Zero
= z
foldNat z
s
(Succ n)
= s (foldNat z s n)
add a = foldNat a
Succ
mul a = foldNat one (add a)
exp = (\x -> add (add x x) x) (add Zero two)
Теперь в STG:
data Nat = Zero | Succ Nat
zero
= CON(Zero)
one
= CON(Succ zero)
two
= CON(Succ one)
foldNat = FUN( z s arg ->
case arg of
Zero
-> z