Учебник по Haskell

Арность неизвестна

|

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). Вместе с функцией мы храним информацию о том, сколько аргу-