воду, что ни одна из стратегий не даёт существенного преимущества на этапе вычислений. Потребление
ресурсов оказалось примерно равным. Но вторая стратегия заметно выигрывала в простоте реализации. По-
дробнее об этом можно почитать в статье 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-объекта
мы запомним в стеке, адрес с которым необходимо связать полученное значение.
При вычислении в стратегии вставка-вход мы будем сохранять в стеке аргументы функции. А при вычис-
лении в стратегии вычисление-применение мы также будем сохранять аргументы функции в стеке. Какая
разница между этими вариантами? В первой стратегии мы можем доставать из стека произвольное число
аргументов, после определения арности функции мы добираем столько, сколько нам нужно, поэтому мы
будем хранить аргументы по одному. Во второй же стратегии нам нужно просто сохранить все оставшиеся
аргументы. Мы сохраняем и извлекаем их все сразу. Упрощая, объекты стека можно представить так:
k
::=
case • of {alt 1; . . . altn}
контекст case-выражения
|
U pd t •
Обновить отложенное вычисление
|
( • a 1 …an)
Применить функцию к аргументам, только для
стратегии вычисление-применение
|
Arg a
Аргумент на потом, только для
стратегии вставка-вход
Рис. 10.3: Синтаксис STG
Правила общие для обеих стратегий вычисления
Состояние вычислителя состоит из трёх частей. Это выражение для вычисления e, стек s и куча H. Мы
рассмотрим правила по которым вычислитель переходит из одного состояния в другое. Все они имеют вид:
e 1;
s 1;
H 1
? e 2; s 2; H 2
Левая часть переходит в правую, при условии, что левая часть имеет определённый вид. Начнём с правил,
которые одинаковы и в той и в другой стратегии вычисления. Для простоты пока мы будем полагать, что
объекты только добавляются в кучу и никогда не стираются. Мы будем обозначать добавление в стек как
добавление элемента в обычный список: elem : s.
Рассмотрим правило для let-выражений:
let x = obj in e;
s;
H
? e[ x / x]; s; H[ x > obj] , x – новое имя
Рис. 10.4: Синтаксис STG
В этом правиле мы добавляем в кучу новый объект obj под именем (или по адресу) x . Запись e[ x / x]
означает замену x на x в выражении e.
Теперь разберёмся с правилами для case-выражений.
case v of {. . . ; C x 1 . . . xn > e; . . . };
? e[ a 1/ x 1 . . . an/ xn]; s; H
s;
H[ v > CON ( C a 1 . . . an)]
case v of {. . . ; x > e};
s;
H
? e[ v/ x]; s; H
Если v – литерал или H[ v] – значение,
которое не подходит ни по одной из альтернатив
case e of {. . . };
s;
H
? e; case • of {. . . } : s; H
v;
case • of {. . . } : s;
H
? case v of {. . . }; s; H
Рис. 10.5: Синтаксис STG
Вычисления начинаются с третьего правила, в котором нам встречается case-выражения с произвольным
e. В этом правиле мы сохраняем в стеке альтернативы и адрес возвращаемого значения и продолжаем вы-
числение выражения e. После вычисления мы перейдём к четвёртому правилу, тогда мы снимем со стека
160 | Глава 10: Реализация Haskell в GHC
информацию необходимую для продолжения вычисления case-выражения. Это приведёт нас к одному из
первых двух правил. В первом правиле значение аргумента содержит конструктор, подходящий по одной из
альтернатив, а во втором мы выбираем альтернативу по умолчанию.
Теперь посмотрим как вычисляются THUNK-объекты.
x;
s;
H[ x > T HU N K e]
? e; Upd x • : s; H[ x > BLACKHOLE]
y;
U pd x • : s;
H
? y; s; H[ x > H[ y]]
если H[ y] является значением
Рис. 10.6: Синтаксис STG
Если переменная указывает на отложенное вычисление e, мы сохраняем в стеке адрес по которому
необходимо обновить значение и вычисляем значение e. В это время мы записываем в по адресу x объ-
ект BLACKHOLE. У нас нет такого правила, которое реагирует на левую часть, если в ней содержится
объект BLACKHOLE. Поэтому во время вычисления T HUNK ни одно из правил сработать не может.
Этот трюк необходим для избежания утечек памяти. Как только выражнение будет вычислено мы извлечём
из стека адрес x и обновим значение.
Правила применения функций, если арность совпадает с числом аргументов в тексте выражения:
f n a 1 . . . an;
s;
H[ y > F U N ( x 1 . . . xn > e)]
? e[ a 1/ x 1 . . . an/ xn]; s; H
? a 1 . . . an; s; H
? a; s; H
a – результат вычисления ( ? a 1 . . . an)
Рис. 10.7: Синтаксис STG
Мы просто заменяем все вхождения аргументов на значения. Второе правило выполняет применение
примитивной функции к значениям.
Правила для стратегии вставка-вход
f k a 1 . . . am;
s;
H
? f; Arg a 1 : … : Arg am : s; H
f ;
Arg a 1 : … : Arg an : s;
H[ f > F U N ( x 1 . . . xn > e)]
? e[ a 1/ x 1 . . . an/ xn]; s; H
f ;
Arg a 1 : … : Arg am : s;
H[ f > F U N ( x 1 . . . xn > e)]
? p; s; H[ p > P AP ( f a 1 . . . am)]
при m ? 1; m < n; верхний элемент s
не является Arg; p – новый адрес
f ;
Arg an+1 : s;
H[ f > P AP ( g a 1 . . . an)]
? g; Arg a 1 : … : Arg an : Arg an+1 : s; H
Рис. 10.8: Синтаксис STG
Первое правило выполняет этап “вставка”. Если мы видим применение функции, мы первым делом со-
храняем все аргументы в стеке. Во втором правиле мы вычислили значение f, оно оказалось функцией с
арностью n. Тогда мы добираем из стека n аргументов и подставляем их в правую часть функции e. Если
в стеке оказалось слишком мало аргументов, то мы переходим к третьему правилу и составляем частичное
применение. Последнее правило говорит о том как расшифровывается частичное применение. Мы вставляем
в стек все аргументы и начинаем вычисление функции g из тела P AP .
