Учебник по Haskell

части 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 Управление памятью. Сборщик мусора

В прошлом разделе для простоты мы считали, что объекты только добавляются в кучу. На самом деле это

не так. Допустим во время вычисления функции нам нужно было вычислить какие-то промежуточные дан-

ные, например объявленные в локальных переменных, тогда после вычисления результата все эти значения

больше не нужны. При этом в куче висит много-много объектов, которые уже не нужны. Нам нужно как-то от

них избавится. Этой задачей занимается отдельный блок вычислителя, который называется сборщиком му-

сора (garbage collector), соответственно процесс автоматического освобождения памяти называется сборкой

мусора (garbage collection или GC).

На данный момент в GHC используется копирующий последовательный сборщик мусора, который рабо-

тает по алгоритму Чейни (Cheney). Для начала рассмотрим простой алгоритм сборки мусора. Мы выделяем

небольшой объём памяти и начинаем наполнять его объектами. Как только место кончится мы найдём все

“живые” объекты, а остальное пространство памяти будем считать свободным. Как только после очередной