Лекция на тему FALGOL - теоретическая модель языков программирования высокого уровня (Лекция на тему FALGOL – теоретическая модель языков программирования высокого уровня)

FALGOL – ТЕОРЕТИЧЕСКАЯ МОДЕЛЬ

ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ

1. Введение.

В разделе 2 описан синтаксис языка . Семантика языка уточняется несколькими способами – в формах операционной, денотационной и трансформационной семантик. Операционная семантика (раздел 3) представлена описанием абстрактной -машины, основными компонентами которой являются два стека – левый стек, данные для которого представляют собой записи -программ, правый стек, данными для которого являются отдельные инструкции (элементы программ), а также память типа «куча », единицами хранения для которой также являются записи программ. В параграфе 3.1 уточнены средства доступа к этим компонентам -машины, а в параграфе 3.2 описана архитектура и алгоритм работы -машины, реализующей выполнение -программ. В разделе 4 определена денотационная семантика языка путем определения отношений содержательного включения, содержательной эквивалентности и содержательной несравнимости -программ. В разделе 5 приводятся правила эквивалентных преобразований (трансформационная семантика) формул языка , не противоречащих введенной денотационной семантике. Большинство из этих преобразований носит направленный характер, что позволяет определить процесс вычислений как процесс преобразований формулы к нормальной форме, в которой уже невозможно направленное применение этих правил. В разделе 6 рассматривается частный случай модели – со статическим связыванием – и его расширение атомарными константами.

1. Синтаксис языка .

Пусть , и – счетные множества атомов трех видов. Символ назовем вызовом значения -ой переменной, – присваиванием значения -ой переменной, а – связыванием -ой переменной.

Множество -термов (далее просто термов) определяется как множество списков на множестве атомов , то есть как множество любых конечных последовательностей (кортежей) элементов термов: , где . Элемент вида назовем процедурой, а терм – ее телом.

Так как термы – списки, то индуктивные определения различных понятий для термов удобно давать рассмотрением случаев: 1) пустого списка , 2) одноэлементного списка с элементом-атомом, 3) одноэлементного списка с элементом-процедурой и 4) конкатенации (сцепления) двух списков.

Введем понятие контекста. Синтаксически контекст определяется как терм, в котором в качестве одного из атомарных подтермов используется символ  – «дырка». Пусть – множество всевозможных контекстов. Результат замены в контексте «дырки» на будем обозначать как : если – терм, то результатом замены будет терм, если – контекст, то результатом замены будет тоже контекст.

Далее приводятся индуктивные определения понятий:

• множества номеров переменных терма ,

• множества номеров свободно используемых переменных терма ,

• множества номеров свободно изменяемых переменных терма .

Пусть . Тогда

, , , ;

;

.

Определение 1. Терм называется замкнутым, если . Множество всех замкнутых термов обозначим .

Определение 2. Нуль-термом назовем терм , такой, что   . далее обозначает множество всех нуль-термов.

1. Операционная семантика.

3.1. Основные компоненты архитектуры: стеки и «куча». Множество состояний стека над множеством данных есть множество кортежей элементов : . Пусть – пустой кортеж («пустое» состояние стека); – конструктор нового состояния (операция записи данного в стек), . Операция чтения данного из стека определяется как соответствующий деструктор: , а операция записи в стек кортежа данных вводится рекурсивным определением: ; .

Пусть – счетное множество «адресов». Множество состояний памяти типа «куча» (над множеством данных и с множеством адресов ) есть множество всех функций из в с конечными графиками: . есть, вообще говоря, многозначное отображение, описывающее «инициализацию» новой ячейки памяти: , где , ( – «инициальное» значение), а для всех ; – частично-определенная функция «записи» данного в кучу: если , то , где , а для всех ; – частично-определенная функция «чтения» данного из кучи: если , то . Если , то и не определены.

3.2. Абстрактная FALGOL-машина. На рис. 1 представлена архитектура абстрактной FALGOL-машины. Ее основными компонентами, состояние которых передается от одного рабочего цикла к другому, являются

• левый стек над множеством данных ;

• память типа «куча» над множеством данных и с множеством натуральных чисел в качестве множества адресов;

• п
  равый стек над множеством данных .

Остальные компоненты используются для временного хранения информации:

• регистр , играющий роль регистра «команд»; в нем размещается выполняемый элемент терма, считываемый из правого стека. Так как элементами могут быть и атомы, и процедуры, то включает и поле для хранения натурального числа – номера атома, и поле для размещения тела элемента-процедуры . Это поле используется и как буфер при обмене «данными» между другими компонентами FALGOL-машины, в которых могут храниться термы;

• регистр «адреса» , в который заносится число – адрес новой ячейки в куче.

В исходном состоянии FALGOL-машины выполняемый терм размещается в правом стеке: , в левом стеке находятся «исходные данные»: , состояние «кучи» ( ) представляет собой «среду» выполнения терма . Начальное состояние FALGOL-машины должно удовлетворять условию корректности:

      .

Алгоритм работы FALGOL-машины описан в форме рекурсивной процедуры на Pascal-подобном языке. Результатами работы FALGOL-машины являются заключительные состояния левого стека (собственно результаты вычислений) и кучи (побочный эффект); выполнение программы завершается безрезультатно, если в процессе работы FALGOL-машины предпринимается попытка чтения данного из пустого левого стека. Возможен и такой случай, когда выполнение программы длится бесконечно долго; результат при этом также не определен. Условие корректности, во-первых, гарантирует, что в процессе работы FALGOL-машины не возникнет обращение для чтения или записи к находящейся в некотором состоянии «куче» по адресу и, во-вторых, обеспечивает уникальность вновь выделяемых в «куче» адресов.

// – выделенное в инициальное значение. Например, в качестве // может быть выбран терм (см. дальше), передача которого для выполне- // ния в правый стек приводит к «зацикливанию» работы машины.

[ ]

// [ ] обозначает результат замены номера на номер во всех // атомах терма , т.е. замены на , на , на .

Нетрудно заметить, что

• условие корректности сохраняется в процессе работы FALGOL-машины;

• для любых состояний FALGOL-машины существует состояние кучи , наименьшее относительно операции включения состояний кучи, рассматриваемых как графики, удовлетворяющее условию корректности. При этом состояния ячеек памяти с адресами, не принадлежащими , гарантированно не влияют на выполнение алгоритма работы FALGOL-машины, т.е. являются «мусором». В трансформационной семантике уточняется понятие «мусора», учитывающее вводимые ниже определения содержательных отношений между термами;

• с точностью до выбора новых адресов-переменных при выполнении команд связывания (вариант «команды» ) процедура вычисляет функцию , в общем случае, частичную; далее обозначает второй компонент значения функции .

Отметим также, что структура термов отражает традиционную для языков программирования общего назначения «списковую» структуру большинства программных объектов. Интерпретация термов как программ, для исполнения которых используется стек, позволяет на синтаксическом уровне трактовать последовательность элементов терма как обратную польскую (суффиксная бесскобочная) форму записи выражений. При этом символы вызова значений переменных и процедуры выступают как операнды, т.е. символы арности , а символы присваивания – как символы арности , а связывания – как символы арности , где – арность конкретной процедуры, к которой «применяется» связывание переменной.

Наконец, самое главное – по своему духу FALGOL-машина является классической машиной фон-Неймана на новом уровне абстракции: все ее компоненты (регистры, ячейки памяти, уровни стеков, сама «куча» и сами стеки) имеют потенциально неограниченную информационную сложность. Действительно, интерпретация перемещающихся во всех направлениях информационных объектов (термов и их элементов) – как данных или как команд – зависит от того, в каком блоке FALGOL-машины они оказываются. Однако, дальнейшее развитие архитектуры FALGOL-машины, реализующей модель смешанных вычислений, естественно приводит FALGOL-машину к виду, который принято называть нетрадиционной, не фон-неймановской архитектурой.

1. Денотационная семантика.

Денотационная семантика FALGOLа определяется в форме некоторых отношений на множестве термов – содержательного включения, содержательной эквивалентности и содержательной несравнимости. Приведенные ниже определения этих отношений не являются конструктивными; и, как станет понятным далее, проблема содержательной эквивалентности термов вообще является алгоритмически неразрешимой.

Определение 3.Терм содержательно включает терм (обозначается ), если

.