اختزال الرسم البياني

في علوم الحاسوب ، يُطبّق اختزال الرسوم البيانية نسخةً فعّالةً من التقييم غير الصارم، وهي استراتيجية تقييم لا تُقيّم فيها وسائط الدالة فورًا. يُعرف هذا النوع من التقييم غير الصارم أيضًا بالتقييم الكسول ، ويُستخدم في لغات البرمجة الوظيفية . طُوّرت هذه التقنية لأول مرة على يد كريس وادزورث عام ١٩٧١.

فيما يلي مثال بسيط لتقييم تعبير حسابي:

${\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+(2+2))+6\\&{}&=&((2+2)+4)+6\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}$

تستخدم سلسلة الاختزال المذكورة أعلاه استراتيجية تُعرف باسم اختزال الشجرة الخارجية . ويمكن تقييم التعبير نفسه باستخدام اختزال الشجرة الداخلية ، مما ينتج عنه سلسلة الاختزال التالية:

${\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+4)+(3+3)\\&{}&=&(4+4)+(3+3)\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}$

لاحظ أن ترتيب الاختزال مُوضَّحٌ بإضافة الأقواس. كان من الممكن أيضًا تقييم هذا التعبير ببساطة من اليمين إلى اليسار، لأن الجمع عملية تجميعية .

إذا تم تمثيل التعبير أعلاه على شكل شجرة ، فسيبدو كالتالي:

من هنا جاء مصطلح اختزال الشجرة. فعند تمثيلها كشجرة، يمكننا أن نفكر في الاختزال الداخلي على أنه يعمل من الأسفل إلى الأعلى، بينما يعمل الاختزال الخارجي من الأعلى إلى الأسفل.

يمكن أيضًا تمثيل التعبير كرسم بياني موجه غير دوري ، مما يسمح بمشاركة التعبيرات الفرعية:

أما بالنسبة للأشجار، فإن الاختزال الخارجي والداخلي ينطبق أيضاً على الرسوم البيانية. ومن ثم لدينا اختزال الرسوم البيانية .

يمكن الآن إجراء التقييم باستخدام اختزال الرسم البياني الخارجي على النحو التالي:

لاحظ أن التقييم يتطلب الآن أربع خطوات فقط. يُشار إلى اختزال الرسم البياني الخارجي بالتقييم الكسول ، ويُشار إلى اختزال الرسم البياني الداخلي بالتقييم الفوري .

يُعد اختزال الرسم البياني التجميعي أسلوبًا أساسيًا لتنفيذ لغات البرمجة الوظيفية ، حيث يتم تحويل البرنامج إلى تمثيل تجميعي يتم تعيينه إلى بنية بيانات الرسم البياني الموجه في ذاكرة الكمبيوتر، ثم يتكون تنفيذ البرنامج من إعادة كتابة أجزاء من هذا الرسم البياني ("اختزاله") من أجل الانتقال نحو نتائج مفيدة.

طُوِّر مفهوم اختزال الرسم البياني الذي يسمح بمشاركة القيم المُقَيَّمة لأول مرة على يد كريس وادزورث في أطروحته للدكتوراه عام 1971. ^{[ 1 ]} وقد استشهد بيتر هندرسون وجيمس إتش. موريس الابن بهذه الأطروحة في ورقة بحثية نُشرت عام 1976 بعنوان "مُقَيِّم كسول" ^{[ 2 ]} ، والتي قدمت مفهوم التقييم الكسول. وفي عام 1976، أدمج ديفيد تيرنر التقييم الكسول في لغة SASL باستخدام المُركِّبات. ^{[ 3 ]} وكانت SASL لغة برمجة وظيفية مبكرة طوّرها تيرنر لأول مرة عام 1972.

• آلة اختزال الرسوم البيانية
• آلة SECD

• بيرد، ريتشارد (1998). مقدمة في البرمجة الوظيفية باستخدام هاسكل . برنتيس هول. ISBN 0-13-484346-0.

• بيتون جونز، سيمون ل. (1987). تطبيق لغات البرمجة الوظيفية . برنتيس هول. ISBN 013453333XLCCN 86020535. تم الاطلاع عليه بتاريخ 15-04-2022 .