Astaraki

D. تعريف ساختارهاي كنترلي

هر چنداكنون تعريف توابع جديد با تعريف توابع پيش ساخته و توابعي كه كاربر تعريف مي‌كند ممكن است برنامه‌نويسي درLisp بسيار خسته كننده خواهد شداگر كنترل جريان اطلاعات بوسيله شاخه‌هاي شرطي ممكن نبود شايد بارها تكرار مي‌شد تا اينكه يك روند توقف اجرا شود گزينشLisp بر مبناي ارزيابي توابع است توابع كنترل تستهايي روي عبارات نمادين واقعي انجام مي‌دهد و ارزيابي عبارات نمادين متناوب را بسته به نتايج انتخاب مي‌كنند تابع اساسي براي تعيين اثباتهاي شرطي درcond،Lisp است.cond تعداد دلخواهي آرگومان رامي‌پذيرد هر آرگومان يك بخش ممكن را بيان مي‌كنند و بعنوان يك ليست نمايش داده شده كه عنصر اول يك تست و بقيه عناصر اعمال (عبارات نمادين) هستند كه اگر تست انجام شود ارزيابي مي‌شوند مقدار آخرين عمل به عنوان مقدار پيشنهادي برگردانده مي‌شود همه آرگومانهاي ممكنcond (يعني بخشها) تا زماني كه بخش اول بطور مثبت تست شوداز چپ به راست ارزيابي مي‌شوند درآن حالت مقدار آن بخش مقدار كل تابعcond است. در واقع اين مفهوم بسيار پيچيده تر از آن است اجازه دهيد تابعverbalize-prop زيركه يك مقدار احتمال را بيان مي‌كند. به عنوان يك عدد حقيقي فرض مي‌كنيم.

(defun verbalize–prop (prob-value)
(cond ((> prob–value 0.75) ’very-probable)
((> prob–value 0.5) ’probable)
((> prob–value 0.25) ’improbable)
(T ’very-improbable)))

وقتي(verbalize-prop 0.33) فراخواني مي‌شود مقدار واقعي آرگومانها به پارامترprop-value متصل مي‌شود.سپسcond با آن اتصالات ارزيابي مي‌شود very-probable)’((>prop-value)است.> يك گزاره پيش ساخته است كه تست مي‌كند كه آيا آرگومان اول از دومي بزرگتر است،چونpropvalue،0.33 است. بهnil ارزيابي مي‌شود كه به معني انجام نشدن تست است. بنابراين ارزيابي اين بخش پيشنهادي بلافاصله پايان مي‌يابد. و سپس پيشنهاد

((> prob–value 0.5) ’probable)ارزيابي مي‌شود كه تابع تست باز هم nilبرمي‌گرداندبنابراين ارزيابي هم پايان مي‌يابد. سپس ((prop-value 0.25) ’improbable) ارزيابي مي‌شود حال با بكار بردن تابع تستT برگردانده مي‌شود كه به معني انجام تست است.آنگاه همه اعمال اين بخش كه بطور مثبت تست شده است. ارزيابي ومقدار آخرين عمل به عنوان مقدارcond برگردانده مي‌شود در مثال ما تنها عملimprobable’ تعيين مي‌شود كه مقدارimprobable (غيرمحتمل) را برمي‌گرداند از آنجايي كه اين مقدارcond را تعيين مي‌كند و عبارت cond تنها عبارت بدنه تابعverbalize-prop است. نتيجه فراخواني improbable ,((verbalize-prop 0.33) است. توضيح اينكهاگرما (verbalize- prop 0.1)را وارد كنيم مقدارvery- improbable را بر‌مي‌گرداند زيرا تست هر سه با شكست مواجه شده و بايد بخش (T ’very-improbable)ارزيابي شوددر اين حالت نمادT به عنوان تستي كه هميشهT بر‌مي‌گرداند استفاده شده است بنابراين مقدار اين پيشنهاد very- improbable است.

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 )، زيرا هنوز هم زبان برنامه‌نويسي پر استفاده‌اي براي تعدادي از مسئله‌هاي هوش مصنوعي مانند فهم زبان طبيعي، استخراج اطلاعات، يادگيري ماشين،‌ برنامه‌ريزي هوش مصنوعی يا برنامه‌نويسي ژنتيك است. دركنار 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 در واقع خلاصه‌نويسي شده ليست 123:[ ] )) است، كه[ ] ليست خالي است و: عملگري ميانوندي است كه آرگومان اولش را جلوي آرگومان دومش اضافه مي‌كند( يك ليست). بعنوان مثالي از يك تابع كاربر تعريفي كه روي ليستها عمل مي‌كند، مسئله شمارش تعداد عناصر در يك ليست با تعريف تابع 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 است كه در برنامه‌نويسي هوش مصنوعی بطور گسترده مورد استفاده قرار مي‌‌گيرد.

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!