арностью n. Тогда мы добираем из стека n аргументов и подставляем их в правую часть функции e. Если
в стеке оказалось слишком мало аргументов, то мы переходим к третьему правилу и составляем частичное
применение. Последнее правило говорит о том как расшифровывается частичное применение. Мы вставляем
в стек все аргументы и начинаем вычисление функции g из тела P AP .
Вычисление STG | 161
f • a 1 . . . an;
s;
H[ f > F U N ( x 1 . . . xn > e)]
? e[ a 1/ x 1 . . . an/ xn]; s; H
f k a 1 . . . am;
s;
H[ f > F U N ( x 1 . . . xn > e)]
? e[ a 1/ x 1 . . . an/ xn]; ( • an+1 . . . am) : s; H
при m ? n
? p; s; H[ p > P AP ( f a 1 . . . am)]
при m < n, p – новый адрес
f • a 1 . . . am;
s;
H[ f > T HU N K e]
? f; ( • a 1 . . . am) : s; H
f k an+1 . . . am;
s;
H[ f > P AP ( g a 1 . . . an)]
? g• a 1 . . . an an+1 . . . am; s; H
f ;
( • a 1 . . . an) : s;
H
? f• a 1 . . . an; s; H
H[ f ] является F U N или P AP
Рис. 10.9: Синтаксис STG
Правила для стратегии вычисление-применение
Разберёмся с первыми двумя правилами. В первом правиле статическая арность f неизвестна, но зна-
чение f уже вычислено, и мы можем узнать арность по объекту F UN, далее возможны три случая. Число
аргументов переданных в функцию совпадает с арностью F UN, тогда мы применяем аргументы к правой
части F UN. Если в функцию передано больше аргументов чем нужно, мы сохраняем лишние на стеке. Если
же аргументов меньше, то мы создаём объект P AP . Третье правило говорит о том, что нам делать, если зна-
чение f ещё не вычислено. Оно является T HUNK. Тогда мы сохраним аргументы на стеке и вычислим его.
В следующем правиле мы раскрываем частичное применение. Мы просто организуем вызов функции со все-
ми аргументами (и со стека и из частичного применения). Последнее правило срабатывает после третьего.
Когда мы вычислим T HUNK и увидим там F UN или P AP . Тогда мы составляем применение функции.
Сложность применения стратегии вставка-вход связана с плохо предсказуемым изменением стека. Если в
стратегии вычисление-выполнение мы добавляем и снимаем все аргументы, то в стратегии вставка-вход мы
добавляем их по одному и неизвестно сколько снимем в следующий раз. Кроме того стратегия вычисление-
применение позволяет проводить оптимизацию перемещения аргументов. Вместо стека мы можем хранить
аргументы в регистрах. Тогда скорость обращения к аргументам резко возрастёт.
10.4 Представление значений в памяти. Оценка занимаемой памяти
Ранее мы говорили, что полностью вычисленное значение – это дерево, в узлах которого находятся одни
лишь конструкторы. Процесс вычисления похож на очистку дерева выражения от синонимов. Мы начинаем с
самого верха и идём к листьям. Потом мы выяснили, что для предотвращения дублирования вычислений мы
подставляем в функции не сами значения, а ссылки на значения. Теперь нам понятно, что ссылки указывают
на объекты в куче. Ссылки – это атомарные переменные. Полностью вычисленное значение является сетью
(или графом) объектов кучи типа CON.
Поговорим о том сколько места в памяти занимает то или иное значение. Как мы говорили память ком-
пьютера состоит из ячеек, в которых хранятся значения. У каждой ячейки есть адрес. Ячейки памяти неде-
лимы, их также принято называть словами. Мы будем оценивать размер значения в словах.
Каждый конструктор требует столько слов сколько у него полей плюс ещё одно слово для ссылки на
служебную информацию (она нужна вычислителю). Посмотрим на примеры:
data Int = I# Int#
— 2 слова
data Pair a b = Pair a b
— 3 слова
У этого правила есть исключение. Если у конструктора нет полей, то есть он является константой или
примитивным конструктором, то в процессе вычисления значение этого конструктора представлено ссылкой.
Это означает, что внутри программы все значения ссылаются на одну область памяти. У нас действительно
есть лишь один пустой список или одно значение True или False.
Посчитаем число слов в значении [Pair 1 2]. Для этого для начала перепишем его в STG
nil = []
— глобальный объект (не в счёт)
162 | Глава 10: Реализация Haskell в GHC
let x1
= I# 1
— 2 слова
x2
= I# 2
— 2 слова
p
= Pair x1 x2
— 3 слова
val = Cons p nil
— 3 слова
in
val
————
— 10 слов
Поскольку объект кучи CON может хранить только ссылки, нам пришлось введением дополнительных
переменных “развернуть” значение. Примитивный конструктор не считается, поскольку он сохранён гло-
бально, в итоге получилось 10 слов. Посмотрим на ещё один пример, распишем значение [Just True, Just
True, Nothing]:
nil
= []
true
= True
nothing = Nothing
let x1 = Just true
— 2 слова
x2 = Just true
— 2 слова
p1 = Cons nothing nil
— 3 слова
p2 = Cons x2 p1
— 3 слова
p3 = Cons x1 p2
— 3 слова
in
p3
———-
— 13 слов
Обычно одно слово соответствует 16, 32 или 64 битам. Эта цифра зависит от процессора. Мы считали,
что любое значение можно поместить в одно слово, но это не так. Возьмём к примеру действительные чис-
ла с двойной точностью, они не поместятся в одно слово. Это необходимо учитывать при оценке объёма
занимаемой памяти.
10.5 Управление памятью. Сборщик мусора
В прошлом разделе для простоты мы считали, что объекты только добавляются в кучу. На самом деле это