-
Операционная семантика.
3.1.
Основные компоненты архитектуры: стеки
и «куча».
Множество
состояний стека
над множеством данных
есть
множество
кортежей
элементов
:
.
Пусть
– пустой кортеж («пустое» состояние
стека);
– конструктор нового состояния (операция
записи данного в стек),
.
Операция
чтения
данного из стека
определяется как
соответствующий
деструктор:
,
а операция
записи
в стек кортежа данных вводится рекурсивным
определением:
;
.
Пусть
– счетное множество «адресов». Множество
состояний памяти типа «куча» (над
множеством данных
и с множеством адресов
) есть множество всех функций из
в
с конечными графиками:
.
есть, вообще говоря, многозначное
отображение, описывающее «инициализацию»
новой ячейки памяти:
,
где
,
(
– «инициальное» значение), а для всех
;
– частично-определенная функция «записи»
данного в кучу: если
,
то
,
где
,
а для всех
;
– частично-определенная функция «чтения»
данного из кучи: если
,
то
.
Если
,
то
и
не определены.
3.2. Абстрактная FALGOL-машина. На рис. 1 представлена архитектура абстрактной FALGOL-машины. Ее основными компонентами, состояние которых передается от одного рабочего цикла к другому, являются
-
левый стек
над множеством данных
; -
память
типа
«куча» над множеством данных
и с множеством
натуральных чисел в качестве множества
адресов; -
п
равый
стек
над множеством данных
.
Остальные компоненты используются для временного хранения информации:
-
регистр
,
играющий роль регистра «команд»; в нем
размещается выполняемый элемент терма,
считываемый из правого стека. Так как
элементами могут быть и атомы, и
процедуры, то
включает и поле
для хранения натурального числа –
номера атома, и поле
для размещения тела элемента-процедуры
.
Это поле используется и как буфер при
обмене «данными» между другими
компонентами FALGOL-машины,
в которых могут храниться термы; -
регистр «адреса»
,
в который заносится число – адрес новой
ячейки в куче.
В
исходном состоянии FALGOL-машины
выполняемый терм
размещается в правом стеке:
,
в левом
стеке находятся «исходные данные»:
,
состояние
«кучи» (
)
представляет собой «среду» выполнения
терма
.
Начальное состояние FALGOL-машины
должно удовлетворять условию корректности:
.
Алгоритм
работы FALGOL-машины
описан в форме рекурсивной процедуры
на Pascal-подобном
языке. Результатами работы FALGOL-машины
являются заключительные состояния
левого стека (собственно результаты
вычислений) и кучи (побочный эффект);
выполнение программы завершается
безрезультатно, если в процессе работы
FALGOL-машины
предпринимается попытка чтения данного
из пустого левого стека. Возможен и
такой случай, когда выполнение программы
длится бесконечно долго; результат при
этом также не определен. Условие
корректности, во-первых, гарантирует,
что в процессе работы FALGOL-машины
не возникнет обращение для чтения или
записи к находящейся в некотором
состоянии
«куче» по адресу
и, во-вторых, обеспечивает уникальность
вновь выделяемых в «куче» адресов.
//
– выделенное в
инициальное значение. Например, в
качестве
// может быть выбран терм (см. дальше),
передача которого для выполне- //
ния
в правый стек приводит к «зацикливанию»
работы
машины.
[
]
//
[
]
обозначает
результат замены номера
на
номер
во всех // атомах терма
,
т.е.
замены
на
,
на
,
на
.
Нетрудно заметить, что
-
условие корректности сохраняется в процессе работы FALGOL-машины;
-
для любых состояний FALGOL-машины существует состояние кучи
,
наименьшее
относительно операции включения
состояний кучи, рассматриваемых как
графики, удовлетворяющее условию
корректности. При этом состояния ячеек
памяти с адресами, не принадлежащими
,
гарантированно
не
влияют на выполнение алгоритма работы
FALGOL-машины,
т.е. являются «мусором». В трансформационной
семантике уточняется понятие «мусора»,
учитывающее вводимые ниже определения
содержательных отношений между термами;
-
с точностью до выбора новых адресов-переменных при выполнении команд связывания (вариант
«команды»
)
процедура
вычисляет
функцию
,
в общем случае, частичную;
далее обозначает второй компонент
значения функции
.
Отметим
также, что структура термов отражает
традиционную для языков программирования
общего назначения «списковую» структуру
большинства программных объектов.
Интерпретация термов как программ, для
исполнения которых используется стек,
позволяет на синтаксическом уровне
трактовать последовательность элементов
терма как обратную польскую (суффиксная
бесскобочная) форму записи выражений.
При этом символы вызова значений
переменных и процедуры выступают как
операнды, т.е. символы арности
,
а символы присваивания – как символы
арности
,
а связывания – как символы арности
,
где
– арность конкретной процедуры, к
которой «применяется» связывание
переменной.
Наконец, самое главное – по своему духу FALGOL-машина является классической машиной фон-Неймана на новом уровне абстракции: все ее компоненты (регистры, ячейки памяти, уровни стеков, сама «куча» и сами стеки) имеют потенциально неограниченную информационную сложность. Действительно, интерпретация перемещающихся во всех направлениях информационных объектов (термов и их элементов) – как данных или как команд – зависит от того, в каком блоке FALGOL-машины они оказываются. Однако, дальнейшее развитие архитектуры FALGOL-машины, реализующей модель смешанных вычислений, естественно приводит FALGOL-машину к виду, который принято называть нетрадиционной, не фон-неймановской архитектурой.