№1 Зертханалыќ ж±мыс

1. 
   Рекурсия мехнизімінің жұмысын талдау
   
2. 
   Тұрақты сандар арқылы рекурсия механизмін жүргізу
   
3. 
   cdr функциясына тізбек құру
   

№4, 5 Зертханалық жұмыс

• 
  Прологтағы ДҚ-мен жұмыс және тізімдерді пайдалану
  
• 
  Қарапайым предикатты сипаттайтын Прологта программа құру
  

1	2	3
4	5	6
7	8	9

move(1, 6) . move(3, 4) .move(6, 7) .move(8, 3)

move(1, 8) . move(3, 8) .move(6, 1) .move(8, 1)

move(2, 7) . move(4, 3) .move(7, б) .move(9, 4)

move(2, 9) . move(4, 9) .move(7, 2) .move(9, 2)

path(Z, Z).

path(Х, Y) : — move(Х, W), not(been(W)), assert(been(W)), path(W, Y)

Соңғы белгіленген path предикатының анықтамасы оның пролог тіліндегі іске асуы. Жоғарыда келтірілген assert — пролог тіліндегі ішкі предикат, ол өз аргументтерін спецификациялар дерек қорына орналастырады және үнемі "шын" деген мәнге ие. Been –предикаты бұрынғы болған алдыңғы күйлерді жазуға және циклдерді болдырмауға пайдаланылады.

been предикатын бұлай пайдалану глобалды айнымалыларды қолданбай предикаттар логикасында спецификациялар жасау жөніндегі программа құру мақсатына қайшы келеді. Мысалы been (3 ) деректер қорына қосқан соң, ол глобалды мағынаға ие факт бола алады. Бұл фактіні осы деректер қорына кез келеген процедура қолдана алады.

Программаны басқаруда глобалды құрылымдар жасау продукциял лық жүйелерде есеп логикасы (есеп спецификациясы) программа басқарудан бөлек сақтанады. ық жүйелерді үлгілейтін негізгі принципіне қайшы келеді. Подукция жоғарыдағы мысалда been құрылымы программа орындалуын модификациялауға арналған глобальды специфика ретінде құрылған.

path – предикатын шақырғанда жүріп өткен күйлерді есепке алу үшін және циклдарды болдырмау үшін тізімді пайдалануға болады. Ұқсас күйлерді (циклдарды ) анықтау үшін member предикатын пайдалануға болады. Бұндай тәсіл been (W) – глобалды тұжырымын қолдану проблемасын айналып өтуге мүмкіндік береді.

Пролог тіліндегі тереңнен іздеу әдісінің қайталау алгоритмі көмегімен шешімі былайша іске асады:

а1Ь(Е Z, L) .

а~1«(Х, У, Ь): — move (Х, Е), not (member (Z, Ь) ), path(Z, Y, [Z ~ Ь] )

Мұндағы member — жоғарыда анықталған предикат.

path — предикатының үшінші аргументі жүріп өткен күйлерден тұратын тізімді көрсететін локалды айнымалы . Жаңа күй генерацияланғанда (move предикатын пайдалана отырып ол [Z ( Ь] – күйлер тізімінің басында болады да қайтадан path – шақырады. Бұл шақыру егер осы уақытқа дейін айнымалы жүріп өткен күйлер тізімінде болмаса, not (member (Z, Ь) ) path – предикатының барлық параметрлері локалды болады және олардың ағымдағы мәні іздеу графын шақыру орнына тәуелді. Әр рекурсивтік шақыруда бұл тізімге жаңа күй қосылады. Егер берілген күйдің туындылары сәтсіз болса, path шақыруы да сәтсіз болады. Егер интерпретатор аталық шақыруға қайтса, онда жүріп өткен күйлерден тұратын тізімді беретін үшінші параметр өзінің алдыңғы мәнін қабылдайды.

Осылайша, графтағы қайталап іздеу процесінде күйлер тізімге қосылып және өшіріліп отырады.

path – шақыруы сәтті аяқталғанда, алғашқы екі параметр бірден мән қабылдайды. Үшінші параметр - шешім жолындағы жүріп өткен күйлерден тұратын тізім. Бұл жолда аталған күйлер кері тәртіпте беріледі. Осылайша шешім табудың барлық кезеңдерін басып шығаруға болады. Сонымен тізімдерді және графтағы қайталап іздеу көмегімен «Ат жүрісі»есебіне арналған Пролог спецификациясын path және move,member предикаттарын пайдаланып құруға болады. .

рath(X, Y, [Х] ) командасын Пролог интерпретаторымен шақыру, мұндағы Х және Y — 1-ден 9 саны аралығындағысандар. Х күйінен У –күйіне көшетін жолды табуға мүмкіндік береді. Егер әрине мұндай жол болса. Үшінші параметр Х алғашқы күйінің жүріп өткен күйлерден тұратын тізімін инициализациялайды. Пролог тілінде таңбалар регистрі есепке алынбайды. Алғашқы екі параметр есептің анықталу аумағындағы кез-келгенкүйлерді бейнелейді, ал үшінші параметр –күйлер тізімін көрсетеді. Унификация көмегімен барлық мүмкін болатын деректер типтерінің шаблондарға сәйкестігінің жалпылама тексерілуі оырндалады.

Осылайша рath –кез келген графқа қолдануға болатын тереңнене іздеудің жалпылама алгоритмі.

ЗХЗ – тақтасында берілген "ат жүрісі"есебіне қайтадан оралайық. Осы мысалдың Зх8 тақтасына арналаған түрінің РROLOG тіліндегі шешімін қарастырайық. Ол үшін path – алгоритмінің екі жағын нөмірлейік.

1. is path(Е, Е, ь) .

2. is path(X, Y, Ь): — move(Х, Z), not(member(Z, Ь) ), path(Z, Y, [Е (Ь] )

?- path(1, 3, [1] ) .

Мысалдың трассировкасы мынадай болады.

path(1, 3, [1] ) attempts to match 1. fail 1 Ф 3.

path(1, 3, [1] ) matches 2. Х is 1, Y is 3, L is [1]

move(1, Е) matches Z as б, not(member(6, [1] ) ) is true,

call path(6, 3, [6,1] )

path(6, 3, [6,1]) attempts to match 1. fail б ~ 3.

path(6, 3, [6,1]) matches 2. Х is б, Y is 3, ? is [6,1].

move(6,Е) matches Z as 7, not(member(7,[6, 1])) is true,

path(7, 3, [7, б, 1] )

path(7,3,[7,6,1]) attempts to match 1. fail 7 Ф 3.

path(7,3,[7,6,1]) matches 2. Х is 7, Y is 3, L is [7,6,1].

move(7,Z) is Е=б, not(member(6,[7,6, 1])) fails, backtrack!

move(7,Z) is Z=2, not(member(2,[7,б,1])) true,

path(23,[2,7,б,1])

path call attempts 1, fail, 2 Ф 3.

path matches 2, Х is 2, Y is 3, ? is [2,7,6,1]

move matches Z as 7, not(member(...)) fails, backtrack!

move matches Z as 9, not(member(...)) true,

path(9,3,[9,2,7,б,1])

path fails 1, 9 Ф 3.

path matches 2, Х is 9, Y is 3, L is [9,2,7,6,1]

move is Z = 4, not(member(...)) true,

path(4, 3,[4,9,2,7,6,1])

path fails 1, 4 Ф 3.

path matches 2, Х is 4, Y is 3, ? is [4,9,2,7,6,1]

move Z = 3, not(member( )) true,

path(3 3,[3,4,9,2,7,6,1])

path attempts 1, true, 3 = 3, yes

yes

yes

yes

yes