Unknown - haskell-notes

letgxy = THUNK(g x y)

hx

= THUNK(h x)

in

foldr f gxy hx

У функций появились степени. Что это? Степени указывают на арность функции, то есть на количество

принимаемых аргументов. Количество принимаемых аргументов определяется по левой части функции. По-

скольку в Haskell функции могут возвращать другие функции, очень часто мы не можем знать арность, тогда

мы пишем • .

Отметим два важных принципа вычисления на STG:

• Новые объекты создаются в куче только в let-выражениях

• Выражение приводится к СЗНФ только в case-выражениях

Язык STG | 157

Выражение leta =obj ine означает добавь в кучу объект obj под именем a и затем вычисли e.

Выражение casee of~{alt1; ...;alt2} означает узнай конструктор в корне e и продолжи вычисления в

соответствующей альтернативе. Обратите внимание на то, что сопоставления с образцом в альтернативах

имеет только один уровень вложенности. Также аргумент case-выражения в отличие от функции не обязан

быть атомарным.

Для тренировки перепишем на STG пример из раздела про ленивые вычисления.

data Nat = Zero | Succ Nat

zero

= Zero

one

= Succzero

two

= Succone

foldNat ::a ->(a ->a) -> Nat ->a

foldNat z

s

Zero

=z

foldNat z

s

( Succn)

=s (foldNat z s n)

add a =foldNat a

Succ

mul a =foldNat one (add a)

exp =(\x ->add (add x x) x) (add Zerotwo)

Теперь в STG:

data Nat = Zero | Succ Nat

zero

= CON( Zero)

one

= CON( Succzero)

two

= CON( Succone)

foldNat = FUN( z s arg ->

casearg of

Zero

->z

Succn

-> letnext = THUNK(foldNat z s n)

in

s next

)

add

= FUN( a ->

letsucc = FUN( x ->

letr = CON( Succx)

inr)

in

foldNat a succ

)

mul

= FUN( a ->

letsucc = THUNK(add a)

in

foldNat one succ

)

exp

= THUNK(

letf = FUN( x -> letaxx = THUNK(add x x)

in

add axx x)

a = THUNK(add Zerotwo)

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 окажется