Unknown - haskell-notes

в стек все аргументы и начинаем вычисление функции 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 Paira b = Paira b

-- 3 слова

У этого правила есть исключение. Если у конструктора нет полей, то есть он является константой или

примитивным конструктором, то в процессе вычисления значение этого конструктора представлено ссылкой.

Это означает, что внутри программы все значения ссылаются на одну область памяти. У нас действительно

есть лишь один пустой список или одно значение Trueили False.

Посчитаем число слов в значении [ Pair1 2]. Для этого для начала перепишем его в STG

nil = []

-- глобальный объект (не в счёт)

162 | Глава 10: Реализация Haskell в GHC

letx1

= I#1

-- 2 слова

x2

= I#2

-- 2 слова

p

= Pairx1 x2

-- 3 слова

val = Consp nil

-- 3 слова

in

val

------------

-- 10 слов

Поскольку объект кучи CONможет хранить только ссылки, нам пришлось введением дополнительных