Учебник по Haskell

ментов ей нужно. Если это статически определённая функция (определение выписано пользователем),

то число аргументов мы можем понять по левой части определения. В этой стратегии, если число ар-

гументов известно, мы сразу вычисляем значение с нужным числом аргументов, сохранив оставшиеся

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

Возвращаясь к исходному примеру, предположим, что арность функции f равна единице. Тогда страте-

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

Стратегия вычисление-применение сначала вычислит (f x), сохранив y на стеке, затем попробует приме-

нить результат к y. Почему мы говорим попробует? Может так случиться, что арность значения f x окажется

равным трём, но пока у нас есть лишь один аргумент, тогда мы создадим объект PAP, который соответствует

частичному применению.

Эти стратегии применимы как к ленивым, так и к энергичным языкам. Исторически сложилось, что лени-

вые языки тяготеют к первой стратегии, а энергичные ко второй. До недавнего времени и в GHC применялась

первая стратегия. Пока однажды разработчики GHC всё же не решили сравнить две стратегии. Реализовав

обе стратегии, и проверив их на большом количестве разных по сложности программ, они пришли к вы-

воду, что ни одна из стратегий не даёт существенного преимущества на этапе вычислений. Потребление

ресурсов оказалось примерно равным. Но вторая стратегия заметно выигрывала в простоте реализации. По-

дробнее об этом можно почитать в статье 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

Левая часть переходит в правую, при условии, что левая часть имеет определённый вид. Начнём с правил,

которые одинаковы и в той и в другой стратегии вычисления. Для простоты пока мы будем полагать, что

объекты только добавляются в кучу и никогда не стираются. Мы будем обозначать добавление в стек как