الحوسبة التزايدية

الحوسبة التزايدية ، أو ما يُعرف أيضًا بالحساب التزايدي ، هي ميزة برمجية تعمل على توفير الوقت عند تغيير أي جزء من البيانات ، وذلك بإعادة حساب المخرجات التي تعتمد فقط على البيانات المتغيرة. ^[¹^]^[²^]^[³^] عندما تنجح الحوسبة التزايدية، فإنها تكون أسرع بكثير من حساب المخرجات الجديدة بالطريقة التقليدية. على سبيل المثال، قد يستخدم برنامج جداول البيانات الحوسبة التزايدية في وظائف إعادة الحساب، لتحديث الخلايا التي تحتوي على صيغ تعتمد (بشكل مباشر أو غير مباشر) على الخلايا المتغيرة فقط.

أداة الحوسبة التزايدية الآلية هي أداة متخصصة لتحليل البرامج بهدف التحسين.

ثابت مقابل ديناميكي

يمكن تصنيف تقنيات الحوسبة التزايدية بشكل عام إلى نوعين من الأساليب:

تحاول الأساليب الثابتة اشتقاق برنامج تدريجي من برنامج تقليدي P باستخدام، على سبيل المثال، إما التصميم اليدوي وإعادة الهيكلة، أو التحويلات البرمجية التلقائية. تحدث هذه التحويلات البرمجية قبل توفير أي مدخلات أو تغييرات في المدخلات.

تسجل الأساليب الديناميكية معلومات حول تنفيذ البرنامج P على مدخل معين (I1)، وتستخدم هذه المعلومات عند تغيير المدخل (إلى I2) لتحديث المخرج (من O1 إلى O2). يوضح الشكل العلاقة بين البرنامج P، ودالة حساب التغيير ΔP، التي تُشكل جوهر البرنامج التزايدي، وزوج من المدخلات والمخرجات، I1 وO1 وI2 وO2.

الأساليب المتخصصة مقابل الأساليب العامة

تتنوع أساليب الحوسبة التزايدية بين أساليب متخصصة وأخرى عامة. تتطلب الأساليب المتخصصة من المبرمج تحديد الخوارزميات وهياكل البيانات المستخدمة للحفاظ على العمليات الحسابية الفرعية دون تغيير. أما الأساليب العامة، فتستخدم اللغة أو المترجم أو التقنيات الخوارزمية لإضفاء سلوك تزايدي على البرامج غير التزايدية. ^{[ 4 ]}

الأساليب الثابتة

مشتقات البرنامج

بالنظر إلى عملية حسابية $C=f(x_{1},x_{2},\dots x_{n})$ وتغيير محتمل $x_{j}:=\Delta _{x_{j}}$ يمكننا إدراج التعليمات البرمجية قبل حدوث التغيير (المشتقة السابقة) وبعد التغيير (المشتقة اللاحقة) لتحديث قيمة $C$ أسرع من إعادة العرض $f$ . قام بايج بتدوين قائمة من القواعد للتفاضل الرسمي للبرامج في SUBSETL. ^{[ 5 ]}

عرض الصيانة

في أنظمة قواعد البيانات مثل DBToaster، تُعرَّف طرق العرض باستخدام الجبر العلائقي. يقوم نظام صيانة طرق العرض التزايدي بتحليل الجبر العلائقي بشكل ثابت لإنشاء قواعد تحديث تُحافظ على طريقة العرض بسرعة في حالة وجود تحديثات صغيرة، مثل إدراج صف. ^{[ 6 ]}

الأساليب الديناميكية

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

يمكن تجنب رصد التبعيات عبر جميع القيم الممكنة من خلال تحديد مجموعة فرعية من القيم المهمة (مثل نتائج التجميع) التي يمكن تتبع التبعيات عبرها، وإعادة حساب المتغيرات التابعة الأخرى تدريجياً، وبالتالي تحقيق التوازن بين كمية معلومات التبعية التي يجب تتبعها وكمية إعادة الحساب التي يجب إجراؤها عند تغيير المدخلات. ^{[ 7 ]}

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

مع وجود دورات في مخطط التبعية، قد لا تكفي عملية مرور واحدة عبر المخطط للوصول إلى نقطة ثابتة. في بعض الحالات، تكون إعادة التقييم الكاملة للنظام مكافئة دلاليًا للتقييم التدريجي، وقد تكون أكثر كفاءة عمليًا إن لم تكن كذلك نظريًا. ^{[ 8 ]}

الأنظمة الحالية

دعم المترجم واللغة

التزايد التلقائي (يُسمى أيضًا "الحوسبة ذاتية التعديل" و"البرمجة الوظيفية التكيفية")، ^{[ 9 ]} دلتا إم إل ، هاسكل التكيفي
مولد توليف كورنيل ^{[ 10 ]}
آيس داست - لغة مخصصة لمجال معين.

الأطر والمكتبات

Adapton ^{[ 11 ]} - مع تطبيقات بلغات متعددة
قيود تدفق البيانات أحادي الاتجاه (الحساب التفاعلي في لغة C++)
تدفق البيانات التفاضلي
جين ستريت إنكريديال
سجل البيانات التزايدي ( LogicBlox )
مقدمة تزايدية (XSB) ^{[ 12 ]}
FSharp.Data.Adaptive
الأساليب الخاصة بالمجال:
- التحقق التدريجي من النوع.

التطبيقات

قواعد البيانات (عرض الصيانة)
أنظمة البناء
الجداول الإلكترونية ^{[ 13 ]}
بيئات التطوير
الحسابات المالية
تقييم قواعد الإسناد
العمليات الحسابية والاستعلامات على الرسوم البيانية
واجهات المستخدم الرسومية (مثل React و DOM diffing)
التطبيقات العلمية.

انظر أيضاً

مراجع

↑ كارلسون، ماغنوس (2002). "المونادات للحوسبة التزايدية". وقائع المؤتمر الدولي السابع لجمعية ACM SIGPLAN حول البرمجة الوظيفية . نيويورك: ACM . الصفحات 26-35 . doi : 10.1145/581478.581482 . ISBN 1-58113-487-8.
↑ أوموت أ. أكار (2005). الحوسبة ذاتية التكيف (PDF) (أطروحة دكتوراه).
↑ كاميل ديميتريسكو؛ إيرين فينوتشي؛ أندريا ريبشيني (2011). "البرمجة الإجرائية التفاعلية مع قيود تدفق البيانات" . وقائع المؤتمر الدولي السادس والعشرين لجمعية الحوسبة الآلية (ACM) حول أنظمة ولغات وتطبيقات البرمجة كائنية التوجه (OOPSLA 2011) . جمعية الحوسبة الآلية (ACM ). الصفحات 407-426 . arXiv : 1104.2293 . doi : 10.1145/2048066.2048100 . ISBN 978-1-4503-0940-0.
↑ يان تشين؛ جوشوا دنفيلد؛ ماثيو أ. هامر؛ أوموت أ. أكار. الحوسبة الضمنية ذاتية التعديل للبرامج الوظيفية البحتة . المؤتمر الدولي للبرمجة الوظيفية 2011. الصفحات 129-141 . مؤرشف من الأصل بتاريخ 30 أكتوبر 2016. تم الاطلاع عليه بتاريخ 12 مارس 2018 .
↑ بايج، روبرت (1981). التمايز الرسمي: تقنية لتوليف البرامج . مطبعة يو إم آي للأبحاث. رقم ISBN 978-0-8357-1213-2.
↑ أحمد، يانيف؛ كينيدي، أوليفر؛ كوخ، كريستوف؛ نيكوليتش، ميلوس (2012-06-01). "DBToaster: معالجة دلتا من الرتبة العليا لعرض ديناميكي ومتجدد باستمرار". وقائع VLDB Endow . 5 (10): 968-979 . arXiv : 1207.0137 . doi : 10.14778/2336664.2336670 . ISSN 2150-8097 .
↑ موغيلان ماريبان؛ كيفال فورا (2019). "GraphBolt: معالجة متزامنة مدفوعة بالتبعية للرسوم البيانية المتدفقة". في المؤتمر الأوروبي لأنظمة الحاسوب (EuroSys'19) . الصفحات 25:1–25:16. doi : 10.1145/3302424.3303974 .
↑ كيمبرلي بيرشيت؛ غريغوري هـ. كوبر؛ شري رام كريشنامورثي (2007). "التخفيض: تقنية تحسين ثابتة للتفاعل الوظيفي الشفاف". في ندوة ACM SIGPLAN حول التقييم الجزئي ومعالجة البرامج القائمة على الدلالات . الصفحات 71-80 . CiteSeerX 10.1.1.90.5866 . ISBN 978-1-59593-620-2.
↑ هامر، ماثيو أ.؛ أكار، أوموت أ.؛ تشين، يان (2009). "CEAL". وقائع مؤتمر ACM SIGPLAN لعام 2009 حول تصميم لغات البرمجة وتنفيذها - PLDI '09 . ص 25. doi : 10.1145/1542476.1542480 . ISBN 9781605583921. S2CID 11058228 .
↑ ريبس، توماس؛ تيتلبوم، تيم (1984). "مولد المُركِّب". وقائع الندوة الأولى لهندسة البرمجيات ACM SIGSOFT/SIGPLAN حول بيئات تطوير البرمجيات العملية - SDE 1. الصفحات 42-48 . doi : 10.1145/800020.808247 . ISBN 978-0897911313.
↑ "Adapton: تجريدات لغة البرمجة للحساب التزايدي" . adapton.org . تم الاطلاع عليه بتاريخ 7 أكتوبر 2016 .
↑ ساها، ديبتيكاليان؛ راماكريشنان، سي آر (2005). "التقييم التزايدي لبرولوج الجدولي: ما وراء برامج المنطق البحت". الجوانب العملية للغات التصريحية . سلسلة محاضرات في علوم الحاسوب. المجلد 3819. الصفحات 215-229 . CiteSeerX 10.1.1.111.7484 . doi : 10.1007/11603023_15 . ISBN 978-3-540-30947-5ISSN 0302-9743
↑ هامر، ماثيو؛ فانغ، خو؛ هيكس، مايكل؛ فوستر، جيفري (2014). ADAPTON: الحوسبة التزايدية القابلة للتركيب والقائمة على الطلب (ملف PDF) . PLDI.

[monads-for-incremental-1] كارلسون، ماغنوس (2002). "المونادات للحوسبة التزايدية". وقائع المؤتمر الدولي السابع لجمعية ACM SIGPLAN حول البرمجة الوظيفية . نيويورك: ACM . الصفحات 26-35 . doi : 10.1145/581478.581482 . ISBN 1-58113-487-8.

[2] أوموت أ. أكار (2005). الحوسبة ذاتية التكيف (PDF) (أطروحة دكتوراه).

[3] كاميل ديميتريسكو؛ إيرين فينوتشي؛ أندريا ريبشيني (2011). "البرمجة الإجرائية التفاعلية مع قيود تدفق البيانات" . وقائع المؤتمر الدولي السادس والعشرين لجمعية الحوسبة الآلية (ACM) حول أنظمة ولغات وتطبيقات البرمجة كائنية التوجه (OOPSLA 2011) . جمعية الحوسبة الآلية (ACM ). الصفحات 407-426 . arXiv : 1104.2293 . doi : 10.1145/2048066.2048100 . ISBN 978-1-4503-0940-0.

[4] يان تشين؛ جوشوا دنفيلد؛ ماثيو أ. هامر؛ أوموت أ. أكار. الحوسبة الضمنية ذاتية التعديل للبرامج الوظيفية البحتة . المؤتمر الدولي للبرمجة الوظيفية 2011. الصفحات 129-141 . مؤرشف من الأصل بتاريخ 30 أكتوبر 2016. تم الاطلاع عليه بتاريخ 12 مارس 2018 .

[5] بايج، روبرت (1981). التمايز الرسمي: تقنية لتوليف البرامج . مطبعة يو إم آي للأبحاث. رقم ISBN 978-0-8357-1213-2.

[6] أحمد، يانيف؛ كينيدي، أوليفر؛ كوخ، كريستوف؛ نيكوليتش، ميلوس (2012-06-01). "DBToaster: معالجة دلتا من الرتبة العليا لعرض ديناميكي ومتجدد باستمرار". وقائع VLDB Endow . 5 (10): 968-979 . arXiv : 1207.0137 . doi : 10.14778/2336664.2336670 . ISSN 2150-8097 .

[7] موغيلان ماريبان؛ كيفال فورا (2019). "GraphBolt: معالجة متزامنة مدفوعة بالتبعية للرسوم البيانية المتدفقة". في المؤتمر الأوروبي لأنظمة الحاسوب (EuroSys'19) . الصفحات 25:1–25:16. doi : 10.1145/3302424.3303974 .

[8] كيمبرلي بيرشيت؛ غريغوري هـ. كوبر؛ شري رام كريشنامورثي (2007). "التخفيض: تقنية تحسين ثابتة للتفاعل الوظيفي الشفاف". في ندوة ACM SIGPLAN حول التقييم الجزئي ومعالجة البرامج القائمة على الدلالات . الصفحات 71-80 . CiteSeerX 10.1.1.90.5866 . ISBN 978-1-59593-620-2.

[HammerAcar2009-9] هامر، ماثيو أ.؛ أكار، أوموت أ.؛ تشين، يان (2009). "CEAL". وقائع مؤتمر ACM SIGPLAN لعام 2009 حول تصميم لغات البرمجة وتنفيذها - PLDI '09 . ص 25. doi : 10.1145/1542476.1542480 . ISBN 9781605583921. S2CID 11058228 .

[RepsTeitelbaum1984-10] ريبس، توماس؛ تيتلبوم، تيم (1984). "مولد المُركِّب". وقائع الندوة الأولى لهندسة البرمجيات ACM SIGSOFT/SIGPLAN حول بيئات تطوير البرمجيات العملية - SDE 1. الصفحات 42-48 . doi : 10.1145/800020.808247 . ISBN 978-0897911313.

[11] "Adapton: تجريدات لغة البرمجة للحساب التزايدي" . adapton.org . تم الاطلاع عليه بتاريخ 7 أكتوبر 2016 .

[SahaRamakrishnan2005-12] ساها، ديبتيكاليان؛ راماكريشنان، سي آر (2005). "التقييم التزايدي لبرولوج الجدولي: ما وراء برامج المنطق البحت". الجوانب العملية للغات التصريحية . سلسلة محاضرات في علوم الحاسوب. المجلد 3819. الصفحات 215-229 . CiteSeerX 10.1.1.111.7484 . doi : 10.1007/11603023_15 . ISBN 978-3-540-30947-5ISSN 0302-9743

[adapton-pldi2014-13] هامر، ماثيو؛ فانغ، خو؛ هيكس، مايكل؛ فوستر، جيفري (2014). ADAPTON: الحوسبة التزايدية القابلة للتركيب والقائمة على الطلب (ملف PDF) . PLDI.

[

[

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]