10.Семантика на термове.Компактност на термове.

Един терм c ще наричаме функционален ако в c не участват обектови променливи.Терма c наричаме основен ако в него участват нито обектови, нито функционални променливи.Всеки основен терм представлява израз който съдържа само константи и основни операции и който може да бъде пресметнат.Ако c е основен терм то | c| ще използваме ст-ста на c . Ако c (Х₁,..., Х_n ,F₁^m1 ,, F_k^mk ) е терм а c₁,..., c_n са термове от тип Nat то с c (Х₁ / c₁ ,..., Х_n / c_n , F₁^m1 ,, F_k^mk ) ще означяваме терма получен от c чрез замяна на всички участия на променливите Х₁,..., Х_n съответно с c₁,..., c_n . Ако термовете c₁,..., c_n са функционални то и c (Х₁ / c₁ ,..., Х_n / c_n , F₁^m1 ,, F_k^mk ) ще е функционален терм.Ще използваме буквите l и u ,евнтуално с индекс за означяване на функционални термове , а с а,b,c,d,ще означяваме константи.Често пъти c (Х₁,..., Х_n ,F₁^m1 ,, F_k^mk ) ще съкращаваме като c (Х/ l, F).Операционната семантика на рекурсивните програми се основават на специални правила за опростяване на функционални термове.По-натаък изразът от вида lс където l е функционален терм ,а с константа ще наричаме опростяване.Нека е дадена рекурсивна програма R:

c₀ (Х₁,..., Х_n ,F₁^m1 ,, F_k^mk ), where

F_i^mi (Х₁,..., Х_mi )= c_i (Х₁ ,, Х_mi , F₁^m1 ,, F_k^mk),i=1,..,k.

Семантиката на R с предаване на параметрите по ст/ст се базира на изброените правила за опростяване.Ще предполагаме че типовете на функционалните термове са подбрани така че всички написани изрази имат смисъл.

0)сс за всяка константа с.

1)Нека f е n-местна основна операция , l ₁ с₁ ,..., l _n c _n и f(с₁ ,..., c _n)=с.Тогава f(l ₁ ,.., l _n)с.

2.Ако ptt и l ₁ с,то if p then l ₁ else l ₂ c.

2б)Ако p ff и l ₂ с, то if p then l ₁ else l ₂ ђc.

3)Нека 1ik.Ако l _m1 с₁ ,, l _mi c _mi и c₁ (Х₁ / с₁ ,..., Х _mi /с _mi , F)с , то F_i^mi (l ₁ ,, l _mi )c.

Горните правила са всъщност два вида.Правилото 0) е приложимо директно докато за да приложим останалите правила трябва да разполагаме с известни опростявания които са необходими за да се удовлетворят съответните предпоставки.Първите ще наричаме директни а вторият вид индуктивни.