В операционной семантике алгебраического подхода к описанию семантики функций рассматривается следующий частный случай системы равенств (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-ом шаге получено.