lisp زبان برنامه نویسی لیسپ و برنامه‌نويسي در هوش مصنوعي

[دانه کولانه]

F. توابع مرتبه بالا
درLisp توابع مي‌توانند بعنوان آرگومان استفاده شود تابعي كه بتواند توابع را بعنوان آرگومانهايش بپذيرد تابع مرتبه بالا ناميده مي‌شود. مشكلات فراواني وجود دارند كه يكي پيمايش يك ليست(يا يك درخت يا يك گراف) است كه بايد براي هر ليست عنصر تابع معيني استفاده شود. براي مثال****** تابعي است كه تستي براي عناصر ليست به‌كار مي‌برد و آنهايي كه شكست مي‌خورند را حذف مي‌كند. نگاشتها توابعي هستند كه همان تابع را روي هر عنصر ليست به كار مي‌برند تا ليستي از نتايج را برگردانند. تعاربف توابع مرتبه بالا مي‌تواند براي تعريف توابع عمومي پيمايش ليست استفاده شود كه آنها از توابع خاصي كه براي پردازش عناصر ليست بكار مي‌روند خلاصه مي‌شوند (چكيده مي‌شوند). به منظور پشتيباني تعاريف مرتبه بالا يك تابع خاص است كه يك تابع و دنباله‌اي از آرگومانها را به عنوان آرگومان مي‌پذيرد و آن تابع را در آرگومانهاي آنها به كار مي‌برد. بعنوان مثال با استفاده ازfuncall، تابع عمومي****** را تعريف خواهيم كرد كه مي‌تواند به اين صورت فراخواني شود:
(****** ’(1 3 -9 -5 6 -3) #’plusp) ==>(1 3 6)
plusp يك تابع پيش ساخته است كه كنترل مي‌كند آيا يك عدد داده شده مثبت است يا نه؟ اگر باشد آن عدد را بر‌مي‌گرداند در غير اين صورتnil بر‌مي‌گرداند نماد خاص# بكار مي‌رود تا به مفسرLisp بگويد كه مقدار آرگومان يك شي تابعي است . تعريف به صورت زير است:
(defun ****** (list test)

(cond ((null list) list)

((funcall test (car list))

(cons (car list) (****** (cdr list) test)))

(T (****** (cdr list) test))))
اگر ليست خالي باشد آنگاه بسادگي برمي‌گردد در غير اين صورت تابع تست روي عنصر اول ليست بكار مي‌رود. اگر تابع تست موفق شودcons بكار مي‌رود تا ليست حاصل را با استفاده از اين عنصر و همه عناصري كه در طول فراخواني بازگشتي****** ازcdr و تابع تست استفاده مي‌كنند بسازد. اگر تابع تست براي عنصر اول با شكست مواجه شود اين عنصر بسادگي با بكاربردن****** بصورت بازگشتي روي عناصر باقيمانده پرش مي‌كند. يعني اين عنصر نمي‌تواند جزئي از ليست حاصل باشد تابع مي‌تواند براي بسياري از توابع مختلف تست استفاده شود مانند:

(****** ’(1 3 A B 6 C 4) #’numberp) ==> (1 3 6 4)

(****** ’(1 2 3 4 5 6) #’even) ==> (2 4 6)

به عنوان مثال ديگري از تعريف****** تابع مرتبه بالا، مامي‌خواهيم يك تابع نگاشت ساده تعريف كنيم كه يك تابع روي همه عناصر يك ليست بكاررفته، ليستي از همه مقادير بر‌مي‌گرداند. اگر تابع 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 بطور گسترده مورد استفاده قرار مي‌‌گيرد.