مكالمات الذيل في البنية دون مكدس المكالمات

Question

إجابتي للحديث سؤال حول Gotos and Tail Recursion كان الصياغة من حيث مكدس المكالمات. أنا قلق من أنه لم يكن عاما كافيا، لذلك أسألك: كيف هي فكرة مكالمة الذيل (أو ما يعادلها) مفيدة في الهندسة دون مكدس مكالمة؟

في مرور الاستمرار، تحل جميع الوظائف المسماة استبدال وظيفة الدعوة، وبالتالي فإن مكالمات الذيل، لذلك لا يبدو أن "مكالمة الذيل" هو تمييز مفيد. في المراسلة والبنية القائمة على الأحداث، لا يبدو أن هناك ما يعادلها، رغم أن من فضلك تصحيح لي إذا كنت مخطئا. الهندسة الأخيرة هي حالات مثيرة للاهتمام كما ترتبط مع OOP، بدلا من FP. ماذا عن البنية الأخرى؟ هل كانت آلات LISP القديمة بناء على مكدسات الاتصال؟

تحرير: وفقا ل "ما هيك هو: الاستمرار النمط النمط (CPS)"(وأليكس أدناه)، أي ما يعادل مكالمة الذيل بموجب استمرار استمرار المرور" يسمى الوظيفة تحل محل وظيفة الاتصال "لكن وظيفة الاتصال يمر في استمرار استمرارها، بدلا من إنشاء استمرار جديد". هذا النوع من مكالمة الذيل مفيدة، على عكس ما أكدته.

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

Answer 1

على فرصة قبالة أن هذا السؤال يهتم شخص آخر غيري، لدي الجواب الموسع للسؤال الآخر يجيب أيضا على هذا واحد. ها هي النسخة البحري غير الصارمة.

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

ترجمة الذيل الدعوة إلى التعامل غير المتزامن للحدث هو أكثر تعقيدا، لذلك بدلا من ذلك النظر في نسخة عامة أكثر. إذا تم الاشتراك في حدث على القناة 1، فإن B مشترك في نفس الحدث على القناة 2 و BR's Handler فقط يطلق الحدث على القناة 1 (يقوم بترجمة الحدث عبر القنوات)، ثم يمكن الاشتراك في الحدث على القناة 2 بدلا من الاشتراك B. هذا هو أكثر عمومية لأن ما يعادل مكالمة الذيل يتطلب ذلك

• يتم إلغاء اشتراك A على القناة 1 عند الاشتراك في القناة 2
• المعالجات إلغاء الاشتراكات الذاتية (عند الاحتجاج، يقومون بإلغاء الاشتراك)

الآن لنظامين لا يقومان بأداء الحسابات الفرعية: Lambda Calculus (أو أنظمة إعادة كتابة الأجل بشكل عام) و RPN. بالنسبة لحساب التفاضل والتكامل Lambda، يتوافق الذيل يتوافق تقريبا مع سلسلة من التخفيضات حيث يكون طول المصطلح O (1) (انظر عمليات تكرارية في SICP القسم 1.2.). خذ RPN لاستخدام مكدس بيانات ومكدسة العمليات (بدلا من دفق العمليات؛ العمليات هي تلك التي لم تتم معالجتها بعد)، وبيئة تقوم بخرائط الرموز على سلسلة من العمليات. يمكن أن تتوافق مكالمات الذيل مع عمليات نمو المكدس O (1).

Answer 2

"البنية دون مكدس مكالمة" عادة "محاكاة" واحد في مستوى في مستوى - على سبيل المثال، مرة أخرى في وقت IBM 360، استخدمنا اتفاقية الربط من النوع S باستخدام مجالات حفظ التسجيل وقوائم الوسائط المشار إليها، من خلال الاتفاقية، من خلال بعض السجلات العامة للأغراض العامة.

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

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