Пәндердің оқу-әдістемелік кешенінің тізімдемесі
Тақырыбы: Пролог тілінің түсіндіргішін оқып білу
жүктеу/скачать 2.35 Mb.
|
- Бұл бет үшін навигация:
- Есептің қойылуы
| Тақырыбы: Пролог тілінің түсіндіргішін оқып білу
Мақсаты: Пролог тілінің түсіндіргіші жұмысының алгоритмін оқып білу, Пролог тілінің түсіндіргішінің Лисп-бағдарламасын оқып білу, Лисп тілінде Пролог тілінің түсіндіргішін құру және жетілдіру қабілетіне ие болу. Есептің қойылуыПролог тілі – логикалық бағдарламалау тілі. Прологтың теоретикалық негізі бірінші реттік предикаттарды есептеу болып табылады. Пролог декларативті тілдерге жатады. Пролог тілінде бағдарламалау келесі қадамдардан тұрады: нысаналар және олардың арасындағы қатынастар жөнінде кейбір фактілерді жариялау; нысаналар және олардың арасындағы қатынастар жөнінде кейбір ережелерді анықтау; нысаналар және қатынастар жөнінде сұрақтарды құру. Ережелер, фактілер және мақсаттар хорновтық дизъюнкттер (клоздар). Ережелер келесі түрде ұсынылады: B:-A1, A2,…,An (n>=1), мұндағы Ai, i=1,2,…,n – шарттар, В – қорытынды. Ереженің мұндай жазылуы келесі түрдегі импликациямен бірдей күшке ие: A1 & A2 &…& An ->B Фактілер тек қана қорытындылардан тұратын клоздар түрінде ұсынылады: В:- Тек :-A1, A2,…,An түріндегі шарттардан тұратын клоздар теріске шығару формасында ұсынылған мақсаттық жорамалдар (мақсаттар) ретінде түсіндіріледі. Прологта іздеу және қайтаруы бар логикалық механизм бар. Прологта мақсаттық жорамалдарды дәлелдеу үшін семантикалық түзу сызықты резолюция қолданылады. Пролог түсіндіргішін құрудың негізі болып ережелердің процедуралық түсіндірілуі табылады. Осыны ескере отырып “логикалық шығару” термині орнына “есептеу” термині қолданылады. “Мақсатты дәлелдеу” термині орнына кейде “мақсаттық жорамалдарды мәліметтер базасымен келістіру” термині қолданылады. Бағдарламаның орындалуының ағымдағы қадамында дәлелденуі тиіс мақсаттардың коньюнкциясын резольвента деп атаймыз. Басында резольвента бастапқы шартпен (сұрақпен) сәйкес келеді. Егер кезектегі мақсатты тиімді унификациялағаннан соң, осы мақсатты таңдап алынған ереженің денесімен ауыстырсақ, онда бағдарламаның орындалуының кезектегі қадамы үшін резольвента аламыз. Мазмұны берілген мақсатпен сәйкес келетін Р бағдарламасындағы G мақсатын сол ереженің денесімен ауыстырумен байланысты операция редукция деп аталады. Бұл жағдайда ауыстырылатын мақсат алынған, ал қосылатын мақсат туынды деп аталады. А термі В термінің нұсқасы (немесе нақтылануы) деп аталады, егер A=#B болатындай, # алмастырып қойылу бар болса. #B термі В-дағы айнымалылардың барлық сәйкестіктерінің, # -ға қатысты олардың образдарына алмастырылушы болады. {T1, T2,…, Tn} термдер жиыны унифицирленеді, егер #[T1]=#[T2]=…=#[Tn] болатындай, # алмастырылып қойылу бар болса. Бұл жағдайда # -ні {T1, T2,…,Tn} үшін унификатор деп атаймыз, өйткені оны қолданған жағдайда бұл жиын бір элементке “жабысады”. {Ti} жиыны үшін барынша жалпы (немесе қарапайым) унификатор (БЖУ) L сондай қасиетке ие, егер # - {Ei} үшін #[Ei] беретін кез-келген унификатор болса, онда #[Ei]=#’*L[Ei] болатындай, кейбір #’ алмастырылып қойылу бар. Мұндағы * - алмастырылып қойылу композицияларының операциясы. Унификация алгоритмі төменде Лисп тілінде жазылған unify рекурсивті унификация функциясын оқып жатқанда қарастырылады. Әр түрлі ережелерде бірдей айнымалыларды қолданғанда жаңылысуды жою үшін, сөйлем редукцияны орындау үшін таңдап алынатын жағдайдың барлығында айнымалылардың атын өзгертеміз. Жаңа аттардың арасында алдын есептелуде қолданылған айнымалылар кездеспеу керек. Бірінші жуықтауда түсіндіргіш жұмысының алгоритмін келесі түрде сипаттауға болады. Шығатын мәліметтер. Р логикалық бағдарламасы және G сұрағы. Нәтиже. Q[G] өрнегі, егер бұл үлгі Р-дан шығатын болса, немесе тиімсіздік жөнінде хабар, егер шығару мүмкін болмаса. Алгоритм. Бастапқы резольвента ретінде кіріс G мақсатын қабылдау. Егер резольвента бос болмаса, резольвентадағы ең сол жақ мақсатты G ағымдағы ретінде алу. 4-пунктті орындау. Егер резольвента бос болса, онда алынған үлгі сұраққа жауап болады. 16-пунктті орындау. Бастамасының функторы ағымдағы мақсаттың функторымен сәйкес келетін ережені бағдарламадан табу. Егер бағдарламада ереже табылса, 10-пунктті орындау. Егер бағдарламада ереже табылмаса, 15-пунктті орындау. Бағдарламадан кезектегі альтернативті ережені табу. Егер осындай ереже бар болса, 10-пунктті орындау. Егер альтернативті ережелер басқа жоқ болса, 13-пінктті орындау. Таңдалған ережені және ағымдағы мақсатты унификациялау. Егер унификация тиімді жүргізілген болса, онда ағымдағы мақсаттың редукциясын орындау. 2-пунктті орындау. Егер унификация тиімсіздікпен аяқталса, 7-пунктті орындау. Егер алдыңғы қадамның мақсаты бастапқы мақсат болса, онда 15-пунктті орындау. Егер алдыңғы қадамның мақсаты бастапқы мақсат болмаса, онда ағымдағы мақсатты алдыңғы қадам мақсатымен ауыстыру. 7-пунктті орындау. Тиімсіздік жөнінде хабар шығару. Алгоритмнің орындалуын аяқтау. Келтірілген алгоритмді іске асыратын түсіндіргіш берілген мақсаттың бірінші үлгісін тапқаннан соң тоқтауы тиіс. Түсіндіргіштерде қайта қосу механизмі қарастырылған. Ол мақсаттың басқа үлгілері бар болған жағдайда оларды алуға мүмкіндік береді. Төменде xlisp тілінде жазылған Пролог тілінің түсіндіргіші қарастырылады. Rename_variables, print_bindings, try_each, unify, value функциялары рекурсивті, өйткені осы функциялардың анықталуында осы функциялардың өздерінің шақырылуы бар. Бұдан басқа prove және try_each функциялары өзара рекурсивті, себебі олардың анықталуында бір-бірін шақыру бар. Түсіндіргішті іске қосу келесі жолмен орындалады: (prolog db), мұндағы db – мәліметтер базасы (database). Мәліметтер базасы факттер мен ережелерден тұратын тізім түрінде ұсынылады. Факттер мен ережелер өз кезегінде тізім формасында ұсынылады. Ережелердегі айнымалылар келесі түрдегі екіэлементті тізім түрінде ұсынылады: (? <айнымалы аты>). Тізімде басы мен құраушы бөліктің кезектесу реті сақталады. Мысалы, Прологта father(madelga, ernest). түрінде анықталатын факт (father madelga ernest) түріндегі тізім түрінде ұсынылады, ал grandparent(X, Y):- parent(X, Z), parent(Z, Y). түріндегі ереже ((grandparent(? X) (? Y)) (parent(? X) (? Z)) (parent(? Z) (? Y))). түріндегі тізім. Басқа да негізгі құрылымдар арасынан айнымалыларының өздерінің мәндерімен байланысы сақталатын (әйтпесе алмастырып қою) ассоциативті тізімді environment бөлуге болады. Level сандық параметрі көмегімен өзгеше ережелердегі бір аттас айнымалылардың байланыстары өзгешеленеді. Пролог түсіндіргішінің негізгі циклі жоғарғы деңгейлі функция prolog арқылы жүзеге асырылады. Мұнда database параметрі ретінде Пролог-бағдарлама беріледі. Функция келесі түрде xlisp тілінде анықталған: (defun prolog (database &aux goal) (do () ((not (progn (princ “Query ?”) (setq goal (read))))) (prove (list (rename-variables goal ‘(0))) ‘((bottom-of-environment)) database 1))) Функция “Query ?” қатарын шығарады да қолданушының goal мақсаттық тұжырымдамасын енгізуін күтеді. Егер бос тізім енгізсек, түсіндіргіш жұмысын аяқтайды. Енгізілген мақсаттық тұжырым prove функциясына дәлелдену үшін беріледі. Одан алдын, мақсаттық тұжырымдағы айнымалылар аты өзгертіледі және оларға 0 деңгейі тағайындалады. (bottom-of-environment) тізімі айнымалылар байланысының стек түбі маркері ретінде енеді. Prove функциясы xlisp тілінде келесі жолмен анықталады: (defun prove (list-of-goals environment database level) (cond ((null list-of-goals) (print-bindings environment environment) (not (y-or-n-p “More ?”))) (t (try-each database database (cdr list-of-goals) (car list-of-goals) environment level)))) prove функциясы келесі парамертлерді алады: list-of-goal – резольвентаны (мақсаттар тізімі түрінде); environment – айнымалылар байланысы; database – тізім формасындағы Пролог-бағдарлама; level – деңгей. Prove функциясы мақсаттар тізімін тексереді, егер берілген тізім бос болса, онда мақсаттық тұжырым дәлелденді деп есептелінеді. Айнымалылар байланысы шығарылады, y-or-n-p функциясы шақырылады. Бұл функция мақсаттық тұжырымды дәлелдеуде альтернативті шешімдерді іздеуді жалғастыру керек пе жоқ па сұрайды. Егер list-of-goal мақсаттар тізімі бос емес болса, онда осы тізімдегі мақсаттарды дәлелдеу үшін try-each функциясы шақырылады. Мұнда тізімдегі бірінші мақсат ағымдағы болып алынады. Try-each функциясының тексті төменде көрсетілген: (defun try-each (database-left database goals-left goal environment level &aux assertion new-environment) (cont ((null database-left) nil) (t (setq assertion (rename-variables (car database-left) (list level))) (setq new-environment (unify goal (car assertion) environment)) (cond ((null new-environment) (try-each (cdr database-left) database goals-left goal environment level)) ((prove (append (cdr assertion) goals-left) new-environment database (+1 level))) (t (try-each (cdr database-left) database goals-left goal environment level)))))) try-each функциясы келесі параметрлерді алады: database-left – дәлелдеу процесінде қолданылатын Пролог-бағдарламаның қалдығы; database – барлық Пролог-бағдарлама; goals-left - әлі дәлелденбеген мақсаттар мен резольвенталар; goal – ағымдағы дәлелденіп жатқан мақсат; environment – айнымалылар байланыстары; level – деңгей. try-each функциясы database-left тізімін тексереді. Егер тізім бос балса, функция NIL (дәлелдеу кезіндегі тиімсіздік белгісі) қайтарады. Қарсы жағдайда Пролог-бағдарламаның қалдығынан кезекті ережені (assertion) таңдайды, rename-variables функциясының көмегімен айнымалылардың атын өзгертеді және unify функциясының көмегімен таңдалған ереженің басын (car assertion) және ағымдағы мақсатты (goal) унификациялайды. Егер унификация тиімсіз өтсе (new-environment тізімі бос), онда Пролог-бағдарламаның қалдығынан ағымдағы унификацияланбайтын ереже алып тасталынады да дәл сол goal мақсатын дәлелдеу үшін try-each функциясы шақырылады. Егер унификация тиімді өтсе (new-environment тізімі унификациялаудан пайда болған жаңа айнымалылар байланысына ие), онда ағымдағы мақсаттың goal редукциясы ағымдағы ереже assertion денесінің предикаттарын дәлелденбеген мақсаттар тізіміне goal-left енгізу және жаңа резольвентаны goal-left дәлелдеу үшін prove функциясын шақыру арқылы іске асырылады. Егер осы резольвентаның дәлелденуі тиімсіз өтсе, Прологөбағдарламаның қалдығынан ағымдағы ереже алынып тастайды және Пролог-бағдарламаның осы қалдығында алдыңғы резольвентаны goal дәлелдеу әрекеті жасалынады. Unify функциясы екі термді х және у унификациялау үшін арналған. Үшінші парамаетр ретінде функция ағымдағы БЖУ-ды ұсынатын environment тізімді алады. Функция БЖУ немесе NIL қайтарады (NIL – егер термдер унификацияланбайтын болса немесе БЖУ бос тізім). Xlisp тілінде unify функциясы келесі түрде ұсынылады: (defun unify (x y environment &aux new-environment) (setq x (value x environment)) (setq y (value y environment)) (cond ((variable-p x) (cons (list x y) environment)) ((variable-p y) (cons (list y x) environment)) ((or (atom x) (atom y)) (cond ((equal x y) environment) (t nil))) (t (setq new-environment (unify (car x) (car y) environment)) (cond (new-environment (unify (cdr x) (cdr y) new-environment)) (t nil))))) unify(x, y, environment) функциясының алгоритмі – унификациялау келесі жолмен жазылуы мүмкін: value функциясының көмегімен х-ке х мәнін тағайындауға әрекет жасау. value функциясының көмегімен у-ке у мәнін тағайындауға әрекет жасау. Егер х айнымалы болса, онда құрылып жатқан БЖУ-ға (environment) (х, у) жұбын қосу. Environment қайтарылады. Егер у айнымалы болса, онда құрылып жатқан БЖУ-ға (environment) (у, хы) жұбын қосу. Environment қайтарылады. Егер х немесе у атом болса, онда егер х=у, онда environment қайтарылады әйтпесе NIL қайтарылады. Егер 3, 4, 5-пункттердің шарттары орындалмаса, онда істеу керек х және у тізімдерінің бірінші элементтерін унификациялау жолымен олардың БЖУ алу – new-environment егер new-environment бос емес болса (унификация тиімді өтті), онда істеу керек х және у тізімдерінің басының унификацияланғанын және БЖУ – new-environment құрылғанын еске ала отырып х және у тізімдерінің соңын унификациялау соңын унификациялау нәтижесінде құрылған БЖУ қайтарылады соңы БЖУ келесі түрдегі жұптар тізімі екенін ескеру қажет: (<айнымалы><орын басушы терм>). Unify функциясы айнымалының орын басушы термге сай келуін тексермейді. Дегенмен айнымалының орын басушы термге сай келуі қате жағдай. Value функциясы айнымалының мәнін анықтауға арналған. Функцияның параметрлері: х – айнымалы (? символымен басталатын тізім түрінде); environment – айнымалылар байланыстары. Функция айнымалы мәнін қайтарады, егер айнымалымен оның мәні арасында байланыс бар болса немесе айнымалы атын қайтарады, егер айнымалымен environment тізіміндегі мән байланысты болмаса. Егер х – айнымалы емес болса, онда есептелмеген х-тің өзі қайтарылады. Функцияның тексті төменде көрсетілген: (defun value (x environment &aux binding) (cond ((variable-p x) (setq binding (assoc x environment :test #’equal)) (cond ((null binding) x) (t (value (cadr binding) environment)))) (t x))) Нақтыланбаған айнымалының өзінің мәні – басқа айнымалының аты, басқаша айтқанда басқа айнымалыға бағыттауыш болатынын ескеру керек. Осылайша, environment ассоциативті тізіміндегі айнымалылар “тізбектелуі” мүмкін, яғни қандай да бір логикалық тізім құрады. Value функциясы осы рекурсиялық тізбектің басы ретінде рекурсиялық шақырулар жолымен х айнымалысын алып, осы тізбекті “айналдырады” және өзінің мәні ретінде элемент – тізім соңын қайтарады. Variable-p функциясы оның жалғыз кіріс параметрі х айнымалы ма жоқ па тексереді. Бұл функцияның тексті келесідей: (defun variable-p (x) (and x (listp x) (eq (car x) ‘?))) Функция денесінің сипатталуына сәйкес егер х тізім және осы тізімнің бірінші элементі ? символы болса, х айнымалы болып табылады. Терминдерде кездесетін айнымалылар “аты өзгертілу” xlisp тіліндегі тексті төменде келтірілген rename-variables функциясымен іске асады: (defun rename-variables (term list-of-level) (cond ((variable-p term) (append term list-of-level)) ((atom term) (t (cons (rename-variables (car term) list-of-level) (rename-variables (cdr term) list-of-level))))) Функцияның кіріс мәліметтері: term – тізім формасындағы терм; list-of-level – деңгей. Функция аты өзгертілген айнымалылары бар тем қайтарады. Айнымалылардың аты өзгертілуі айнымалыға деңгейдің сандық мәнін қосумен сай келеді. Бұл басқа функцияларда әр түрлі ережелердегі бірдей атты айнымалылардың байланыстарын ажыратыға көмек береді. Rename-variables функциясының жұмысына мысал: (rename-variables ‘((parent (? x) (? y))) ‘(0)) (parent (? x 0) (? y 0)) print-binding функциясы функцияның бірінші параметрі болып табылатын environment-left тізімінің айнымалыларының байланыстарының мәндерін шығарады. Xlisp тілінде бұл функция келесі түрде анықталады: (defun print-bindings (environment-left environment) (cond ((cdr environment-left) (cond ((= 0 (nth 2 (caar environment-left))) (prit1 (cadr (caar environment-left))) (princ “ = “) (print (value (caar environment-left) environment)))) (print-bindings (cdr environment-left) environment)))) Функция келесідей жолмен жұмыс істейді. Environment-left тізімінің оқылып жатқан қалдығының соңғы бөлігінің бос бос еместігі тексеріледі. Егер ол бос емес болса, environment-left жұптар тізімінде бірінші болып тұрған айнымалының деңгейі тексеріледі (айнымалы caar environment-left сөйлемімен анықталады). Егер ол нольге тең болса, онда айнымалы аты (айнымалыны ұсынатын – (cadr (caar environment)) тізімінде екінші болып тұр), “=” таңбасы және value функциясының көмегмен анықталатын айнымалының мәні баспаға шығарылады. Егер environment-left соңғы бөлігі бос болса, print-bindings функциясы рекурсиялық түрде шақырылады, ол рекурсияның келесі қадамында cond-тың екінші операторымен NIL мәнінің қайтарылуына және сол арқылы рекурсияның өшуіне алып келеді. y-or-n-p функциясы Пролог-түсіндіргішпен альтернативті шешімді іздеуді бекітетін (у) немесе бекітпейтін (у-тен бөтен жауап) жауапты енгізу үшін арналған. Функцияның тексті төменде келтірілген: (defun y-or-n-p (promt) (princ promt) (eq (read) ‘y)) жүктеу/скачать 2.35 Mb. Достарыңызбен бөлісу:
|