Программирование
Программа как описание процесса обработки данных. Неконструктивность понятия правильной программы. Надежность программного средства. Технология программирования как технология разработки надежных программных средств. Интеллектуальные возможности.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 26.12.2008 |
| Размер файла | 168,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
В независимой от пользователя разработке требования к ПС определяются без какого-либо участия пользователя (на полную ответственность разработчика). Это происходит обычно тогда, когда разработчик решает создать ПС широкого применения в расчете на то, разработанное им ПС найдет спрос на рынке программных средств.
С точки зрения обеспечения надежности ПС наиболее предпочтительным является контролируемая пользователем разработка.
3. Спецификация качества программного средства
Разработка спецификации качества сводится, по существу, к построению своеобразной модели качества разрабатываемой ПС [2, 3]. В этой модели должен быть перечень всех тех достаточно элементарных свойств, которые требуется обеспечить в разрабатываемом ПС и которые в совокупности образуют приемлемое для пользователя качество ПС. При этом каждое из этих свойств должно быть в достаточной степени конкретизировано с учетом определения требований к разрабатываемому ПС и возможности оценки его наличия у разработанного ПС или необходимой степени обладания им этим ПС.
Для конкретизации качества ПС по каждому из критериев используется стандартизованный набор достаточно простых свойств ПС [3, 4, 5, 6], однозначно интерпретируемых разработчиками. Такие свойства мы будем называть примитивами качества ПС. Некоторые из примитивов могут использоваться по нескольким критериям. Ниже приводится зависимость критериев качества от примитивов качества ПС.
Функциональность: завершенность.
Надежность: завершенность, точность, автономность, устойчивость, защищенность.
Легкость применения: П-документированность, информативность (только применительно к документации по применению), коммуникабельность, устойчивость, защищенность.
Эффективность: временнaя эффективность, эффективность по памяти, эффективность по устройствам.
Сопровождаемость. С данным критерием связано много различных примитивов качества. Однако их можно распределить по двум группам, выделив два подкритерия качества: изучаемость и модифицируемость. Изучаемость -- это характеристики ПС, которые позволяют минимизировать усилия по изучению и пониманию программ и документации ПС. Модифицируемость -- это характеристики ПС, которые упрощают внесение в него необходимых изменений и доработок.
Изучаемость: С-документированность, информативность (здесь применительно и к документации по сопровождению), понятность, структурированность, удобочитаемость.
Модифицируемость: расширяемость, структурированность, модульность.
Мобильность: независимость от устройств, автономность, структурированность, модульность.
Ниже даются определения используемых примитивов качества ПС [3, 4, 5].
Завершенность -- свойство, характеризующее степень обладания ПС всеми необходимыми частями и чертами, требующимися для выполнения своих явных и неявных функций.
Точность -- мера, характеризующая приемлемость величины погрешности в выдаваемых программами ПС результатах с точки зрения предполагаемого их использования.
Автономность -- свойство, характеризующее способность ПС выполнять предписанные функции без помощи или поддержки других компонент программного обеспечения.
Устойчивость -- свойство, характеризующее способность ПС продолжать корректное функционирование, несмотря на задание неправильных (ошибочных) входных данных.
Защищенность -- свойство, характеризующее способность ПС противостоять преднамеренным или нечаянным деструктивным (разрушающим) действиям пользователя.
П-документированность -- свойство, характеризующее наличие, полноту, понятность, доступность и наглядность учебной, инструктивной и справочной документации, необходимой для применения ПС.
Информативность -- свойство, характеризующее наличие в составе ПС информации, необходимой и достаточной для понимания назначения ПС, принятых предположений, существующих ограничений, входных данных и результатов работы отдельных компонент, а также текущего состояния программ в процессе их функционирования.
Коммуникабельность -- свойство, характеризующее степень, в которой ПС облегчает задание или описание входных данных, а также обеспечивает выдачу полезных сведений в форме и с содержанием, простыми для понимания.
Временнaя эффективность -- мера, характеризующая способность ПС выполнять возложенные на него функции за определенный отрезок времени.
Эффективность по памяти -- мера, характеризующая способность ПС выполнять возложенные на него функции при определенных ограничениях на используемую память.
Эффективность по устройствам -- мера, характеризующая экономичность использования устройств машины для решения поставленной задачи.
С-документировапнность -- свойство, характеризующее с точки зрения наличия документации, отражающей требования к ПС и результаты различных этапов разработки данной ПС, включающие возможности, ограничения и другие черты ПС, а также их обоснование.
Понятность -- свойство, характеризующее степень в которой ПС позволяет изучающему его лицу понять его назначение, сделанные допущения и ограничения, входные данные и результаты работы его программ, тексты этих программ и состояние их реализации. Этот примитив качества синтезирован нами из таких примитивов ИСО [4.4], как согласованность, самодокументированность, четкость и, собственно, понятность.
Структурированность -- свойство, характеризующее программы ПС с точки зрения организации взаимосвязанных их частей в единое целое определенным образом (например, в соответствии с принципами структурного программирования).
Удобочитаемость -- свойство, характеризующее легкость восприятия текста программ ПС (отступы, фрагментация, формативность).
Расширяемость -- свойство, характеризующее способность ПС к использованию большего объема памяти для хранения данных или расширению функциональных возможностей отдельных компонент.
Модульность -- свойство, характеризующее ПС с точки зрения организации его программ из таких дискретных компонент, что изменение одной из них оказывает минимальное воздействие на другие компоненты.
Независимость от устройств -- свойство, характеризующее способность ПС работать на разнообразном аппаратном обеспечении (различных типах, марках, моделях ЭВМ).
4. Функциональная спецификация программного средства
С учетом назначения функциональной спецификации ПС и тяжелых последствий неточностей и ошибок в этом документе, функциональная спецификация должна быть математически точной. Это не означает, что она должна быть формализована настолько, что по ней можно было бы автоматически генерировать программы, решающие поставленную задачу. А означает лишь, что она должна базироваться на понятиях, построенных как математические объекты, и утверждениях, однозначно понимаемых разработчиками ПС. Достаточно часто функциональная спецификация формулируется на естественном языке. Тем не менее, использование математических методов и формализованных языков при разработке функциональной спецификации весьма желательно, поэтому этим вопросам будет посвящена отдельная лекция.
Функциональная спецификация состоит из трех частей:
· описания внешней информационной среды, к которой должны применяться программы разрабатываемой ПС;
· определение функций ПС, определенных на множестве состояний этой информационной среды (такие функции будем называть внешними функциями ПС);
· описание нежелательных (исключительных) ситуаций, которые могут возникнуть при выполнении программ ПС, и реакций на эти ситуации, которые должны обеспечить соответствующие программы.
В первой части должны быть определены на концептуальном уровне все используемые каналы ввода и вывода и все информационные объекты, к которым будет применяться разрабатываемое ПС, а также существенные связи между этими информационными объектами. Примером описания информационной среды может быть концептуальная схема базы данных или описание сети датчиков и приборов, которой должна управлять разрабатываемая ПС.
Во второй части вводятся обозначения всех определяемых функций, специфицируются все входные данные и результаты выполнения каждой определяемой функции, включая указание их типов и заданий всех соотношений (или ограничений), которым должны удовлетворять эти данные и результаты. И, наконец, определяется семантика каждой из этих функций, что является наиболее трудной задачей функциональной спецификации ПС. Обычно эта семантика описывается неформально на естественном языке - примерно так, как это делается при описании семантики многих языков программирования. Эта задача может быть в ряде случаев существенно облегчена при достаточно четком описании внешней информационной среды, если внешние функции задают какие-либо манипуляции с ее объектами.
В третьей части должны быть перечислены все существенные с точки зрения внешнего наблюдателя (пользователя) случаи, когда ПС не сможет нормально выполнить ту или иную свою функцию (например, при обнаружении ошибки во время взаимодействия с пользователем, или при попытке применить какую-либо функцию к данным, не удовлетворяющим соотношениям, указанным в ее спецификации, или при получении результата, нарушающего заданное ограничение). Для каждого такого случая должна быть определена (описана) реакция ПС.
5. Методы контроля внешнего описания программного средства
Разработка внешнего описания обязательно должна завершаться проведением тщательного и разнообразного контроля правильности внешнего описания. Целью этого процесса является найти как можно больше ошибок, сделанных на этом этапе. Учитывая, что результатом этого этапа является, как правило, еще неформализованный текст, то здесь на первый план выступают психологические факторы контроля. Можно выделить следующие методы контроля, применяемые на этом этапе:
· статический просмотр,
· смежный контроль,
· пользовательский контроль,
· ручная имитация.
Первый метод предполагает внимательное прочтение текста внешнего описания разработчиком с целью проверка его полноты и непротиворечивости, а также выявления других неточностей и ошибок.
Смежный контроль спецификации качества сверху -- это её проверка со стороны разработчика требований к ПС, а смежный контроль функциональной спецификации -- это её проверка разработчиками требований к ПС и спецификации качества. Смежный контроль внешнего описания снизу -- это его изучение и проверка разработчиками архитектуры ПС и текстов программ, а также разработчиками документации по применению и разработчиками комплекта тестов.
Пользовательский контроль внешнего описания выражает участие пользователя (заказчика) в принятии решений при разработке внешнего описания и его контроле. Если разработка требований к ПС велась под управлением пользователя, то пользовательский контроль внешнего описания, по существу, означает его смежный контроль сверху. Однако, если представителю пользователя оказывается трудно самостоятельно разобраться во внешнем описании, создается специальная группа разработчиков, выполняющая роль пользователя (и взаимодействующая с ним) для проведения такого контроля.
Ручная имитация выражает своеобразный динамический контроль внешнего описания, точнее говоря, функциональной спецификации ПС. Для этого необходимо подготовить исходные данные (тесты) и на основании функциональной спецификации осуществить имитацию поведения (работы) разрабатываемого ПС. При этом эту имитацию осуществляет специально назначенный разработчик, выполняющий, по существу, роль будущих программ ПС. Разновидностью такого контроля является имитация за терминалом. В этом случае данные вводятся в компьютер человеком, играющего роль пользователя, и передаются с помощью несложной программы на другой терминал, за которым сидит разработчик, выполняющий роль программ ПС. Полученные результаты передаются через компьютер на первый терминал.
ЛИТЕРАТУРА
Ian Sommerville. Software Engineering. -- Addison-Wesley Publishing Company, 1992.
Г.Майерс. Надежность программного обеспечения. -- М.: Мир, 1980. с. 49-77.
Е.А. Жоголев. Введение в технологию программирования (конспект лекций). -- М.: «ДИАЛОГ-МГУ», 1994.
Criteria for Evalution of Software. -- ISO TC97/SC7 #383.
Revised version of DP9126 -- Criteria for Evalution of Software Quality Characteristics. -- ISO TC97/SC7 #610. -- Part 6.
Б. Боэм, Дж. Браун, Х. Каспар и др. Характеристики качества программного обеспечения. -- М.: Мир, 1981.
ЗАМОК ДРАКОНА
Все, что вообще может быть сказано, должно быть сказано ясно, а о чем невозможно говорить, о том следует молчать.
Л. Витгенштейн
Лекция 5.
МЕТОДЫ СПЕЦИФИКАЦИИ СЕМАНТИКИ ФУНКЦИЙ
Основные подходы к спецификации семантики функций. Табличный подход, метод таблиц решений. Алгебраический подход: операционная, денотационная и аксиоматическая семантика.
1. Основные подходы к спецификации семантики функций
Для спецификации семантики функций используются следующие подходы: табличный, алгебраический и логический (1), а также графический (5.2).
Табличный подход для определения функций хорошо известен еще со средней школы. Он базируется на использовании таблиц. В программировании эти методы получили развитие в методе таблиц решений.
Алгебраический подход базируется на использовании равенств для определения функций. В этом случае для определения некоторого набора функций строится система равенств вида:
L1 = R1,
(1) .………..
Ln = Rn.
где Li и Ri, i = 1, ..., n, некоторые выражения, содержащие предопределенные операции, константы, переменные, от которых зависят определяемые функции (формальные параметры этих функций), и вхождения самих этих функций. Семантика определяемых функций извлекается в результате интерпретации этой системы равенств. Эта интерпретация может производиться по-разному (базироваться на разных системах правил), что порождает разные семантики. В настоящее время активно исследуются операционная, денотационная и аксиоматическая семантики.
Третий подход, логический, базируется на использовании предикатов -- функций, аргументами которых могут быть значения различных типов, а результатами которых являются логические значения (ИСТИНА и ЛОЖЬ). В этом случае набор функций может определяться с помощью системы предикатов. Заметим, что система равенств алгебраического подхода может быть задана с помощью следующей системы предикатов:
РАВНО(L1, R1),
(2) ……………….
РАВНО(Ln, Rn),
где предикат РАВНО истинен, если равны значения первого и второго его аргументов. Это говорит о том, что логический подход располагает большими возможностями для определения функций, однако он требует от разработчиков ПС умения пользоваться методами математической логики, что, к сожалению, не для всех коллективов разработчиков оказывается приемлемым. Более подробно этот подход в нашем курсе лекций мы рассматривать не будем.
Графический подход также известен еще со средней школы. Но в данном случае речь идет не о задании функции с помощью графика, хотя при данном уровне развития компьютерной техники ввод в компьютер таких графиков возможен и они могли бы использоваться (с относительно небольшой точностью) для задания функций. В данном случае речь идет о графическом задании различных схем, выражающих сложную функцию через другие функции, связанными с какими-либо компонентами заданной схемы. Графическая схема может определять ситуации, когда для вычисления представляемой ею функции должны применяться связанные с этой схемой более простые функции. Графическая схема может достаточно точно и формализовано определять часть семантики функции. Примером такой схемы может быть схема переходов состояний конечного автомата, такая, что в каждом из этих состояний должна выполняться некоторая дополнительная функция, указанная в схеме.
2. Метод таблиц решений
Метод таблиц решений базируется на использовании таблиц следующего вида (см. Табл. 1).
Верхняя часть этой таблицы определяет различные ситуации, в которых требуется выполнять некоторые действия (операции). Каждая строка этой части задаёт ряд значений некоторой указанной переменной или некоторого указанного условия в первом поле (столбце) этой строки. Таким образом, первый столбец этой части представляет собой список переменных или условий, от значений которых зависит выбор определяемых ситуаций. В каждом следующем столбце указывается комбинация значений этих переменных (условий), определяющая конкретную ситуацию. При этом последний столбец определяет ситуацию, отличную от предыдущих, т.е. для любых других комбинаций значений (будем обозначать их звездочкой *), отличных от первых, определяется одна и та же, (m+1)-ая, ситуация. Впрочем, в некоторых таблицах решений этот столбец может отсутствовать. Эта часть таблицы решений аналогична соответствующей части таблицы, определяющей какую-либо функцию обычным способом - в ней задаются комбинации значений аргументов функции, которым ставится в соответствие значения этой функции.
Табл. 1. Общая схема таблиц решений
|
Переменные / условия |
Ситуации (комбинации значений) |
|||||
|
x1 |
a1,1 |
a1,2 |
... |
a1,m |
* |
|
|
x2 |
a2,1 |
a2,2 |
... |
a2,m |
* |
|
|
.….. |
.…………………………………………. |
|||||
|
xn |
an,1 |
an,2 |
... |
an,m |
* |
|
|
S1 |
u1,1 |
u1,2 |
... |
u1,m |
u1,m+1 |
|
|
S2 |
u2,1 |
u2,2 |
... |
u2,m |
u1,m+1 |
|
|
.….. |
.………………………………………… |
|||||
|
s1k |
uk,1 |
uk,2 |
... |
uk,m |
uk,m+1 |
|
|
Действия |
Комбинации выполняемых действий |
Нижняя часть таблицы решений определяет действия, которые требуется выполнить в той или иной ситуации, определяемой в верхней части таблицы решений. Она также состоит из нескольких (k) строк, каждая из которых связана с каким-либо одним конкретным действием, указанным в первом поле (столбце) этой строки. В остальных полях (столбцах) этой строки (т.е., для ui j, i = 1, ..., m+1, j = 1, ..., k) указывается, следует ли (ui,j = '+') выполнять это действие в данной ситуации или не следует (ui,j = '-'). Таким образом, первый столбец нижней части этой таблицы представляет собой список обозначений действий, которые могут выполняться в той или иной ситуации, определяемой этой таблицей. В каждом следующем столбце этой части указывается комбинация действий, которые следует выполнить в ситуации, определяемой в том же столбце верхней части таблицы решений. Для ряда таблиц решений эти действия могут выполняться в произвольном порядке, но для некоторых таблиц решений этот порядок может быть предопределен, например, в порядке следования соответствующих строк в нижней части этой таблицы.
Табл. 2. Таблица решений «Светофор у пешеходной дорожки».
|
Условия |
Ситуации |
||||||||
|
Состояние светофора |
? |
? |
? |
? |
? |
? |
? |
? |
|
|
T = Tкр |
Нет |
Нет |
Да |
* |
* |
* |
* |
* |
|
|
T = Tжёл |
* |
* |
* |
Нет |
Да |
* |
* |
* |
|
|
T > Tзел |
* |
* |
* |
* |
* |
Нет |
Да |
Да |
|
|
Появление привилегированной машины |
Нет |
Да |
* |
* |
* |
* |
Нет |
Да |
|
|
Включить ? |
- |
- |
- |
- |
- |
- |
+ |
- |
|
|
Включить ? |
- |
+ |
+ |
- |
- |
- |
- |
- |
|
|
Включить ? |
- |
- |
- |
- |
+ |
- |
- |
- |
|
|
T := 0 |
- |
+ |
+ |
- |
+ |
- |
+ |
- |
|
|
T := T+1 |
+ |
- |
- |
+ |
- |
+ |
- |
+ |
|
|
Освобождение пешеходной дорожки |
- |
- |
- |
+ |
- |
- |
- |
- |
|
|
Пропуск пешеходов |
+ |
+ |
+ |
- |
- |
- |
- |
- |
|
|
Пропуск машин |
- |
- |
- |
- |
- |
+ |
+ |
+ |
|
|
Действия |
Комбинации выполняемых действий |
Рассмотрим в качестве примера описание работы светофора у пешеходной дорожки. Переключение светофора в нормальных ситуациях должно производиться через фиксированное для каждого цвета число единиц времени (Tкр -- для красного цвета, Tжёл -- для жёлтого, Tзел -- для зелёного). У светофора имеется счетчик таких единиц. При переключении светофора в счетчике устанавливается 0. Работа светофора усложняется необходимостью пропускать привилегированные машины (об их появлении на светофор поступает специальный сигнал) с минимальной задержкой, но при обеспечении безопасности пешеходов. Приведенная на Табл. 2 таблица решений описывает работу такого светофора и порядок движения у него в каждую единицу времени. Звездочка (*) в этой таблице означает произвольное значение соответствующего условия.
3. Операционная семантика
В операционной семантике алгебраического подхода к описанию семантики функций рассматривается следующий частный случай системы равенств (1):
f1(x1, x2, ..., xk) = E1,
f2(x1, x2, ..., xk) = E2,
(3) .........……………
fn(x1, x2, ... , xk) = En,
где в левых частях равенств явно указаны определяемые функции с формальными параметрами, включающими (для простоты) обозначения всех входных данных x1, x2, ..., xk, а правые части представляют собой выражения, содержащие, вообще говоря, вхождения этих функций с аргументами, задаваемыми некоторыми выражениями, зависящими от входных данных x1, x2, ..., xk.
Операционная семантика интерпретирует эти равенства как систему подстановок. Под подстановкой
| s E | | T
выражения (терма) T в выражение E вместо символа s (в частности, переменной) будем понимать переписывание выражения E с заменой каждого вхождения в него символа s на выражение T. Каждое равенств
fi(x1, x2, ..., xk) = Ei
задает в параметрической форме множество правил подстановок вида
|x1, x2, ..., xkfi(T1, T2, ..., Tk) -> Ei | |T1, T2, ..., Tk
где T1, T2, ..., TK -- конкретные аргументы (значения или определяющие их выражения) данной функции. Это правило допускает замену вхождения левой его части в какое-либо выражение на его правую часть.
Интерпретация системы равенств (3) для получения значений определяемых функций в рамках операционной семантики производится следующим образом. Пусть задан набор входных данных (аргументов) d1, d2, ..., dk. На первом шаге осуществляется подстановка этих данных в левые и правые части равенств с выполнением там, где это возможно, предопределенных операций и с выписыванием получаемых в результате этого равенств. На каждом следующем шаге просматриваются правые части полученных равенств. Если правая часть является каким-либо значением, то оно и является значением функции, указанной в левой части этого равенства. В противном случае правая часть является выражением, содержащим вхождения каких-либо определяемых функций с теми или иными наборами аргументов. Если для такого вхождения соответствующая функция с данным набором аргументов имеется в левой части какого-либо из полученных равенств, то либо вместо этого вхождения подставляется значение правой части этого равенства, если оно уже вычислено, с выполнением, где это возможно, предопределённых операций. Либо не производится никаких изменений, если значение этой правой части ещё не вычислено. В том же случае, если эта функция с данным набором аргументов не является левой частью никакого из полученных равенств, то формируется (и дописывается к имеющимся) новое равенство. Оно получается из исходного равенства для данной функции с подстановкой в него вместо параметров указанных аргументов этой функции. Эти шаги осуществляются до тех пор, пока все определяемые функции не будут иметь вычисленные значения.
В качестве примера операционной семантики рассмотрим определение функции факториала F(n) = n! Она определяется следующей системой равенств:
F(0) = 1, F(n) = F(n-1)Чn.
Для вычисления значения F(3) осуществляются следующие шаги:
1-й шаг:
F(0) = 1,
F(3) = F(2)Ч3.
2-й шаг:
F(0) =1,
F(3) = F(2)Ч3,
F(2) = F(1)Ч2.
3-й шаг:
F(0) = 1,
F(3) = F(2)Ч3,
F(2) = F(1)Ч2,
F(1) = F(0)Ч1.
4-й шаг:
F(0) = 1,
F(3) = F(2)Ч3,
F(2) = F(1)Ч2,
F(1) = 1.
5-й шаг:
F(0) = 1,
F(3) = F(2)Ч3,
F(2) = 2,
F(1) = 1.
6-й шаг:
F(0) = 1,
F(3) = 3,
F(2) = 2,
F(1) = 1.
Значение F(3) на 6-ом шаге получено.
4. Денотационная семантика
В денотационной семантике алгебраического подхода рассматривается также система равенств вида (3), которая интерпретируется как система функциональных уравнений, а определяемые функции являются некоторым решением этой системы. В классической математике изучению функциональных уравнений (в частности, интегральных уравнений) уделяется большое внимание и связано с построением достаточно глубокого математического аппарата. Применительно к программированию этими вопросами серьезно занимался Д. Скотт [3].
Основные идеи денотационной семантики проиллюстрируем на более простом случае, когда система равенств (5.3) является системой языковых уравнений:
X1 = ц1,1 ? ц1,2 ? ... ? ц1,k1,
X2 = ц2,1 ? ц2,2 ? ... ? ц2,k2,
(4) .....…………………………
Xn= цn,1 ? цn,2 ? ... ? цn,kn,
причем i-ое уравнение при ki = 0 имеет вид
Xi = ?
Как известно, формальный язык -- это множество цепочек в некотором алфавите. Такую систему можно рассматривать как одну из интерпретаций набора правил некоторой грамматики, представленную в форме Бэкуса-Наура (каждое из приведенных уравнений является аналогом некоторой такой формулы). Пусть фиксирован некоторый алфавит A = {a1, a2, …, am} терминальных символов грамматики, из которых строятся цепочки, образующие используемые в системе (4) языки. Символы X1, X2, ..., Xn являются метапеременными грамматики, здесь будут рассматриваться как переменные, значениями которых являются языки (множества значений этих метапеременных). Символы цi,j, i = 1, ..., n, j = 1, ..., kj, обозначают цепочки в объединенном алфавите терминальных символов и метапеременных:
цi,j ? (A | { X1, X2, ..., Xn})* .
Цепочка цi,j рассматривается как некоторое выражение, определяющее значение, являющееся языком (множеством цепочек в алфавите A). Такое выражение определяется следующим образом. Если значения X1, X2, ..., Xn заданы, то цепочка
ц = Z1 Z2 ... Zk, Zi???(A | { X1, X2, ..., Xn }),
обозначает сцепление множеств Z1 Z2 ... Zk, причём вхождение в эту цепочку символа aj представляет множество из одного элемента {aj}. Это означает, что ц определяет множество цепочек
{ p1 p2 ... pk | pj???Zj, j = 1, ..., k},
причём цепочка
p1, p2, ..., pk
представляет собой последовательность выписанных друг за другом цепочек p1, p2, ..., pk. Таким образом, каждая правая часть уравнений системы (4) представляет собой объединение множеств цепочек.
Решением системы (4) является набор значений (языков)
L1, L2, ..., Ln
переменных X1, X2, ..., Xn, для которых все уравнения системы (4) превращаются в тождество.
Рассмотрим в качестве примера частный случай системы (4), состоящий из одного уравнения
X = a X ? b X ? c
с алфавитом A = {a, b, c}. Решением этого уравнения является язык
L = { ц c | ц???{a, b}*}.
Система (4) может иметь несколько решений. Так в рассмотренном примере помимо L решениями являются также
L1 = L ? {ц a | ц???{a, b}*}
и
L2 = L ? { ц b | ц???{a, b}*}.
В соответствии с денотационной семантикой в качестве определяемого решения системы (4) принимается наименьшее. Решение (L1, L2, ..., Ln) системы (4) называется наименьшим, если для любого другого решения (L?1, L?2, ..., L?n) выполняется
L1 ? L?1, L2 ? L?2, ..., Ln ? L?n.
Так в рассмотренном примере наименьшим (а значит, определяемым денотационной семантикой) является решение L.
В качестве метода решения систем уравнений (3) и (4) можно использовать метод последовательных приближений. Сущность этого метода для системы (4) заключается в следующем. Обозначим правые части уравнений системы (4) операторами Ti(X1, X2, ..., Xn). Тогда система (4) примет вид
X1 = T1(X1, X2, ..., Xn),
X2 = T2(X1, X2, ..., Xn),
(5) ………………………
Xn = Tn(X1, X2, ..., Xn).
В качестве начального приближения решения этой системы примем набор языков (L1[0], ..., Ln[0]) = (?, ?, ..., ?). Каждое следующее приближение определяется по формуле:
(L1[0], ..., Ln[0]) = (T1(L1[i-1], ..., Ln[i-1]), …………….. (Tn(L1[i-1], ..., Ln[i-1])).
Так как операции объединения и сцепления множеств являются монотонными функциями относительно отношения порядка Н, то этот процесс сходится к решению (L1, ..., Ln) системы (5), т.е.
(L1, ..., Ln)= (T1(L1, ..., Ln), ..., Tn(L1, ..., Ln))
и это решение является наименьшим. Это решение называют ещё наименьшей неподвижной точкой системы операторов
T1, T2, ..., Tn.
В рассмотренном примере этот процесс даёт следующую последовательность приближений:
L[0] = ?, L[1] = {c}, L[2]= {c, ac, bc},
L[3] = {c, ac, bc, aac, abc, bac, bbc},
…………………………………………
Этот процесс сходится к указанному выше наименьшему решению L.
5. Аксиоматическая семантика
В аксиоматической семантике алгебраического подхода система (5) интерпретируется как набор аксиом в рамках некоторой формальной логической системы, в которой есть правила вывода и / или интерпретации определяемых объектов.
Для интерпретации системы (1) вводится понятие аксиоматического описания (S, E) -- логически связанной пары понятий: S -- сигнатура используемых в системе (1) символов функций f1, f2, ..., fm и символов констант (нульместных функциональных символов) c1, c2, ..., cm, а E -- набор аксиом, представленный системой (1). Предполагается, что каждая переменная xi, i = 1, ..., k, и каждая константа cj, j =1, ..., l, используемая в E, принадлежит к какому-либо из типов данных t1, t2, ..., tr, а каждый символ fi, i =1, ..., m, представляет функцию, типа
ti1 * ti2 * ... * tik > ti0.
Такое аксиоматическое описание получит конкретную интерпретацию, если будут заданы конкретные типы данных ti = t?i, i = 1, ..., r, и конкретные значения констант ci = c?i, i = 1, ..., l. В таком случае говорят, что задана одна конкретная интерпретация A символов сигнатуры S, называемая алгебраической системой
A = (t?1, ..., t?r, f ?1, ..., f ?r, с?1, ..., с? r),
где f ?i, i = 1, ..., m, конкретная функция, представляющая символ fi. Таким образом, аксиоматическое описание (S, E) определяет класс алгебраических систем (частный случай: одну алгебраическую систему), удовлетворяющих системе аксиом E, т.е. превращающих равенства системы E в тождества после подстановки в них f ?i, i = 1, ..., m, и ci = c?i, i = 1, ..., l, вместо fi и ci соответственно.
В программировании в качестве алгебраической системы можно рассматривать, например, тип данных, при этом определяемые функции представляют операции, применимые к данным этого типа. Так К. Хоор построил аксиоматическое определение набора типов данных [4], которые потом Н. Вирт использовал при создании языка Паскаль.
В качестве примера рассмотрим систему равенств:
УДАЛИТЬ(ДОБАВИТЬ(m,d))=m,
ВЕРХ(ДОБАВИТЬ(m,d))=d,
УДАЛИТЬ(ПУСТ)=ПУСТ,
ВЕРХ(ПУСТ)=ДНО,
где УДАЛИТЬ, ДОБАВИТЬ, ВЕРХ -- символы функций, а ПУСТ и ДНО -- символы констант, образующие сигнатуру этой системы. Пусть D, D1 и М -- некоторые типы данных, такие, что m???M, d???D, ПУСТ???M, ДНО??? D1, а функциональные символы представляют функции следующих типов:
УДАЛИТЬ: M > M,
ДОБАВИТЬ: M * D > M,
ВЕРХ: M > D1.
Данная сигнатура вместе с указанной системой равенств, рассматриваемой как набор аксиом, образует некоторое аксиоматическое описание.
С помощью этого аксиоматического описания определим абстрактный тип данных, называемый магазином, задав следующую интерпретацию символов её сигнатуры: пусть D -- множество значений, которые могут быть элементами магазина, D1 = D | {ДНО}, а M -- множество состояний магазина,
M = {d1, d2, ..., dn | dni???D, i = 1, ..., n, ni0},
ПУСТ = {}, ДНО -- особое значение (зависящее от реализации магазина), не принадлежащее D. Тогда указанный набор аксиом определяют свойства магазина.
С аксиоматической семантикой связана логика равенств (эквациональная логика), изучаемая в курсе «Математическая логика». Эта логика содержит правила вывода из заданного набора аксиом других формул (равенств).
6. Аксиоматическая семантика
Как уже отмечалось, функциональная спецификация представляет собой математически точное, но, как правило, не формальное описание поведения ПС. Однако, формализованное представление функциональной спецификации имеет ряд достоинств, главным из которых является возможность применять некоторые виды автоматизированного контроля функциональной спецификации.
Под языком спецификаций понимается формальный язык, предназначенный для спецификации функций. В нем используется ряд средств, позволяющих фиксировать синтаксис и выражать семантику описываемых функций. Различие между языками программирования и языками спецификации может быть весьма условным: если язык спецификаций имеет реализацию на компьютере, позволяющую как-то выполнять представленные на нем спецификации (например, с помощью интерпретатора), то такой язык является и языком программирования, может быть, и не позволяющий создавать достаточно эффективные программы. Однако, для языка спецификаций важно не эффективность выполнения спецификации (программы) на компьютере, а её выразительность. Язык спецификации, не являющийся языком программирования, может быть, тем не менее, полезен в процессе разработки ПС (для автоматизации контроля, тестирования и т.п.).
Язык спецификации может базироваться на каком-либо из рассмотренных нами методов описания семантики функций, а также поддерживать спецификацию функций для какой-либо конкретной предметной области.
ЛИТЕРАТУРА
В.Н. Агафонов. Спецификация программ: понятийные средства и их организация. -- Новосибирск: Наука (Сибирское отделение), 1987. -- c. 30-73.
Ian Sommerville. Software Engineering. -- Addison-Wesley Publishing Company, 1992.
Д. Скотт. Теория решеток, типы данных и семантика. // Данные в языках программирования. -- М.: Мир, 1982. -- c. 25-53.
К. Хоор. О структурной организации данных // У. Дал, Э. Дейкстра, К. Хоор. Структурное программирование. -- М.: Мир, 1975. -- c. 98-197.
ЗАМОК ДРАКОНА
Разделяй и властвуй!
Латинское изречение
Лекция 6.
АРХИТЕКТУРА ПРОГРАММНОГО СРЕДСТВА
Понятие архитектуры и задачи ее описания. Основные классы архитектур программных средств. Взаимодействие между подсистемами и архитектурные функции. Контроль архитектуры программных средств.
1. Понятие архитектуры программного средства
Архитектура ПС -- это его строение как оно видно (или должно быть видно) извне его, т.е. представление ПС как системы, состоящей из некоторой совокупности взаимодействующих подсистем. В качестве таких подсистем выступают обычно отдельные программы. Разработка архитектуры является первым этапом борьбы со сложностью ПС, на котором реализуется принцип выделения относительно независимых компонент.
Основные задачи разработки архитектуры ПС:
· выделение программных подсистем и отображение на них внешних функций (заданных во внешнем описании) ПС;
· определение способов взаимодействия между выделенными программными подсистемами.
2. Основные классы архитектур программных средств
Различают следующие основные классы архитектур программных средств [1]:
· цельная программа;
· комплекс автономно выполняемых программ;
· слоистая программная система;
· коллектив параллельно выполняемых программ.
Цельная программа представляет вырожденный случай архитектуры ПС: в состав ПС входит только одна программа. Такую архитектуру выбирают обычно в том случае, когда ПС должно выполнять одну какую-либо ярко выраженную функцию и её реализация не представляется слишком сложной. Естественно, что такая архитектура не требует какого-либо описания (кроме фиксации класса архитектуры), так как отображение внешних функций на эту программу тривиально, а определять способ взаимодействия не требуется (в силу отсутствия какого-либо внешнего взаимодействия программы, кроме как взаимодействия её с пользователем, а последнее описывается в документации по применению ПС).
Комплекс автономно выполняемых программ состоит из набора программ, такого, что:
· любая из этих программ может быть активизирована (запущена) пользователем;
· при выполнении активизированной программы другие программы этого набора не могут быть активизированы до тех пор, пока не закончит выполнение активизированная программа;
· все программы этого набора применятся к одной и той же информационной среде.
Таким образом, программы этого набора по управлению никак не взаимодействуют -- взаимодействие между ними осуществляется только через общую информационную среду.
Слоистая программная система состоит из некоторой упорядоченной совокупности программных подсистем, называемых слоями, такой, что:
· на каждом слое ничего не известно о свойствах (и даже существовании) последующих (более высоких) слоёв;
· каждый слой может взаимодействовать по управлению (обращаться к компонентам) с непосредственно предшествующим (более низким) слоем через заранее определенный интерфейс, ничего не зная о внутреннем строении всех предшествующих слоёв;
· каждый слой располагает определенными ресурсами, которые он либо скрывает от других слоев, либо предоставляет непосредственно последующему слою (через указанный интерфейс) некоторые их абстракции.
Таким образом, в слоистой программной системе каждый слой может реализовать некоторую абстракцию данных. Связи между слоями ограничены передачей значений параметров обращения каждого слоя к смежному снизу слою и выдачей результатов этого обращения от нижнего слоя верхнему. Недопустимо использование глобальных данных несколькими слоями.
В качестве примера рассмотрим использование такой архитектуры для построения операционной системы. Такую архитектуру применил Дейкстра при построении операционной системы THE [2]. Эта операционная система состоит из четырех слоёв (см. Рис. 1). На нулевом слое производится обработка всех прерываний и выделение центрального процессора программам (процессам) в пакетном режиме. Только этот уровень осведомлен о мультипрограммных аспектах системы. На первом слое осуществляется управление страничной организацией памяти. Всем вышестоящим слоям предоставляется виртуальная непрерывная (не страничная) память. На втором слое осуществляется связь с консолью (пультом управления) оператора. Только этот слой знает технические характеристики консоли. На третьем слое осуществляется буферизация входных и выходных потоков данных и реализуются так называемые абстрактные каналы ввода и вывода, так что прикладные программы не знают технических характеристик устройств ввода-вывода.
Рис. 1. Архитектура операционной системы THE.
Коллектив параллельно действующих программ представляет собой набор программ, способных взаимодействовать между собой, находясь одновременно в стадии выполнения. Это означает, что такие программы, во-первых, вызваны в оперативную память, активизированы и могут попеременно разделять по времени один или несколько центральных процессоров, а во-вторых, осуществлять между собой динамические (в процессе выполнения) взаимодействия, на базе которых производиться их синхронизация. Обычно взаимодействие между такими процессами производится путём передачи друг другу некоторых сообщений.
Простейшей разновидностью такой архитектуры является конвейер, средства, для организации которого имеются в операционной системе UNIX [3]. Конвейер представляет собой последовательность программ, в которой стандартный вывод каждой программы, кроме самой последней, связан со стандартным вводом следующей программы этой последовательности (см. Рис. 2). Конвейер обрабатывает некоторый поток сообщений. Каждое сообщение этого потока поступает на ввод первой программе, которая, обработав его, передаёт переработанное сообщение следующей программе, а сама начинает обработку очередного сообщения потока. Таким же образом действует каждая программа конвейера: получив сообщение от предшествующей программы и обработав его, она передаёт переработанное сообщение следующей программе, а последняя программа конвейера выводит результат работы всего конвейера (результирующее сообщение). Таким образом, в конвейере, состоящим из n программ, может одновременно находиться в обработке до n сообщений. Конечно, в силу того, что разные программы конвейера могут затратить на обработку очередных сообщений разные отрезки времени, необходимо обеспечить каким-либо образом синхронизацию этих процессов (некоторые процессы могут находиться в стадии ожидания либо возможности передать переработанное сообщение, либо возможности получить очередное сообщение).
Рис. 2. Конвейер параллельно действующих программ.
Порт сообщений представляет собой программную подсистему, обслуживающую некоторую очередь сообщений: она может принимать на хранение от программы какое-либо сообщение, ставя его в очередь, и может выдавать очередное сообщение другой программе по её требованию. Сообщение, переданное какой-либо программой некоторому порту, уже не будет принадлежать этой программе (и использовать её ресурсы), но оно не будет принадлежать и никакой другой программе, пока в порядке очереди не будет передано какой-либо программе по её запросу. Таким образом, программа, передающая сообщение не будет находиться в стадии ожидания пока программа, принимающая это сообщение, не будет готова его обрабатывать (если только не будет переполнен принимающий порт).
Пример программной системы с портами сообщений приведен на Рис. 3. Порт U может рассматриваться как порт вводных сообщений для представленного на этом рисунке коллектива параллельно действующих программ, а порт W -- как порт выводных сообщений для этого коллектива программ.
Рис. 3. Пример программной системы с портами сообщений.
Программные системы с портами сообщений могут быть как жесткой конфигурации, так и гибкой конфигурации. В системах с портами жесткой конфигурации с каждой программой могут быть жестко связаны один или несколько входных портов. Для передачи сообщения такая программа должна явно указать адрес передачи: имя программы и имя ее входного порта. В этом случае при изменении конфигурации системы придется корректировать используемые программы: изменять адреса передач сообщений. В системах с портами гибкой конфигурации с каждой программой связаны как входные, так и выходные виртуальные порты. Перед запуском такой системы должна производиться ее предварительная настройка с помощью специальной программной компоненты, осуществляющая совмещение каждого выходного виртуального порта с каким-либо входным виртуальным портом на основании информации, задаваемой пользователем. Тем самым при изменении конфигурации системы в этом случае не требуется какой-либо корректировки используемых программ -- необходимые изменения должны быть отражены в информации для настройки. Однако в этом случае требуется иметь специальную программную компоненту, осуществляющую настройку системы.
3. Архитектурные функции
Для обеспечения взаимодействия между подсистемами в ряде случаев не требуется создавать какие-либо дополнительные программные компоненты (помимо реализации внешних функций) -- для этого может быть достаточно заранее фиксированных соглашений и стандартных возможностей базового программного обеспечения (операционной системы). Так в комплексе автономно выполняемых программ для обеспечения взаимодействия достаточно описания (спецификации) общей внешней информационной среды и возможностей операционной системы для запуска программ. В слоистой программной системе может оказаться достаточным спецификации выделенных программных слоёв и обычный аппарат обращения к процедурам. В программном конвейере взаимодействие между программами также может обеспечивать операционная система (как это имеет место в операционной системе UNIX).
Однако в ряде случаев для обеспечения взаимодействия между программными подсистемами может потребоваться создание дополнительных программных компонент. Так для управления работой комплекса автономно выполняемых программ часто создают специализированный командный интерпретатор, более удобный в данной предметной области для подготовки требуемой внешней информационной среды и запуска требуемой программы, чем базовый командный интерпретатор используемой операционной системы. В слоистых программных системах может быть создан особый аппарат обращения к процедурам слоя (например, обеспечивающий параллельное выполнение этих процедур). В коллективе параллельно действующих программ для управления портами сообщений требуется специальная программная подсистема. Такие программные компоненты никаких внешних функций не выполняют -- они реализуют функции, возникшие в результате разработки архитектуры программного средства. В связи с этим такие функции мы будем называть архитектурными.
4. Контроль архитектуры программных средств
Для контроля архитектуры ПС используется смежный контроль и ручная имитация.
Смежный контроль архитектуры ПС сверху -- это её контроль разработчиками внешнего описания: разработчиками спецификации качества и разработчиками функциональной спецификации. Смежный контроль архитектуры ПС снизу -- это её контроль потенциальными разработчиками программных подсистем, входящих в состав ПС в соответствии с разработанной архитектурой.
Ручная имитация архитектуры ПС производится аналогично ручной имитации функциональной спецификации, только целью этого контроля является проверка взаимодействия между программными подсистемами. Так же как и в случае ручной имитации функциональной спецификации ПС должны быть сначала подготовлены тесты. Затем группа разработчиков должна для каждого такого теста имитировать работу каждой программной подсистемы, входящей в состав ПС. При этом работу каждой подсистемы имитирует один какой-либо разработчик (не автор архитектуры), тщательно выполняя все взаимодействия этой подсистемы с другими подсистемами (точнее, с разработчиками, их имитирующими) в соответствии с разработанной архитектурой ПС. Тем самым обеспечивается имитационное функционирование ПС в целом в рамках проверяемой архитектуры.
ЛИТЕРАТУРА
Г.Майерс. Надежность программного обеспечения. -- М.: Мир, 1980. -- с. 78-91.
E.W. Dijkstra. The Structure of the THE-Multiprogramming // Communications of the ACM. -- 1968, 11(5). -- pp. 341-346.
М. Кристиан. Введение в операционную систему UNIX. -- М.: Финансы и статистика, 1985. -- с. 46-49.
ЗАМОК ДРАКОНА
Разделяй и властвуй!
Латинское изречение
Лекция 7.
РАЗРАБОТКА СТРУКТУРЫ ПРОГРАММЫ И МОДУЛЬНОЕ ПРОГРАММИРОВАНИЕ
Цель разработки структуры программы. Понятие программного модуля. Основные характеристики программного модуля. Методы разработки структуры программы. Спецификация программного модуля. Контроль структуры программы.
1. Цель модульного программирования
Приступая к разработке каждой программы ПС, следует иметь ввиду, что она, как правило, является большой системой, поэтому мы должны принять меры для её упрощения. Для этого такую программу разрабатывают по частям, которые называются программными модулями [1, 2]. А сам такой метод разработки программ называют модульным программированием [3]. Программный модуль -- это любой фрагмент описания процесса, оформляемый как самостоятельный программный продукт, пригодный для использования в описаниях процесса. Это означает, что каждый программный модуль программируется, компилируется и отлаживается отдельно от других модулей программы, и тем самым, физически разделён от других модулей программы. Более того, каждый разработанный программный модуль может включаться в состав разных программ, если выполнены условия его использования, декларированные в документации по этому модулю. Таким образом, программный модуль может рассматриваться и как средство борьбы со сложностью программ, и как средство борьбы с дублированием в программировании (т.е. как средство накопления и многократного использования программистских знаний).
Подобные документы
Обоснование выбора программно-технических средств. Надежность программы и состав технических средств. Разработка структурной схемы программы, алгоритмического и программного интерфейса. Технология разработки интерфейса пользователя и программных модулей.
дипломная работа [3,2 M], добавлен 22.01.2013Характеристика этапов разработки программных средств. Спецификация, алгоритм, кодирование, отладка и тестирование. Создание справочной системы и установочного диска. Назначение программы, язык программирования. Технические требования к программе.
курсовая работа [1006,4 K], добавлен 19.12.2013Модульная структура программного продукта и типовые управляющие структуры алгоритмов обработки данных различных программных модулей в основе структурного программирования. Особенности пошаговой разработки программ. Основные типы базовых конструкций.
контрольная работа [163,7 K], добавлен 04.06.2013Возможности среды программирования delphi при разработке приложения с визуальным интерфейсом. Отладка программных модулей с использованием специализированных программных средств. Тестирование программного обеспечения. Оптимизация программного кода.
курсовая работа [974,0 K], добавлен 21.12.2016Порядок описание процесса разработки модели для разрешения задачи программирования с помощью средств языка программирования. Структуры данных и основные принципы их построения. Этапы компьютерного моделирования. Этапы и значение написания программы.
курсовая работа [19,5 K], добавлен 19.05.2011Программное обеспечение как продукт. Основные характеристик качества программного средства. Основные понятия и показатели надежности программных средств. Дестабилизирующие факторы и методы обеспечения надежности функционирования программных средств.
лекция [370,1 K], добавлен 22.03.2014Проектирование программы, реализующей синтаксический анализ простой программы на языке С: этапы создания, алгоритм ее функционирования, структура, технология обработки информации. Описание программных модулей, интерфейс; выбор инструментальных средств.
курсовая работа [1,6 M], добавлен 12.12.2011Язык разработки, среда реализации, инструменты разработки. Особенности виртуальной среды реализации программ и их учет в разработке программного продукта. Системные макросы и их применение в текстах разработки. Средства визуального программирования.
учебное пособие [1,7 M], добавлен 26.10.2013Технология и средства прикладного программирования. Физическая модель данных. Программа для управления базой данных. Добавление, удаление и редактирование информации. Трудоёмкость ведения базы данных взятых и оставшихся книг. Типы структуры данных.
курсовая работа [2,3 M], добавлен 14.04.2014Эффективные средства разработки программного обеспечения. Технология визуального проектирования и событийного программирования. Конструирование диалоговых окон и функций обработки событий. Словесный алгоритм и процедуры программы Borland Delphi 7 Studio.
дипломная работа [660,2 K], добавлен 21.05.2012
