ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ. Теория вычислительных процессов
 Скачать 2.17 Mb.
|
|
Структурированные схемы Возрастающая сложность программ привлекает все большее внимание к проблемам технологии программирования. Технологические соображения заставили, в первую очередь, пересмотреть принципы организации программ, их структуру. Дейкстра первым высказался против неупорядоченного использования переходов на метки, которое может привести и фактически приводит к переусложнению структуры программы, затрудняющему ее понимание и декомпозицию на более простые фрагменты. Реализуя концепцию так называемого структурированного программирования, он предложил, отказаться от использования переходов и ограничиться более дисциплинирующими средствами управления вычислениями, такими, как условные операторы и операторы цикла. Класс cтруктурированных схем Y(S) определяется в том же (полном) базисе В, который был введен для ССП Y. Различие между Y и Y(S) проявляется на уровне структур схем. Вместо специальных символов Y вводятся специальные символы: if , then, else, while, do, end. Вместо инструкций с метками вводятся три типа схемных оператора в базисе В: простой оператор, условный оператор и оператор цикла. Простой оператор — это начальный (заключительный) оператор и оператор присваивания. Условный оператор — это оператор вида if then 1 else 0 end, где — логическое выражение, 1, 0 — последовательности (может быть, пустые) операторов, среди которых нет ни начального, ни заключительного. Операторы цикла имеют вид while do end или until do end, где , имеют тот же смысл, что и выше. Ниже приведен пример эквивалентных схем Y и Y(S).
Структурированные программы универсальны в том смысле, что набора предоставленных им средств достаточно для описания любой вычислимой функции. Задача автоматического преобразования стандартных схем в структурированные имеет отрицательное решение. Доказано, что класс 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). Основные выводы и результаты Вместо понятия правильности программы следует использовать понятие надежности программы. Тезис Тьюринга: каждая функция, для которой существует алгоритм нахождения ее значений, представима некоторой машиной Тьюринга, т. е. является вычислимой. Теорема Тьюринга: Проблема остановки машины Тьюринга неразрешима. Из приведенных утверждений следует, что существуют вычислимые и невычислимые функции. ССП позволяет исследовать только структурные свойства программ, интерпретация ССП определяет семантику вычислений. Протокол выполнения программы – ценное средство отладки программ. Программа останавливается тогда и только тогда, когда протокол ее выполнения конечен. В противном случае программа зацикливаетсяи результат ее выполнения не определен. Теорема Лакхэма – Парка – Паттерсона: Стандартные схемы S1 и S2 в базисе В функционально эквивалентны тогда и только тогда, когда они функционально эквивалентны на множестве всех свободных интерпретаций базиса В. Из логико-терминальной эквивалентности следует функциональная эквивалентность. Обратное утверждение не верно. Для одноленточного конечного автомата доказано, что проблемы пустоты и эквивалентности разрешимы. Для двухголовочнного конечного автомата проблемы пустоты и эквивалентности не являются частично разрешимыми. По заданному двоичному двухголовочному конечному автомату возможно построить ССП и наоборот, что позволяет решить задачу разрешимости (не разрешимости) свойств ССП. Теоремы Лакхэма - Парка – Паттерсона: Проблема пустоты, свободы, функциональной эквивалентности стандартных схем не является частично разрешимой. Проблема тотальности стандартных схем частично разрешима. Вычисление рекурсивной программы может завершиться за конечное число шагов с результатом, равным значению запрограммированной функции для заданных аргументов, но может и продолжаться бесконечно. Классы ССП транслируемы друг в друга. Теорема Ашкрофта – Манна: Класс стандартных схем транслируем в класс схем с логическими операциями. СЕМАНТИЧЕСКАЯ ТЕОРИЯ ПРОГРАММ Описание смысла программ Существует несколько причин, по которым следует заниматься описанием семантики программ, или смысла выражений, операторов и программных единиц. Руководство по использованию языка программирования должно включать описание каждой конструкции языка, как по отдельности, так и в совокупности с другими конструкциями. В языке имеется множество различных конструкций, точное определение которых необходимо как программисту, использующему язык, так и разработчику реализации этого языка. Программисту эти сведения нужны для того, чтобы писать правильные программы и заранее знать результат выполнения любых операторов программы. Разработчику компилятора корректные определения конструкций необходимы для создания правильной реализации языка. В большинстве руководств определение семантики дается в виде обычного текста. Как правило, сначала при помощи какой-либо формальной грамматики дается определение синтаксиса конструкции, а затем для пояснения семантики приводятся несколько примеров и небольшой пояснительный текст. К сожалению, смысл этого текста часто неоднозначен, так что разные читатели могут понимать его по-разному. Программист может получить ошибочное представление о том, что именно будет делать написанная им программа при выполнении, а разработчик может реализовать какую-либо языковую конструкцию иначе, чем разработчики других реализаций того же языка. Как и для синтаксиса, нужен какой-то метод, позволяющий дать удобочитаемое, точное и лаконичное определение семантики языка. Задача определения семантики языка программирования рассматривается теоретиками давно, но до сих пор не найдено удовлетворительного универсального решения. Было разработано множество различных методов формального определения семантики. Ниже приводится описания некоторых из них. Операционная семантика Операционная семантика, сводится к описанию смысла программы посредством выполнения ее операторов на реальной или виртуальной машине. Смысл оператора определяется изменениями, произошедшими в состоянии машины после выполнения данного оператора. Для того чтобы разобраться в этой концепции, рассмотрим команду на машинном языке. Пусть состояние компьютера - это значения всех его регистров и ячеек памяти, в том числе коды условий и регистры состояний. Если просто записать состояние компьютера, выполнить команду, смысл которой нужно определить, а затем изучить новое состояние машины, то семантика этой команды станет понятной: она представляется изменением в состоянии компьютера, вызванным выполнением команды. Описание операционной семантики операторов языков программирования высокого уровня требует создания реального или виртуального компьютера. Аппаратное обеспечение компьютера является чистым интерпретатором его машинного языка. Чистый интерпретатор любого языка программирования может быть создан с помощью программных средств, которые становятся виртуальным компьютером для данного языка. Семантику языка высокого уровня можно описать, используя чистый интерпретатор данного языка. При таком подходе, правда, существуют две проблемы. Во-первых, сложность и индивидуальные особенности аппаратного обеспечения компьютера и операционной системы, используемых для запуска чистого интерпретатора, затрудняют понимание происходящих действий. Во-вторых, выполненное таким образом семантическое определение будет доступно только для людей с абсолютно идентичной конфигурацией компьютера. Этой проблемы можно избежать, заменив реальный компьютер виртуальным компьютером низкого уровня. Регистры, память, информация о состоянии и процесс выполнения операторов - все это можно смоделировать, соответствующими программами. Набор команд можно создать так, чтобы семантику каждой отдельной команды было легко понять и описать. Таким образом, машина была бы идеализирована и значительно упрощена, что облегчило бы понимание изменений ее состояния. Использование операционного метода для полного описания семантики языка программирования L требует создания двух компонентов. Во-первых, для преобразования языка L в операторы выбранного языка низкого уровня нужен транслятор. Во-вторых, для этого языка низкого уровня необходима виртуальная машина, состояние которой изменяется с помощью команд, полученных при трансляции операторов высокого уровня. Именно изменения состояния этой виртуальной машины определяет смысл данного оператора. Семантику конструкции for языка С можно описать в терминах следующих простых команд. Пример 2.1.Оператор языка С Операционная семантика for (expr1; expr2; ехрr3)expr1 {loop:if expr2 = 0 goto out ...… } ехрr3; gotoloop out: Человек, читающий подобное описание, является «виртуальным компьютером» и предполагается способным правильно «выполнить» команды описания и распознать эффект такого «выполнения». В качестве примера низкоуровневого языка, который можно применять для операционной семантики, рассмотрим следующий список операторов, соответствующих простым управляющим операторам типичного языка программирования: ident := var ident := ident - 1 goto label if var relop var goto label Здесь relop - одни из операторов отношений из набора {= , <>, >, <, >=, <=}, ident - идентификатор, a var - идентификатор или константа. Все эти операторы просты и легки для понимания и реализации. Незначительное обобщение приведенных выше трех операторов присваивания позволяет описывать более общие арифметические выражения и операторы присваивания. Например: ident := varbin_op var ident := un_op var Здесь bin_op - бинарный арифметический оператор, a un_op - унарный оператор. Многочисленные арифметические типы данных и автоматическое преобразование типов, конечно, несколько усложняют это обобщение. Введение небольшого количества новых относительно простых команд позволит описывать семантику массивов, записей, указателей и подпрограмм. Описание операционной семантики функций рассмотрим на примере системы равенств: f1(x1, x2, ... , xk) = E1, f2(x1, x2, ... , xk) = E2, fm(x1, x2, ... , xk) = Em, . . . . . . . . . . . . .(2.1) где в левых частях равенств явно указаны определяемые функции с формальными параметрами, включающими обозначения всех входных данных x1, x2, ... , xk, а правые части представляют собой выражения, содержащие, вообще говоря, вхождения этих функций с аргументами, задаваемыми некоторыми выражениями, зависящими от входных данных x1, x2, ... , xk. Операционная семантика интерпретирует эти равенства как систему подстановок. Под подстановкой <s, E, > терма в выражение E вместо символа s (в частности, переменной) будем понимать переписывание выражения E с заменой каждого вхождения в него символа s на выражение . Каждое равенство fi(x1, x2, ... , xk) = Ei задает в параметрической форме множество правил подстановок: <x1, x2, ... , xk; fi(1, 2, ... , k) → Ei; 1, 2, ... , k> где 1, 2, ... , k - конкретные аргументы (значения или определяющие их выражения) данной функции. Это правило допускает замену вхождения левой его части в какое-либо выражение на его правую часть. Интерпретация системы равенств (2.1) для получения значений определяемых функций в рамках операционной семантики производится следующим образом. Пусть задан набор входных данных (аргументов) d1, d2,... ,dk. На первом шаге осуществляется подстановка этих данных в левые и правые части равенств с выполнением там, где это возможно, предопределенных операций и с выписыванием получаемых в результате этого равенств. На каждом следующем шаге просматриваются правые части полученных равенств. Если правая часть является каким-либо значением, то оно и является значением функции, указанной в левой части этого равенства. В противном случае правая часть является выражением, содержащим вхождения каких-либо определяемых функций с теми или иными наборами аргументов. Если для такого вхождения соответствующая функция с данным набором аргументов имеется в левой части какого-либо из полученных равенств, то либо вместо этого вхождения подставляется вычисленное значение правой части этого равенства, либо не производится никаких изменений. В том же случае, если эта функция с данным набором аргументов не является левой частью никакого из полученных равенств, то формируется (и дописывается к имеющимся) новое равенство. Оно получается из исходного равенства для данной функций подстановкой в него вместо параметров указанных аргументов этой функции. Такие шаги осуществляются до тех пор, пока все определяемые функции не будут иметь вычисленные значения. Пример 2.2. Рассмотрим систему равенств, определяющую функцию FACT(n) = n! FACT(0) = 1, FACT(n) = n  FACT(n-1).Для вычисления значения FACT(3) осуществляются следующие 6 шагов. 1-й шаг:2-й шаг:3-й шаг: FACT(0) = 1FACT(0) = 1FACT(0) = 1 FACT(3) = 3 FACT(2).FACT(3) = 3FACT(2)FACT(3) = 3FACT(2) FACT(2) = 2 FACT(1).FACT(2)= 2FACT(1)FACT(1)= 1 FACT(0).4-й шаг:5-й шаг: 6-й шаг: FACT(0) = 1 FACT(0) = 1FACT(0) = 1 FACT(3) = 3 FACT(2) FACT(3) = 3FACT(2)FACT(3) = 6FACT(2) = 2 FACT(1) FACT(2) = 2FACT(2) = 2FACT(1) = 1.FACT(1) = 1. FACT(1) = 1. Первым и самым значительным использованием формальной операционной семантики было описание семантики языка PL/I. Эта абстрактная машина и правила трансляции языка PL/I были названы общим именем ViennaDefinitionLanguage(VDL) в честь города, в котором они были созданы корпорацией IBM. Операционная семантика является эффективной до тех пор, пока описание языка остается простым и неформальным. К сожалению, описание VDL языка PL/I настолько сложно, что практическим целям оно фактически не служит. Операционная семантика зависит от алгоритмов, а не от математики. Операторы одного языка программирования описываются в терминах операторов другого языка программирования, имеющего более низкий уровень. Этот подход может привести к порочному кругу, когда концепции неявно выражаются через самих себя. Методы, описываемые в следующих двух разделах, значительно более формальны в том смысле, что они опираются на логику и математику, а не на машины. |