تثمين كسول

في نظرية لغة البرمجة، إنَّ التثمين الكسول (بالإنجليزية: Lazy evaluation)‏ أو الاستدعاء عند الحاجة (بالإنجليزية: call-by-need)‏[1]، هي استراتيجية تثمين تؤخِّر تثمين التعبير لحين احتياج قيمته (تثمين غير صارم) وَتتجنّب بذلك -مُشاركة- التَثمينات المُتكرِّرة.[2][3] يُمكن للمُشاركة إنقاص وقت تشغيل دوال مُعيَّنة بعاملٍ أُسِّي على استراتيجيَّات التثمين غير الصارم، مثل الاستدعاء بالاسم.[بحاجة لمصدر]

استرتيجية تثمين
  • تثمين لهوف
  • تثمين كسول
  • تثمين جزئي
  • تثمين بعادي
  • تثمين قصير الدوران

تتضمَّن منافع التثمين الكسول:

  • القدرة على تعريف بُنى تدفق السيطرة بتجريدٍ بدلًا من أن تكون مُدمجة.
  • القدرة على تعريف بُنى بيانات مُمكنة الأزليَّة، يسمح هذا بتنفيذ دقيق للمزيد من الخوارزميَّات.
  • زيادة الأداء بتجنُّب الحسابات غير الضروريَّة وَالأخطاء في حالة تثمين التعابير المُركَّبة.

غالبًا ما يُدمَج التثمين الكسول مع استحضار الذاكرة[4](memoization أو memoisation)، كما قد ذُكِر في «كتابة برامج كفء»(Writing Efficient Programs) لِـجون بينتلي، غالبًا ما يُدمَج التثمين الكسول مع التذكُّر.[5] بعد أن تُحوسب قيمة الدالَّة من أجل مُعطىً أو مجموعة من المُعطيات، فإنَّ النَّتيجة تُخَزَّن في جدول المُشاهدات المُفَهرَس وفق قيم المُعطيات؛ وفي المرَّة القادمة الَّتي سَتُستَدعى فيها الدالَّة سيتم تفقُّد الجدول لتحديد فيما إذا كانت نتيجة قيم المُعطيات متوفِّرةً بالفعل أم لا. عندها وببساطة سَتُعاد قيمة النتيجة المُخَزَّنة وَإن كان العكس فَسيتم تثمين الدالَّة وَيُضاف مُدخَل جديد إلى جدول المُشاهدات لِيُعاد استخدامه لاحقًا.

قد يؤدِّي التثمين الكسول إلى نقص في الذكرة اللّازمة للبرامج(المحجوزة لها)؛ لأنَّ القيم تُنسَئ عند الحاجة إليها.[6] ومن الصَّعب دمج التثمين الكسول مع المَزايا الأمريَّة مثل استيعاب الأخطاء وَالدخل/الخرج، لأنّ ترتيب العمليّات يصبح غيرَ مُحدَّدٍ. وَقد يسبّب التثمين الكسول تسرب الذاكرة.[7]

عكس التثمين الكسول هو «التثمين اللَّهوف»(eager evaluation)؛ وَأحيانًا يُعرَف باسم التثمين الصارم(strict evaluation). ولقد وظِّف التثمين اللَّهوف كاستراتيجيّة تثمين في أغلب لُغات البرمجة.

لمحة تاريخيّة

قُدِّمَ التثمين الكسول من أجل حسابات اللامدا من قِبَل كريستوفر وادز-ورث[8] وَباستقلالٍ من أجل لُغات البرمجة من قِبَل بيتر هيندرسن وَجيمس حيرم موريس[9] وَدانيال بول فريدمان وَديفيد س. وايز.[10][11]

التطبيقات

يُستخدم التثمين المؤجَّل(Delayed evaluation) تحديدًا في لُغات البرمجة الوظيفيَّة. فعند استخدام التثمين المؤجَّل، لا يتم تثمين التعبير عند إسناده إلى مُتَغَيِّر بل يُثَمَّن عند الحاجة لإنتاج قيمة التعبير. هذه إفادة كمثال، x:=expression; (إسناد نتيجة التعبير إلى مُتَغَيِّر). بوضوحٍ، تَمَّ استدعاء التعبير بُغية تثمينه وَوُضِعَت النتيجة في x، لكن يتم تعليق ما بداخل x لِحين احتياج قيمته وذلك باستخدام فهرس يقود إلى x في تعبيرٍ ما لاحِقٍ وقد يكون هذا التعبير أيضًا مؤجّلًا، وأخيرًا تُشَذَّب شجرة الاعتماديَّات النامية هذه لإنتاج بعض الرموز الّتي يُفَضَّل رؤيتها.[12]

من فوائد التثمين المؤجَّل قدرته على إنشاء قوائم لانهائيَّة قابلة للحِساب بدون تداخل الحلقات اللَّانهائيَّة أو الحجم في الحِساب. كمثال، يُمكن إنشاء دالَّة تُنشِئ قائمة لانهائيَّة (تُدعى غالبًا «جريان») من أعداد فيبوناتشي. إنَّ حِساب عدد فيبوناتشيّ ما -وليكن «ن»- سيكون بكلّ بساطة استخلاصًا لهذا العنصر -الّذي هو العدد «ن»- من القائمة اللَّانهائيَّة، مُجبرًا بذلك على تثمين أوَّل ن عنصر من القائمة.[13][14]

كمثال، يُمكن في لغة البرمجة هاسكل كتابة قائمة بكلّ أعداد فيبوناتشي كالتالي:[14]

 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

في نحويَّة هاسكل، «:» تُضيف عنصرًا إلى بداية القائمة وَ«tail» تعود بالقائمة بدون عنصرها الأوَّل وَ«zipWith» تَستَخدِم دالَّة مُعَيَّنة (في حالتنا هذه هي الجمع «+») لجمع العناصر المُتوافقة لِكلا القائمتين بهدف إنتاج قائمة ثالثة.[13]

يجب أن يكون المبرمج حذرًا وَدقيقًا؛ لأنّه يتم فقط تثمين القيم اللّازمة لإنتاج نتيجة معيّنة. ومع ذلك، قد تؤدّي بعض الحسابات إلى محاولة البرنامج لتثمين عدد لا حصر له من العناصر؛ على سبيل المثال، طلب طول القائمة أو محاولة جمع عناصر القائمة بعملية الطيّ يؤدي بالبرنامج إمَّا إلى فشل الإنهاء أو نفاد الذاكرة.

بُنى التحكّم

في كلّ اللّغات «اللّهوفة» تقريبًا، يتمّ تثمين الإفادة «if» بأسلوب كسولٍ.

if a then b else c

سيتمّ تثمين (a)، وَإذا وَفقط إذا ثُمِّنَت (a) لتكون صح «true» سيتمّ تثمين (b) وَإلّا سيتمّ تثمين (c). وبذلك لن يتمّ تثمين واحد من (b) وَ (c). بالمُقابِل، سيكون السلوك المُتَوَقَّع هو هذا:

define f(x, y) = 2 * x
set k = f(d, e)

سيتمّ تثمين (e) عند حِساب قيمة f(d, e) وعلى الرُّغم من ذلك فقيمة (e) غير مُستخدمة في الدالَّة f. وبالتالي تعتمد بُنى التحكّم المُعرَّفة من قِبَل المُستَخدِم على النحويَّة المضبوطة، كمثال:

define g(a, b, c) = if a then b else c
l = g(h, i, j)

سيتمّ تثمين كُلٍّ من (i) وَ (j) في اللُّغة اللَّهوفة. بينما في اللُّغة الكسولة،

l' = if h then i else j

سيتمّ تثمين إمَّا (i) أو (j)، ولن يتمّ تثمين كليهما معًا أبدًا.

يسمَح التثمين الكسول بتعريف بُنى التحكّم طبيعيًّا، وَلكن لا يسمح لها أن تكون مُدمَجة أو كتقنيّات وقت-التجميع. فإذا كان لِـ (i) أو (j) آثارًا جانبيّةً أو أثارت أخطاءً في وقت التشغيل، عنها ستكون الاختلافات غير الملحوظة بين (l) وَ (l') مُعَقَّدَةً. وَمن المُمكن عادةً إنشاء بُنى تحكّمٍ كسولة يُعرّفها المُستخدِم كَدوالٍّ في اللُّغات اللَّهوفة، لذلك قد تُزاح تلك الدَّوال من نحويَّة اللُّغة عند التثمين اللَّهوف: غالبًا ما يُحتَاج ادّثار جسد الشِفرة (مثل: (i) وَ (j)) ليصبح قيمة الدالَّة، ولذلك يتمّ فقط تنفيذها عند الاستدعاء.

يُدعى التثمين قصير الدوران (وَيُسمّى أيضًا: تثمين دُونيّ أو تثمين مَكارثي) لِبُنى التحكّم البوليانيّة(المنطقيّة) تثمينًا «كسولًا».

العمل مع بُنى بيانات أزليّة

توفّر العديد من اللُّغات مفهوم «بُنى-البيانات الأزليّة (لا محدودة)» (بالإنجليزية: infinite data-structures)‏. ويسمح ذلك بتعريف البيانات كمجالات أزليّة أو كتعاوديّة غير منتهية (unending recursion)، لكن يتمّ حساب القيم الفعليّة عندما نحتاجها فحسب. تفقّد هذا المِثال المتواضع؛ وهو برنامج في لغة هاسكل:

numberFromInfiniteList :: Int -> Int
numberFromInfiniteList n = infinity !! n - 1
    where infinity = [1..]

main = print $ numberFromInfiniteList 4

في الدالَّة numberFromInfiniteList، إنّ قيمة infinity هي مجال لا محدود، ولحين احتياجه يتمّ تثمين المجال وصولًا إلى المؤشِّر (index) المطلوب.

قائمة الأنماط الناجحة
هذا القسم فارغ أو غير مكتمل، ساهم بتحريره.

المراجع
  1. Hudak 1989، صفحة 384
  2. David Anthony Watt; William Findlay (2004). Programming language design concepts. John Wiley and Sons. صفحات 367–368. ISBN 978-0-470-85320-7. مؤرشف من الأصل في 12 مارس 2017. اطلع عليه بتاريخ 30 ديسمبر 2010. الوسيط |CitationClass= تم تجاهله (مساعدة)
  3. Reynolds 1998، صفحة 307
  4. مَجمع اللُّغة العربيَّة على الشَّبكة العالميَّة، الفتوى: 1120. نسخة محفوظة 05 مارس 2017 على موقع واي باك مشين.
  5. Bentley, Jon Louis. Writing Efficient Programs. Prentice-Hall, 1985. ISBN 978-0-13-970244-0
  6. Chris Smith (22 October 2009). Programming F#. O'Reilly Media, Inc. صفحة 79. ISBN 978-0-596-15364-9. مؤرشف من الأصل في 13 يناير 2020. اطلع عليه بتاريخ 31 ديسمبر 2010. الوسيط |CitationClass= تم تجاهله (مساعدة)
  7. Edward Z. Yang. "Space leak zoo". نسخة محفوظة 17 يناير 2018 على موقع واي باك مشين.
  8. (Wadsworth 1971)
  9. (Henderson & Morris 1976)
  10. (Friedman & Wise 1976)
  11. Reynolds 1998، صفحة 312
  12. Philip Wadler (2006). Functional and logic programming: 8th international symposium, FLOPS 2006, Fuji-Susono, Japan, April 24-26, 2006 : proceedings. Springer. صفحة 149. ISBN 978-3-540-33438-5. مؤرشف من الأصل في 14 يناير 2020. اطلع عليه بتاريخ 14 يناير 2011. الوسيط |CitationClass= تم تجاهله (مساعدة)
  13. Daniel Le Métayer (2002). Programming languages and systems: 11th European Symposium on Programming, ESOP 2002, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002, Grenoble, France, April 8-12, 2002 : proceedings. Springer. صفحات 129–132. ISBN 978-3-540-43363-7. مؤرشف من الأصل في 14 أبريل 2020. اطلع عليه بتاريخ 14 يناير 2011. الوسيط |CitationClass= تم تجاهله (مساعدة)
  14. Association for Computing Machinery; ACM Special Interest Group on Programming Languages (1 January 2002). Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell '02): Pittsburgh, Pennsylvania, USA ; October 3, 2002. Association for Computing Machinery. صفحة 40. ISBN 978-1-58113-605-0. مؤرشف من الأصل في 12 مارس 2017. اطلع عليه بتاريخ 14 يناير 2011. الوسيط |CitationClass= تم تجاهله (مساعدة)

    مصادر

    قراءة موسَّعة
    • Wadsworth, Christopher P. (1971). Semantics and Pragmatics of the Lambda Calculus. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link) PhD thesis, Oxford University
    • Henderson, Peter; Morris, James H. (January 1976). "A Lazy Evaluator". Conference Record of the Third ACM symposium on Principles of Programming Languages. مؤرشف من الأصل في 14 أبريل 2020. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
    • Friedman, D. P.; Wise, David S. (1976). S. Michaelson and Robin Milner (المحررون). "Cons should not evaluate its arguments" (PDF). Automata Languages and Programming Third International Colloquium. Edinburgh University Press. الوسيط |CitationClass= تم تجاهله (مساعدة)صيانة CS1: يستخدم وسيط المحررون (link) CS1 maint: ref=harv (link)
    • Launchbury, John (1993). "A Natural Semantics for Lazy Evaluation". Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '93). doi:10.1145/158511.158618. مؤرشف من الأصل في 07 فبراير 2019. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
    أنماط التصميم
    الكسل في اللُّغات الصَّارمة
    تدوينات لعلماء الحاسوب

    روابط خارجيّة
    • بوابة برمجة الحاسوب
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.