Основы программирования

Лекция 5 - Операционная семантика
Индекс материала
Лекция 5
Метод таблиц решений
Операционная семантика
Денотационная семантика
Аксиоматическая семантика
Аксиоматическая семантика1
Все страницы

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-ом шаге получено.