соответствующей альтернативе. Обратите внимание на то, что сопоставления с образцом в альтернативах
имеет только один уровень вложенности. Также аргумент 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). Вместе с функцией мы храним информацию о том, сколько аргу-
ментов ей нужно. Если это статически определённая функция (определение выписано пользователем),
то число аргументов мы можем понять по левой части определения. В этой стратегии, если число ар-
гументов известно, мы сразу вычисляем значение с нужным числом аргументов, сохранив оставшиеся
в стеке, а затем извлекаем аргументы из стека и применяем к ним вычисленное значение.
Возвращаясь к исходному примеру, предположим, что арность функции f равна единице. Тогда страте-
гия вставка-вход сначала добавит на стек x и y, а затем будет добирать из стека необходимые аргументы.
Стратегия вычисление-применение сначала вычислит (f x), сохранив y на стеке, затем попробует приме-
нить результат к y. Почему мы говорим попробует? Может так случиться, что арность значения f x окажется
равным трём, но пока у нас есть лишь один аргумент, тогда мы создадим объект PAP, который соответствует
частичному применению.
Эти стратегии применимы как к ленивым, так и к энергичным языкам. Исторически сложилось, что лени-
вые языки тяготеют к первой стратегии, а энергичные ко второй. До недавнего времени и в GHC применялась
первая стратегия. Пока однажды разработчики GHC всё же не решили сравнить две стратегии. Реализовав
обе стратегии, и проверив их на большом количестве разных по сложности программ, они пришли к вы-
воду, что ни одна из стратегий не даёт существенного преимущества на этапе вычислений. Потребление
ресурсов оказалось примерно равным. Но вторая стратегия заметно выигрывала в простоте реализации. По-
дробнее об этом можно почитать в статье Simon Marlow, Simon Peyton Jones: Making a Fast Curry: Push/Enter
vs. Eval/Apply. Описание модели вычислений GHC, которое вы сейчас читаете копирует описание приведён-
ное в этой статье.
Куча
Объекты кучи принято называть замыканиями (closure). Их называют так, потому что обычно для вычис-
ления выражения нам не достаточно знать его текст, например посмотрим на функцию:
mul
= FUN( a ->
let succ = THUNK (add a)
in
foldNat one succ
)
Для того, чтобы вычислить THUNK(add a) нам необходимо знать значение a, это значение определено в те-
ле функции. Оно определяется из контекста. По отношению к объекту такую переменную называют свободной
(free). В куче мы будем хранить не только выражение (add a), но и ссылки на все свободные переменные, ко-
торые участвуют в выражении объекта. Эти ссылки называют довесок (payload). Объект кучи содержит ссылку
на специальную таблицу и довесок. В таблице находятся информация о типе объекта и код, который необ-
ходимо вычислить, а также другая служебная информация. При вычислении объекта мы заменяем ссылки
настоящими значениями или ссылками на конструкторы.
Объект кучи может быть:
• FUN – определением функции;
• PAP – частичным применением;
• CON – полностью применённым конструктором;
• THUNK – отложенным вычислением;
• BLACKHOLE – это значение используется во время вычисления THUNK. Этот трюк предотвращает появле-