примитивной функции к значениям.
Правила для стратегии вставка-вход
f k a 1 . . . am;
s;
H
⇒ f; Arg a 1 : … : Arg am : s; H
f ;
Arg a 1 : … : Arg an : s;
H[ f → F U N ( x 1 . . . xn → e)]
⇒ e[ a 1/ x 1 . . . an/ xn]; s; H
f ;
Arg a 1 : … : Arg am : s;
H[ f → F U N ( x 1 . . . xn → e)]
⇒ p; s; H[ p → P AP ( f a 1 . . . am)]
при m ≥ 1; m < n; верхний элемент s
не является Arg; p – новый адрес
f ;
Arg an+1 : s;
H[ f → P AP ( g a 1 . . . an)]
⇒ g; Arg a 1 : … : Arg an : Arg an+1 : s; H
Рис. 10.8: Синтаксис STG
Первое правило выполняет этап “вставка”. Если мы видим применение функции, мы первым делом со-
храняем все аргументы в стеке. Во втором правиле мы вычислили значение f, оно оказалось функцией с
арностью n. Тогда мы добираем из стека n аргументов и подставляем их в правую часть функции e. Если
в стеке оказалось слишком мало аргументов, то мы переходим к третьему правилу и составляем частичное
применение. Последнее правило говорит о том как расшифровывается частичное применение. Мы вставляем
в стек все аргументы и начинаем вычисление функции g из тела P AP .
Вычисление STG | 161
f • a 1 . . . an;
s;
H[ f → F U N ( x 1 . . . xn → e)]
⇒ e[ a 1/ x 1 . . . an/ xn]; s; H
f k a 1 . . . am;
s;
H[ f → F U N ( x 1 . . . xn → e)]
⇒ e[ a 1/ x 1 . . . an/ xn]; ( • an+1 . . . am) : s; H
при m ≥ n
⇒ p; s; H[ p → P AP ( f a 1 . . . am)]
при m < n, p – новый адрес
f • a 1 . . . am;
s;
H[ f → T HU N K e]
⇒ f; ( • a 1 . . . am) : s; H
f k an+1 . . . am;
s;
H[ f → P AP ( g a 1 . . . an)]
⇒ g• a 1 . . . an an+1 . . . am; s; H
f ;
( • a 1 . . . an) : s;
H
⇒ f• a 1 . . . an; s; H
H[ f ] является F U N или P AP
Рис. 10.9: Синтаксис STG
Правила для стратегии вычисление-применение
Разберёмся с первыми двумя правилами. В первом правиле статическая арность f неизвестна, но зна-
чение f уже вычислено, и мы можем узнать арность по объекту F UN, далее возможны три случая. Число
аргументов переданных в функцию совпадает с арностью F UN, тогда мы применяем аргументы к правой
части F UN. Если в функцию передано больше аргументов чем нужно, мы сохраняем лишние на стеке. Если
же аргументов меньше, то мы создаём объект P AP . Третье правило говорит о том, что нам делать, если зна-
чение f ещё не вычислено. Оно является T HUNK. Тогда мы сохраним аргументы на стеке и вычислим его.
В следующем правиле мы раскрываем частичное применение. Мы просто организуем вызов функции со все-
ми аргументами (и со стека и из частичного применения). Последнее правило срабатывает после третьего.
Когда мы вычислим T HUNK и увидим там F UN или P AP . Тогда мы составляем применение функции.
Сложность применения стратегии вставка-вход связана с плохо предсказуемым изменением стека. Если в
стратегии вычисление-выполнение мы добавляем и снимаем все аргументы, то в стратегии вставка-вход мы
добавляем их по одному и неизвестно сколько снимем в следующий раз. Кроме того стратегия вычисление-
применение позволяет проводить оптимизацию перемещения аргументов. Вместо стека мы можем хранить