выражения разделяют на не рекурсивные (let) и рекурсивные (letrec). Разделение проводится в целях оп-
тимизации, мы же будем считать, что эти случаи описываются одной конструкцией.
На что стоит обратить внимание? Заметим, что функции могут принимать только атомарные значения
(либо примитивные значения, либо переменные). В данном случае переменные указывают на объекты в куче.
Так если в Haskell мы пишем:
foldr f (g x y) (h x)
В STG это выражение примет вид:
let gxy = THUNK (g x y)
hx
= 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
Succ n
-> let next = THUNK (foldNat z s n)
in
s next
)
add
= FUN( a ->
let succ = FUN( x ->
let r = CON(Succ x)
in r)
in
foldNat a succ
)
mul
= FUN( a ->
let succ = THUNK (add a)
in
foldNat one succ
)
exp
= THUNK(
let f = FUN( x -> let axx = THUNK (add x x)
in
add axx x)
a = THUNK (add Zero two)
in
f a
)
Программа состоит из связок вида имя = объектКучи. Эти связки называют глобальными, они становятся
статическими объектами кучи, остальные объекты выделяются динамически в let-выражениях. Глобальный
объект типа THUNK называют постоянной аппликативной формой (constant applicative form или сокращённо
CAF).
10.3 Вычисление STG
Итак у нас есть упрощённый функциональный язык. Как мы будем вычислять выражения? Присутствие
частичного применения усложняет этот процесс. Для многих функций мы не знаем заранее их арность. Так
например в выражении
158 | Глава 10: Реализация Haskell в GHC
f x y
Функция f может иметь один аргумент в определении, но вернуть функцию. Есть два способа вычисления
таких функций:
• вставка-вход (push-enter). Когда мы видим применение функции, мы сначала вставляем все аргументы
в стек, затем совершаем вход в тело функции. В процессе входа мы вычисляем функцию f и узнаём чис-
ло аргументов, которое ей нужно, после этого мы извлекаем из стека необходимое число аргументов, и
применяем к ним функцию, если мы снова получаем функцию, тогда мы опять добираем необходимое
число аргументов из стека. И так пока аргументы в стеке не кончатся.
• вычисление-применение (eval-apply). Вместе с функцией мы храним информацию о том, сколько аргу-
ментов ей нужно. Если это статически определённая функция (определение выписано пользователем),
то число аргументов мы можем понять по левой части определения. В этой стратегии, если число ар-
гументов известно, мы сразу вычисляем значение с нужным числом аргументов, сохранив оставшиеся