8.Синтаксис на рекурсивните програми.

Ще разгледаме само два типа данни: Nat и Bool.Елементите на Nat ще бъдат естествените числа.Ще предполагаме че разполагаме и с определен запас от операции от тип Natⁿ Nat, n1, като +, * и т.н.Елементите на Bool ще са булевите ст/сти tt и ff. За всички операции в основните типове данни ще използзваме термина основни операции.синтактични елементи на езика:

• константи за означяване на елементите на Bool и Nat

• символи за основните операции

• обектови променливи от тип Nat коитто ще означяваме с главни латински букви,евентуално с индекс

• функционални променливи F_kⁿ , n=1,2; k=0,1,, където всяка променлива с горен индекс n е от тип Natⁿ ђ Nat .

Ще използваме три вида термове които ще наричаме съответно термове от тип Nat , термове от тип Bool и условни термове. Термовете от тип Nat се определят посредством следната индуктивна дефиниция:

1.Всяка константа от тип Nat е терм.

2.Всяка обектова променлива е терм.

3.Ако f е основна операция от тип Natⁿ ђ Nat , а c₁,..., c_n са термове от тип Nat ,то f(c₁,..., c_n) е терм от тип Nat.

4.Ако F е финкционална променлива от тип Natⁿ ђ Nat а c₁,..., c_n са термове от тип Nat то F(c₁,..., c_n) е терм от тип Nat.

Термове от тип Bool се определят както следва:

1.Булевите константи са термове от тип Bool.

2.Ако f е основна операция от тип Natⁿ ђ Bool , а c₁,..., c_n са термове от тип Nat то (c₁,..., c_n) е терм от тип Bool.

3.Ако f е основна операция от тип Bool ⁿ ђ Bool а p ₁,..., p _n са термове от тип Bool то f(p ₁,..., p _n) е терм от тип Bool.

Накрая ще определим условните термове.Това са изрази от вида if p then c₁ else c₂ където p е терм от тип Bool а c₁ и c₂ са термове от тип Nat.Ако c е терм от кой да е тип то в c може да участвуват най-много краен брой обектови и функционални променливи.Ще използваме записването c(Х₁,..., Х_n ,F₁^m1 ,, F_k^mk ), за да означяваме че всички обектови променливи-сред F₁^m1 ,..., F_k^mk .Рекурсивна програма ще наричаме синтактичен обект R от следният вид:

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

F₁^m1 (Х₁ ,, Х_m1)= c₁ (Х₁ ,, Х_m1 , F₁^m1 ,, F_k^mk)

.

F_k^mk (Х₁ ,, Х_mk)= c_k(Х₁ ,, Х_mk , F₁^m1 ,, F_k^mk)

където всеки от термовете c₁,..., c_к е от тип Nat или е условен терм а c₀ е от тип Nat.Както се вижда от синтаксиса, рекурсивните програми твърде много наподобяват програни на Lisp.Основнта разлика е че ние сме въвели списъци и не представяме самите програми като списъци.Рекурсивните програми са въведени в теоретичното програмиране от автора на езика Lisp Дж. Маккарти макар че под една или друга форма те са били изучавани и преди него.Пример на рекурсивна програма:

F(Х), where

F(Х)= if Х =0 then 1 else F(Х-1)*Х