аргументы. Мы сохраняем и извлекаем их все сразу. Упрощая, объекты стека можно представить так:
k
::=
case • of {alt 1; . . . altn}
контекст case-выражения
|
U pd t •
Обновить отложенное вычисление
|
( • a 1 ...an)
Применить функцию к аргументам, только для
стратегии вычисление-применение
|
Arg a
Аргумент на потом, только для
стратегии вставка-вход
Рис. 10.3: Синтаксис STG
Правила общие для обеих стратегий вычисления
Состояние вычислителя состоит из трёх частей. Это выражение для вычисления e, стек s и куча H. Мы
рассмотрим правила по которым вычислитель переходит из одного состояния в другое. Все они имеют вид:
e 1;
s 1;
H 1
⇒ e 2; s 2; H 2
Левая часть переходит в правую, при условии, что левая часть имеет определённый вид. Начнём с правил,
которые одинаковы и в той и в другой стратегии вычисления. Для простоты пока мы будем полагать, что
объекты только добавляются в кучу и никогда не стираются. Мы будем обозначать добавление в стек как
добавление элемента в обычный список: elem : s.
Рассмотрим правило для let-выражений:
let x = obj in e;
s;
H
⇒ e[ x / x]; s; H[ x → obj] , x – новое имя
Рис. 10.4: Синтаксис STG
В этом правиле мы добавляем в кучу новый объект obj под именем (или по адресу) x . Запись e[ x / x]
означает замену x на x в выражении e.
Теперь разберёмся с правилами для case-выражений.
case v of {. . . ; C x 1 . . . xn → e; . . . };
⇒ e[ a 1/ x 1 . . . an/ xn]; s; H
s;
H[ v → CON ( C a 1 . . . an)]
case v of {. . . ; x → e};
s;
H
⇒ e[ v/ x]; s; H
Если v – литерал или H[ v] – значение,
которое не подходит ни по одной из альтернатив
case e of {. . . };
s;