Шпаргалка по "Программированию и компьютерам"

 

10. Обогащенные схемы

Выделяют следующие классы обогащенных схем: класс счетчиковых схем, класс магазинных схем, класс схем с массивами.

Классы счетчиковых и магазинных схем образован добавлением в базис ССП счетного множества счетчиков и магазинов с их интерпретированными операторами.

Счетчик — интерпретированная переменная, у которой областью значений является множество Nat; начальное значение счетчика равно 0.

Интерпретированные операторы имеют следующий вид:

c := c + 1 — оператор прибавления единицы;

c := c - 1  — оператор вычитания единицы;

c = 0 — условный оператор проверки равенства счетчика нулю.

При значении счетчика равном 0 оператор вычитания единицы не изменяет его, оно остается равным 0.

К интерпретированным операторам может быть добавлен оператор пересылки значения счетчика с₂ := с₁, который может быть получен при помощи стандартных операторов.

Рисунок 1.10

Магазин — неинтерпретированная переменная сложной структуры. В процессе выполнения интерпретированной схемы состояние магазина — это конечный набор элементов (d₁,d₂,…,d_n) из области интерпретации, где d_n — верхушка магазина.

Интерпретированные операторы имеют следующий вид:

М := x — запись в магазин;

х := М — выборка из магазина;

М = Æ — условный оператор проверки пустоты магазина,

где М – магазин, х — обычная переменная. Первый оператор меняет состояние (d₁,d₂,…,d_n) магазина М на состояние (d₁,d₂,…,d_n+1), где d_n+1 — значение переменной х. После выполнения этого оператора элемент d_n+1 становится новой верхушкой магазина. Второй оператор присваивает переменной х значение, равное верхушке магазина, состояние которого меняется с (d₁,d₂,…,d_n-1,d_n) на (d₁,d₂,…,d_n-1), при этом d_n.₁ становится новой верхушкой магазина. Если магазин М пуст, то применение второго оператора оставляет его пустым, а переменная х не меняет своего значения. Третий оператор— предикат проверки магазина на пустоту; если магазин пуст, то значение предиката М = 0 равно 1, в противном случае — 0.

Класс схем с массивами — это  расширение класса счетчиковых схем за счет добавления счетного множества массивов и операторов над ними.

Массив — неинтерпретированная переменная сложной структуры. При выполнении интерпретированной схемы состояние массива — бесконечная последовательность (d₁,d₂,…,d_i,…) элементов из области интерпретациии.

Интерпретированные операторы имеют следующий вид:

А[c]:= x — запись в магазин;

х:= А[c] — выборка из магазина,

где А — массив, [c] — целое число, равное текущему значению счетчика с.

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

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

 

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

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

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

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

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

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

if p then  s₁ else s₀ end,

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

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

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

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

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

Стандартная схема программ Y	Структурированная схема  программ Y(S)
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).

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

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

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

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

В этом случае справедлива

Теорема (Ашкрофт - Манн) Класс стандартных схем Y транслируем в класс схем с логическими операциями Y(SL).

 

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

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

Y — стандартные схемы;	Y(М) — магазинные схемы;
Y(R) — рекурсивные схемы;	Y(А) — схемы с массивами;
Y(с) — счетчиковые схемы;	Y(P) — схемы с процедурами.

Диаграмма показывает, что классы Y(М) и Y(А) являются универсальными в  том смысле, что схемы всех других классов транслируемы в них. В то же время, в класс Y не транслируются схемы ни одного другого класса. Следует отметить, что класс Y(с) достигает полной мощности при количестве счетчиков не менее 2, т.е. класс Y(с) с одним счетчиком равномощен классу Y.

 

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

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

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

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

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

Семантику конструкции for языка С можно описать в терминах следующих простых команд.

Пример 2.1. Оператор языка С    Операционная семантика

for (expr1; expr2; ехргЗ){    exrp1

...      loop: if expr2 = 0 goto out

}       …

ехргЗ;

goto loop

out:

Операционная семантика является эффективной до тех пор, пока описание языка остается простым и неформальным. К сожалению, описание VDL языка PL/I настолько сложно, что практическим целям оно фактически не служит.

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

 

14. Аксиоматическая семантика

Аксиоматическая семантика была создана в процессе разработки метода доказательства правильности программ. Данный метод распространяет на программы область применения исчисления предикатов. Семантику каждой синтаксической конструкции языка можно определить как некий набор аксиом или правил вывода, который можно использовать для вывода результатов выполнения этой конструкции. Чтобы понять смысл всей программы (то есть разобраться, что и как она делает), эти аксиомы и правила вывода следует использовать так же, как при доказательстве обычных математических теорем. В предположении, что значения входных переменных удовлетворяют некоторым ограничениям, аксиомы и правила вывода могут быть использованы для получения (вывода) ограничений на значения других переменных после выполнения каждого оператора программы. В конце концов, когда программа выполнена, мы получаем доказательство того, что вычисленные результаты удовлетворяют необходимым ограничениям на их значения относительно входных значений. То есть, доказано, что выходные данные представляют значения соответствующей функции, вычисленной по значениям входных данных.

Аксиоматическая семантика основана на математической логике.

 

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

Денотационная семантика - самый строгий широко известный метод описания значения программ. Она прочно опирается на теорию рекурсивных функций. Всестороннее рассмотрение денотационной семантики - длительное и сложное дело. Здесь мы познакомимся лишь с ее основными принципами.

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

Используя денотационную семантику можно описать очень простую языковую конструкцию - двоичные числа.

<двоичное_число> ->  0   |  1  | 

<двоичное_число> 0  | <двоичное_число> 1

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

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

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

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

 

16. Декларативная семантика

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