آموزش LISP 1: برنامه نویسی اساسی LISP

برخی از مبتدیان ممکن است تماس های عملکردی تو در تو را پیدا کنند مانند موارد زیر برای درک بسیار دشوار: نوشتن و درک چنین عباراتی ، می توان اتصالات نام محلی را برای نشان دادن نتایج واسطه تعریف کرد:اجازه دهیدفرم ویژه بالا دو متغیر محلی را تعریف می کند ،F1وتF2، که به ترتیب به فیبر (N-1) و فیبر (N-2) متصل می شود. تحت این اتصالات محلی ،اجازه دهیدارزیابی کردن(+ F1 F2)بشردرفیبوناچیبنابراین می توان عملکرد را به شرح زیر بازنویسی کرد:

توجه کنید کهاجازه دهیدهمه اتصالات را به صورت موازی ایجاد می کند. یعنی هر دو(فیبوناچی (- شماره 1))وت(فیبوناچی (- شماره 2))ابتدا ارزیابی می شوند ، و سپس آنها موظف هستندF1وتF2بشراین بدان معنی است که کد LISP زیر کار نخواهد کرد: LISP قبل از برقراری اتصالات سعی در ارزیابی قسمتهای دست راست دارد. بنابراین ، بیان(* x 2)قبل از اتصال ارزیابی می شودxموجود است. برای انجام اتصال متوالی ، ازاجازه دهید*در عوض فرم: LISP به هم متصل خواهد شد1بهx، سپس ارزیابی کنید(* x 2)قبل از اینکه مقدار به آن محدود شودy.

لیست

مقادیر عددی تنها نوع پشتیبانی از داده های LISP نیستند. LISP برای محاسبات نمادین طراحی شده است. ساختار داده اصلی LISP برای پشتیبانی از دستکاری نمادین لیست هایی هستند. در حقیقت ، LISP مخفف "پردازش لیست" است.

لیست ها ظروف هستند که از مسیر متوالی پشتیبانی می کنند. لیست همچنین یک ساختار داده بازگشتی است: تعریف آن بازگشتی است. به همین ترتیب ، بیشتر الگوریتم های مسافرتی آن توابع بازگشتی هستند. به منظور درک بهتر یک نوع داده انتزاعی بازگشتی و آماده سازی خود برای توسعه عملیات بازگشتی در نوع داده ، باید نوع داده را از نظر سازندگان ، انتخاب کنندگان و شناسه های آن ارائه داد.

1. نیل: ارزیابینیلیک لیست خالی ایجاد می کند.
2. (منفی x l): با توجه به یک شیء LISP X و یک لیست L ، ارزیابی(منفی x l)لیستی حاوی x و به دنبال آن عناصر موجود در l ایجاد می کند.

توجه کنید که تعریف فوق ذاتاً بازگشتی است. به عنوان مثال ، برای ساخت لیستی حاوی 1 و به دنبال آن 2 ، می توانیم عبارت را تایپ کنیم: LISP با چاپ پاسخ می دهد(1 2)، که نمایش قابل خواندن تر از لیست حاوی 1 و به دنبال آن است. برای درک اینکه چرا موارد فوق کار می کند ، توجه کنیدنیلیک لیست (یک خالی) است ، و بنابراین(منفی 2 صفر)همچنین یک لیست است (لیستی که حاوی 1 است و به دنبال آن چیزی نیست). با استفاده از سازنده دوم دوباره ، آن را می بینیم(منفی 1 (منفی 2 صفر))همچنین یک لیست (لیستی حاوی 1 و به دنبال آن 2 و به دنبال آن چیزی نیست).

تایپ کردنمنفیعبارات می توانند خسته کننده باشند. اگر از قبل همه عناصر موجود در یک لیست را می شناسیم ، می توانیم لیست خود را به عنوان لیست های لیست وارد کنیم. به عنوان مثال ، برای وارد کردن لیستی که شامل تمام اعداد اصلی کمتر از 20 است ، می توانیم عبارت زیر را تایپ کنیم: توجه داشته باشید که ما لیست را با استفاده از لیست نقل کرده ایمنقل قولفرم خاصاین امر ضروری است زیرا ، بدون نقل قول ، LISP عبارت را تفسیر می کند(2 3 5 7 11 13 17 19)به عنوان یک تابع فراخوانی با یک تابع با نام "2" و آرگومان های 3 ، 5 ،. 19نقل قولفقط یک وسیله نحوی است که به LISP دستور می دهد تا فرم A را به ترتیب کاربردی ارزیابی نکند ، بلکه آن را به عنوان یک لفظی رفتار می کند. از آنجا که نقل قول اغلب در برنامه های LISP استفاده می شود ، یک کوتاه برای آن وجود داردنقل قول: نماد نقل قول'چیزی نیست جز یک syntactic shorthand برای(نقل قول.).

ماده دوم از نوع داده انتزاعی انتخاب کننده های آن هستند. با توجه به یک شی ترکیبی که از چندین مؤلفه ساخته شده است ، یک فرم انتخاب کننده یکی از مؤلفه های آن را برمی گرداند. به طور خاص ، یک لیست L فرض کنید₁با ارزیابی ساخته می شود(منفی x l₂ )، جایی که x یک شیء lisp و l است₂یک لیست استسپس ، انتخاب کننده شکل می گیرد(اول ل₁ )وت(استراحت L₁ )ارزیابی به X و L₂به ترتیب ، همانطور که نمونه های زیر نشان می دهد:

سرانجام ، ما به شناسه ها نگاه می کنیم ، عباراتی که چگونه یک شیء ساخته می شود. مربوط به هر سازنده از یک نوع داده ، تشخیص دهنده است. در مورد لیست ، آنها هستندخالیبراینیلوتتلقین کردنبرایمنفیبشربا توجه به لیست l ،(NULL L)بازگرداندنtiff l استنیلوت(Consp L)بازگرداندنtiff l از ساخته شده استمنفیبشرتوجه کنید که ، از آنجا که لیست ها فقط دو سازنده دارند ، شناسه کننده مکمل هستند. بنابراین ، ما معمولاً فقط به یکی از آنها احتیاج داریم. در بحث زیر ، ما فقط استفاده می کنیمخالی.

بازگشت ساختاری با لیست

• مورد 1: L استنیلبشرطول یک لیست خالی صفر است.
• مورد 2: L توسط ساخته شده استمنفیبشرسپس L از دو بخش تشکیل شده است ، یعنی ،(اول L)وت(استراحت L)بشردر چنین حالتی ، طول L را می توان با افزودن 1 به طول به صورت القایی بدست آورد(استراحت L).

به طور رسمی ، ما می توانیم نسخه خودمان را اجرا کنیمطول لیستبه شرح زیر: در اینجا ، ما از تشخیص دهنده استفاده می کنیمخالیبرای تمایز نحوه ساخت L. در مورد L استنیل، ما 0 را به عنوان طول آن برمی گردانیم. در غیر این صورت ، lمنفی، و ما 1 به علاوه طول(استراحت L)بشربه یاد بیاورید که(1+ n)به سادگی کوتاه است(+ n 1).

باز هم ، استفاده از امکانات ردیابی برای بررسی آشکار شدن دعوت های بازگشتی آموزنده است:

1. برای تعیین چگونگی ایجاد X از تشخیص دهندگان استفاده کنید (یعنی کدام سازنده آن را ایجاد می کند). در مثال ما استفاده می کنیمخالیبرای تصمیم گیری در مورد ایجاد لیست توسطنیلیامنفی.
2. برای مواردی که اتمی هستند (یعنی آنهایی که توسط سازندگان ایجاد شده اند و دارای مؤلفه نیستند) ، یک مقدار بی اهمیت را برمی گردانند. به عنوان مثال ، در موردی که یک لیست استنیل، ما صفر را به عنوان طول آن برمی گردانیم.
3. اگر نمونه کامپوزیت است ، از انتخاب کنندگان برای استخراج اجزای آن استفاده کنید. در مثال ما استفاده می کنیماولینوتباقی ماندهبرای استخراج دو مؤلفه یک لیست غیر خالی.
4. پس از آن ، ما در یک یا چند مؤلفه x دوباره بازگشتی را اعمال می کنیم. به عنوان مثال ، ما به طور مجدد فراخوانی کردیملیست بازگشتیبر(استراحت L).
5. سرانجام ، ما از سازندگان یا برخی از توابع دیگر برای ترکیب نتیجه تماس های بازگشتی استفاده می کنیم و مقدار عملکرد را به دست می آوریم. در شرایطی کهلیست بازگشتی، ما یک به علاوه نتیجه تماس بازگشتی را برمی گردانیم.

ورزش: یک عملکرد بازگشتی خطی را اجرا کنید(جمع L)که مبلغ همه اعداد را در یک لیست l محاسبه می کند. راه حل خود را با الگوی استاندارد بازگشت ساختاری مقایسه کنید.

بعضی اوقات ، ردیابی های طولانی مانند یکی برای طول لیست ممکن است خواندن روی صفحه ترمینال دشوار باشد.common Lisp به شما امکان می دهد صفحه نمایش I/O را در یک پرونده ضبط کنید تا به عنوان مثال بتوانید یک نسخه سخت را برای خواندن راحت تر تهیه کنید. برای گرفتن اثری از اجرای(طول بازگشتی "(2 3 5 7 11 13 17 19))، ما ازچیدنفرمان: فرم(دریبل "output. txt")به LISP مشترک دستور می دهد تا همه ترمینال I/O را در پرونده ای به نام شروع کندoutput. txtبشردنباله دار(دریبل)فرم به LISP مشترک برای متوقف کردن ضبط I/O دستور می دهد و پرونده را می بنددoutput. txtبشراگر بررسی کنیمoutput. txt، موارد زیر را خواهیم دید:

نماد

لیست هایی که تاکنون دیده ایم لیست شماره هایی است. نوع داده دیگر LISP نمادها است. یک نماد به سادگی دنباله ای از شخصیت ها است:

با نمادها می توانیم لیست های جالب تری بسازیم: توجه داشته باشید که لیست(جفت (2 3))دارای طول 2: توجه به نتیجه استفاده از دسترسی ها: لیست های حاوی لیست های دیگر به عنوان اعضا برای مبتدیان دشوار است. اطمینان حاصل کنید که مثال فوق را درک کرده اید.

مثال:نهم

• مورد 1: L استنیلبشردسترسی به عنصر N 'Th یک عمل نامشخص است و اجرای ما باید به طور خودسرانه بازگرددنیلبرای نشان دادن این
• مورد 2: L توسط a ساخته شده استمنفیبشرسپس L دارای دو مؤلفه است:(اول L)وت(استراحت L). There are two subcases: either N = 0 or N >0:
  • مورد 2. 1: n = 0. عنصر Zeroth L به سادگی است(اول L).
  • Case 2.2 : N >0عضو N 'L دقیقاً عضو (N-1) است(استراحت L).

  ورزش: LISP یک عملکرد داخلی دارد(آخرین L)که آخرین را برمی گرداندمنفیساختار در یک لیست معین l. نسخه خود را ازآخربا استفاده از بازگشت خطی. شما ممکن است فرض کنید که(آخرین صفر)بازگرداندننیلبشراجرای خود را با الگوی استاندارد بازگشت ساختاری مقایسه کنید.

  توجه کنید که ما در اجرای خود یک ساختار استاندارد IF-Then-Else-If داریملیستبشرچنین منطقی می تواند با استفاده ازمجرایفرم خاصدرمجرایفرم بالا به شرح زیر ارزیابی می شود. شرایط(NULL L)ابتدا ارزیابی می شود. اگر نتیجه درست باشد ، پسنیلبرگردانده شده استدر غیر این صورت ، شرط(Zerop n)ارزیابی می شوداگر شرط نگه داشته شود ، مقدار آن(اول L)برگردانده شده استدر صورتی که هیچ یک از شرایط وجود نداشته باشد ، ارزش آن(لیست-nth (1- n) (استراحت l))برگردانده شده است

  ورزش: بررسی CLTL2 بخش 7. 6 (صفحات 156-161) و دریابید که سایر فرم های خاص مشروط در LISP مشترک چیست. آیا می دانید چه زمانی اشکال خاص استچه زمانیوتمگر اینکهباید به جای استفاده شودif?

  مثال:عضو

  • مورد 1: L استنیلبشرL خالی است ، و هیچ راهی وجود ندارد که E در L باشد.
  • مورد 2: L توسط ساخته شده استمنفیسپس دو مؤلفه دارد:(اول L)وت(استراحت L)بشردو مورد نیز وجود دارد(اول L)خود E است ، یا اینطور نیست.
    • مورد 2. 1: E برابر است(اول L)بشراین بدان معنی است که E عضو L است ،
    • مورد 2. 2: E برابر نیست(اول L)بشرسپس E عضو L iff E عضو است(استراحت L).

    ردیابی اعدامعضو لیست، ما موارد زیر را دریافت می کنیم:

    در اجرایعضو لیست، تماس عملکرد(eq x y)اگر دو نماد یکسان باشند ، آزمایش می شوند. در حقیقت ، معناشناسی این آزمون تعیین می کند که منظور ما از یک عضو چیست: در مثال بالا ، ما انتظار داشتیمtبشربا این حال ، از آنجا(A B)نمی کندeqنسخه دیگری از(A B)(آنها همان نماد نیستند) ،عضو لیستبازگرداندننیلبشراگر می خواهیم برای هم ارزی لیست حساب کنیم ، می توانستیم از عملکرد داخلی LISP استفاده کنیمبرابربجایeqبشرCommon LISP مجموعه زیر را برای آزمایش برابری تعریف می کند:

     

    (= x y)	اگر x و y به همان تعداد ارزیابی می شوند ، درست است.
    (eq x y)	اگر x و y به همان نماد ارزیابی می شوند ، درست است.
    (eql x y)	اگر x و y هم باشند درست است=یاeq.
    (برابر x y)	اگر x و y هستند درست استEQLیا اگر آنها در همان لیست ارزیابی کنند.
    (برابر x y)	برای بحث در آموزش 4.

    ورزش: رفتار چه خواهد بودعضو لیستاگر جایگزین کنیمeqتوسط=؟توسطEQL؟توسطبرابر?

    مثال:ضمیمه کردن

    • مورد 1: L1 استنیلبشرپیوستن به L2 به L1 به سادگی منجر به L2 می شود.
    • مورد 2: L1 از دو بخش تشکیل شده است:(اول L1)وت(استراحت L1)بشراگر ما نتیجه ضمیمه L2 را می دانیم(استراحت L1)، سپس ما می توانیم این نتیجه را بگیریم ، درج کنیم(اول L1)به جلو ، و ما لیست مورد نظر خود را داریم.

    به طور رسمی ، ما عملکرد زیر را تعریف می کنیم: ردیابی اجرای موارد زیر است:

    ورزش: LISP یک عملکرد را تعریف می کند(Butlast L)این لیستی را که حاوی همان عناصر در L است به جز مورد آخر باز می گرداند. نسخه خود را ازکله پابا استفاده از بازگشت خطی. شما ممکن است فرض کنید که(باتلاست نیل)بازگرداندننیل.

    با استفاده از لیست ها به عنوان مجموعه

    1. مجموعه ها بدون هماهنگ هستند ، اما لیست ها هستند.(A B C)وت(C B A)دو لیست متفاوت هستند.
    2. یک عنصر یا متعلق به یک مجموعه است یا اینطور نیست. هیچ تصوری از وقایع متعدد وجود ندارد. با این حال ، یک لیست ممکن است حاوی چندین مورد از همان عنصر باشد.(A B B C)وت(A B C)دو لیست متفاوت هستند.
    • مورد 1: L1 یک مجموعه خالی است. سپس تعامل آن با L2 آشکارا خالی است.
    • مورد 2: L1 خالی نیست. L1 هر دواولینمؤلفه وباقی ماندهجزء. دو مورد وجود دارد: یا(اول L1)عضو L2 است یا اینطور نیست.
      • مورد 2. 1:(اول L1)عضو L2 است.(اول L1)متعلق به هر دو L1 و L2 است و به این ترتیب متعلق به تقاطع آنها است. بنابراین ، تقاطع L1 و L2 به سادگی است(اول L1)به علاوه تقاطع(استراحت L1)و L2
      • مورد 2. 2:(اول L1)عضو L2 نیست. از آنجا که(اول L1)متعلق به L2 نیست ، متعلق به تقاطع L1 و L2 نیست. در نتیجه ، تقاطع L1 و L2 دقیقاً تقاطع است(استراحت L1)و L2

      اثری از اجرای عملکرد در زیر آورده شده است:

      تمرین: اجرای خطی بازگشتی ازاتحاد. اتصالوتتفاوت.