التكرار المتبادل

الموسوعة الحرة

في الرياضيات وعلوم الحاسوب ، يُعدّ الاستدعاء المتبادل شكلاً من أشكال الاستدعاء حيث يتم تعريف كائنين رياضيين أو حسابيين أو أكثر، مثل الدوال أو أنواع البيانات، بدلالة بعضها البعض. [ 1 ] يُعدّ الاستدعاء المتبادل شائعًا جدًا في البرمجة الوظيفية وفي بعض مجالات المسائل، مثل محللات الانحدار التكراري ، حيث تكون أنواع البيانات متبادلة الاستدعاء بطبيعتها.

أمثلة

أنواع البيانات

أهم مثال أساسي لنوع بيانات يمكن تعريفه بالتكرار المتبادل هو الشجرة ، والتي يمكن تعريفها بشكل تكراري متبادل بدلالة غابة (قائمة من الأشجار). رمزياً:

f: [t[1], ..., t[k]] t: vf

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

يمكن تحويل هذا التعريف المتداخل إلى تعريف متداخل بشكل فردي عن طريق تضمين تعريف الغابة:

t: v [t[1], ..., t[k]]

تتكون الشجرة t من زوج من القيمة v وقائمة من الأشجار (أبنائها). هذا التعريف أكثر إيجازًا، ولكنه أكثر تعقيدًا بعض الشيء: تتكون الشجرة من زوج من نوع واحد وقائمة من نوع آخر، مما يتطلب فصلهما لإثبات النتائج المتعلقة بهما.

في لغة ML القياسية ، يمكن تعريف أنواع بيانات الشجرة والغابة بشكل متكرر متبادل على النحو التالي، مما يسمح بالأشجار الفارغة: [ 2 ]

نوع البيانات 'a tree = فارغ | عقدة من 'a * 'a forest و 'a forest = لا شيء | عقدة من 'a tree * 'a forest

وظائف الحاسوب

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

كما هو الحال مع الدوال التكرارية المباشرة، قد تكون الدالة المُغلِّفة مفيدة، حيث تُعرَّف الدوال التكرارية المتبادلة كدوال متداخلة ضمن نطاقها إذا كان ذلك مدعومًا. يُعد هذا مفيدًا بشكل خاص لمشاركة الحالة بين مجموعة من الدوال دون الحاجة إلى تمرير المعاملات بينها.

أمثلة أساسية

يُعدّ مثالٌ نموذجيٌّ للتكرار المتبادل، وهو مثالٌ اصطناعيٌّ بلا شك، تحديد ما إذا كان عددٌ غير سالبٍ زوجيًّا أم فرديًّا من خلال تعريف دالتين منفصلتين تستدعيان بعضهما البعض، مع إنقاص قيمة كلٍّ منهما بمقدار 1 في كل مرة. [ 3 ] في لغة C:

دالة منطقية is_even ( عدد صحيح غير مُوقّع n ) { إذا كان ( n == 0 ) { أرجع صحيحًا ؛ } وإلا { أرجع is_odd ( n - 1 )؛ } }دالة منطقية is_odd ( عدد صحيح غير مُوقّع n ) { إذا كان ( n == 0 ) { أرجع خطأ ؛ } وإلا { أرجع is_even ( n - 1 )؛ } }

تعتمد هذه الدوال على ملاحظة أن السؤال " هل العدد 4 زوجي؟" يُكافئ السؤال " هل العدد 3 فردي؟" ، والذي بدوره يُكافئ السؤال " هل العدد 2 زوجي؟" ، وهكذا حتى 0. هذا المثال هو استدعاء ذاتي متبادل ، ويمكن استبداله بسهولة بالتكرار. في هذا المثال، تُعدّ الاستدعاءات المتبادلة استدعاءات ذيلية ، وسيكون تحسين الاستدعاءات الذيلية ضروريًا للتنفيذ في مساحة مكدس ثابتة. في لغة C، سيستغرق هذا مساحة مكدس من رتبة O ( n )، ما لم يُعاد كتابته باستخدام القفزات بدلًا من الاستدعاءات. [ 4 ] يمكن اختزال هذا إلى دالة تكرارية واحدة is_even. في هذه الحالة، is_oddستستدعي الدالة، التي يمكن تضمينها، الدالة is_even، ولكنها is_evenستستدعي نفسها فقط.

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

دالة f_tree ( شجرة : شجرة ) -> لا شيء : f_value ( شجرة . قيمة ) f_forest ( شجرة . أبناء )def f_forest ( forest : Forest ) -> None : for tree in forest : f_tree ( tree )

في هذه الحالة، تستدعي دالة الشجرة دالة الغابة عن طريق الاستدعاء الذاتي الفردي، لكن دالة الغابة تستدعي دالة الشجرة عن طريق الاستدعاء الذاتي المتعدد .

باستخدام نوع بيانات Standard ML المذكور أعلاه، يمكن حساب حجم الشجرة (عدد العقد) من خلال الدوال المتكررة المتبادلة التالية: [ 5 ]

دالة حجم_الشجرة فارغة = 0 | حجم_الشجرة ( العقدة (_, f )) = 1 + حجم_الغابة f و حجم_الغابة لا شيء = 0 | حجم_الغابة ( العقدة ( t , f' )) = حجم_الشجرة t + حجم_الغابة f'

مثال أكثر تفصيلاً في لغة Scheme ، لحساب أوراق الشجرة: [ 6 ]

( تعريف ( عدد أوراق الشجرة ) ( إذا ( ورقة؟ شجرة ) 1 ( عدد أوراق الغابة ( أبناء الشجرة ))))( تعريف ( عدد-الأوراق-في- الغابة الغابة ) ( إذا ( الغابة فارغة؟ ) 0 ( + ( عدد-الأوراق ( سيارة الغابة )) ( عدد-الأوراق-في-الغابة ( cdr الغابة )))))

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

أمثلة متقدمة

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

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

هناك أيضًا بعض الخوارزميات التي تحتوي بشكل طبيعي على مرحلتين، مثل minimax (min و max)، والتي يمكن تنفيذها من خلال وجود كل مرحلة في دالة منفصلة مع تكرار متبادل، على الرغم من أنه يمكن أيضًا دمجها في دالة واحدة مع تكرار مباشر.

الدوال الرياضية

في الرياضيات، تعتبر متتاليات هوفستاتر الأنثوية والذكرية مثالاً على زوج من المتتاليات الصحيحة المعرفة بطريقة تكرارية متبادلة.

يمكن حساب الأشكال الكسورية (حتى دقة معينة) باستخدام الدوال التكرارية. ويمكن أحيانًا القيام بذلك بطريقة أكثر أناقة عبر الدوال التكرارية المتبادلة؛ ويُعد منحنى سيربينسكي مثالًا جيدًا على ذلك.

انتشار

يُعدّ الاستدعاء المتبادل شائعًا جدًا في البرمجة الوظيفية ، ويُستخدم غالبًا في البرامج المكتوبة بلغات مثل LISP و Scheme و ML ولغات برمجة مشابهة . على سبيل المثال، يصف أبيلسون وسوسمان كيفية استخدام مُقيِّم دائري فوقي لتنفيذ LISP باستخدام دورة eval-apply. [ 7 ] في لغات مثل Prolog ، يكاد يكون الاستدعاء المتبادل أمرًا لا مفر منه.

تُثني بعض أساليب البرمجة عن استخدام الاستدعاء الذاتي المتبادل، بحجة أنه قد يكون من الصعب التمييز بين الشروط التي تُعيد إجابة والشروط التي تسمح للبرنامج بالعمل إلى ما لا نهاية دون إنتاج إجابة. ويشير بيتر نورفيج إلى نمط تصميم يُثني عن استخدام الاستدعاء الذاتي المتبادل تمامًا، قائلاً: [ 8 ]

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

مصطلحات

يُعرف الاستدعاء المتبادل أيضًا بالاستدعاء غير المباشر ، وذلك على عكس الاستدعاء المباشر حيث تستدعي دالة واحدة نفسها مباشرةً. هذا مجرد اختلاف في التركيز، وليس مفهومًا مختلفًا: يُركز "الاستدعاء غير المباشر" على دالة واحدة، بينما يُركز "الاستدعاء المتبادل" على مجموعة الدوال، ولا يُحدد دالة بعينها. على سبيل المثال، إذا استدعت الدالة f نفسها، فهذا استدعاء مباشر. أما إذا استدعت f الدالة g ، ثم استدعت g الدالة f، التي بدورها استدعت g مرة أخرى، فمن وجهة نظر f وحدها، تكون f في حالة استدعاء غير مباشر، بينما من وجهة نظر g وحدها، تكون g في حالة استدعاء غير مباشر، أما من وجهة نظر كلتيهما، فإن f و g تستدعيان بعضهما البعض. وبالمثل، يمكن تسمية مجموعة من ثلاث دوال أو أكثر تستدعي بعضها البعض بمجموعة من الدوال المستدعاة بشكل متبادل.

التحويل إلى التكرار المباشر

رياضياً، تُعتبر مجموعة الدوال المتكررة المتبادلة دوالاً تكرارية أولية ، ويمكن إثبات ذلك من خلال تكرار مسار القيم ، وبناء دالة واحدة F تسرد قيم الدالة التكرارية الفردية بالترتيب:F=و1(0)،و2(0)،و1(1)،و2(1)،...،{\displaystyle F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),\dots ,}وإعادة كتابة الاستدعاء المتبادل كاستدعاء بدائي.

يمكن تحويل الاستدعاء المتبادل البسيط بين إجراءين إلى استدعاء مباشر عن طريق تضمين شيفرة أحد الإجراءين في الآخر. [ 9 ] إذا كان هناك موقع واحد فقط يستدعي فيه أحد الإجراءين الآخر، فإن هذا الأمر بسيط؛ أما إذا كان هناك عدة مواقع، فقد يتطلب الأمر تكرار الشيفرة. من حيث مكدس الاستدعاءات، ينتج عن إجراءين متبادلين مكدسًا ABABAB...، ويؤدي تضمين B في A إلى الاستدعاء المباشر (AB)(AB)(AB)...

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

انظر أيضاً

مراجع

  1. ↑ مانويل روبيو سانشيز، خايمي أوركيسا فوينتيس، كريستوبال باريخا فلوريس (2002)، "مقدمة لطيفة للتكرار المتبادل"، وقائع المؤتمر السنوي الثالث عشر حول الابتكار والتكنولوجيا في تعليم علوم الحاسوب، 30 يونيو - 2 يوليو 2008، مدريد، إسبانيا.
  2. ↑ هاربر 2000 ، " أنواع التواريخ ".
  3. ↑ Hutton 2007 ، 6.5 التكرار المتبادل ، ص 53-55 .
  4. ↑ " الاستدعاء الذاتي المتبادل " و" الدوال ذات الاستدعاء الذاتي "، دليل تعليمي حول ميزات البرمجة في ATS ، هونغوي شي، 2010
  5. ↑ هاربر 2000 ، " أنواع البيانات ".
  6. ↑ هارفي ورايت 1999 ، V. التجريد: 18. الأشجار: التكرار المتبادل، ص 310-313 .
  7. ↑ أبيلسون، هارولد؛ سوسمان، جيرالد جاي؛ سوسمان، جولي (1996). بنية وتفسير برامج الحاسوب (ملف PDF) . لندن، إنجلترا: مطبعة معهد ماساتشوستس للتكنولوجيا. ص  492. ISBN 978-0262510875.
  8. ↑ حل جميع ألغاز سودوكو
  9. ↑ حول تحويل الاستدعاء غير المباشر إلى الاستدعاء المباشر بواسطة أوين كاسر، سي آر راماكريشنان، وشوناك باواجي في جامعة ولاية نيويورك، ستوني بروك (1993)
  10. ↑ رينولدز، جون (أغسطس 1972). "المترجمات التعريفية للغات البرمجة عالية المستوى" (ملف PDF) . وقائع المؤتمر السنوي لجمعية آلات الحوسبة . بوسطن، ماساتشوستس. الصفحات 717-740 . 
  • هاربر، روبرت (2000)، البرمجة بلغة ستاندرد إم إل
  • هارفي، برايان؛ رايت، ماثيو (1999). سيمبلي سكيم: مدخل إلى علوم الحاسوب . مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0-26208281-5.
  • هاتون، غراهام (2007). البرمجة بلغة هاسكل . مطبعة جامعة كامبريدج. ISBN 978-0-52169269-4.