برنامه نویسی منطقی در Prolog

[Reyhane]

برنامه نویسی منطقی در Prolog


در دهه 1970 يك الگوي ديگر براي محاسبات نمادين در برنامه‌نويسي هوش مصنوعی از موفقيت در زمينه اثبات قضيه خودكار ارئه شد. حل رويه اثبات بطور قابل توجهي توسط رابينسون (1965) توسعه يافته كه كه با منطق رسمي نشان داده شده است، در محاسبات گزاره‌اي خاص مي‌‌توان بعنوان نمادي براي تعيين الگوريتم‌ها و بنابراين براي انجام محاسبات نمادين استفاده شود. در اوايل (دهه 1970) Prolog ، مخفف(برنامه‌نويسي در منطق) اولين زبان‌‌ برنامه‌‌نويسي بر مبناي منطق پديدار شد. آن توسط آلن كالمرار، رابرت كووا لسكي و فيليپ راسل توسعه يافته است. اساس Prolog شامل يك روش براي مشخص كردن گزاره‌هاي محاسبات گزاره‌اي و تصميات محدود است. برنامه‌‌نوسي در Prolog شامل مشخصات حقيقي در مورد اشياء و ارتباط آنها و قوانيني كه ارتباطات را مشخص مي‌كند، است. برنامه‌هاي Prolog مجموعه‌اي از جملات اعلاني در مورد يك مسئله هستند زيرا آنها نحوه محاسبه نتيجه را مشخص نمي‌‌‌كند.بلكه ساختار منطقي نتيجه را مشخص مي‌‌كنند Prolog با برنامه‌نويسي دستوري و حتي برنامه‌‌نويسي تابعي در تعريف نحوه محاسبه نتيجه كاملاً متفاوت است. با استفاده از Prolog برنامه‌نويسي مي‌تواند در يك سطح خيلي خلاصه و كاملاً نزديك به مشخصات رسمي يك مسئله انجام مي‌‌گيرد. Prolog هنوز هم مهمترين زبان برنامه‌نوسي منطقي است. تعدادي از سيستمهاي برنامه‌نوسي تجاري در بازار موجود است كه شامل ماجولهاي مدرن برنامه‌‌‌نويسي هستند، يعني كامپايلر، Debugger و ابزارهاي تجسم. Prolog در تعدادي از زمينه‌هاي هوش مصنوعی مانند سيستم‌هاي خبره و پردازش زبان طبيعي بطور موفقيت‌آميزي استفاده شده است. اما در زمينه‌هاي ديگري مانند سيستم‌ هاي مديريت پايگاه داده رابطه‌اي يا در آموزش نيز استفاده مي‌شود. يك برنامه Prolog بسيار ساده برنامه‌اي است كه شامل دو حقيقت و يك قاعده است.

scientist(godel).
scientist(einstein).
logician(X) :- scientist(X).

دو جمله اول مي‌تواند بصورت ’’Godel is a scientist ‘‘ و ’’Einstein is a scientist ‘‘ تفسير شود.جمله قانون مي‌‌‌گويد: ’’X is a logician if x is a scientist ‘‘. براي تست اين برنامه بايد عبارات پرس و جو( يا قضايا) را مشخص كنيم كه Prolog سعي مي‌كند با استفاده از برنامه مشخص شده به آنها جواب دهد(يا اثبات كند). يك پرس و جوي ممكن اين است: ?- scientist(godel).

كه مي‌تواند به صورت ’’Is Godel a scientist?‘‘ بيان شود. Prolog با بكار بردن رويه اثبات پيش‌ساخته خودش ’’yes‘‘ جواب خواهد داد، زيرا ممكن است يك حقيقت پيدا شود كه كاملاً مطابق با پرس و جو باشد. ديگر پرس و جوي ممكن بصورت سئوال:

’’who is a scientist?‘‘و در Prolog بصورت زير بيان مي‌شود:

?- scientist(X).

Prolog نتيجه خواهد داد’’X = godel , X= Einstein ‘‘. در اين حالت Prolog نه‌تنها جواب مي‌دهد’’yes ‘‘ بلكه همه متغيرهاي متصل به x را كه در طول اثبات موفق پرس و جو پيدا مي‌كند را بر مي‌گرداند. مثال ديگر، ممكن است ما با پرس و جوي Prolog زير سئوال كنيم ’’who is a logician ‘‘:

?- logician(X).

اثبات اين پرس و جو همان مجموعه‌اي از حقايق را كه قانون مشخص كرده است را نتيجه مي‌دهد. سرانجام ممكن است ما پرس و جوي زير را مشخص كنيم:

?- logician(mickey-mouse).

در اين حالت Prolog جواب خواهد داد با ’’No ‘‘. هر چند قانون مي‌گويد كسي منطق‌دان است كه دانشمند هم باشد، ‌ولي Prolog حقيقتي نمي‌يابد كه بگويدMickey Mouse دانشمند است. توضيح اينكه Prolog تنها نسبت به برنامه داده شده مي‌تواند پاسخ بدهد. در واقع به اين معني است كه ‘‘ No, I couldn’t deduce the fact‘‘. اين ويژگي بعنوان فرض جهان بسته يا رد آن بصورت شكست،‌ مشهور است. به اين معني كه Prolog همه اطلاعات لازم براي حل مسئله موجود در پايگاه داده را فرض مي‌‌كند.

جملات برنامه‌هاي Prolog شامل مجموعه‌اي از جملات بنام بند هستند كه براي نمايش داده‌ها و برنامه‌ها استفاده مي‌شوند. نماد نقطه‌ براي پايان دادن بند بكار مي‌رود. يك واژه مي‌تواند يك ثابت(نامهاي نمادين كه با يك حرف كوچك شروع مي‌شوند مانند godel يا eInstein )، يك متغير(نمادهايي كه با يك حرف بزرگ شروع مي‌شوند مانند x يا ‌ Scientist)، يا يك ساختار باشد. ساختارهاي گزاره‌هاي اتمي محاسبات گزار‌ه‌اي را نمايش مي‌دهند و شامل عملگر نام و يك ليست پارامتر هستند. هر پارامتر مي‌تواند يك واژه باشد به اين معني كه واژه‌ها،‌ اشياء‌ بازگشتي هستند. Prolog سه نوع بند را تشخيص مي‌دهد: حقايق،‌قوانين و پرس و جوها. يك حقيقت با يك ساختار واحد نمايش داده مي‌شود كه بعنوان يك گزاره درست ساده تفسير مي‌شود. قبلاً در مثال ساده برنامه بالا دو حقيقت ساده را معرفي كرديم.

اينها چند مثال ديگر هستند:

male(john).
male(bill).
female(mary).
female(sue).
father(john, mary).
father(bill,john).
mother(sue,mary).

توضيح اينكه اين حقايق داراي معاني ذاتي نيستند يعني معني عملگر نام father تعريف نشده است. براي مثال با بكار بردن حواس معمول ممكن است آن را بصورت ’’John is the father of mary‘‘ تفسير كنيم. هر چند براي Prolog اين معني وجود ندارد و تنها يك نماد است.

قوانين متعلق به نوع ديگري از بندها هستند. يك بند قانون شامل دو قسمت است،‌ سر كه تنها يك واژه است و بدنه كه تنها يك واژه يا يك اتحاد است. يك اتحاد يك مجموعه از واژه‌هاست كه با نماد كاما از هم جدا مي‌شوند.

منطقاً يك بند قانون بعنوان يك استدلال تفسير مي‌شود، اگر همه عناصر بدنه درست باشند، آنگاه عنصر سر نيز درست است. بنابراين بدنه بند به صورت قسمت if (اگر) و سر بند بصورت قسمت then (آنگاه) قانون مشخص مي‌شوند.

اين مثال براي مجموعه‌اي از بندهاي قانون است:

parent(X,Y) :- mother(X, Y).
parent(X,Y) :- father(X, Y).
grandparent(X,Z) :- parent(X,Y), parent(Y,Z).

قانون اخير خوانده مي‌شود:

’’X is a grand parent of z if X is a parent of y and y is a parent of z ‘‘

دو قانون اولي مي‌گويند:

’’some one is parent if it is the father or mother of some one else‘‘

دليل رفتار دو قانون اول را هنگام معرفي رويه اثبات Prolog بعنوان فصلي بطور آشكار خواهد آمد. قبل از انجام اين كار بايد آخرين نوع بند را معرفي كنيم،‌ بند پرس و جو (كه بند هدف ناميده مي‌شود). يك پرس و جو براي فعال كردن رويه اثبات Prolog بكار مي‌رود.

منطقاً يك پرس و جو مشابه يك قضيه مجهول است. آن شكلي مشابه حقيقت دارد تا به Prolog بگويد كه يك پرس و جو بايد اثبات شود، عملگر مخصوص پرس و جو –?است معمولاً در جلوي پرس و جو نوشته مي‌شود. در مثالهاي ساده برنامه Prolog معرفي شده در بالا، قبلاً توصيفي غير رسمي از چگونگي استفاده پرس و جو در Prologرا ديديم.

فرايند استنتاج Prolog شامل دو مؤلفه اساسي است: روش جستجو و يكي كننده. روش جستجو براي جستجو ميان حقيقت و قانون پايگاه داده بكار مي‌رود در حالي كه يكي‌سازي براي تطبيق الگو و بازگرداندن اتصالاتي كه يك عبارت صحيح مي‌سازد بكار مي‌رود.

يكي‌ساز روي دو واژه بكار مي‌رود و سعي مي‌كند با تركيب آن دو يك واژه جديد شكل بدهد. اگر يكي سازي ممكن نباشد آنگاه گفته مي‌شود يكي‌سازي شكست خورده است. اگر دو واژه مادي هيچ متغيري نباشند آنگاه يكي‌سازي در واقع از بررسي اينكه آيا واژه‌ها برابرند، خواهد كاست. براي مثال، يكي‌سازي دو واژه father (john,mary) و father(john,mary) موفق مي‌شود در حاليكه يكي‌سازي جفت واژه‌هاي زير با شكست مواجه خواهند شد.

father(X,mary) و father(john,sue)
sequence(a,b,c) و sequence(a,b)

اگر يك واژه حاوي يك متغير (يا بيشتر) باشد آنگاه يكي كننده بررسي مي‌كند كه آيا متغير مي‌تواند با بعضي از اطلاعات واژه دوم متصل شود، هر چند تنها اگر قسمتهاي باقيمانده واژه‌ها يكي شوند. براي مثال، براي دو واژه زير:

father(X,mary) and father(john,mary)

يكي كننده X را به john متصل خواهد كرد زيرا واژه‌هاي باقيمانده برابرند. هرچند براي

زوج زير:

father(X,mary) and father(john,sue)

 

[Reyhane]

مفهوم اتصال ساخته نمي‌شود چون mary و sue مطابق نيستند. روش جستجويي كه براي پيمايش فضاي جستجو بكار مي‌رود بوسيله حقايق و قوانين برنامه Prolog محدود شده است. Prolog يك روش بالا به پائين، روش جستجوي عمقي (dfs) استفاده مي‌كند. اين به چه معنا است؟ همه مراحل كاملاً شبيه به روش تابع ارزيابي استفاده شده در Lisp است اگر يك پرس و جوي Q مشخص شده باشد آنگاه ممكن است آن مطابق يك حقيقت يا يك قاعده باشد. در حالتي از قاعده Prolog ,R ابتدا سعي مي‌كند سر R را تطبيق دهد و اگر موفق شود آنگاه سعي مي‌كندهمه عناصر بدنه R كه زير پرس و جو ناميده مي‌شوند را تطبيق دهد اگر سر R حاوي متغيرها باشد آنگاه اتصالات در طول اثبات از زير پرس و جوها استفاده خواهند كرد. از آنجايي كه اتصالات تنها براي زير پرس و جوها معتبر هستند، گفته مي‌شود كه براي يك قاعده محلي هستند. يك زير پرس و جو هم مي‌تواند يك قاعده باشد و هم يك حقيقت. اگر يك قاعده باشد آنگاه فرايند استنتاج Prolog بطور بازگشتي براي بدنه اين پرس و جو بكار مي‌رود. اين، قسمت بالا به پائين روش جستجو را مي‌سازد. عناصر بدنه يك قاعده از چپ به راست بكار مي‌روند و تنها اگر عنصر جاري بتواند با موفقيت اثبات شود عنصر بعدي سعي مي‌شود. اين روش جستجوي عمقي را مي‌سازد. ممكن است براي اثبات يك زير پرس و جو دو يا چند حقيقت يا قاعده ديگر تعريف شوند. در آن صورت A, Prolog را انتخاب مي‌كند و سعي مي‌كند آن را اثبات كند، اگر لازم باشد زير پرس و جوهاي A را نيز پردازش مي‌كند. اگر A با شكست مواجه شود Prolog به نقطه‌اي كه اثبات A شروع شده بر مي‌گردد(با حذف همه اتصالهايي كه در طول اثبات A انتساب داده شده است) و سعي مي‌كند ديگري را اثبات كند. اين فرايند عقب‌گرد نام دارد . به منظور شرح همه روشها پرس و جوهاي نمونه زير را مي‌توانيم ملاحظه كنيد (مثال معرفي شده در بندهاي پاراگراف قبلي را بعنوان پايگاه داده Prolog استفاده مي‌كنيم):

?- grandparent(bill,mary).

تنها بندي كه با اين پرس و جو تطبيق مي‌كند قاعده زير است.

grandparent(X,Z) :- parent(X,Y), parent(Y,Z).

و يكي‌سازي پرس و جو با سر قاعده اتصالهاي زير را بر مي‌گرداند: Z=mary,X=bill براي اثبات قاعده، بايد دو عنصر بدنه قاعده از چپ به راست اثبات شوند. توضيح اينكه متغيرهاي مشترك قواعد با سر قاعده و بنابراين اتصالهاي محاسبه شده در طول تطبيق سر با پرس و جو براي پاسخ به زير پرس و جوها موجودند. بنابراين زير پرس و جوي اول در واقع بصورت parent(bill,y) و زير پرس و جوي دوم بصورت parent (y,mary) معرفي شود. حال براي اثبات بند اول prolog دو قاعده parent ديگر مي‌يابد. اجازه دهيد فرض كنيم prolog اولي را انتخاب مي‌كند.( براي ياد‌آوري بيش از يك انتخاب، prolog يك نقطه انتخاب مشخص مي‌كند)

parent(X,Y) :- mother(X, Y).

يكي‌سازي زير پرس و جوها با سه قاعده به راحتي ممكن است و متغيرx به واژه bill متصل خواهد شد . اين عنصر تك بدنه‌اي بصورت (bill,y) mother معرفي مي‌شود. متاسفانه هيچ حقيقتي كه اين زير پرس و جو را معتبر كند در پايگاه داده وجود ندارد. چون يكي‌سازي (bill,y) mother با شكست مواجه مي‌شود. پس همه قاعده انجام مي‌شود. سپس prolog به نقطه انتخابي كه اولين قاعده parent ممكن را انتخاب كرده بود، برگشته و دومي را انتخاب مي‌كند.

parent(X,Y) :- father(X, Y)

يكي‌سازي زير پرس و جوي (هنوز فعال) parent(bill,y) ، father(bill,y) معرفي خواهد شد. اينبار يكي‌سازي ممكن است،‌اتصال y=john برگردانده مي‌شود. حال اولين زير پرس و جوي parent از قاعده grand parent اثبات شده متغيرهاي واقعي X=bill Z=mary,Y=john, هستند. عنصر دوم از بدنه قاعده grandparent، parent (john, mary) معرفي مي‌شود (توضيح اينكه مقدار z بعد از انتخاب قاعده grand parent فوراً متصل شده است).

همان روش براي اين زير پرس و جو بكار رفته و prolog حقايق كافي براي اثبات موفقيت‌آميز آن خواهد يافت. وقتي كه دو عنصر بدنه قاعده grand parent به طور معتبر اثبات شد، prolog به پايان مي‌رسد كه اولين پرس و جو true مي‌شود. توسعه prolog ، به منظور استفاده از prolog براي برنامه‌نويسي كاربردي است. كه با توسعه‌هايي مانند ليست ساختارهاي داده، عملكردهايي براي كنترل واضح پيمايش از فاصله جستجو با يك برنامه prolog(بنام عملگر برش) و روالهايي براي رابطهاي ورودي /خروجي، تست درستي (رديابي) و اشكالزدايي مي‌آيد. ما نمي‌توانيم همه اين توسعه‌ها را در متن اين مرور كوتاه شرح دهيم. ما تنها بطور خلاصه نشان مي‌دهيم كه ليستها در prolog چگونه مي‌توانند استفاده شوند. Prolog ليستها را بعنوان يك ساختار داده‌اي پايه‌اي با استفاده از syntax متداول پشتيباني مي‌كند. عناصر ليست با كاما جدا مي‌شوند. كل ليست با براكت تعيين مي‌شود. يك عنصر ليست مي‌تواند يك واژه دلخواه يا يك ليست باشد، بنابراين كاملاً شبيه ساختارهاي ليست در Lisp است. اين مثالي از يك ليست prolog است:

[john, mary, bill]

ليست خالي بصورت [ ] نمايش داده مي‌شود. براي ايجاد و پيمايش ليستها، prolog يك تركيب خاص مبني بر سر و دنبال يك ليست فراهم مي‌كند. [X | Y]يك ليست است شامل يك سرليست x و يك دنباله y است. براي مثال ليست بالا مي‌تواند بصورت زير مشخص شود.

[john | mary, bill]

ما گزارهmember را بصورت مثالي براي نحوه رفتار ليستها در prolog استفاده خواهيم كرد. اين گزاره تعيين خواهد كرد كه آيا يك عنصر داده شده در يك ليست داده شده واقع مي‌شود؟ با توجه به توضيحات بالا يك عنصر در يك ليست است اگر سر ليست آن ليست باشد يا اگر در جايي از دنباله ليست واقع شود، با استفاده از تعريف غيررسمي گزاره member ما مي‌توانيم برنامه prolog زير را طرح كنيم. (نمادي كه يك متغير بي‌نام را مشخص مي‌كند،‌استفاده مي‌شود تا به prolog بگويد مهم نيست مقدار يكي كننده به آن متصل شود)
member(Element,[Element | ]).
member(Element,[ | List]) :- member(Element,List).

با فرض پر س و جوي زير

?- member(a, [b,c,a,d]).

Prolog ابتدا كنترل مي‌كند كه آيا سر ليست [b | c,a,d]برابر a است.

به اين علت بند اول با شكست مواجه مي‌شود، پس دومي سعي مي‌شود. اين زير پرس و جوي member (a,[c,a,d]) معرفي خواهد شد كه معني‌اش اين است كه از روي عنصر اول بسادگي مي‌پرد با بكار بردن بازگشي member،prolog سعي مي‌كند تا اثبات كند كه آيا سر ليست [c | a,d]با a برابر است، كه با شكست مواجه مي‌شود.، زير پر س و جوي جديد member (a,[a,d]) را با معرفي بند دوم بدست مي‌آوريم. گام بازگشتي بعدي ليست [a | d]را كنترل خواهد كرد. اينبار a براستي با عنصر سر ليست اين ليست برابر مي‌شود، بنابراين prolog با "yes" پايان خواهد يافت.

برنامه‌نويسي منطقي محدوديت (clp)تصميمي از سبك برنامه‌نويسي (ساده)‌prologاست. در clp واژه يكي‌سازي به حل محدوديت تعميم يافته است. در برنامه‌نويسي منطقي محدوديت مولفه‌هاي اصلي يك مسئله بصورت محدوديت‌ها حالت يافته‌اند (يعني ساختار اشياء در سؤال) و مسئله بصورت يك كل كه با گذاشتن محدوديتهاي مختلف بوسيله قواعد ارائه شده است. (اساساً بوسيله تعريف بندها) براي مثال بند معين زير نمونه يك تجزيه ريز از گرامر يك زبان طبيعي مانند انگليسي است.

sign(X0) ←
sign(X1),
sign(X2),
X0 syn cat = s,
X1 syn cat = np,
X2 syn cat = vp,
X1 syn agr = X2 syn ag

بيان مي‌شود يك شي زباني بصورت يك عبارت S طبقه‌بندي مي‌شود كه بايد مركب از يك شيء طبقه‌بندي شد كه بصورت يك NP (عبارت اسمي) و يك شئ طبقه‌بندي شده بصورت يك VP(عبارت لفظي) باشد و قرارداد اطلاعات (مانند شخص، حالت) بايد بين NP و VP يكسان باشد. همه اشيايي كه حداقل اين محدوديتها را انجام مي‌دهند جزء‌اشياي S هستند. توضيح اينكه هيچ ترتيب پيش فرضي براي VP,NPبعنوان حالتي براي گرامر زبان طبيعي مبني بر ظواهر وجود ندارد كه متن بدون استحكام به آن تكيه كند. اگر يك محدوديت نياز به محدوديتهاي اضافي داشته باشد. بايد به قاعده اضافه شود، براي نمونه زير ريشه‌ها بايد با الحاق تركيب شوند از نجاطيآنآن آنجايي كه محدوديتهاي مثال بالا تنها شرايط لازم براي شئ از كلاس S را مشخص مي‌كند آنها اطلاعات مختصري بيان مي‌كنند. اين براي دانش مبني بر استدلال خيلي مهم است زيرا در كل ما تنها اطلاعات مختصري درباره جهان (محيط)‌داريم، ‌ما براي پردازش چنين خصوصياتي دليل مبني بر حل محدوديت و الگوي برنامه‌نويسي منطقي مي‌خواهيم. چون يكي‌سازي، فقط حالت خاصي از حل محدوديت است، برنامه‌هاي منطقي محدوديت توان بيان بالايي دارند.

تعدادي از زبانهاي برنامه‌نويسي منطقي محدوديت (همراه با رابط كاربر سطح بالا و ابزارهاي توسعه) تحقق يافته‌اند. مانند CHIP يا زبان OZ كه برنامه‌نويسي اعلاني، برنامه‌نويسي شئ گرا، برنامه‌نويسي محدوديت و همزماني را بعنوان جزئي از كل منسجم پشتيباني مي‌كند. OZ زباني محدوديت قدرتمندي با متغيرهاي منطقي،‌دامنه‌متناهي، مجموعه‌هاي متناهي، درختهاي عقلاني و ركورد محدوديت‌هاست. آن در صدد است تا يك روش يكتا و انعطاف‌پذير بدون شاخ و بندها براي برنامه‌نويسي منطقي فراهم كند. OZ بين روشهاي مستقيم و غير مستقيم برنامه‌نويسي منطقي اعلاني تفاوت قايل مي‌شود.