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

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

1. Введение.

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

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

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

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

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

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

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

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

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

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

Пусть . Тогда

, , , ;

;

.

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

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