. تعریف توابع بازگشتیدومین روش اصلی
برای تعریف کنترل جریان درLisp تعاریف توابع بازگشتی هستند. تابعی که از
تعریفش بعنوان جزئی از تعریفش استفاده میکند بازگشتی نام دارد. بنابراین،
یک تعریف بازگشتی، تا جایی که امکان دارد مسئلهای را به قسمتهای کوچکتر
تقسیم میکند سپس این قسمتهای کوچکتر را با استفاده از توابع مشهور و جمع
پاسخهای یکسان حل کرده و حل برنامه را کامل میکند. بازگشت یک روش طبیعی
برای کنترل ساختارهای دادهای است که اندازه معینی ندارد. مانند لیستها،
درختها و گرافها. بنابراین برای مسئلههایی که در یک فاصله از حالات دنبال
حل کاندید میگردند مناسب است.
Lisp اولین زبان برنامهنویسی کاربردی
بود که با روش معین تعریف تعاریف بازگشتی را پشتیبانی کرده است. ما از دو
مثال کوچک برای نشان دادن بازگشت درLisp استفاده خواهیم کرد. اولین مثال
برای تعیین طول یک لیست طویل دلخواه استفاده میشود. طول یک لیست برابر
تعداد عناصر آن است. تابع بازگشتی آن به صورت زیر است.
E. تعریف توابع بازگشتیدومین
روش اصلی برای تعریف کنترل جریان درLisp تعاریف توابع بازگشتی هستند.
تابعی که از تعریفش بعنوان جزئی از تعریفش استفاده میکند بازگشتی نام
دارد. بنابراین، یک تعریف بازگشتی، تا جایی که امکان دارد مسئلهای را به
قسمتهای کوچکتر تقسیم میکند سپس این قسمتهای کوچکتر را با استفاده از
توابع مشهور و جمع پاسخهای یکسان حل کرده و حل برنامه را کامل میکند.
بازگشت یک روش طبیعی برای کنترل ساختارهای دادهای است که اندازه معینی
ندارد. مانند لیستها، درختها و گرافها. بنابراین برای مسئلههایی که در یک
فاصله از حالات دنبال حل کاندید میگردند مناسب است. Lisp اولین زبان برنامهنویسی کاربردی بود که با روش معین تعریف تعاریف بازگشتی را پشتیبانی کرده است. ما از دو مثال کوچک برای نشان دادن بازگشت درLisp استفاده خواهیم کرد. اولین مثال برای تعیین طول یک لیست طویل دلخواه استفاده میشود. طول یک لیست برابر تعداد عناصر آن است. تابع بازگشتی آن به صورت زیر است. (defun length (list) (cond ((null list) 0) (T (+ 1 (length (cdr list)))))) وقتی یک تعریف بازگشتی تعریف میشود. ما باید حالتهای اساسی راشناسایی کنیم یعنی آن قسمتهایی که نمیتوانند بیشتر تجزیه شوند. مسئله اندازه وابسته به لیست است. کوچکترین مسئله اندازه در لیست، لیست خالی است. بنابراین اولین چیزی که ما باید مشخص کنیم تستی برای شناسایی لیست خالی است و تعیین اینکه طول لیست خالی باید چقدر باشد تابع پیشساخته null تست میکند که آیا این لیست خالی است در این صورت t برمیگرداند. از آنجایی که لیست خالی بدون عنصر است تعریف میکنیم که طول لیست خالی صفر باشد کار دیگری که باید انجام شود تجزیه مسئله اندازه به قسمتهای کوچکتر است که همان مسئله میتواند برای فسمتهای کوچکتر استفاده شود. تجزیه لیست میتواند با استفاده از توابع cdr,car انجام شود. به این معنی که ما باید تعیین کنیم تا وقتی که لیست خالی پیدا شود عنصر اول و بقیه عناصر لیست چه کار بکنند. از آنجایی که ما ازقبل لیست خالی را بعنوان حالت اساسی شناسایی کردیم، میتوانیم فرض کنیم تجزیه برروی لیستی شامل حداقل یک عنصر انجام خواهد شد. بنابراین هر بار که قادر خواهیم بود تا با بکار بردن cdr بقیه عناصر لیست را بدست آوریم، ما یک عنصر اضافی پیدا کردیم که باید برای افزایش تعداد عناصر لیست قبلا شناسایی شده بوسیله یک استفاده میشود. استفاده از این تعریف تابع(length ’( )) بلافاصله صفر برخواهد گرداند و اگر (length ’(a b c)) را فراخوانی کنیم، نتیجه 3 خواهد بود زیرا برای اینکه لیست خالی شود باید سه فراخوانی بازگشتی member انجام دهیم بعنوان مثال دوم، تعریف بازگشتی را در نظر میگیریم که تست میکند که آیا عنصر داده شده در لیست داده شده قرار دارد اگر عنصر براستی در لیست پیدا شود زیر لیستی که با عنصر پیدا شده شروع میشود را برمیگرداند اگر عنصر پیدا نشوددnil برگردانده میشود مثال فراخوانیها هستند. (member ’b ’(a f b d e b c)) ==> (b d e b c) (member ’k ’(a f b d e b c)) ==> nil مشابه تعریف بازگشتی ما لیست خالی را به عنوان حالت اساسی استفاده میکنیم برایmember لیست خالی به این معنی است که عنصر مورد سوال در لیست پیدا نشود. بنابراین ما باید یک لیست را تا زمانی که عنصر مورد سوال پیدا میشود یا لیست خالی است تجزیه میکنیم تجزیه با استفاده ازcar وcdr انجام میشود.car برای استخراج عنصر اول لیست به کار میرود که میتواند برای کنترل اینکه با عنصر مورد سوال برابر است استفاده شود در این حالت میتوانیم پردازشهای اضافی را مستقیماً متوقف کنیم اگر برابر نبود آنگاه باید تابعmember را برای بقیه عناصر تا خالی شدن لیست بکار ببریم بنابراین میتواند به صورت زیر تعریف شود. (defun member (elem list) (cond ((null list) nil) ((equal elem (car list)) list) (T (member elem (cdr list))))) F. توابع مرتبه بالا درLisp توابع میتوانند بعنوان آرگومان استفاده شود تابعی که بتواند توابع را بعنوان آرگومانهایش بپذیرد تابع مرتبه بالا نامیده میشود. مشکلات فراوانی وجود دارند که یکی پیمایش یک لیست(یا یک درخت یا یک گراف) است که باید برای هر لیست عنصر تابع معینی استفاده شود. برای مثالfilter تابعی است که تستی برای عناصر لیست بهکار میبرد و آنهایی که شکست میخورند را حذف میکند. نگاشتها توابعی هستند که همان تابع را روی هر عنصر لیست به کار میبرند تا لیستی از نتایج را برگردانند. تعاربف توابع مرتبه بالا میتواند برای تعریف توابع عمومی پیمایش لیست استفاده شود که آنها از توابع خاصی که برای پردازش عناصر لیست بکار میروند خلاصه میشوند (چکیده میشوند). به منظور پشتیبانی تعاریف مرتبه بالا یک تابع خاص است که یک تابع و دنبالهای از آرگومانها را به عنوان آرگومان میپذیرد و آن تابع را در آرگومانهای آنها به کار میبرد. بعنوان مثال با استفاده ازfuncall، تابع عمومیfilter را تعریف خواهیم کرد که میتواند به این صورت فراخوانی شود: (filter ’(1 3 -9 -5 6 -3) #’plusp) ==>(1 3 6) plusp یک تابع پیش ساخته است که کنترل میکند آیا یک عدد داده شده مثبت است یا نه؟ اگر باشد آن عدد را برمیگرداند در غیر این صورتnil برمیگرداند نماد خاص# بکار میرود تا به مفسرLisp بگوید که مقدار آرگومان یک شی تابعی است . تعریف به صورت زیر است: (defun filter (list test) (cond ((null list) list) ((funcall test (car list)) (cons (car list) (filter (cdr list) test))) (T (filter (cdr list) test)))) اگر لیست خالی باشد آنگاه بسادگی برمیگردد در غیر این صورت تابع تست روی عنصر اول لیست بکار میرود. اگر تابع تست موفق شودcons بکار میرود تا لیست حاصل را با استفاده از این عنصر و همه عناصری که در طول فراخوانی بازگشتیfilter ازcdr و تابع تست استفاده میکنند بسازد. اگر تابع تست برای عنصر اول با شکست مواجه شود این عنصر بسادگی با بکاربردنfilter بصورت بازگشتی روی عناصر باقیمانده پرش میکند. یعنی این عنصر نمیتواند جزئی از لیست حاصل باشد تابع میتواند برای بسیاری از توابع مختلف تست استفاده شود مانند: (filter ’(1 3 A B 6 C 4) #’numberp) ==> (1 3 6 4) (filter ’(1 2 3 4 5 6) #’even) ==> (2 4 6) به عنوان مثال دیگری از تعریفfilter تابع مرتبه بالا، مامیخواهیم یک تابع نگاشت ساده تعریف کنیم که یک تابع روی همه عناصر یک لیست بکاررفته، لیستی از همه مقادیر برمیگرداند. اگر تابع my-map را فراخوانی کنیم آنگاه تعریفی شبیه این داریم: (defun my-map (fn list) (cond ((null list) list) (T (cons (funcall fn (car list)) (my-map fn (cdr list)))))) اگر یک تابع Double وجود داشته یاشد که تنها عدد را دو برابر کند آنگاه یک فراخوانی ممکن my-map به این صورت میتواند باشد: (my-map #’double ’(1 2 3 4))==> (2 4 6 8) بارها شده که یک تابع باید یکبار استفاده میشد. بنابراین اگر ما بتوانیم مستقیما تعریفی از یک تابع بعنوان آرگومان از تابع نگاشت فراهم کنیم کاملا مناسب خواهد بود برای اینکار تعریف عبارت lambda را پشتیبانی میکند. ما قبلا به طور غیر رسمی نمادسازی عبارات را در بخش II بعنوان تعریف توابع بی نام یا مستعار معرفی کردیم. در Lisp عبارات lambda با استفاده از نوع خاصی از lambda تعریف میشوند نوع عمومی عبارت lambda به این صورت است: (lambda ( parameter . . . ) body . . . ) یک عبارت lambda امکان میدهد تا ما تعریف تابع را از نام تابع تشخیص دهیم عبارات lambda میتوانند به جای نام تابع در تابع funcall استفاده شوند مانند عبارت که تابع double ما میتواند باشد: (lambda (x) (+ x x)) برای مثال: فراخوانی تابع my-map بالا میتواند با استفاده از عبارت lambda مجدداً به صورت زیر بیان شود: (my-map #’(lambda (x) (+ x x)) ’(1 2 3 4) ==> (2 4 6 8) یک عبارت lambda یک شئ تابعی بر میگرداند که به نام تابع متصل نیست در تعریف my-map ، پارامتر fn را بعنوان متغیر نام تابع استفاده میکنیم. وقتی شکل lambda محاسبه شد مفسر Lisp شئ تابعی را به متغیر نام تابع متصل خواهد کرد. به این طریق یک پارامتر تابع بصورت یک نام تابع پویا استفاده میشود. نماد # صروری است تا به Lisp بگوید که نه تنها یک شئ تابعی را وصل کند بلکه باید اتصالات محلی و سراسری مقادیر وابسته به شئ تابعی را نیز نگه دارد. این تنها با استفاده از عملگر quote امکانپذیر نخواهد بود (متأسفانه به دلیل محدودیت جا جزئیات بیشتری داده نمیشود). G. سایر زبانهای برنامهنویسی تابعی غیر از Lispما Lisp را به عنوان نماینده اصلی زبان برنامهنویسی تابعی معرفی کردیم (مخصوصاً نسخه پر استفاده Common Lisp )، زیرا هنوز هم زبان برنامهنویسی پر استفادهای برای تعدادی از مسئلههای هوش مصنوعی مانند فهم زبان طبیعی، استخراج اطلاعات، یادگیری ماشین، برنامهریزی AI یا برنامهنویسی ژنتیک است. درکنار Lispتعدادی از زبانهای برنامهنویسی تابعی دیگر توسعه یافتند. ما بطور خلاصه دو عضو مشهور را ذکر میکنیم، ML و Haskell. ML برگرفته از Meta-Language است یک زبان برنامهنویسی تابعی با دامنه ایستاست. تفاوت اصلیاش با Lisp درsyntax (نحو) است (که بیشتر شبیه پاسکال است)، و یک نوع سیستم چند ریختی محض است (یعنی بکاربردن انواع قوی و نوع استنتاجی بوسیله متغیرهایی که نیاز به اعلان ندارند). نوع هر متغیر اعلان شده و عبارت میتواند در زمان کامپایل تعیین شود. MLتعریف انواع داده خلاصه را پشتیبانی میکند، به صورتی که در مثال زیر شرح داده شده است: datatype tree = L of int | int * tree * tree; خوانده میشود’’ هر درخت دو دویی دارای یک برگ شامل یک عدد صحیح و یا یک گره شامل یک عدد صحیح و دو درخت است( زیر درختها)‘‘ در مثال بعدی، مثالی از تعریف یک تابع بازگشتی که روی یک ساختار درخت بکار میرود نشان داده شده است: fun depth(L ) = 1 | depth(N(i,l,r)) = 1 + max(depth l, depth r); تابع depth نگاشتی از درختها به اعداد است. عمق هر برگ 1 است و عمق هر درخت دیگر 1 بعلاوه بیشترین عمق زیر درختهای چپ و راست آن است. Haskell شبیه ML است: Syntax مشابهی بکار میبرد، دامنهاش هم ایستاست و از همان روش استنتاج استفاده میکند. با ML در این تفاوت دارد که یک زبان کاملاً تابعی است. به این معنی است که به اثرات جانبی اجازه نداده و شامل هیچ نوع ویژگی دستوری نیست، در اصل متغیر و جملات انتسابی ندارد. بعلاوه از یک تکنیک ارزیابی کند استفاده میکند، که زیر عبارت را ارزیابی نمیکند تا موقع نیاز مقدارش معلوم باشد. لیستها رایجترین ساختار داده در Haskell هستند. برای مثال [1,2,3] لیستی از سه عدد صحیح 3,2,1 است لیست [1,2,3] در Haskell در واقع خلاصهنویسی شده لیست 1:(2:(3:[ ] )) است، که[ ] لیست خالی است و: عملگری میانوندی است که آرگومان اولش را جلوی آرگومان دومش اضافه میکند( یک لیست). بعنوان مثالی از یک تابع کاربر تعریفی که روی لیستها عمل میکند، مسئله شمارش تعداد عناصر در یک لیست با تعریف تابع length ملاحظه میشود. length :: [a] -> Integer length [ ] = 0 length (x:xs) = 1 + length xs خوانده میشود’’طول لیست خالی 0 است، و طول لیستی که عنصر اولش x است و بقیه xs است،1 بعلاوه طول xs است‘‘. در Haskell تابع invocation احضار با تطبیق الگو راهنمایی میکند، برای مثال طرف چپ معادله داری الگوهایی مانند[ ] و x:xs است. در یک کاربرد تابع این الگوها با پارامترهای واقعی تطبیق داده میشوند [ ] ) تنها با لیست خالی مطابقت میکند، و x :xs با هر لیست با حداقل یک عنصر با موفقیت تطبیق میکند، x به عنصر اول و xs به بقیه لیست متصل میشوند). اگر تطبیق موفقیتآمیز باشد طرف راست معادله ارزیابی و بعنوان نتیجه کاربرد برگردانده میشود. اگر با شکست مواجه شود معادله بعدی سعی میشود، و اگر همه معادلات با شکست مواجه شوند، حاصل یک خطا میشود. این پایان کوتاه ما از’’سفر در Lisp ‘‘ است. ما تنهای توانستیم جنبه بسیار مهم Lisp را مطرح کنیم. خوانندگان علاقمند به جزئیات خاص بیشتر باید حداقل یکی از کتابهای مذکور در آخر مقاله را کنکاش کنند. بقیه این مقاله معرفی الگوی برنامهنویسی دیگری بنام Prolog است که در برنامهنویسی AI بطور گسترده مورد استفاده قرار میگیرد. IV. برنامهنویسی منطقی در Prolog در دهه 1970 یک الگوی دیگر برای محاسبات نمادین در برنامهنویسی AI از موفقیت در زمینه اثبات قضیه خودکار ارئه شد. حل رویه اثبات بطور قابل توجهی توسط رابینسون (1965) توسعه یافته که که با منطق رسمی نشان داده شده است، در محاسبات گزارهای خاص میتوان بعنوان نمادی برای تعیین الگوریتمها و بنابراین برای انجام محاسبات نمادین استفاده شود. در اوایل (دهه 1970) Prolog ، مخفف(برنامهنویسی در منطق) اولین زبان برنامهنویسی بر مبنای منطق پدیدار شد. آن توسط آلن کالمرار، رابرت کووا لسکی و فیلیپ راسل توسعه یافته است. اساس Prolog شامل یک روش برای مشخص کردن گزارههای محاسبات گزارهای و تصمیات محدود است. برنامهنوسی در Prolog شامل مشخصات حقیقی در مورد اشیاء و ارتباط آنها و قوانینی که ارتباطات را مشخص میکند، است. برنامههای Prolog مجموعهای از جملات اعلانی در مورد یک مسئله هستند زیرا آنها نحوه محاسبه نتیجه را مشخص نمیکند.بلکه ساختار منطقی نتیجه را مشخص میکنند Prolog با برنامهنویسی دستوری و حتی برنامهنویسی تابعی در تعریف نحوه محاسبه نتیجه کاملاً متفاوت است. با استفاده از Prolog برنامهنویسی میتواند در یک سطح خیلی خلاصه و کاملاً نزدیک به مشخصات رسمی یک مسئله انجام میگیرد. Prolog هنوز هم مهمترین زبان برنامهنوسی منطقی است. تعدادی از سیستمهای برنامهنوسی تجاری در بازار موجود است که شامل ماجولهای مدرن برنامهنویسی هستند، یعنی کامپایلر، Debugger و ابزارهای تجسم. Prolog در تعدادی از زمینههای AI مانند سیستمهای خبره و پردازش زبان طبیعی بطور موفقیتآمیزی استفاده شده است. اما در زمینههای دیگری مانند سیستم های مدیریت پایگاه داده رابطهای یا در آموزش نیز استفاده میشود. یک برنامه 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) مفهوم اتصال ساخته نمیشود چون 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 بین روشهای مستقیم و غیر مستقیم برنامهنویسی منطقی اعلانی تفاوت قایل میشود. V. سایر روشهای برنامهنویسیدر این مقاله قبلاً زبانهای AI را با روشهای برنامهنویسی دستوری مقایسه کردیم. زبانهای شیء گرا به الگوی برنامهنویسی مشهور دیگری تعلق دارند. در این جور زبانها اولین وسیله برای تعیین مسئلهها، تعیین خلاصه ساختارهای داده است که کلاسها، اشیاءنام دارند. یک کلاس شامل یک ساختار داده همراه با عملیات اصلیاش که اغلب اسلوبها (روشها) نام دارند است. یک ویژگی مهم این است که ممکن است کلاسها در سلسله مراتبی از کلاسها و زیر کلاسها مرتب شوند. یک کلاس میتواند صفات سوپر کلاسهایش که پیمانهای بودن را پشتیبانی میکنند را به ارث ببرد. مشهورترین زبانهای شیءگرا C++,Eiffel و Java (جاوا) هستند. سیستم Common Lisp شیءگرا یک توسعه از common Lisp است. آن یکپارچهسازی کامل برنامهنویسی تابعی و شیءگرا را پشتیبانی میکند. اخیراً جاوا در بعضی از زمینهها AI، خصوصاً در فنآوری عامل هوشمند، موتورهای جستجوی اینترنت یا استخراج دادهها کاملاً مشهور شده است. جاوا بر مبنای C++ است و زبان اصلی برای برنامهنویسی کاربردهای اینترنتی است. مهمترین ویژگیهای زبان که جاوا را از چشمآنداز AI جذاب میسازد فضای هرز خودکار پیشساخته آن و مکانیزم چند نخی (چند وظیفهای) آن است. با افزایش تحقیقات در زمینه وب هوشمند یک الگوی برنامهنویسی جدید- برنامهنویسی عاملگرا – پدیدار شد. برنامهنویسی عاملگرا یک الگوی جدید برنامهنویسی است که یک نمای اجتماعی از محاسبه را به خوبی پشتیبانی میکند. در AOP اشیاء بعنوان عاملهایی شناخته میشوند که برای دستیابی به اهداف شخصی عمل میکنند. عامل در یک ساختار میتواند به پیچیدگی شبکه سراسری اینترنت یا به سادگی یک پیمانه (ماجول) از یک برنامه معمولی باشد. عاملها میتوانند موجودیتهای مستقل باشند یعنی بدون دخالت کاربر برای گام بعدیشان تصمیم بگیرند، یا میتوانند قابل کنترل باشند، یعنی بعنوان وسیلهای بین کاربر و عاملهای دیگر بکار بردند. از آنجایی که عاملها زنده در نظر گرفته میشوند، با رشد موجودیتهای نرمافزار، به نظر میرسد انتقالی از نقطهنظر زبانهای برنامهنویسی به طرف نقطهنظر سکوی پیشرفت نرمافزار پدیدار میشود. اینجا تأکید روی طراحی سیستم، سکوی پیشرفت و اتصال است. سئوالات حساس عبارتنداز: چگونه تعدادی از منابع پیشرفته AI که در زبانها و سکوهای مختلف موجودند میتوانند با سایر منابع استفادهکننده از ابزارهای پیشرفت سیستم جدید مانند CORBA (معماری عادی رابط درخواست شئ) ترکیب شوند (یکپارچه شوند)، خلاصهسازی عمومی انواع داده و زبانهای تفسیری(یادداشت حاشیهای) مانند XML و زبان استاندارد ارتباطات عاملگرا مانند KQML (زبان شناخت پرس و جو و دستکاری). بنابراین آینده برنامهنویسی AI کمتر نگران سئوالاتی مثل: ” مناسبترین الگوی برنامهنویسی چیست؟ “ است ولی باید به سئوالاتی مثل: ” چگونه میتوانم الگوهای مختلف برنامهنویسی را زیر یک سایبان یکپارچه کنم؟ “ و ” بهترین زبان ارتباطی برای نرمافزارهای مستقل پیمانهای هوشمند چیست؟ “ پاسخ دهیم. |