языке не пишут программы, он предназначен для автоматической генерации кода. Далее из него получают
другие низкоуровневые коды. Возможна генерация C, LLVM и нативного кода (код, который исполняется
операционной системой).
10.2 Язык STG
STG расшифровывается как Spineless Tagless G-machine. G-machine или Г-машина – это низкоуровневое
описание процесса редукции графов (от Graph). Пока мы называли этот процесс редукцией синонимов.
Spineless и Tagless – это термины специфичные для G-машины, которая была придумана разработчиками
GHC. Tagless относится к особому представлению объектов в куче (объекты представлены единообразно, так
156 | Глава 10: Реализация Haskell в GHC
что им не нужен специальный тег для обозначения типа объекта), а Spineless относится к тому, что в от-
личие от машин-предшественников, которые описывают процесс редукции графов виде последовательности
инструкций, STG является небольшим функциональным языком. На (рис. ?? ) представлен синтаксис языка
STG. Синтаксис упрощён для чтения людьми. Несмотря на упрощения мы сможем посмотреть как происходит
вычисление выражений.
Переменные x, y, f, g
Конструкторы
C
Объявлены в определениях типов
Литералы
lit
::=
i | d
Незапакованные целые
или действительные числа
Атомы
a, v
::=
lit | x
Аргументы функций атомарны
Арность функции
k
::=
•
Арность неизвестна
|
n
Арность известна n ? 1
Выражения
e
::=
a
Атом
|
f k a 1 . . . an
Вызов функции ( n ? 1)
|
? a 1 . . . an
Вызов примитивной функции ( n ? 1)
|
let x = obj in e
Выделение нового объекта obj в куче
|
case e of {alt 1; . . . ; altn}
Приведение выражения e к СЗНФ
Альтернативы
alt
::=
C x 1 . . . xn > e
Сопоставление с образцом ( n ? 1)
|
x > e
Альтернатива по умолчанию
Объекты в куче
obj
::=
F U N ( x 1 . . . xn > e)
Функция арности n ? 1
|
P AP ( f a 1 . . . an)
Частичное применение f может
указывать только на F UN
|
CON ( C a 1 . . . an)
Полное применение конструктора ( n ? 0)
|
T HU N K e
Отложенное вычисление
|
BLACKHOLE
Используется только во время
выполнения программы
Программа
prog
::=
f 1= obj 1 ; . . . ; fn= objn
Рис. 10.2: Синтаксис STG
По синтаксису STG можно понять, какие выражения языка Haskell являются синтаксическим сахаром. Им
просто нет места в языке STG. Например, не видим мы сопоставления с образцом. Оно как и if-выражения
переписывается через case-выражения. Исчезли where-выражения. Конструкторы могут применяться толь-
ко полностью, то есть для применения конструктора мы должны передать ему все аргументы. В STG let—
выражения разделяют на не рекурсивные (let) и рекурсивные (letrec). Разделение проводится в целях оп-
тимизации, мы же будем считать, что эти случаи описываются одной конструкцией.
На что стоит обратить внимание? Заметим, что функции могут принимать только атомарные значения
(либо примитивные значения, либо переменные). В данном случае переменные указывают на объекты в куче.
Так если в Haskell мы пишем:
foldr f (g x y) (h x)
В STG это выражение примет вид:
let gxy = THUNK (g x y)
hx
= THUNK (h x)
in
foldr f gxy hx
У функций появились степени. Что это? Степени указывают на арность функции, то есть на количество
принимаемых аргументов. Количество принимаемых аргументов определяется по левой части функции. По-
скольку в Haskell функции могут возвращать другие функции, очень часто мы не можем знать арность, тогда
мы пишем •.
Отметим два важных принципа вычисления на STG:
• Новые объекты создаются в куче только в let-выражениях
• Выражение приводится к СЗНФ только в case-выражениях
Язык STG | 157
Выражение let a = obj in e означает добавь в кучу объект obj под именем a и затем вычисли e.
Выражение case e of~{alt1; … ;alt2} означает узнай конструктор в корне e и продолжи вычисления в
соответствующей альтернативе. Обратите внимание на то, что сопоставления с образцом в альтернативах
имеет только один уровень вложенности. Также аргумент case-выражения в отличие от функции не обязан
быть атомарным.
Для тренировки перепишем на STG пример из раздела про ленивые вычисления.
data Nat = Zero | Succ Nat
zero
= Zero
one
= Succ zero
two
= Succ one
foldNat :: a -> (a -> a) -> Nat -> a
foldNat z
s
Zero
= z
foldNat z
s
(Succ n)
= s (foldNat z s n)
add a = foldNat a
Succ
mul a = foldNat one (add a)
exp = (x -> add (add x x) x) (add Zero two)
Теперь в STG:
data Nat = Zero | Succ Nat
zero
= CON(Zero)
one
= CON(Succ zero)
two
= CON(Succ one)
foldNat = FUN( z s arg ->
case arg of
Zero
-> z
Succ n
-> let next = THUNK (foldNat z s n)
in
s next
)
add
= FUN( a ->
let succ = FUN( x ->
let r = CON(Succ x)
in r)
in
foldNat a succ
)
mul
= FUN( a ->
let succ = THUNK (add a)
in
foldNat one succ
)
exp
= THUNK(
let f = FUN( x -> let axx = THUNK (add x x)
in
add axx x)
a = THUNK (add Zero two)
in
f a
)
Программа состоит из связок вида имя = объектКучи. Эти связки называют глобальными, они становятся
статическими объектами кучи, остальные объекты выделяются динамически в let-выражениях. Глобальный
объект типа THUNK называют постоянной аппликативной формой (constant applicative form или сокращённо
CAF).
10.3 Вычисление STG
Итак у нас есть упрощённый функциональный язык. Как мы будем вычислять выражения? Присутствие
частичного применения усложняет этот процесс. Для многих функций мы не знаем заранее их арность. Так
например в выражении
158 | Глава 10: Реализация Haskell в GHC
f x y
Функция f может иметь один аргумент в определении, но вернуть функцию. Есть два способа вычисления
таких функций:
• вставка-вход (push-enter). Когда мы видим применение функции, мы сначала вставляем все аргументы
в стек, затем совершаем вход в тело функции. В процессе входа мы вычисляем функцию f и узнаём чис-
ло аргументов, которое ей нужно, после этого мы извлекаем из стека необходимое число аргументов, и
применяем к ним функцию, если мы снова получаем функцию, тогда мы опять добираем необходимое
число аргументов из стека. И так пока аргументы в стеке не кончатся.
• вычисление-применение (eval-apply). Вместе с функцией мы храним информацию о том, сколько аргу-
ментов ей нужно. Если это статически определённая функция (определение выписано пользователем),
то число аргументов мы можем понять по левой части определения. В этой стратегии, если число ар-
гументов известно, мы сразу вычисляем значение с нужным числом аргументов, сохранив оставшиеся
в стеке, а затем извлекаем аргументы из стека и применяем к ним вычисленное значение.
Возвращаясь к исходному примеру, предположим, что арность функции f равна единице. Тогда страте-
гия вставка-вход сначала добавит на стек x и y, а затем будет добирать из стека необходимые аргументы.
Стратегия вычисление-применение сначала вычислит (f x), сохранив y на стеке, затем попробует приме-
нить результат к y. Почему мы говорим попробует? Может так случиться, что арность значения f x окажется
равным трём, но пока у нас есть лишь один аргумент, тогда мы создадим объект PAP, который соответствует
частичному применению.
Эти стратегии применимы как к ленивым, так и к энергичным языкам. Исторически сложилось, что лени-
вые языки тяготеют к первой стратегии, а энергичные ко второй. До недавнего времени и в GHC применялась
первая стратегия. Пока однажды разработчики GHC всё же не решили сравнить две стратегии. Реализовав
обе стратегии, и проверив их на большом количестве разных по сложности программ, они пришли к вы-
