Основные подходы к спецификации семантики функций. Табличный подход, метод таблиц решений. Алгебраический подход: операционная, денотационная и аксиоматическая семанти-ки. Языки спецификаций.
Семантика - в программировании - система правил истолкования отдельных языковых конструкций. Семантика определяет смысловое значение предложений алгоритмического языка.
1. Основные подходы к спецификации семантики функций. Для спецификации семантики функций используются следующие подходы: табличный, алгебраический и логический, а также графический. Табличный подход для определения функций хорошо известен ещё со средней школы. Он базируется на использовании таблиц. В программировании эти методы получили развитие в методе таблиц решений. Алгебраический подход для определения функций базируется на использовании равенств. В этом случае для определения некоторого набора функций строится система равенств вида: L1=R1, . . . (1) Ln=Rn. где Li и Ri, i=1, ... n, некоторые выражения, содержащие предопределенные операции, кон-станты, переменные, от которых зависят определяемые функции (формальные параметры этих функций), и вхождения самих этих функций. Семантика определяемых функций извлекается в результате интерпретации этой системы равенств. Эта интерпретация может осуществляться по-разному (базироваться на разных системах правил), что порождает разные семантики. В настоящее время активно исследуются операционная, денотационная и аксиоматическая семантики. Третий подход, логический, базируется на использовании предикатов функций, у кото-рых аргументами могут быть значения различных типов, а результатами являются логические значения (ИСТИНА и ЛОЖЬ). В этом случае набор функций может определяться с помощью системы предикатов. Заметим, что система равенств алгебраического подхода может быть за-дана с помощью следующей системы предикатов: РАВНО(L1, R1), . . . (2) РАВНО(Ln, Rn), где предикат РАВНО истинен, если равны значения первого и второго его аргументов. Это говорит о том, что логический подход располагает не меньшими возможностями для определения функций, однако он требует от разработчиков ПС умения пользоваться методами математической логики, что, к сожалению, не для всех разработчиков оказывается приемлемым. Более подробно этот подход мы рассматривать не будем. Графический подход также известен еще со средней школы. Но в данном случае речь идет не о задании функции с помощью графика, хотя при данном уровне развития компьютерной техники ввод в компьютер таких графиков возможен и они могли бы использоваться (с отно-сительно небольшой точностью) для задания функций. В данном случае речь идет о графиче-ском задании различных схем, выражающих сложную функцию через другие функции, свя-занными с какими-либо компонентами заданной схемы. Графическая схема может определять ситуации, когда для вычисления представляемой ею функции должны применяться связанные с этой схемой более простые функции. Графическая схема может достаточно точно определять часть семантики функции. Примером такой схемы может быть схема переходов состояний конечного автомата, такая, что в каждом из этих состояний должна выполняться некоторая дополнительная функция, указанная в схеме.
2. Метод таблиц решений. Метод таблиц решений базируется на использовании таблиц следующего вида (см. табл.1).
Верхняя часть этой таблицы определяет различные ситуации, в которых требуется выпол-нять некоторые действия (операции). Каждая строка этой части задает ряд значений некоторой переменной или некоторого условия. Первый столбец этой части представляет собой список переменных или условий, от значений которых зависит выбор определяемых ситуаций. В каждом следующем столбце указывается комбинация значений этих переменных (условий), определяющая конкретную ситуацию. При этом последний столбец определяет ситуацию, отличную от предыдущих, т.е. для любых других комбинаций значений (будем обозначать их звёздочкой *), отличных от первых, определяется одна и та же, (m+1)-ая, ситуация. Впрочем, в некоторых таблицах решений этот столбец может отсутствовать. Нижняя часть таблицы решений определяет действия, которые требуется выполнить в той или иной ситуации, определяемой в верхней части таблицы решений. Она также состоит из нескольких (k) строк, каждая из которых связана с каким-либо одним конкретным действием, указанным в первом поле (столбце) этой строки. В остальных полях (столбцах) этой строки (т.е. для u[i, j], i=1, ... m+1, j=1, ... k) указывается, следует ли выполнять (при u[i, j]= '+') это действие в данной ситуации или не следует (при u[i, j]= ''). Таким образом, первый столбец нижней части этой таблицы представляет собой список обозначений действий, которые могут выполняться в той или иной ситуации, определяемой этой таблицей. В каждом следующем столбце этой части указывается комбинация действий, которые следует выполнить в ситуации, определяемой в том же столбце верхней части таблицы решений. Для ряда таблиц решений эти действия могут выполняться в произвольном порядке, но для некоторых таблиц решений этот порядок может быть предопределён, например, в порядке следования строк в нижней части этой таблицы. Рассмотрим в качестве примера описание работы светофора у пешеходной дорожки. Пере-ключение светофора в нормальных ситуациях должно производиться через фиксированное для каждого цвета число единиц времени (Tкр для красного цвета, Tжёл для жёлтого, Tзел для зелёного). У светофора имеется счётчик таких единиц. При переключении светофора в счётчике устанавливается 0. Работа светофора усложняется необходимостью пропускать при-вилегированные машины (при их появлении на светофор поступает специальный сигнал) с минимальной задержкой, но при обеспечении безопасности пешеходов. Приведённая на рис. 5.2 таблица решений описывает работу такого светофора, управляющего порядком движения у него в каждую единицу времени. Звёздочка (*) в этой таблице означает произвольное значе-ние соответствующего условия.
Условия Ситуации Состояние светофора Кр Кр Кр Жёл Жёл Зел Зел Зел T=Tкр Нет Нет Да * * * * * T=Tжёл * * * Нет Да * * * T>Tзел * * * * * Нет Да Да Появление привиле-гированной машины Нет Да * * * * Нет Да Включить красный + Включить жёлтый + + Включить зелёный + T:=0 + + + + T:=T+1 + + + + Освобождение пеше-ходной дорожки +
Пропуск пешеходов + + + Пропуск машин + + + Действия Комбинации выполняемых действий
Рис. 5.2. Таблица решений "Светофор у пешеходной дорожки".
3. Операционная семантика. В операционной семантике алгебраического подхода к описанию семантики функций рас-сматривается следующий частный случай системы равенств (1): f1(x1, x2, ... , xk)= E1, . . . . . . . . . . . . . (3) fn(x1, x2, ... , xk)= En, где в левых частях этих равенств явно указаны определяемые функции, каждая из которых зависит (для простоты) от одних и тех же параметров x1, x2, ..., xk, а правые части этих равенств представляют собой выражения, содержащие, вообще говоря, вхождения этих функций, т.е. определяемые функции могут быть рекурсивными. Поэтому определяемая функция может иметь дополнительные вхождения в левые части этой системы равенств с постоянными значениями некоторых параметров. Таким образом, каждый параметр xj вхождения определяемой функции fi в левую часть равенств (3) будем понимать либо как переменную yj, либо как константу cij, причём совокупность переменных y1, y2, …, yk представляет входные данные, для которых требуется вычислять определяемые функции. Операционная семантика интерпретирует эти равенства как систему подстановок. Под подстановкой s E T выражения (терма) T в выражение E вместо символа s будем понимать переписывание вы-ражения E с заменой каждого вхождения в него символа s на выражение T. Каждое равенство fi(x1, x2, ... , xk)= Ei задает в параметрической форме множество правил подстановок вида x1, x2, ... , xk fi(T1, T2, ... , Tk) Ei , T1, T2, ... , Tk где T1, T2, ... , Tk конкретные аргументы (значения или определяющие их выражения) данной функции. Каждое такое правило допускает замену в каком-либо выражении вхождения его левой части на её правую часть. Интерпретация системы равенств (5.3) для получения значений определяемых функций в рамках операционной семантики производится следующим образом. Пусть задан набор вход-ных данных (аргументов) d1, d2, ... , dk. На первом шаге осуществляется подстановка этих данных в левые и правые части равенств с выполнением там, где это возможно, предопределённых операций и с переписыванием получаемых в результате этого равенств. В результате этого будет сформирована исходная преобразуемая система равенств. На каждом следующем шаге по текущей преобразуемой системы равенств производится формирование новой преобразуемой системы равенств (которая становится текущей) путем переписывания этих равенств со следующими преобразованиями. (1) Если правая часть очередного равенства является каким-либо значением, то это равенство не изменяется (это значение и является значением функции, указанной в левой части этого равенства). (2) В противном случае правая часть является выражением, содержащим вхождения каких-либо определяемых функций с теми или иными наборами аргументов. В этом случае для каж-дого вхождения функции в эту правую часть (с конкретным набором аргументов) просматри-ваются левые части преобразуемых равенств и выполняются следующие действия. (2.1) Если для этого вхождения в текущей преобразуемой системе равенств находится сов-падающая с ним левая часть некоторого равенства, то проверяется правая часть этого равенст-ва (2.1.1) и в случае, если она является уже вычисленным значением, производится подста-новка этого значения вместо указанного вхождения определяемой функции, (2.1.2) если же эта правая часть не является вычисленным значением, то указанное вхож-дение переписывается в неизменном виде. (2.2) В том же случае, если для указанного вхождения в текущей преобразуемой системе равенств не находится совпадающей с ним левой части никакого равенства, то к новой преоб-разуемой системе равенств дописывается новое равенство. Это равенство получается из ис-ходного равенства для определяемой функции fi(y1, y2, …, yk), вхождение которой в данный момент исследуется, путем подстановки аргументов этой функции из исследуемого вхождения вместо параметров y1, y2, …, yk этой функции (с выпол-нением предопределённых операций там, где это возможно). Эти шаги будут осуществляться до тех пор, пока все определяемые функции не будут иметь вычисленные значения. В качестве примера операционной семантики рассмотрим определение функции 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. Денотационная семантика. В денотационной семантике алгебраического подхода рассматривается также система ра-венств вида (5.3), которая интерпретируется как система функциональных уравнений, а опре-деляемые функции являются некоторым решением этой системы. В классической математике изучению функциональных уравнений (в частности, интегральных уравнений) уделяется большое внимание и связано с построением достаточно глубокого математического аппарата. Применительно к программированию этими вопросами серьёзно занимался Д. Скотт [5.3]. Основные идеи денотационной семантики проиллюстрируем на более простом случае, ко-гда система равенств (5.3) является системой языковых уравнений: X1= φ[1,1] φ[1,2] ... φ[1,k1], X2= φ[2,1] φ[2,2] ... φ[2,k2], . . . . . . . . . . . . . . . . . . . . . . . . . . . . (5.4) Xn= φ[n,1] φ[n,2] ... φ[n,kn], причём i-ое уравнение при ki=0 имеет вид Xi=. Формальный язык это множество цепочек в некотором алфавите. Такую систему можно рассматривать как одну из интерпретаций набора правил некоторой грамматики, представленную в форме Бэкуса-Наура (каждое из приведенных уравнений является аналогом некоторой такой формулы). Пусть фиксирован некоторый алфавит A={a1, a2, ... , am} терминальных символов грамматики, из которых строятся цепочки, образующие используемые в системе (5.4) языки. Символы X1, X2, ... , Xn являются метапеременными грамматики, здесь будут рассматриваться как переменные, значениями которых являются языки (множества значений этих метапеременных). Символы φ[i,j], i=1,...,n, j=1,...,kj, обозначают цепочки в объединённом алфавите терминальных символов и метапеременных: φ[i,j] (A {X1, X2, ... , Xn})* . Цепочка φ[i,j] рассматривается как некоторое выражение, определяющее значение, являю-щееся языком. Такое выражение определяется следующим образом. Если значения X1, X2, ... , Xn заданы, то цепочка φ= Z1 Z2 ... Zk , Zi (A {X1, X2, ... , Xn}) для i=1, ... , k, обозначает сцепление множеств Z1, Z2, ... , Zk , причём вхождение в эту цепочку символа aj представляет множество из одного элемента {aj}. Это означает, что φ определяет множество цепочек {p1 p2 ... pk | pj Zj, j=1, ... , k}, причём цепочка p1 p2 ... pk представляет собой последовательность записанных друг за другом цепочек p1, p2, ... , pk (результат выполнения операции конкатенации цепочек). Таким образом, каждая правая часть уравнений системы (5.4) представляет собой объединение мно-жеств цепочек. Решением системы (5.4) является набор языков (L1, L2, ... , Ln), если все уравнения системы (5.4) превращаются в тождество при X1= L1, X2= L2, ... , Xn= Ln. Рассмотрим в качестве примера частный случай системы (5.4), состоящий из одного урав-нения X= a X b X X c с алфавитом A={a, b, c}. Решением этого уравнения является язык L={ φ c | φ {a, b}*}. Система (5.4) может иметь несколько решений. Так в рассмотренном примере помимо L решениями являются также L1=L {φ a | φ {a, b}*} и L2=L {φ b | φ {a, b}*}. φ В соответствии с денотационной семантикой в качестве определяемого решения системы (5.4) принимается наименьшее решение. Решение (L1, L2, ... , Ln) системы (5.4) называется наименьшим, если для любого другого решения (L1', L2',..., Ln') выполняются соотношения L1 L1', L2 L2', ... , Ln Ln'. Так в рассмотренном примере наименьшим (а значит, определяемым денотационной се-мантикой) является решение L. В качестве метода решения систем уравнений (5.3) и (5.4) можно использовать метод по-следовательных приближений. Сущность этого метода для системы (5.4) заключается в сле-дующем. Обозначим правые части уравнений системы (5.4) операторами Ti(X1, X2, ... , Xn). Тогда система (5.4) примет вид X1=T1(X1, X2, ... , Xn), X2=T2(X1, X2, ... , Xn), . . . . . . . . . . . (5.5) Xn=Tn(X1, X2, ... , Xn). В качестве начального приближения решения этой системы принимается набор языков (L1[0], ... , Ln[0]) = (,,...,). Каждое следующее приближение будет определяться по формуле: (L1[i],...,Ln[i])= (T1(L1[i-1], ... , Ln[i-1]), . . . . . . . . . . . . . Tn(L1[i-1], ... , Ln[i-1])). Так как операции объединения и сцепления множеств являются монотонными функциями относительно отношения порядка , то этот процесс сходится к решению (L1, ... , Ln) системы (5.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. С помощью денотационной семантики можно определять более широкий класс граммати-ки по сравнению с формой Бэкуса-Наура. Так в форме Бэкуса-Наура не определены правила вида X::= X тогда как уравнение вида X= X имеет вполне корректную интерпретацию в денотационной семантике.
5. Аксиоматическая семантика. В аксиоматической семантике алгебраического подхода система (1) интерпретируется как набор аксиом в рамках некоторой формальной логической системы, в которой есть правила вывода и/или интерпретации определяемых объектов. Для интерпретации системы (1) вводится понятие аксиоматического описания (S, E) ло-гически связанной пары понятий: S сигнатура используемых в системе (1) символов функ-ций f1, f2, ... , fm и символов констант (нульместных функциональных символов) c1,c2, ... , cl, а E набор аксиом, представленный системой (1). Предполагается, что каждая переменная xi, i=1, ... , k, и каждая константа ci, i=1, ... , l, используемая в E, принадлежит к какому-либо из типов данных t1, t2, ... , tr, а каждый символ fi, i=1, ... , m, представляет функцию, типа ti1 * ti2 * ... * tik ti0. Такое аксиоматическое описание получит конкретную интерпретацию, если будут заданы конкретные типы данных ti=ti', i=1, ... , r, и конкретные значения констант ci=ci', i=1, ... , l. В таком случае говорят, что задана одна конкретная интерпретация A символов сигнатуры S, называемая алгебраической системой A=(t1', ... , tr', f1', ... , fm', c1', ... , cl'), где fi', i=1, ... , m, конкретная функция, представляющая символ fi. Таким образом, аксио-матическое описание (S, E) определяет класс алгебраических систем (частный случай: одну алгебраическую систему), удовлетворяющих системе аксиом E, т.е. превращающих в тождест-ва равенства системы E после подстановки в них fi', i=1, ... , m, и ci', i=1, ... , l, вместо fi и ci со-ответственно. В программировании в качестве алгебраической системы можно рассматривать, например, тип данных, при этом определяемые функции представляют операции, применимые к данным этого типа. Так К. Хоор построил аксиоматическое определение набора типов данных [5.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 | di D, i=1, ... , n, n0}, ПУСТ={}, ДНО особое значение (зависящее от реализации магазина), не принадлежащее D. Тогда указан-ный набор аксиом определяет свойства магазина. С аксиоматической семантикой связана логика равенств (эквациональная логика), изучае-мая в курсе "Математическая логика". Эта логика содержит правила вывода из заданного на-бора аксиом других формул. 6. Языки спецификаций. Как уже отмечалось, функциональная спецификация представляет собой математически точное, но, как правило, не формальное описание поведения ПС. Однако, формализованное представление функциональной спецификации имеет ряд достоинств, главным из которых является возможность применять некоторые виды автоматизированного контроля функциональной спецификации. Под языком спецификаций понимается формальный язык, предназначенный для специфи-кации функций. В нём используется ряд средств, позволяющих фиксировать синтаксис и вы-ражать семантику описываемых функций. Различие между языками программирования и язы-ками спецификации может быть весьма условным: если язык спецификаций имеет реализацию на компьютере, позволяющую как-то выполнять представленные на нём спецификации (например, с помощью интерпретатора), то такой язык является и языком программирования, может быть, и не позволяющий создавать эффективные программы. Однако, для языка спецификаций важно не эффективность выполнения спецификации на компьютере, а её выразительность. Язык спецификации, не являющийся языком программирования, также может быть полезен в процессе разработки ПС (для автоматизации контроля, тестирования и т.п.). Язык спецификации может базироваться на каком-либо из рассмотренных методов описа-ния семантики функций, а также поддерживать спецификацию функций для какой-либо кон-кретной предметной области.
