Учебник по Haskell

добавление элемента в обычный список: 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 .

Вычисление 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, тогда мы применяем аргументы к правой