ние утечек памяти.
Мы будем считать, что куча – это таблица, которая ставит в соответствие адресам объекты или вычис-
ленные значения.
Вычисление 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, оно оказалось функцией с