гия вставка-вход сначала добавит на стек 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. Этот трюк предотвращает появле-
ние утечек памяти.
Мы будем считать, что куча – это таблица, которая ставит в соответствие адресам объекты или вычис-
ленные значения.
Вычисление STG | 159
Стек
Стек служит для быстрого переключения контекста. Мы будем пользоваться стеком при вычислении case-
выражений и THUNK-объектов. При вычислении case-выражения мы сохраняем в стеке альтернативы и место
возврата значения, а сами начинаем вычислять аргумент case-выражения. При вычислении THUNK-объекта
мы запомним в стеке, адрес с которым необходимо связать полученное значение.
При вычислении в стратегии вставка-вход мы будем сохранять в стеке аргументы функции. А при вычис-
лении в стратегии вычисление-применение мы также будем сохранять аргументы функции в стеке. Какая
разница между этими вариантами? В первой стратегии мы можем доставать из стека произвольное число
аргументов, после определения арности функции мы добираем столько, сколько нам нужно, поэтому мы