Core – это функциональный язык программирования, который является сильно урезанной версией
Haskell. Помните мы говорили, что в Haskell поддерживается несколько стилей (композиционный и декла-
ративный). Что хорошо для программиста, не очень хорошо для компилятора. Компилятор устраняет весь
синтаксический сахар и выражает все определения через простейшие конструкции языка Core. Далее проис-
ходит серия оптимизаций языка Core. На дереве описания программы выполняется серия функций типа Core
-> Core. Например происходит замена вызовов коротких функций на их правые части урвнений (встраивание
или inlining), выражения, которые проводят декомпозицию в case-выражениях по константам, заменяются
на соответствующие этим константам выражения. По требованию GHC может провести анализ строгости
(strictness analysis). Он заключается в том, что GHC ищет аргументы функций, которые могут быть вычисле-
ны более эфективно с помощью вычисления по значению и расставляет анотации строгости. И многие многие
другие оптимизации кода. Все они представлены в виде преобразования синтаксического дерева программы.
Также этот этап называют упрощением программы.
После этого Core переводится на STG. Это функциональный язык, повторяющий Core. Он содержит допол-
нительную информацию, которая необходима низкоуровневым бибилиотекам на этапе вычисления програм-
мы. Затем из STG генерируется код языка C–. Это язык низкого уровня, “портируемый ассемблер”. На этом
языке не пишут программы, он предназначен для автоматической генерации кода. Далее из него получают
другие низкоуровневые коды. Возможна генерация 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 и продолжи вычисления в