Unknown - haskell-notes

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

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

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

применение. Последнее правило говорит о том как расшифровывается частичное применение. Мы вставляем