ПРЕДИСЛОВИЕ.
Пособие предназначено для студентов и преподавателей, специализирующихся в области разработки и реализации систем программирования. Может также представлять интерес для специалистов в области разработки системного программного обеспечения.Цель пособия - дать концептуальное понимание систем программирования, принципов их разработки и реализации на основе гибкого сочетания математического базиса теории программирования
С практическими подходами. Особое внимание уделяется методам компиляции.
Пособие представляет сокращенный вариант лекционного курса
"ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫТРАНСЛЯЦИИ", читаемого
для студентов факультета вычислительной математики и кибернетики
Казанского государственного университета в настоящее время автором
пособия.
ВВЕДЕНИЕ.
В начале 70-х годов идеологи применения математических моделей
в программировании Скотт и Стрэйчи (авторы целого ряда работ по
l-исчислению и денотационной семантике), работавшие в то время
в Оксфордском университе Великобритании,охарактеризовали в одной из своих публикаций текущее состояние разработок и исследований
по программному обеспечению следующим высказыванием.
… В настоящее время состояние, сложившееся в программировании, определяется достаточно большим разрывом между теорией и практикой. С одной стороны мы имеем достаточно изощренные средства математического моделирования, которые тем не менее
являются стерильными и совершенно непригодны для анализа и исследования практических разработок в области программирования.
С другой стороны имеется большое количество прагматически -
- ориентированных серых, громоздких и неуклюжих программных разработок, в которых отсутствует концептуальная целостность
и логическая взаимосвязь между составляющими частями. Поэтому главной задачей в этой связи является создание промежуточных теорий, которые сохраняя математическую строгость и лаконичность, позволили бы их использовать для предварительного анализа и исследования разрабатываемого программного продукта с целью получения эффективного и качественного результата.
Несмотря на то, что с тех пор прошло более 30 лет, ситуация в этом плане кардинально не изменилась. Революционные изменения в компьютерных технологиях и новых способах программирования, происшедшие за это время, наоборот еще более рельефнее высветили упомянутую выше проблему, правда на более высоком уровне развития.
Сложность и многообразие разрабатываемых программных средств,
увеличившиеся с тех пор на порядки, обусловили еще большую актуальность этапа предварительных исследований на основе адекватного математического моделирования разрабатываемого программного продукта. Следует признать, что в последнее время
появилось достаточно много результатов в области теории программирования и многие теоретические результаты нашли свое применение в практике программирования (это касается например разработки автоматизированных средств перевода с одних
естественных языков в другие, создания эффективных генераторов
компиляторов, практического использования теоретических результатов по синтезу программ для создания интеллектуальных генераторов программ в объектно-ориентированных средах программирования и т.п.).
Однако, с другой стороны, появившиеся в последнее десятиление
объектно-ориентированные системы программирования представляли
из себя продукт, основаный скорее на интуитивных аспектах программирования, нежели на теоретических. Несмотря на появление
языков моделирования для объектно -ориентированного подхода
(например UML - унифицированного языка моделирования), в настоящее время не существует теории, которая могла бы претендовать
на адекватное описание и анализ объектно-ориентированной среды программирования.
Поэтому методика изложения материала данного пособия основывается, насколько это возможно, на гибком сочетании теоретических аспектов программирования с прагматическими задачами.Кроме этого в пределах данного пособия ставится цель систематизировать полученные теоретические и практические результаты по системам программирования и методам реализации этих систем. Поэтому представляемый материал состоит из двух основных разделов. Первый посвящен классификации систем программирования с описанием различных методов программирования в разных системах. Во втором разделе предлагается материал по средствам реализации систем программирования, представленный теоретическими и практическими результатами по разработке компиляторов.
2.Системы программирования. Классификация и методы программирования.
2.1.Основные понятия и определения.
Системы программирования представляют одну из важнейших составляющих программного обеспечения компьютерных технологий.
|
|
|
|
|
программного обеспечения показано на рис. 2.1-1.
 |  | ||
Рис.2.1-1.Классификация программного обеспечения.
Система программирования определяется следующими составными частями: язык программирования,транслятор и интегрированная среда разработки.
Язык программирования - это формальный язык, предназначенный для
описания (кодирования) алгоритмов решения различных задач.
Транслятор - это программа, которая переводит текст исходной программы в эквивалентную объектную программу. Если объектный язык представляет собой ассемблер или некоторый машинный язык, то транслятор называется компилятором.
Интегрированная среда разработки -это библиотека сервисных программ, предназначенных для автоматизации процессов разработки,
программирования и отладки (понятие интегрированной среды
разработки возникло с появлением объектно-ориентированного программирования, однако в том или ином виде это понятие
присутствует также в процедурно-ориентированных системах программирования).
2.2. Классификация языков программирования.
Существует много разных способов классификации языков
программирования. Традиционно все это сводится к следующему.
Универсальные и проблемно-ориентированные языки
программирования. Язык программирования относится к универсальным языкам, если он обеспечивает возможность программирования широкого спектра задач. В случае ориентации на решение специализированного класса задач, мы имеем дело с проблемно-ориентированными языками программирования.
Языки высокого и низкого уровня. К языкам низкого уровня относятся
машинные языки и ассемблеры. Все остальные языки принято относить
к языкам высокого уровня. Однако необходимо иметь в виду наличие языков высокого уровня, в которые для удобства включены средства программирования низкого уровня. Примером является язык
программирования C.
Машинно- ориентированные и машинно - независимые языки
программирования. Языки программирования, зависящие от специфики определенного типа компьютеров, называются машинно-
- ориентированными. Все остальные относятся к машинно- независимым языкам.К машинно- ориентированным языкам традиционно принято относить машинные языки и ассемблеры. Однако из этого вовсе не следует, что все остальные языки программирования автоматически можно отнести к машинно-независимым языкам. Имеются языки программирования,в которых содержатся машинно-ориентированная и машинно- независимые части.
Операторные и функциональные языки программирования.
К операторным языкам программирования относится большинство
традиционных языков (PASCAL, C и т.п.), в которых имеются понятия
операторов и функций. В отличие от операторных, в функциональных
языках программирования отсутствует понятие оператора, а программа
строится в виде суперпозиции функций. Классическим примером
является функциональный язык программирования LISP.
Процедурно- ориентированные и объектно-ориентированные языки программирования. Процедурно- ориентированные языки
программирования основаны на традиционном подходе к созданию программного обеспечения, при котором основным строительным блоком является процедура или функция. При объектно-ориентированном подходе в качестве основного строительного блока в процессе программирования выступает объект, принадлежащий определенному классу (являющийся экземпляром определенного
класса). Содержательно класс можно рассматривать как некий абстрактный объект, наделяемый свойствами, характерными для некоторого множества объектов.
Языки компилируемого и интерпретируемого типов.Язык
программирования относится к языкам компилируемого типа, если в результате трансляции текста исходной программы получается объектная программа на ассемблере или на некотором машинном языке. Языки интерпретируемого типа предусматривают получение в результате трансляции так называемого промежуточного кода, выполнение которого осуществляется специальной программой, называемой интерпретатором. Иными словами, для языков интерпретируемого типа происходит частичная компиляция, завершаемая генерацией промежуточного кода. Например, язык LISP относится к языкам интерпретируемого типа, а язык PASCAL -к языкам компилируемого типа.
Замечания к разделу. Приведенная классификация никоим образом
не претендует на полноту, так как кроме приведенных выше типов языков, существуют языки логического программирования, языки параллельного программирования, языки управления базами данных,
языки искусственного интелекта и т.п.
2.3.Функциональные языки программирования.
Функциональное программирование -это способ составления
программ, в котором единственным действием является вызов функции,
единственным способом расчленения на части -введение имени для
функции и задание для этого имени выражения, вычисляющего
значение функции, единственным правилом композиции - суперпозиция функций. В этом разделе предлагаются элементы функционального программирования на основе языка программирования LISP. Раздел
никоим образом не претендует на руководство по программированию
на языке LISP, его цель - знакомство с основными принципами функционального стиля программирования. В предлагаемом ниже
изложении функционального стиля программирования в целях более прозрачного описания материала автор намеренно отходит в ряде
случаев от классической LISP- нотации, что по мнению автора
не затрагивает принципы функционального программирования.
Наиболее удачное изложение принципов функционального
программирования можно найти в книге [ 1 ].
2.3.1.Простейшие приемы программирования.
В основе функционального программирования лежит определение
функции в виде так называемого выражения l - выражения. Функция F
определяется следующим образом: F(x,y.z)=df lx,y,z. PF, где x,y,z -
аргументы, а PF -выражение, определяющее способ вычисления
функции F.
Замечание. Для определенности мы рассматриваем здесь функцию от
трех переменных. В общем случае функция может содержать любое
количество аргументов.
Примеры:
1) (n-факториал)
fact(n))=df ln. IF(n=0,1,n*fact(n-1))
2) (наибольший общий делитель)
gcd(m,n))=df lm,n.IF(mod(m,n)=0,n,gcd(n, mod(m,n))), где
mod(m,n) - остаток от деления m на n.
Замечания.
1) Функция IF(b,P,Q) определяется следующим образом:
ì P, если логическое выражение b истинно
IF(b,P,Q)= í
îQ, в противном случае.
2) В классической LISP-нотации функция записывается в виде (F,x,y,z,…), где F - имя функции (операции), x,y,z,…- аргументы, например (IF,b,P,Q),(MOD,m,n), (EQ, n,0) вместо n=0, (EQ,(MOD,m,n),0) вместо mod(m,n)=0, и т.п. Однако в целях удобства изложения будем использовать привычную математическую нотацию.
3) Основным признаком функционального стиля программирования
является рекурсивное определение функций, характеризуемое
"обращением самой к себе ". Умение "адекватно" программировать
рекурсивно определяемые алгоритмы требует хорошего представления
о специфике реализации рекурсии. В отличие от итерационного способа программирования выполнение рекурсивно определяемой программы
происходит в два этапа. На первом этапе осуществляется построение рекурсивных соотношений и частичное вычисление с задержкой
выполнения действий, которые не могут быть выполнены на данном
этапе.Задержка вычислений обусловливается тем, что в описании
рекурсивно определяемой функции всегда присутствует явное или
косвенное обращение к той же самой функции. Первый этап
завершается после выполнения так называемого условия завершения рекурсии. На втором этапе осуществляется полное завершение всех задержанных действий путем последовательного "сворачивания"
рекурсивных соотношений.Например, при реализации функции
вычисления факториала, если n=4, результатом первого этапа является следующая последовательность:
fact(4)=4*fact(3)
fact(3)=3*fact(2)
fact(2)=2*fact(1)
fact(1)=1*fact(0)
fact(0)=1.
Условием завершения рекурсии здесь является n=0. Сворачивание
рекурсивных соотношений на втором этапе происходит путем
выполнения соответствующих подстановок, в результате чего
получается соотношение: fact(4)=4*3*2*1.
4) В отличие от многих языков программирования в функциональных
языках программирования отсутствует строгое описание типов
переменных, предполагая, что тип переменной определяется в момент присваивания ей значения.
Упражнения к разделу.Запрограммировать следующие функции:
1) max(m,n) - максимальное из чисел m,n;
2) sum(n)=1+2+…+n;
3) exp(n,k)=nk -возвести в степень, используя умножение (k-целое);
4) sumexp(n)=11 + 22+ …+ nn;
2.3.2.Обработка списков.
Списком называется последовательность элементов, являющихся
атомами (т.е. неразложимыми данными) или, в свою очередь, списками.
Атомы представляются константами, именами переменных и функций.
Для обозначения пустого списка используется nil.
Примеры списков:
1) ("ДЖОН", "СМИТ",33,"ГОДА");
2) (x,(y,15),("A","B","C"))
5) () - пустой список (или nil);
6) (F,x,y)
2.3.2.1.Операции над списками.
Над списками определены следующие операции:
1) head(s) -первый (головной) элемент списка s (s ¹ nil);
2) tail(s) -список, получающийся из списка s удалением первого
элемента (tail(nil)= nil);
3) cons(a,s) -список, получающийся в результате добавления
элемента a в начало списка s;
4) ìtrue, если a - атом
atom(a)= í
îfalse, в противном случае.
Из перечисленных выше определений очевидным образом следует соотношение t= cons(a,s) ó head(t)= a & tail(t)=s.
Примеры.
1) Пусть s=(a,b,c), тогда
а) head(s)=a;
б) tail(s)= (b,c);
в) cons("d",s)=("d", a,b,c);
г) tail(tail(tail(s)))=nil;
д) atom(s)=false;
е) atom(head(s))=true.
2) Пусть s= ((a,b,c),d,(x,y)), тогда
а) head(s)= (a,b,c);
б) tail(s)= (d,(x,y));
в) cons((m,n),s) = ((m,n),(a,b,c),d,(x,y));
г) atom(head(head(s)))=true.
2.3.2.2.Примеры программ.
1) Нахождение максимального элемента числового списка s.
Сначала определим функцию max2(x,y), значением которой является максимальное из чисел x,y: max2(x,y))=df lx,y. IF(x>y,x,y).Теперь
функция нахождения максимального элемента списка может быть определена так:
max(s))=df ls.IF(tail(s)=nil, head(s), max2(head(s),max(tail(s)))).
2) Вычисление суммы всех элементов числового списка s.
sum(s))=df ls. IF(tail(s)=nil, head(s),head(s) + sum(tail(s))).
3) Удаление последнего элемента из списка s.
del(s) =df ls. IF(tail(s)=nil, nil, cons(head(s),del(tail(s))).
4) Определение семантики оператора while b do P.
while(b,P) =df ls. IF(b, cons(P, while(b,P)), nil).
Замечание. В отличие от операторных языков программирования в функциональных языках программирования отсутствует понятие
оператора и процедуры. Поэтому программистам, привыкшим к
операторному стилю, приходится сталкиваться с определенными
трудностями при программировании посредством функциональных
средств. Например, рекурсивное определение оператора while b do P
с точки зрения операторного стиля могло бы иметь следующий вид:
while b do P=df IF b then (P; while b do P). Однако отсутствие оператора
последовательной композиции в функциональном программировании
вынуждает нас заменить конструкцию (P; while b do P) на
cons(P, while(b,P)), где функция cons имеет чисто вспомогательную
роль и используется для соединения последовательно выполняемых
функций. С таким же успехом вместо функции cons мы могли бы
использовать любую 2-х местную функцию при условии корректного
согласования типов аргументов. Что же касается отсутствия процедур,
то известно, что любую процедуру можно определить посредством соответствующей эквивалентной функции.
Упражнения к разделу.
Запрограммировать следующие функции:
1) инвертирование списка (например, (a,b,c,d, e) => (e,d,c,b,a));
2) преобразование структурного списка в линейный, т.е. удаление
из списка всех внутренних скобок (например, ((a,b),c, (d, e)) =>
=>(a,b,c,d, e));
3) удаление из списка первых n-элементов (если n ³ числа элементов
списка, результат - nil);
4) удаление из списка последних n-элементов (если n ³ числа
элементов списка, результат - nil);
5) ìtrue, если s=t
Iseq(s,t)= í
îfalse, в противном случае, где s и t - списки.
2.3.2.3.Дополнительные средства функционального программирования.
Кроме перечисленных в предыдущих разделах средств, при
составлении функциональных программ нам необходимы средства
ввода -вывода, присваивания и т.п.. Эти средства представлены
следующими функциями:
1) input(s) - ввод переменной, получаемой в результате вычисления выражения s (s¹ nil);
2) output(s) - вывод результата вычисления выражения s;
3) setq(s1,s2) - присвоение результата вычисления выражения s2
переменной, которая получается в результате вычисления
выражения s1 (s1¹ nil);
4) apply(f,s) - применение функции с именем, получаемым в результате
вычисления выражения f, к списку аргументов, который является
результатом вычисления выражения s;
5) quote(s) - значением этой функции является само выражение s
(содержательно эта функция задерживает вычисление выражения s,
которое в данном случае рассматривается как константа);
6) eval(s) - значением этой функции является результат вычисления
выражения s (в частности, если вычисление выражения было
задержано функцией quote, функция eval позволяет отменить
задержку и вычислить значение соответствующего выражения);
7) list(s,t) - значением этой функции является список (s,t).
При использовании средств функционального программирования
следует учитывать, что функциональные программы, в свою очередь,
представляются в виде списков. Как уже было отмечено в р. 2.3.1,
функциональная программа вида F(x,y,…), где F - имя функции,
x,y,… -аргументы функции, представляется в виде списка (F, x,y,…).
Поэтому в необходимых случаях функциональные программы можно
рассматривать как данные, являющиеся объектом преобразования и обработки.Это свойство, сводящееся по сути к возможности
динамического изменения программы в процессе ее выполнения,
является весьма привлекательным с точки зрения создания
интеллектуальных программ.
Однако, с точки зрения технологии программирования использование
этой возможности является "правилом дурного тона ", посколько может привести к серьезным затруднениям при тестировании и отладке
программ.
Примеры.
1) Пусть s=(x,y), тогда:
а) input(head(s))=input(x) - ввод переменной x;
б) output(head(tail(s)))=output(y) -вывод переменной y;
в) setq(head(s), head(tail(s)))= setq(x,y) - переменной x присваивается
значение переменной y;
г) list(input(head(s)), setq(x,y)) = list(input(x), setq(y,x)) - сначала
вводится значение переменной x, затем переменной y
присваивается значение переменной x (функция list играет в этом
примере лишь вспомогательную роль, обеспечивая
соответствующую последовательность действий).
2) Пусть s=(cons, x, y) и t= ("b","c"), тогда:
а) apply(quote(head(s)),("a",t)) =apply(quote(cons), ("a",t))=cons("a",t)=
=cons("a",("b","c")) = ("a","b","c");
б) cons("a",(t)) = cons("a",(("b","c")))= ("a",("b","c"));
в) list("a",quote(t)) = ("a", t);
г) list("a",t) = ("a", ("b","c")).
Упражнения к разделу.Запрограммировать следующие операции над полиномами:
1) умножение полинома на одночлен;
2) умножение полинома на полином;
3) приведение подобных членов.
Указание: полином С1x1+ С2x2+…+Cnxn представляется в виде
списка: ((С1,1),(С2,x2),…,(Cn,xn)).
2.4. Спецификация, верификация и синтез программ. Основные понятия.
Процессу разработки любой программы всегда предшествует этап
постановки задачи на программирование.Успех разработки и
последующего внедрения программы во многом зависит от того,
насколько точно и хорошо было сделано описание соответствующей
задачи. Такое описание называют спецификацией задачи. Так как саму программу также можно рассматривать в качестве описания задачи, для решения которой она создана, возникает вопрос, чем же спецификация отличается от алгоритма решения задачи. Многие авторы полагают, что
спецификация в отличие от программы (алгоритма) должна описывать,
что надо сделать, а не как это делать, подчеркивая тем самым
непроцедурный характер спецификации. Однако задача может быть процедурной по своей природе и, кроме того, процедурность может быть высокого уровня, свободная от деталей реализации, которые должны обязательно присутствовать в любой работающей программе. В связи
с этим представляется более целесообразным говорить о процедурных
и непроцедурных спецификациях, имея в виду, что непроцедурные
спецификации, как правило, описывают постановку задачи,а
процедурные - способ ее решения. Часто процедурные спецификации называют программными спецификациями, но в отличие от самих
программ в программных спецификациях отсутствуют, как правило,
детали реализации.
Примеры спецификаций.
1) Максимум от чисел a и b:
ì a, если a>b
max(a,b) = í
î b, если a £ b.
2) Наибольший общий делитель натуральных чисел m и n:
ì n, если m mod n=0
gcd(m, n) = í
î gcd(n, m mod n), если m mod n¹ 0.
3) Максимальный элемент множества чисел M:
z=max(M) ó zÎ M & (" x.xÎM => z ³ x)
С понятием спецификации тесно связано понятие надежности
программы. Программа является надежной, если она разработана в
полном соответствии со своей спецификацией. Отсюда следует, что не
всякая надежная программа обязательно является правильной, так как
сама спецификация может содержать ошибки.Соответствие программы
ее спецификации проверяется тестированием.
Однако, позволяя выявить допущенные в программе ошибки, процесс тестирования не позволяет как правило обосновать их отсутствие.
В связи с этим в программировании возникло понятие верификации
программ. Под верификацией программы понимается процесс
формального доказательства ее корректности (надежности).
Предоставляя возможность доказательства отсутствия ошибок в
программе, методы верификации тем не менее не нашли применения в практическом программировании из-за их чрезмерной громоздкости и сложности. Однако, знание методов верификации является полезным
для разработчиков программ, так как эти методы позволяют более точно
и концептуально оценивать суть программирования и стимулируют
строгую и скрупулезную проверку всех промежуточных этапов процесса разработки программ.
Альтернативой верификациии является синтез программ,
заключающийся в автоматическом построении программы по ее
спецификации.Синтез является более привлекательным, нежели
верификация, поскольку в результате синтеза должны получаться
готовые корректные программы при условии корректной работы
"синтезатора". Разработка универсальных средств синтеза программ
относится к классу алгоритмически неразрешимых проблем, однако из
этого вовсе не следует, что использование синтеза программ на
практике обречено на неудачу. При определенном ограничении классов решаемых задач идея синтеза программ находит свое применение при создании генераторов программ.
Об этом свидетельствуют работы по созданию интегрированной
среды разработки современных объектно-ориентированных систем [2,3]. Реализация интегрированной среды разработки основывается на интеллектуальных генераторах программ, которые по сути можно
отнести к средствам синтеза программ.
При использовании спецификаций в разработке программ, а также
реализации интеллектуальных генераторов программ одной из основных
задач является выбор формализованного языка спецификаций и
установление соответствия между конструкциями языков спецификаций
и программирования. Это соответствие может устанавливаться путем
описания семантики базисных средств языка программирования
средствами языка спецификаций или наоборот. Рассмотрим один из
способов спецификации операторов языка программирования,
основанный на языке исчисления предикатов [4].
Введем понятие состояния программы через состояние переменных
программы, в свою очередь определяемого через таблицу значений переменных программы. Состояние программы представляет из себя динамически изменяемый объект в процессе выполнения программы,
которое может меняться в результате выполнения отдельной
программной конструкции (функции, оператора,модуля).
Пусть s={x,y,… } -состояние программы (состояние переменных) до
выполнения некоторой программной конструкции P, а
s'={x',y',…}- состояние программы после выполнения конструкции P.
Тогда для спецификации конструкции P мы можем использовать
предикат YP (s,s'), показывающий, как изменились значения
переменных x,y,… в результате выполнения конструкции P.
В дальнейшем,для простоты изложения материала, ограничимся рассмотрением только двух переменных x,y, полагая, что все
последующие рассуждения и выводы легко обобщаются на случай
любого числа переменных).
Тождественный оператор. Спецификация тождественного оператора
IDENT определяется как:
IDENT=df (x'=x) & (y'=y).
Из спецификации следует, что тождественный оператор оставляет неизменными все значения переменных.
Оператор присваивания. Пусть P- спецификация, x - программная
переменная и e- выражение, не содержащее штрихованных переменных
(т.е. переменных x',y'). Тогда выражение x:=e;P является спецификацией
программной конструкции, которая сначала присваивает переменной x
значение выражения e, затем выполняется в соответствии со
спецификацией P. Пусть (ex -> P) обозначает выражение, получаемое
из P путем замены всех свободных вхождений переменной x на e и
De -область определения выражения e. Тогда:
x:=e;P =df ù (De)Ú (ex -> P)
Примеры:
1) x:=x+y;IDENT = (x'=x+1&y'=y);
2) (y:=y/x; (x:=x+y;IDENT)) = (x=0) Ú (x'=x+y/x & y'=y/x)
Условный оператор. Пусть P и Q -спецификации и b - логическое
выражение, не содержащее штрихованных переменных. Тогда
выражение if b then P else Q является спецификацией программной конструкции, которая выполняется как P, если b -истинно, и как Q - в противном случае. Пусть Db -область определения выражения b. Тогда:
if b then P else Q=df ù (Db)Ú (b&P) Ú (ù b&Q)
Последовательная композиция. Пусть P - спецификация, содержащая переменную p, значением которой может быть любая допустимая спецификация. Тогда, если Q - некоторая спецификация, определим выражение (Qp ->>P) как соотношение, получаемое заменой всех
вхождений переменной p на Q в выражении P. Содержательно точки
вхождения переменной p в этом случае можно рассматривать как вызов
процедуры или функции со спецификацией Q. Важно отметить, что
данная операция подстановки (Qp ->>P) имеет более высокий приоритет,
нежели операция подстановки (ex -> P), то есть в любом случае:
Qp ->>(ex -> P)= (ex ->(Qp ->> P)).
Выделим специальную переменную SKIP для обозначения успешного завершения программной конструкции.
Пусть P и Q - некоторые специФикации, тогда последовательную композицию можно определить следующим образом:
P;Q =df QSKIP->>P.
Содержательно, выражение P;Q определяет программную конструкцию,
которая выполняется в соответствии со спецификацией P,
и после успешного завершения конструкции P выполняется в
соответствии со спецификацией Q. Например, в конструкции y:=y/x;
Q переход на выполнение Q может осуществиться только при x¹ 0.
Примеры:
1) if b then P = if b then P else SKIP
2) SKIP;P=P;SKIP=P
.
Оператор цикла "while". Спецификацию циклического оператора
определим рекурсивным образом:
while b do P=df if b then(P; while b do P) else SKIP,
где b -логическое выражение, а P - спецификация тела цикла.
Использование аппарата спецификаций оказывается более
эффективным, если, кроме описания семантики программ, имеется возможностьисследования их свойств. Исследование свойств программ
может быть сделано на основе алгебраических соотношений,
использование которых обеспечивает возможность эффективного и обоснованного перехода от спецификаций к соответствующим
программным конструкциям.
В исследовании свойств программ одним из важных аспектов является
семантическая эквивалентность программных конструкций.
Программные конструкции являются эквивалентными, тогда и только
тогда, когда их соответствующие спецификации - эквивалентны.
В данном случае мы рассматриваем логические спецификации, а для логических выражений понятие эквивалентности определено.
С содержательной точки зрения программы являются эквивалентными,
если они предназначены для решения одной и той же задачи.
Примеры соотношений:
1) Db => (if b then P else P) = P;
2) if b then P else Q = if ù b then Q else P;
3) x:=e; if b then P else Q = IF (ex -> b) then (x:=e; P) else (x:=e; Q);
4) SKIP;P=P;SKIP=P;
5) P; (Q; R) = (P; Q); R
Доказательства перечисленных выше свойств могут быть проделаны на
основе свойств исчисления предикатов (правил вывода) и
вышеприведенных определений спецификаций программных конструкций.
Ниже приводится перечень классических соотношений из
математической логики, являющихся полезными с точки зрения доказательства свойств:
1) P & P ó P;
2) (P Ú Q) ó ù (ù P & ù Q);
3) (P & Q) ó ù (ù P Ú ù Q);
4) (P & Q) ó (Q & P);
5) (P Ú Q) ó (Q Ú P);
6) ù (ù P) ó P;
7) (P Ú (Q &R)) ó (P Ú Q) & (P Ú R);
8) (P & (Q Ú R)) ó (P & Q) Ú (P & R);
9) (P ó Q) ó (P => Q) & (Q=>P);
10) P Ú TRUE ó TRUE;
11) P & TRUE ó P;
12) P Ú FALSE ó P;
13) P & FALSE ó FALSE;
14) ù (TRUE) ó FALSE;
15) ù (FALSE) ó TRUE;
Пример доказательства.
Доказать:
if b then P else Q = if ù b then Q else P.
Доказательство:
if b then P else Q =
=ù (Db)Ú (b&P) Ú (ù b&Q)= (по определению)
=ù (Db)Ú (ù b&Q) Ú (b&P))= (коммутативность)
= if ù b then Q else P (по определению)
2.5. Системы параллельного программирования.Теория
взаимодействующих процессов и ее использование для спецификации
и анализа параллельных процессов.
Появление систем параллельных вычислений было вызвано
необходимостью существенного увеличения скорости компьютерного решения задач. Появление многопроцессорных вычислительных комплексов, компьютерных сетей и многозадачных операционных систем, основанных на концепции мультипрограммирования, обеспечили реальную базу для практической реализации параллельных вычислений.Содержательно, идея параллельного программирования сводится к декомпозиции проблемы на несколько подзадач, которые выполняются одновременно. Средства связи между параллельно решаемыми задачами, предусматривающие взаимодействие между соответствующими процессами, обеспечивают кооперативное решение проблемы. Существуют разные модели параллелизма, но наиболее распостраненными являются так называемая конвейерная модель и модели параллелизма данных, основанные на одновременном применение одних и тех же операций к различным частям структуры данных. В настоящее время средства параллельного программирования практически встроены в большинство объектно- ориентированных систем управления базами данных. Задача разработки программных средств, обеспечивающих параллельное выполнение процессов, представляется достаточно сложной и поэтому требует построения адекватных математических моделей, позволяющих всесторонне исследовать природу параллельных процессов с целью принятия правильных решений по разработке и реализации алгоримов параллельных вычислений. К настоящему времени сформировалось множество разных подходов к выбору математического аппарата для исследования параллельных процессов. Один из наиболее интересных подходов, сочетающий математическую строгость и адекватность практической реализации, представляет теория взаимодействующих процессов CSP (Communicating Sequential Processes) [5].
Теория базируется на следующих ниже понятиях.
Событие - спецификация существенного факта, имеющего положение
в пространстве и во времени. С точки зрения теории автоматов событие- - это возникновение стимула, который может активизировать переход из одного состояния в другое. Событие является атомарным
(неразложимым понятием) теории CSP. Примерами событий могут быть
возникновение какой либо ошибки в процессе выполнении программ, выполнение определенного запланированного условия, выбор элемента меню, активация командной кнопки, нажатие функциональной клавиши и т.п.. Каждое событие кодируется определенным символом. Множество символов, опред<