برنامه نويسی پرولوگ & Fol
صابر اميرنوين
مقدمه • اشياء داده ای ساده – اتم ها ( ثابت های غير عددی) – اعداد – متغيرها
• • • • • • 2
اشياء ساخت يافته تطابق معنای توصيفی يک برنامه معنای رويه ای يک برنامه ارتباط معنای توصيفی و رويه ای يک برنامه تغيي ر معنای روي ه ای توس ط تغيي ر دادن ترتيب فراکردها و اهداف
مقدمه • مکانيزم های پايه ای در پرولوگ – فراکردهای پرولوگ ()Clauses – حقايق ()Facts – قوانين()Rules – رويه ها ()procedures
• مکانيزم عقبگرد در پرولوگ ()backtracking • تفاوت معنای توصيفی و رويه ای يک برنامه
تعريف روابط بوسيله حقايق • پرولوگ يک زبان برنامه نويسی برای محاسبات نمادين و غير عددی می باشد. • پرولوگ برای حل مسائلی که شامل اشياء و روابط ميان آنها می باشند بسيار مناسب می باشد. • مثال :روابط خانوادگی – اين حقيقت که Tomپدر Bobاست را در پرولوگ به صورت زير نمايش می دهيم:
parent(tom, bob). در اينجا parentنام رابطه و Tomو Bobآرگومانهای رابطه می باشند. توجه :اسامی خاص مانند tomبايد با يک حرف کوچک الفبا نوشته شوند.
تعريف روابط بوسيله حقايق .• اين برنامه از شش فراکرد تشکيل شده است . می باشدparent • هر فراکرد يک نمونه از رابطه parent)tom, bob(.
pam
tom
parent)pam, bob(. bob
parent)tom, liz(.
liz
parent)bob, ann(. parent)bob, pat(. parent)pat, jim(.
ann
pat
jim
تعريف روابط بوسيله حقايق آيا Bobپدر Patمی باشد؟ ?- parent)bob, pat(. yes اين به صورت يک حقيقت در برنامه ذکر شده است. ?- parent)liz, pat(. no در برنامه چنين رابطه ای بيان نشده است. ?- parent)tom, ben(. no برنامه نام Benرا نشنيده است.
تعريف روابط بوسيله حقايق چه کسی والد Lizمی باشد؟ ?- parent)X, liz(. پرولوگ در پاسخ به اين پرسش سعی می کند برای X مقداری بيابد که عبارت بال درست باشد. X = tom فرزندان Bobچه کسانی می باشند؟ ?- parent)bob, X(. ;X = ann مکانيزمی برای درخواست ;X = pat پاسخهای بيشتر no
تعريف روابط بوسيله حقايق چه کسانی والد چه کسانی می باشند؟ ?- parent)X, Y(. X = pam ;Y = bob X = tom ;Y = bob X = tom ;Y = liz …
تعريف روابط بوسيله حقايق جد Jimچه کسی است؟
?- parent)Y, jim(, parent)X, Y(. X = bob Y = pat اگر ترتيب دو درخواست را در پرسش بال عوض کنيم معنای منطقی ثابت باقی می ماند و بنابراين پرسش زير همان پاسخ بال را توليد می کند. ?- parent)X, Y(, parent)Y, jim(.
تعريف روابط بوسيله حقايق نوه های Tomچه کسانی هستند؟ ?- parent)tom, X(, parent)X, Y(. X = bob ;Y = ann X = bob Y = pat
تعريف روابط بوسيله حقايق آيا Annو Patوالد مشترکی دارند؟ کنيم Xباشد) ?- parent)X, ann(, parent)X, pat(. X = bob
تعريف روابط بوسيله حقايق • • • • • •
در پرولوگ تعريف روابط به سادگی توسط يک -nتايي از اشياء که رابطه را ارضاء می کنند،انجام می شود. کاربر به سادگی می تواند از پرولوگ در باره روابط تعريف شده در برنامه پرس و جو کند. يک برنامه پرولوگ از فراکردها تشکيل می شود. پرسش ها شامل يک يا چند هدف می باشند ،مانند: (parent)X, ann(, parent)X, pat اگر پاسخ پرولوگ به يک پرسش مثبت باشد در اين صورت می گوييم پرسش قابل ارضاء و گرنه غير قابل ارضاء می باشد. اگر پرسشی دارای پاسخهای متعددی باشد ،پرولوگ هر تعداد پاسخی را که کاربر بخواهد پيدا می کند.
تعريف روابط بوسيله قوانين برنام ه رواب ط خانوادگ ی را ب ا افزودن اطلعاتی مثل درباره جنسيت افراد می توان تعميم داد: female)pam(. male)tom(. male)bob(. female)liz(. female)pat(. female)ann(. male)jim(. روابط يکتايي و دوتايي.
تعريف روابط بوسيله قوانين • تعريف رابطه ( offspringعکس رابطه )parent اضافه کنيم :مثل offspring)liz, tom(. offspring)Y, X( :- parent)X, Y(. يعنی بازاء هر Xو ، Yاگر Xوالد Yباشد ،آنگاه Yفرزند Xمی باشد.
تعريف روابط بوسيله قوانين • تفاوت ميان حقايق و قوانين: – ي ک حقيق ت چيزی اس ت ک ه همواره و بدون هي چ قيد و شرطی درست می باشد. – از طرف ديگر يک قانون چيزهايی را بيان می کند که برای درستی آنها بايد برخی از شرايط ارضاء شوند.
• بنابراين قوانين از دوقسمت تشکيل می شوند: – بخش شرط ( )condition partو – بخش نتيجه (.)conclusion part offspring)Y, X( :- parent)X, Y(. head body
تعريف روابط بوسيله قوانين آيا Lizفرزند Tomاست؟ ?- offspring) liz, tom(. نحوه پاسخ دهی پرولوگ: چون قانون اسليد قبل بازاء هر Xو Yقابل اعمال است ،پس بر اشياء خاص Lizو Tomنيز قابل اعمال می باشد .برای اعمال اين قانون بر اين اشياء خاص ،بايد Yرا با Lizو Xرا با Tom در قانون فوق جايگزين کنيم( نمونه دهی) X = tom , Y = liz پس از جايگذاری ،ي ک نمون ه خاص از قانون را ب ه شک ل زير بدست می آوريم: (offspring)liz, tom( :- parent)tom, liz اکنون پرولوگ سعی می کند که دريابد آيا بخش شرط قانون بال درست است يا خير .چون بخش شرط درست است ( با توجه به حقايق موجود در برنامه) ،بنابراين پاسخ پرولوگ yesخواهد بود.
تعريف روابط بوسيله قوانين :تعريف رابطه مادری mother)X, Y( :- parent)X, Y(, female)X(. در قانون فوق علمت ويرگول به معنای ترکيب:توجه .) شرايط می باشدAnd( عطفی female
parent
offspring Y
X
X
X
parent
mother
parent Y
Y
parent grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
Z
grandparent
تعريف روابط بوسيله قوانين نحوه قالب بندی برنامه ها grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
نحوه مناسب نوشتن قوانين: grandparent(X, Z) :parent(X, Y), parent(Y, Z).
تعريف روابط بوسيله قوانين )sister(تعريف رابطه خواهری sister)X, Y( :parent)Z, X(, parent)Z, Y(, female)X(.
Z
female
?- sister)ann, pat(. yes ?- sister)X, pat(. X = ann; X = pat
parent
parent X
sister
Y
تعريف روابط بوسيله قوانين تصحيح رابطه خواهری sister)X, Y( :parent)Z, X(, parent)Z, Y(, female)X(, different(X, Y).
تعريف روابط بوسيله قوانين • نکات مهم: – تعميم برنامه های پرولوگ با افزودن فراکردهای جديد. – انواع فراکردها: • حقاي ق :بيانگ ر چيزهاي ي ک ه همواره و بدون شرط درس ت می باشند. • قوانين :بيانگر چيزهايي که درستی آنها بستگی به برخی شرايط دارد. • پرسش ها :وسيله ای که کاربر با آن می تواند از برنامه بپرسد چه چيزهايي درست هستند.
– فراکردها از دوقسمت تشکيل می شوند ( سرآيند و بدنه) • حقايق :قسمت بدنه آنها تهی • پرسش ها :فقط دارای بدنه • قوانين :دارای هر دو قسمت
قوانين بازگشتی )predecessor( تعريف رابطه اجدادی X
X
parent
predecessor
parent
Z
parent
predecessor
parent Z
قوانين بازگشتی :predecessor تعريف رابطه predecessor)X, Z( :parent)X, Z(. predecessor)X, Z( :parent)X, Y(, parent)Y, Z(. predecessor)X, Z( :parent)X, Y1(, parent)Y1, Y2(, parent)Y2, Z(. …
قوانين بازگشتی : به صورت بازگشتیpredecessor تعريف predecessor)X, Z( :parent)X, Z(.
%pr1
predecessor)X, Z( :parent)X, Y(, predecessor)Y, Z(.
%pr2
?- predecessor)pam, X(. X = bob; X = ann; X = pat; X = jim
قوانين بازگشتی تعريف رويه (:)procedure مانن د رابط ه predecessorدر مثال روابط خانوادگ ی ک ه توس ط دو فراکرد تعريف شده است. انواع توضيحات ( )commentدر پرولوگ: /* this is a comment */ % this is also a comment
نحوه پاسخ گويی به پرسشها در پرولوگ در پرولوگ ه ر پرس ش شام ل ي ک ي ا چن د هدف می باشد. پرولوگ برای پاسخ گويی به پرسشها سعی می کند اين اهداف را ارضاء کند. ارضاء هدف يعنی اينکه نشان دهيم هدف درست است ( با اين فرض که روابط موجود در برنامه درست می باشند). ارضاء هدف يعنی اينکه نشان دهيم هدف مورد نظر به طور منطق ی از حقاي ق و قواني ن موجود در برنامه می کند. اگر پرسشی شامل متغير باشد ،پرولوگ بايد دريابد که کدام اشياء خاص ( به جای متغيرها) اهداف را برآورده
نحوه پاسخ گويی به پرسشها در پرولوگ :مثال fallible)X( :- man)X(. man)socrates(. ?- fallible)socrates(. yes
نحوه پاسخ گويی به پرسشها در پرولوگ (predecessor)tom, pat predecessor)X, Z( :- parent)X, Z(. X = tom, Z= pat هدف جديد: (parent)tom, pat چون هي چ فراکردی در برنام ه وجود ندارد ک ه بخش سرآيند آن با اين هدف تطابق ( )matchداشته باشد، بنابراين اين هدف مردود می شود. اکنون پرولوگ به سمت هدف اول عقبگرد می کند تا روش ديگری برای ارضای آن پيدا کند .بنابراين قانون دوم predecessorرا امتحان می کند.
نحوه پاسخ گويی به پرسشها در پرولوگ predecessor)X, Z( :parent)X, Y(, predecessor)Y, Z(. مانند قبل متغيرهای Xو Zبا tomو patنمونه دهی می شوند: X = tom, Z = pat اکنون هدف اص لی يعن ی )predecessor)tom, patبا دوهدف جديد زير جايگزين می شود: parent)tom, Y(, (predecessor)Y, pat اکنون پرولوگ سعی می کند اين دو هدف را به ترتيب نوشتن آنها ارضاء کند.
نحوه پاسخ گويی به پرسشها در پرولوگ هدف اول يعنی )parent)tom, Yبه راحتی با يک حقيقت برنامه يعن ی )parent)tom, bobتطاب ق م ی ياب د ،بنابراين هدف اول بانمونه دهی Y=bobارضاء می شود و هدف دوم به هدف زير تبديل می شود: (predecessor)bob, pat دوباره برای ارضاء اين هدف قانون اول predecessorامتحان می شود ،يعنی قانون زير: predecessor)X’, Z’( :parent)X’, Z’(. از تطابق هدف و بخش سرآيند اين قانون نمونه دهی زير بدست می آيد: X’ = bob, Z’ = pat و هدف فعلی با هدف جديد زير جايگزين می شود: (parent)bob, pat اين هدف بلفاصله قابل ارضاء می باشد .و بنابراين هدف اصلی
نحوه پاسخ گويی به پرسشها در پرولوگ predecessor(tom, pat) by rule pr1 parent(tom, pat) no
by rule pr2 parent(tom, Y) predecessor(Y, pat) Y = bob
by fact parent(tom, bob)
predecessor(bob, pat) by rule pr1 parent(bob, pat) yes
اشياء داده ای data objects
simple objects
constants
atoms
structures
variables
numbers 32
اشياء داده ای • در پرولوگ نوع يک شيء توسط ساختار گرامری آن مشخص می شود. – متغيرها با يک حرف الفبايی بزرگ شروع می شوند. – اتم ها با يک حرف الفبايی کوچک شروع می شوند.
• در پرولوگ ات م ه ا و متغي ر ه ا رشت ه هايي از کاراکترهای زير می باشند: – – – – 33
حروف بزرگ A ،B ، ... ،Z حروف کوچک a ،b ، ... ،z ارقام 9 ، ... ،1 ،0 کاراکتر های خاص مانند ~ _ & . : = > < / * - +
ساختارها P1 = point)1, 1( P2 = point)2, 3( S = seg)P1, P2( = seg)point)1, 1(, point)2, 3( ( T = triangle)point)4, 2(, point)6, 4(, point)7, 1( ( triangle
point
point
4
2
6
point
4
7
1
34
تطابق • عم ل تطاب ق مهمتري ن عمل ی اس ت ک ه برروی عبارت ها در پرولوگ انجام می گيرد. • گوييم دو عبارت داده شده ،باهم تطابق دارند اگر:
شوند که بعد از جايگزينیعبارت ها با هم يکسان شوند .مثل: date)D, M, 2001( , (date)D1, may, Y1 D = D1 دو عبارت بال با هم تطابق دارند اگر: M = may Y1 = 2001 35
تطابق • توججه :عم ل تطاب ق در پرولوگ هميش ه منج ر به می شود. عمومی ترين نمونه دهی ها ?- date)D, M, 2001( = date)D1, may, Y1(, date)D, M, 2001( = date)15, M, Y(. D = 15 M = may D1 = 15 Y1 = 2001 Y = 2001 36
تطابق • الگوريتم تطابق دو عبارت :S, T تطابق هستند که هر دو شیء يکسانی باشند. انطباق هستند و Sبا Tنمونه دهی می شود و برعکس. تطابق می يابند که: 37و
تطابق تعريف خاصيت عمودی و افقی برای پاره خط ها: مثال vertical(seg(point(X, Y), point(X, Y1) ) ). horizontal(seg(point(X, Y), point(X1, Y) ) ).
•
?- vertical)seg)point)1, 1(, point)1, 2( ( (. yes ?- vertical)seg)point)1, 1(, point)2, Y( ( (. no ?- horizontal)seg)point)1, 1(, point)2, Y( ( (. Y=1 ?- vertical)seg)point)2, 3(, P(. P = point)2, H53( ?- vertical)S(, horizontal)S(. S = seg)point)X, Y(, point)X, Y( ( 38
معنای توصيفی برنامه ها • P :- Q, R. معنای توص يفی P :درس ت اس ت اگر Qو R درست باشند. معنای رويه ای:
زير مسأله Rرا حل کن. بنابراين تفاوت در اهميت ترتيب بخش شرايط 39می باشد.
معنای توصيفی برنامه ها • P :- Q; R. معنای توصيفی P :درست است اگر Qدرست باشد يا Rدرست باشد. معادل با: P :- Q. P :- R. اولويت کاما از سمی کالن بيشتر است: P :- Q, R; S, T, U. معادل است با: P :- )Q, R(; )S, T, U(. يا: P :- Q, R. P :- S, T, U. 40
معنای رويه ای برنامه ها • معنای رويه ای چگونگی پاسخ گويی پرولوگ به پرسشها را مشخص می کند. • بنابراين معنای رويه ای پرولوگ ،يک رويه برای اجرای ليستی از اهداف ( پرسش) در رابطه با . باشد می برنامه يک program failure\success indicator
execute instantiation of variables 41
goal list
مسأله ميمون و موز • مسجأله :يک ميمون در کنار در ورودی اتاقی قرار دارد .در وس ط اتاق ي ک موز از سقف آويزان است.ميمون گرسنه است و می خواهد خودش را به موز برس اند ،ام ا دس تش ب ه آ ن نم ی رسد .در کنار پنجره يک جعبه وجود دارد که ميمون می تواند از آن اس تفاده کند .ميمون م ی توان د اعمال زير را انجام دهد: – – – –
کف اتاق راه برود. از جعبه بال برود. جعبه را به اين طرف و آن طرف جابجا کند. موز رابگيرد به شرطی که روی جعبه باشد و جعبه نيز در وسط اتاق و زير موز باشد.
• سوال اي ن ا ست ک ه آي ا ميمون م ی توان د به موزش برسد يا خير و اگر می تواند کدام دنباله از اعمال را بايد انجام دهد؟
مسأله ميمون و موز • فرموله سازی مسأله :در اين مسأله می توان دنيا را در هر لحظ ه توس ط حالت ی بيان کرد ک ه درآ ن موقعيت اشياء مشخ ص شده باشند .حال ت م ی توان د ب ا زمان ( انجام عمل) تغيير کند. (state)P1, P2, P3, H موقعيت جعبه موقعيت عمودی موقعيت افقی ميمون داشتن/نداشتن موز ميمون
• حالت اوليه: (state)atdoor, onfloor, atwindow, hasnot • فرموله سازی هدف: (state)_, _, _, has
مسأله ميمون و موز : • فرموله سازی عمليات move)State1, Move, State2(
move)state)middle, onbox, middle, hasnot(, grasp, state)middle, onbox, middle, has( (.
مسأله ميمون و موز : • فرموله سازی عمليات move)State1, Move, State2(
move)state)Pos1, onfloor, Box, Has(, walk)Pos1, Pos2(, state)Pos2, onfloor, Box, Has( (.
مسأله ميمون و موز : • فرموله سازی عمليات move)State1, Move, State2(
move)state)Pos1, onfloor, Pos1, Has(, push)Pos1, Pos2(, state)Pos2, onfloor, Pos2, Has( (.
مسأله ميمون و موز : • فرموله سازی عمليات move)State1, Move, State2(
move)state)Pos, onfloor, Pos, Has(, climb, state)Pos, onbox, Pos, Has( (.
مسأله ميمون و موز • پرسش اصلی که برنامه بايد پاسخ دهد اين است که آيا دنباله ای از عمليات وجود دارند که ميمون را از ( نهايي) حال ت اولي ه مس أله ب ه حال ت هدف برسانند. (canget)State که می تواند به صورت زير بيان شود: canget)state)_, _, _, has( (. canget)State1( :move)State1, Move, State2(, canget)State2(.
)مسأله ميمون و موز( برنامه کامل move)state)middle, onbox, middle, hasnot(, grasp, state)middle, onbox, middle, has( (. move)state)Pos, onfloor, Pos, Has(, climb, state)Pos, onbox, Pos, Has( (. move)state)Pos1, onfloor, Pos1, Has(, push)Pos1, Pos2(, state)Pos2, onfloor, Pos2, Has( (. move)state)Pos1, onfloor, Box, Has(, walk)Pos1, Pos2(, state)Pos2, onfloor, Box, Has( (. canget)state)_, _, _, has( (. canget)State1( :move)State1, Move, State2(, canget)State2(.
مسأله ميمون و موز :• حل مسأله ?- canget)state)atdoor, onfloor, atwindow, hasnot( (. yes :دنباله عمليات walk)atdoor, atwindow(, push)atwindow, middle(, climb, grasp
ترتيب فراکردها و اهداف • خطر حلقه بی پايان P :- P. اي ن فراکرد از لحاظ معنای توص يفی کامل درس ت است ( P درست است اگر Pدرست باشد). اما از لحاظ رويه ای مشکل ايجاد می کند ( حلقه بی پايان) در برنام ه ميمون و موز عمليات را ب ه ترتي ب زي ر در برنامه نوشتيم: گرفتن موز ،بالرفتن ،جابه جا کردن جعبه و راه رفتن اين ترتيب اولويت اعمال مختلف را برای ميمون مشخص می کنند ،يعنی مثل ميمون بين راه رفتن و گرفتن موز دومی را ترجيح می دهد .اين اولويت ها به ميمون در حل مسأله کمک می کنند .حال اگ ر ترتي ب عمليات را عوض کني م و عمل راه رفتن را بالتر از بقيه اعمال در برنامه قراردهيم ميمون تا ابد در اتاق قدم خواهد زد و هيچگاه به موز نمی رسد ( اگر زنده بماند!) .