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)