ارزیابی کندرو
در میان استراتژی‌های ارزیابی در نظریهٔ زبان‌های برنامه‌نویسی، ارزیابی کندرو یا فراخوانی به هنگام نیاز استراتژی‌ای برای ارزیابی است که دارای دو ویژگی ارزیابی غیرموکد و اشتراک‌گذاری می‌باشد. ارزیابی غیرموکد موجب می‌شود که محاسبه و ارزیابی یک عبارت تا جای ممکن به تأخیر افتاده و در اولین زمانی که دسترسی به آن نیاز بود، محاسبه شود. ارزیابی کندرو به وسیلهٔ اشتراک‌گذاری از ارزیابی‌های تکراری جلوگیری می‌کند. به کمک اشتراک‌گذاری، زمان اجرای یک تابع به صورت توانی نسبت به دیگر استراتژی‌هایی که ارزیابی غیرموکد دارند کاهش می‌یابد و به این صورت ترکیب این دو ویژگی، ارزیابی کندرو را نسبت به دیگر استراتژی‌ها بهبود می‌بخشد. از جمله این استراتژی‌ها می‌توان استراتژی فراخوانی با نام را نام برد.
در مقابل ارزیابی کندرو، ارزیابی تندرو یا استراتژی موکد قرار دارد. این استراتژی ارزیابی در بیشتر زبان‌های برنامه‌نویسی مورد استفاده قرار می‌گیرد. به‌طور خلاصه، در این ارزیابی برخلاف ارزیابی کندرو، رویهٔ یک تابع، حتی اگر هیچگاه مورد استفاده قرار نگیرد و یا بعد از زمان زیادی به آن نیاز داشته باشد، به محض فراخوانی برای یک یا چندین متغیر با مقادیر مشخص اجرا می‌شود.
تاریخچه[ویرایش]
ارزیابی کندرو ابتدا برای جبر لاندا توسط کریستوفر وادزورث تعبیه شد. پیتر هندرسون و جیمز هیرام موریس و همچنین دنیل پائول فریدمن و دیوید وایس هر یک این ارزیابی را برای زبان‌های برنامه‌نویسی به‌طور مستقل تعریف کردند.
شرح استراتژی[ویرایش]
ارزیابی کندرو طبق شرح جان لوئیس بنتلی در گزارش «نوشتن برنامه کارآمد» معمولاً با مموایز کردن ترکیب می‌شود. در عمل به هر عبارت که معادل تابعی از یک یا چند متغیر با مقادیری مشخص می‌باشد، خانه‌ای از حافظه تعلق می‌گیرد که این خانه با داشتن مقادیر متغیرها قابل دسترسی است. در مموایز کردن عبارات به دو دسته تقسیم می‌شوند. دستهٔ اول عباراتی هستند که برای بار اول محاسبه می‌شوند. در این دسته پس از محاسبهٔ عبارت، مقدار حاصل را در خانهٔ مربوطه نیز ذخیره می‌کنند. دستهٔ دوم عباراتی هستند که برای بار دوم و یا بیشتر مورد استفاده قرار می‌گیرند. این عبارات از دفعهٔ دوم به بعد، به جای محاسبهٔ مجدد، به خانهٔ حافظهٔ مربوطه رجوع کرده و مقدار را از خانهٔ حافظه برمی‌دارند. کارکرد مموایز کردن در ارزیابی کندرو تنها این تفاوت را قائل می‌شود که محاسبه و ذخیره‌سازی عبارت را تا اولین زمان نیاز به مقدار عبارت، به تأخیر می‌اندازد. روشن است که ایجاد این تأخیر اثر مخربی بر فرایند مموایز کردن ندارد و سلسله عملکرد آن را حفظ خواهد کرد.
بنابراین در ارزیابی کندرو در صورت مواجه شدن با یک عبارت، ابتدا تا اولین نیاز به مقدار آن هیچ اقدامی صورت نمی‌گیرد. سپس در هنگام نیاز به مقدار عبارت، ابتدا بررسی می‌شود که این اولین باریست که نیاز به محاسبهٔ عبارت وجود دارد یا خیر. اگر اولین بار باشد، مقدار عبارت طبق رویهٔ تابع محاسبه گردیده و مقدار آن در خانهٔ مربوطه نیز ذخیره می‌شود. در غیر این صورت، بدون محاسبهٔ مجدد عبارت، مقدار آن که در مراحل قبل محاسبه شده، از خانهٔ مربوطه برداشته می‌شود و مورد استفاده قرار می‌گیرد. بخشی از حافظه را که به مقادیر عبارات تعلق می‌گیرد، جدول مراجع می‌نامند.
مزایا و معایب[ویرایش]
غیرموکد بودن این ارزیابی، با توجه به این که ذخیرهٔ مقدار را تا زمان نیاز به تأخیر می‌اندازد، موجب کاهش حافظهٔ مورد استفاده در هر لحظه خواهد شد. اما با این حال محاسبهٔ حافظهٔ مورد استفاده در این روش ارزیابی قابل پیش‌بینی نیست. علاوه بر این در عبارات ساختاریافته، می‌توان با بخش‌بندی کردن عبارت، تنها بخش‌های مورد نیاز آن را محاسبه کرد و برای سایر بخش‌ها جدول مراجع و مقادیر ثابت را مورد استفاده قرار داد. با توجه به این که ایجاد لیست واسط نیز تا زمان نیاز به تعویق می‌افتد، استفاده از آن لزوماً هزینهٔ زیادی به همراه نخواهد داشت و این هزینه در موارد خاص چشمگیر خواهد بود. همچنین این ارزیابی، به کمک مموایز کردن، محاسبات تکراری را کاهش داده و زمان اجرای برنامه را بهبود می‌دهد.
علی‌رغم وجود این مزایا، غیرموکد بودن ارزیابی موجب بهم ریختن ترتیب اجرای دستورات شده و ترکیب این ارزیابی با ویژگی‌های ضروری دیگر را دشوار می‌سازد. از جمله این ویژگی‌ها می‌توان مدیریت استثناءها و مدیریت ورودی/خروجی را نام برد. علاوه بر این ارزیابی کندرو می‌تواند موجب نشت حافظه شود.
پیاده سازی در زبان‌های مختلف[ویرایش]
برخی از زبان‌های برنامه‌نویسی به تأخیر انداختن ارزیابی عبارات را به صورت معمول انجام می‌دهند. در عین حال برخی زبان‌های دیگر از توابع و نمادهای خاصی برای این کار استفاده می‌کنند. برای مثال در زبان‌های میراندا و هاسکل این کار به‌طور معمول انجام می‌شود، در حالی که در زبان اسکیم از عباراتی معادل تاخیر و اجرا و در زبان اکمل از عباراتی معادل کندرو و اجرای کندرو استفاده می‌شود. برخی دیگر از زبان‌ها، ارزیابی کندرو را تنها برای برخی از ساختمان‌داده‌ها و یا تنها بر روی یک ساختمان‌دادهٔ خودساخته تعریف می‌کنند. برای مثال در زبان پرل۶ ارزیابی کندرو بر روی لیست‌ها تعریف شده، در حالی که این ارزیابی در این زبان برای محاسبهٔ توابع و عملگرهای ریاضی تعبیه نشده‌است.
شرح یک مثال در زبان پایتون نیز عملکرد استراتژی را واضح‌تر خواهد ساخت. تابع در زبان پایتون را در نظر بگیرید. این تابع لیستی از اعداد را در بازه‌ای خاص و با فاصلهٔ گام‌های مشخص ایجاد می‌کند. این زبان برای این تابع ارزیابی کندرو را مورد استفاده قرار داده است. این ارزیابی برای فراخوانی تابع در بازه‌های بزرگی از اعداد، موجب کاهش زمان اجرا خواهد شد. همچنین حافظهٔ مورد استفاده نیز کاهش خواهد یافت. چرا که تمامی مقادیر بازه در یک لحظه مورد استفاده قرار نمی‌گیرند و نیاز به دسترسی همزمان به تمام اعداد در یک لحظه نخواهد بود.
منابع[ویرایش]
- Haskell: The Craft of Functional Programming (2nd edition), by Simon Thompson
- Programming in Haskell, by Graham Hutton