Теория вычислительных процессов (стр. 14 )

где ‑ массив, ‑ целое число, равное текущему значению счетчика .

На рисунке 1.11. приведены четыре схемы: стандартная (а), счетчиковая (б), магазинная (в) и схема с массивами (г). Все они эквивалентны друг другу и рекурсивной схеме:

F(x), F(x)=if p(x) then x else f(x, F(g(x))).

1.7.2 Трансляция обогащенных схем

Диаграмма на рисунке 1.12 дает полную информацию о возможности трансляции одного класса схем в другой, классы имеют следующие обозначения:

‑ стандартные схемы;	‑ магазинные схемы;
‑ рекурсивные схемы;	‑ схемы с массивами;
‑ счетчиковые схемы;	‑ схемы с процедурами.

Рис. 1.12 Диаграмма взаимной трансляции схем

Диаграмма показывает, что классы и являются универсальными в том смысле, что схемы всех других классов транслируемы в них. В то же время, в класс не транслируются схемы ни одного другого класса.

1.7.3 Структурированные схемы

Возрастающая сложность программ заставляет пересмотреть принципы организации программ, их структуру. Дейкстра первым высказался против неупорядоченного использования переходов на метки, которое может привести к переусложнению структуры программы, затрудняющему ее понимание. Реализуя концепцию так называемого структурированного программирования, он предложил отказаться от использования переходов и ограничиться более дисциплинирующими средствами управления вычислениями, такими, как условные операторы и операторы цикла.

Класс cтруктурированных схем определяется в том базисе , который был введен для ССП .

Различие между и проявляется на уровне структур схем. Вместо специальных символов вводятся специальные символы: if, then, else, while, do, end. Вместо инструкций с метками вводятся три типа схемных оператора в базисе : простой оператор, условный оператор и оператор цикла.

Простой оператор — это начальный (заключительный) оператор и оператор присваивания.

Условный оператор — это оператор вида

if p then s1 else s0 end,

где ‑ логическое выражение, ‑ последовательности (может быть, пустые) схемных операторов, среди которых нет ни начального, ни заключительного.

Операторы цикла имеют вид

while p do s end или until p do s end,

где имеют тот же смысл, что и выше.

Ниже приведен пример эквивалентных схем и .

Стандартная схема программ	Структурированная схема программ
start(х), 1:y :=f(x), 2:if p(y) then 7 else 3, 3:y:=f(y), 4:if p(y) then 5 else 7, 5:if p(x) then 6 else 7, 6:x:=h(x) goto 5, 7:stop(х, y).	start(х), y:=f(x), if p(y) then else y:=f(y), if p(x) then while p(x) do x:=h(x) end else end end, stop(х, y).

Доказано, что класс мощнее класса , т. е. схемы транслируемы в , но не наоборот.

Усилить класс можно за счет усложнения логических выражений в условных операторах и операторах цикла , введением символов логических операций NOT, OR, AND и атомарных формул, которыми являются логические выражения в старом смысле, например:

NOT p(x) AND q(y, x);

p(g(x, t)) OR q(h(x),x).

В этом случае справедлива теорема (Ашкрофт - Манн)

Класс стандартных схем транслируем в класс схем с логическими операциями

Контрольные вопросы

2 Семантическая теория программ

2.1 Описание смысла программ

Семантическая теория программ заниматься описанием семантики программ, или смысла выражений, операторов и программных единиц.

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

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

Задача определения семантики языка программирования рассматривается теоретиками давно, но до сих пор не найдено удовлетворительного универсального решения..

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

Операционная семантика, сводится к описанию смысла программы посредством выполнения ее операторов на реальной или виртуальной машине. Смысл оператора определяется изменениями, произошедшими в состоянии машины после выполнения данного оператора.

Пусть состояние компьютера ‑ это значения всех его регистров и ячеек памяти, в том числе коды условий и регистры состояний. Если просто записать состояние компьютера, выполнить команду, смысл которой нужно определить, а затем изучить новое состояние машины, то семантика этой команды станет понятной: она представляется изменением в состоянии компьютера, вызванным выполнением команды.

Описание операционной семантики операторов языков программирования высокого уровня требует создания реального или виртуального компьютера. Аппаратное обеспечение компьютера является чистым интерпретатором его машинного языка. Чистый интерпретатор любого языка программирования может быть создан с помощью программных средств, которые становятся виртуальным компьютером для данного языка. Семантику языка высокого уровня можно описать, используя чистый интерпретатор данного языка. При таком подходе существуют две проблемы. Во-первых, сложность и индивидуальные особенности аппаратного обеспечения компьютера и операционной системы, используемых для запуска чистого интерпретатора, затрудняют понимание происходящих действий. Во-вторых, выполненное таким образом семантическое определение будет доступно только для людей с абсолютно идентичной конфигурацией компьютера.

Этой проблемы можно избежать, заменив реальный компьютер виртуальным компьютером низкого уровня. Регистры, память, информация о состоянии и процесс выполнения операторов можно смоделировать, соответствующими программами. Набор команд можно создать так, чтобы семантику каждой отдельной команды было легко понять и описать. Таким образом, машина была бы идеализирована и значительно упрощена, что облегчило бы понимание изменений ее состояния.