5.3. Операционная семантика.
В операционной семантике алгебраического подхода к описанию семантики функций рассматривается следующий частный случай системы равенств (5.1):
f1(x1, x2, ... , xk)= E1,
f2(x1, x2, ... , xk)= E2,
. . . . . . . . . . . . .
fn(x1, x2, ... , xk)= En,
(5.3)
где в левых частях равенств явно указаны определяемые функции с формальными параметрами, включающими (для простоты) обозначения всех входных данных x1, x2, ... , xk, а правые части представляют собой выражения, содержащие, вообще говоря, вхождения этих функций с аргументами, задаваемыми некоторыми выражениями, зависящими от входных данных x1, ... , 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 - конкретные аргументы (значения или определяющие их выражения) данной функции. Это правило допускает замену вхождения левой его части в какое-либо выражение на его правую часть.
Интерпретация системы равенств (5.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-ом шаге получено.
Yandex.RTB R-A-252273-3- Разработка программных приложений
- Введение
- Лекция 1. Надежное программное средство как продукт технологии программирования. Исторический и социальный контекст программирования
- 1.1. Программа как формализованное описание процесса обработки данных. Программное средство.
- 1.2. Неконструктивность понятия правильной программы.
- 1.3. Надежность программного средства.
- 1.4. Технология программирования как технология разработки надежных программных средств.
- 1.5. Технология программирования и информатизация общества.
- Литература к лекции 1.
- Лекция 2. Источники ошибок в программных средствах
- 2.1. Интеллектуальные возможности человека.
- 2.2. Неправильный перевод как причина ошибок в программных средствах.
- 2.3. Модель перевода.
- 2.4. Основные пути борьбы с ошибками.
- Литература к лекции 2.
- Лекция 3. Общие принципы разработки программных средств
- 3.1. Специфика разработки программных средств.
- 3.2. Жизненный цикл программного средства.
- 3.3. Понятие качества программного средства.
- 3.4. Обеспечение надежности - основной мотив разработки программных средств.
- 3.5. Методы борьбы со сложностью.
- 3.6. Обеспечение точности перевода.
- 3.7. Преодоление барьера между пользователем и разработчиком.
- 3.8. Контроль принимаемых решений.
- Литература к лекции 3.
- Лекция 4. Внешнее описание программного средства
- 4.1. Назначение внешнего описания программного средства и его роль в обеспечении качества программного средства.
- 4.2. Определение требований к программному средству.
- 4.3. Спецификация качества программного средства.
- 4.4. Функциональная спецификация программного средства.
- 4.5. Методы контроля внешнего описания программного средства.
- Литература к лекции 4.
- Лекция 5. Методы спецификации семантики функций
- 5.1. Основные подходы к спецификации семантики функций.
- 5.2. Метод таблиц решений.
- 5.3. Операционная семантика.
- 5.4. Денотационная семантика.
- 5.5. Аксиоматическая семантика.
- 5.6. Языки спецификаций.
- Литература к лекции 5.
- Лекция 6. Архитектура программного средства
- 6.1. Понятие архитектуры программного средства.
- 6.2. Основные классы архитектур программных средств.
- 6.3. Архитектурные функции.
- 6.4. Контроль архитектуры программных средств.
- Литература к лекции 6.
- Лекция 7. Разработка структуры программы и модульное программирование
- 7.1. Цель модульного программирования.
- 7.2. Основные характеристики программного модуля.
- 7.3. Методы разработки структуры программы.
- 7.4. Контроль структуры программы.
- Литература к лекции 7.
- Лекция 8. Разработка программного модуля
- 8.1. Порядок разработки программного модуля.
- 8.2. Структурное программирование.
- 8.3. Пошаговая детализация и понятие о псевдокоде.
- 8.4. Контроль программного модуля.
- Литература к лекции 8.
- Лекция 9. Доказательство свойств программ
- 9.1. Обоснования программ. Формализация свойств программ.
- 9.2. Свойства простых операторов.
- 9.3. Свойства основных конструкций структурного программирования.
- 9.4. Завершимость выполнения программы.
- 9.5. Пример доказательства свойства программы.
- Литература к лекции 9.
- Лекция 10. Тестирование и отладка программного средства
- 10.1. Основные понятия.
- 10.2. Принципы и виды отладки.
- 10.3. Заповеди отладки.
- 10.4. Автономная отладка модуля.
- 10.5. Комплексная отладка программного средства.
- Лекция 11. Обеспечение функциональности и надежности программного средства
- 11.1. Функциональность и надежность как обязательные критерии качества программного средства.
- 11.2. Обеспечение завершенности программного средства.
- 11.3. Обеспечение точности программного средства.
- 11.4. Обеспечение автономности программного средства.
- 11.5. Обеспечение устойчивости программного средства.
- 11.6. Обеспечение защищенности программных средств.
- Литература к лекции 11.
- Лекция 12. Обеспечение качества программного средства
- 12.1. Общая характеристика процесса обеспечения качества программного средства.
- 12.2. Обеспечение легкости применения программного средства.
- 12.3. Обеспечение эффективности программного средства.
- 12.4. Обеспечение сопровождаемости.
- 12.5. Обеспечение мобильности.
- Литература к лекции 12.
- Лекция 13. Документирование программных средств
- 13.1. Документация, создаваемая в процессе разработки программных средств.
- 13.2. Пользовательская документация программных средств.
- 13.3. Документация по сопровождению программных средств.
- Литература к лекции 13.
- Лекция 14. Аттестация программного средства
- 14.1. Назначение аттестации программного средства.
- 14.2. Виды испытаний программного средства.
- 14.3. Методы оценки качества программного средства.
- Литература к лекции 14.
- 15.2. Особенности объектного подхода к разработке внешнего описания программного средства.
- 15.3. Особенности объектного подхода на этапе конструирования программного средства.
- 15.4. Особенности объектного подхода на этапе кодирования программного средства.
- Лекция 16. Компьютерная поддержка разработки и сопровождения программных средств
- 16.1. Инструменты разработки программных средств.
- 16.2. Инструментальные среды разработки и сопровождения программных средств.
- 16.3. Инструментальные среды программирования.
- 16.4. Понятие компьютерной технологии разработки программных средств и ее рабочие места.
- 16.5. Инструментальные системы технологии программирования.
- Литература к лекции 16.
- Рекламные ссылки