-> 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). Вместе с функцией мы храним информацию о том, сколько аргу-
ментов ей нужно. Если это статически определённая функция (определение выписано пользователем),
то число аргументов мы можем понять по левой части определения. В этой стратегии, если число ар-
гументов известно, мы сразу вычисляем значение с нужным числом аргументов, сохранив оставшиеся
в стеке, а затем извлекаем аргументы из стека и применяем к ним вычисленное значение.