نداء الذيل

في علوم الحاسوب ، يُعرف الاستدعاء النهائي بأنه استدعاء روتيني فرعي يُنفذ كخطوة أخيرة في إجراء ما. ^{[ 1 ]} إذا كان هدف الاستدعاء النهائي هو نفس الروتين الفرعي، يُقال إن هذا الروتين الفرعي يُسمى استدعاءً نهائيًا ، وهو حالة خاصة من الاستدعاء المباشر . يُعد الاستدعاء النهائي (أو الاستدعاء النهائي ) مفيدًا للغاية، وغالبًا ما يكون من السهل تحسينه في التطبيقات.

يمكن تنفيذ استدعاءات الذيل دون إضافة إطار مكدس جديد إلى مكدس الاستدعاءات . لم يعد معظم إطار الإجراء الحالي مطلوبًا، ويمكن استبداله بإطار استدعاء الذيل، مع تعديله حسب الحاجة (على غرار التراكب في العمليات، ولكن لاستدعاءات الدوال). بعد ذلك، يمكن للبرنامج الانتقال إلى الروتين الفرعي المُستدعى. يُطلق على إنتاج هذا النوع من التعليمات البرمجية بدلًا من تسلسل الاستدعاءات القياسي اسم " حذف استدعاء الذيل" أو "تحسين استدعاء الذيل" . يسمح حذف استدعاء الذيل بتنفيذ استدعاءات الإجراءات في موضع الذيل بكفاءة مماثلة لعبارات goto ، مما يتيح برمجة هيكلية فعالة . وكما قال جاي إل. ستيل : "بشكل عام، يمكن اعتبار استدعاءات الإجراءات بمثابة عبارات GOTO تمرر أيضًا معلمات، ويمكن ترميزها بشكل موحد كتعليمات JUMP [في لغة الآلة]". ^{[ 2 ]}

لا تشترط جميع لغات البرمجة حذف الاستدعاءات الذيلية. مع ذلك، في لغات البرمجة الوظيفية ، غالبًا ما يضمن معيار اللغة حذف الاستدعاءات الذيلية ، مما يسمح للاستدعاءات الذيلية باستخدام مقدار مماثل من الذاكرة لحلقة مكافئة . قد تكون الحالة الخاصة للاستدعاءات الذيلية، عندما تستدعي دالة نفسها، أكثر ملاءمة لحذف الاستدعاءات من الاستدعاءات الذيلية العامة. عندما لا تدعم دلالات اللغة صراحةً الاستدعاءات الذيلية العامة، غالبًا ما يستطيع المترجم تحسين الاستدعاءات الشقيقة ، أو الاستدعاءات الذيلية للدوال التي تأخذ وتعيد نفس أنواع البيانات التي تأخذها الدالة المستدعِية وتعيدها. ^{[ 3 ]}

وصف

عند استدعاء دالة، يجب على الحاسوب "تذكر" موقع الاستدعاء، أي عنوان العودة ، لكي يتمكن من العودة إلى ذلك الموقع مع النتيجة بعد اكتمال الاستدعاء. عادةً، تُحفظ هذه المعلومات في مكدس الاستدعاءات ، وهو قائمة بمواقع العودة مرتبةً حسب ترتيب الوصول إلى مواقع الاستدعاء. بالإضافة إلى ذلك، تُخصص المترجمات ذاكرةً للمتغيرات المحلية للدالة المستدعاة، وتُضيف محتوى السجلات (إن وُجد أو كان ذا صلة) إلى المكدس. يتم ذلك عادةً بتخصيص إطار مكدس يتضمن السجلات المحفوظة، ومساحةً مخصصةً للمتغيرات المحلية غير المسجلة، وعنوان العودة، ومعاملات الاستدعاء (إلا إذا تم تمريرها عبر السجلات). أما بالنسبة للاستدعاءات الطرفية، فلا حاجة لتذكر الدالة المستدعِية أو الاحتفاظ بمحتوى السجلات؛ فبدلاً من ذلك، يتجنب حذف الاستدعاءات الطرفية تخصيص إطارات مكدس جديدة، ويُجري فقط الحد الأدنى من التغييرات الضرورية على إطار المكدس الحالي قبل تمريره، وستعود الدالة المستدعاة طرفيًا مباشرةً إلى الدالة المستدعِية الأصلية . ^{[ ٤ ]} مع ذلك، يؤدي هذا إلى فقدان كامل لإطار مكدس الدالة المستدعِية، وهو ما يُعتبر أحيانًا عائقًا في عملية تصحيح الأخطاء. لا يشترط أن يظهر استدعاء الذيل بعد جميع العبارات الأخرى في الكود المصدري؛ المهم فقط أن تعود الدالة المستدعِية مباشرةً بعد استدعاء الذيل، مع إرجاع نتيجة استدعاء الذيل إن وُجدت، نظرًا لتجاوز الدالة المستدعِية عند إجراء التحسين.

بالنسبة لاستدعاءات الدوال غير التكرارية، يُعدّ هذا عادةً تحسينًا يوفر القليل من الوقت والمساحة، نظرًا لقلة عدد الدوال المتاحة للاستدعاء. أما عند التعامل مع الدوال التكرارية أو التكرارية المتبادلة ، حيث يحدث التكرار من خلال استدعاءات الذيل، فإن مساحة المكدس وعدد عمليات الإرجاع المُوفَّرة قد يصبحان كبيرين جدًا، إذ يمكن للدالة استدعاء نفسها، بشكل مباشر أو غير مباشر، مما يُنشئ إطار مكدس استدعاء جديدًا في كل مرة. غالبًا ما يُقلل حذف استدعاءات الذيل متطلبات مساحة المكدس التقاربية من خطية، أو O (n)، إلى ثابتة، أو O(1). لذا، يُعدّ حذف استدعاءات الذيل شرطًا أساسيًا في التعريفات القياسية لبعض لغات البرمجة، مثل Scheme ، ولغات عائلة ML ، وغيرها. ^{[ 5 ]}^{[ 6 ]} يُضفي تعريف لغة Scheme طابعًا رسميًا على المفهوم البديهي لموقع الذيل بدقة، من خلال تحديد الأشكال النحوية التي تسمح بوجود نتائج في سياق الذيل. ^{[ 7 ]} يمكن أيضًا تسمية التطبيقات التي تسمح بعدد غير محدود من استدعاءات الذيل النشطة في نفس اللحظة، بفضل إزالة استدعاءات الذيل، بأنها "ذات استدعاء ذيل صحيح". ^{[ 5 ]}

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

الشكل النحوي

يمكن تحديد موقع استدعاء الذيل قبل النهاية التركيبية للدالة مباشرة.

int a ( int n ); int b ( int n );int foo ( int data ) { a ( data ); return b ( data ); }

هنا، كلاهما a(data)استدعاءات b(data)، لكن bهو آخر ما ينفذه الإجراء قبل العودة، وبالتالي فهو في موضع الذيل. مع ذلك، ليس بالضرورة أن تقع جميع استدعاءات الذيل في نهاية بنية الروتين الفرعي.

int c ( int n );int bar ( int data ) { if ( a ( data ) > 0 ) { return b ( data ); } return c ( data ); }

هنا، كلا الاستدعاءين لـ bو cموجودان في نهاية الشرط. وذلك لأن كل منهما يقع في نهاية فرع الشرط على التوالي، على الرغم من أن الأول ليس في نهاية barجسم الشرط من الناحية التركيبية.

لنأخذ هذا المثال:

int foo1 ( int data ) { return a ( data ) + 1 ; }int foo2 ( int data ) { int ret = a ( data ); return ret ; }دالة foo3 ( عدد صحيح data ) { عدد صحيح ret = a ( البيانات )؛ إرجاع ( ret == 0 ) ؟ 1 : ret ؛ }

الاستدعاء a(data)موجود في موضع الذيل في foo2، ولكنه ليس في موضع الذيل لا في foo1ولا في foo3، لأنه يجب أن يعود التحكم إلى المستدعي للسماح له بفحص أو تعديل قيمة الإرجاع قبل إرجاعها.

برامج نموذجية

البرنامج التالي هو مثال مكتوب بلغة Scheme : ^{[ 8 ]}

;; المضروب: عدد -> عدد ;; لحساب حاصل ضرب جميع الأعداد الصحيحة الموجبة ;; الأقل من أو تساوي n. ( define ( factorial n ) ( if ( = n 0 ) 1 ( * n ( factorial ( -n 1 ) )))))

لم يُكتب هذا بأسلوب الاستدعاء الذاتي الذيل، لأن دالة الضرب ("*") تقع في موضع الذيل. ويمكن مقارنة ذلك بما يلي:

;; المضروب: عدد -> عدد ;; لحساب حاصل ضرب جميع الأعداد الصحيحة الموجبة ;; الأقل من أو تساوي n. ( define ( factorial n ) ( fact-iter 1 n )) ( define ( fact-iter product n ) ( if ( = n 0 ) product ( fact-iter ( * product n ) ( -n 1 ) )))

يفترض هذا البرنامج تقييمًا بترتيب التطبيقfact-iter . يستدعي الإجراء الداخلي نفسه أخيرًا في مسار التحكم. يسمح هذا للمفسر أو المترجم بإعادة تنظيم التنفيذ الذي عادةً ما يبدو على النحو التالي: ^{[ 8 ]}

 استدعاء مضروب (4) استدعاء مُكرِّر الحقائق (1 4) استدعاء مُكرِّر الحقائق (4 3) استدعاء مُكرِّر الحقائق (12 2) استدعاء مُكرِّر الحقائق (24 1) العودة 24 العودة 24 العودة 24 العودة 24 العودة 24

إلى النسخة الأكثر كفاءة ، من حيث المساحة والوقت:

 استدعاء مضروب (4) استدعاء مُكرِّر الحقائق (1 4) استبدل الوسائط بـ (4 3) استبدل الوسائط بـ (12 2) استبدل الوسائط بـ (24 1) العودة 24 العودة 24

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

يلجأ بعض المبرمجين الذين يعملون بلغات البرمجة الوظيفية إلى إعادة كتابة التعليمات البرمجية التكرارية لتصبح تكرارية ذيلية، وذلك للاستفادة من هذه الميزة. ويتطلب هذا غالبًا إضافة وسيط "مُجمِّع" (كما productفي المثال أعلاه) إلى الدالة.

التكرار الذيل modulo cons

يُعدّ التكرار الذيل modulo cons تعميمًا لتحسين التكرار الذيل، الذي قدمه ديفيد إتش دي وارن ^{[ 9 ]} في سياق ترجمة لغة برولوج ، باعتبارها لغة تُضبط مرة واحدة صراحةً . وقد وصفه (وإن لم يُسمَّ) دانيال ب. فريدمان وديفيد إس. وايز عام 1974 ^[¹⁰^] كتقنية ترجمة للغة ليسب . وكما يوحي الاسم، يُطبَّق هذا الأسلوب عندما تكون العملية الوحيدة المتبقية بعد استدعاء تكراري هي إضافة قيمة معروفة في بداية القائمة المُعادة منه (أو تنفيذ عدد ثابت من عمليات بناء البيانات البسيطة، بشكل عام). وبالتالي، سيكون هذا الاستدعاء استدعاءً ذيليًا باستثناء عملية cons المذكورة (" modulo ") . ولكن إضافة قيمة في بداية القائمة عند الخروج من استدعاء تكراري تُعادل إضافة هذه القيمة في نهاية القائمة المتنامية عند الدخول إلى الاستدعاء التكراري، مما يُنشئ القائمة كأثر جانبي ، كما لو كانت في مُعامل تراكم ضمني. يوضح مقطع برولوج التالي هذا المفهوم:

مثال على التعليمات البرمجية

في لغة برولوج، يتم استخدام الاستدعاء الذاتي الذيل modulo cons: partition ([], _ , [], []). partition ([ X | Xs ], Pivot , [ X | Rest ], Bigs ) :- X @< Pivot , !, partition ( Xs , Pivot , Rest , Bigs ). partition ([ X | Xs ], Pivot , Smalls , [ X | Rest ]) :- partition ( Xs , Pivot , Smalls , Rest ).

في لغة هاسكل، الاستدعاء الذاتي المحمي: partition [] _ = ( [] , [] ) partition ( x : xs ) p | x < p = ( x : a , b ) | otherwise = ( a , x : b ) where ( a , b ) = partition xs p

% برولوج، مع توحيدات صريحة: % ترجمة تكرارية غير ذيلية: partition ([], _ , [], []). partition ( L , Pivot , Smalls , Bigs ) :- L = [ X | Xs ], ( X @< Pivot -> partition ( Xs , Pivot , Rest , Bigs ), Smalls = [ X | Rest ] ; partition ( Xs , Pivot , Smalls , Rest ), Bigs = [ X | Rest ] ).

% برولوج، مع توحيدات صريحة: % ترجمة تكرارية ذيلية: partition ([], _ , [], []). partition ( L , Pivot , Smalls , Bigs ) :- L = [ X | Xs ], ( X @< Pivot -> Smalls = [ X | Rest ], partition ( Xs , Pivot , Rest , Bigs ) ; Bigs = [ X | Rest ], partition ( Xs , Pivot , Smalls , Rest ) ).

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

أمثلة بلغة C

يُعرّف الجزء التالي دالة تكرارية في لغة C تقوم بتكرار قائمة مرتبطة (مع بعض التعليمات البرمجية المكافئة بلغة Scheme و Prolog كتعليقات، للمقارنة):

typedef struct LinkedList { void * value ; struct LinkedList * next ; } LinkedList ;LinkedList * duplicate ( const LinkedList * ls ) { LinkedList * head = NULL ;إذا كانت القائمة ( ls ) موجودة، فسيتم تكرار العنصر التالي منها في القائمة ( ls- > next ) وتخزينه في المتغير head . ثم يتم تعيين قيمة العنصر الحالي في القائمة ( head- >value ) إلى قيمة العنصر الحالي في القائمة ( ls- > value ) ، وتعيين العنصر التالي في القائمة (head- > next ) إلى العنصر التالي في القائمة ( p) . بعد ذلك، يتم إرجاع العنصر الحالي في القائمة (head- > next ) .

في لغة Scheme، ( define ( duplicate ls ) ( if ( not ( null? ls )) ( cons ( car ls ) ( duplicate ( cdr ls ))) ' ()))

%% في لغة برولوج، duplicate ([ X | Xs ], R ):- duplicate ( Xs , Ys ), R = [ X | Ys ]. duplicate ([],[]).

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

void duplicate_aux ( const LinkedList * ls , LinkedList * end ) { if ( ls ) { end- > next = ( LinkedList * ) malloc ( sizeof ( * end )); end- > next- > value = ls- > value ; duplicate_aux ( ls- > next , end- > next ); } else { end- > next = NULL ; } }LinkedList * duplicate ( const LinkedList * ls ) { LinkedList head ;duplicate_aux ( ls , & head ); return head . next ; }

في لغة Scheme، ( define ( duplicate ls ) ( let (( head ( list 1 ))) ( let dup (( ls ls ) ( end head )) ( cond (( not ( null? ls )) ( set-cdr! end ( list ( car ls ))) ( dup ( cdr ls ) ( cdr end ))))) ( cdr head )))

%% في لغة برولوج، duplicate ([ X | Xs ], R ):- R = [ X | Ys ], duplicate ( Xs , Ys ). duplicate ([],[]).

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

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

يمكن الآن تحويل التنفيذ الذيل المتكرر إلى تنفيذ تكراري صريح، كحلقة تراكمية :

LinkedList * duplicate ( const LinkedList * ls ) { LinkedList head ; LinkedList * end ; end = & head ; while ( ls ) { end -> next = ( LinkedList * ) malloc ( sizeof ( * end )); end -> next -> value = ls -> value ; ls = ls -> next ; end = end -> next ; } end -> next = NULL ; return head . next ; }

في لغة Scheme، ( define ( duplicate ls ) ( let (( head ( list 1 ))) ( do (( end head ( cdr end )) ( ls ls ( cdr ls ))) (( null? ls ) ( cdr head )) ( set-cdr! end ( list ( car ls ))))))

%% في لغة برولوج، %% غير متوفر

تاريخ

في ورقة بحثية قُدّمت في مؤتمر ACM في سياتل عام 1977، لخّص جاي إل. ستيل النقاش الدائر حول عبارة GOTO والبرمجة الهيكلية ، ولاحظ أن استدعاءات الإجراءات في نهاية مسار الإجراء يُمكن التعامل معها على أفضل وجه باعتبارها نقلًا مباشرًا للتحكم إلى الإجراء المُستدعى، مما يُلغي عادةً عمليات معالجة المكدس غير الضرورية. ^{[ 2 ]} ونظرًا لشيوع هذه "الاستدعاءات في نهاية المسار" في لغة Lisp ، وهي لغة تكثر فيها استدعاءات الإجراءات، فإن هذا النوع من التحسين يُقلل بشكل كبير من تكلفة استدعاء الإجراء مقارنةً بالتطبيقات الأخرى. جادل ستيل بأن استدعاءات الإجراءات سيئة التنفيذ قد أدت إلى تصور خاطئ بأن عبارة GOTO رخيصة مقارنةً باستدعاء الإجراء. كما جادل ستيل أيضًا بأنه "بشكل عام، يُمكن اعتبار استدعاءات الإجراءات بمثابة عبارات GOTO تُمرر أيضًا مُعاملات، ويُمكن ترميزها بشكل موحد كتعليمات JUMP [في لغة الآلة]"، مع اعتبار تعليمات معالجة المكدس في لغة الآلة "تحسينًا (وليس العكس!)". ^{[ ٢ ]} استشهد ستيل بأدلة تُشير إلى أن الخوارزميات العددية المُحسَّنة جيدًا في لغة ليسب يُمكن تنفيذها بسرعة أكبر من الشيفرة التي تُنتجها مُترجمات فورتران التجارية المُتاحة آنذاك، وذلك لأن تكلفة استدعاء الإجراء في ليسب كانت أقل بكثير. في لغة سكيم ، وهي لهجة من ليسب طوّرها ستيل بالتعاون مع جيرالد جاي سوسمان ، يُضمن تنفيذ حذف الاستدعاءات غير الضرورية في أي مُفسِّر. ^{[ ١١ ]}

أساليب التنفيذ

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

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

على سبيل المثال، في آلة جافا الافتراضية (JVM)، يمكن حذف الاستدعاءات التكرارية الذيلية (لأنها تعيد استخدام مكدس الاستدعاءات الحالي)، ولكن لا يمكن حذف الاستدعاءات التكرارية الذيلية العامة (لأنها تُغير مكدس الاستدعاءات). ^{[ 13 ]}^{[ 14 ]} ونتيجةً لذلك، تستطيع اللغات الوظيفية مثل سكالا، التي تستهدف JVM، تنفيذ التكرار الذيلي المباشر بكفاءة، ولكن ليس التكرار الذيلي المتبادل.

تُجري مجموعات مُترجمات GCC و LLVM / Clang و Intel تحسينًا لاستدعاءات الدوال في نهاية الاستدعاءات للغة C وغيرها من اللغات عند مستويات التحسين العالية أو عند -foptimize-sibling-callsتمرير الخيار. ^{[ 15 ]}^{[ 16 ]}^{[ 17 ]} على الرغم من أن بنية اللغة المُعطاة قد لا تدعم ذلك صراحةً، إلا أن المُترجم يُمكنه إجراء هذا التحسين متى ما استطاع تحديد أن أنواع الإرجاع للدالة المُستدعية والدالة المُستدعاة مُتكافئة، وأن أنواع الوسائط المُمررة إلى كلتا الدالتين إما مُتماثلة، أو تتطلب نفس القدر من مساحة التخزين الإجمالية على مكدس الاستدعاءات. ^{[ 18 ]}

تتوفر طرق تنفيذ متنوعة.

أثناء التجميع

غالبًا ما تُحسّن المفسرات والمترجمات للغات البرمجة الوظيفية والمنطقية استدعاءات الذيل لتحقيق أشكال أكثر كفاءة من التكرار . على سبيل المثال، يُعبّر مبرمجو لغة Scheme عادةً عن حلقات while باستدعاءات لإجراءات في موضع الذيل ، ويعتمدون على مترجم أو مفسر Scheme لاستبدال استدعاءات الذيل بتعليمات قفز أكثر كفاءة . ^[¹⁹^]

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

foo: call baz call bar ret

يؤدي حذف استدعاء الذيل إلى استبدال السطرين الأخيرين بتعليمات قفز واحدة:

foo: call baz jmp bar

بعد barاكتمال الروتين الفرعي، سيعود مباشرة إلى عنوان الإرجاع الخاص بـ foo، متجاهلاً retالعبارة غير الضرورية.

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

int foo ( int a , int b ) { baz ( a ); return bar ( b ); }

حيث أن aو bهما معلمات، فقد يترجم المترجم ذلك على النحو التالي: ^{[ ج ]}

foo:mov reg ,[ sp + a ] ; جلب a من معلمة المكدس (sp) إلى سجل مؤقت.push reg ; ضع a على المكدس حيث يتوقع baz ذلكاتصل بـ باز ؛ يستخدم بازpop ; إزالة عنصر من المكدسmov reg ,[ sp + b ] ; جلب b من معلمة المكدس (sp) إلى سجل مؤقت.push reg ; ضع b في المكدس حيث يتوقعه barشريط الاتصال ؛ يستخدم أ بpop ; إزالة b من المكدس.ريت

يمكن لمُحسِّن استدعاء الذيل بعد ذلك تغيير الكود إلى:

foo:mov reg ,[ sp + a ] ; جلب البيانات data1 من معلمة المكدس (sp) إلى سجل مؤقت.push reg ; ضع a على المكدس حيث يتوقع baz ذلكاتصل بـ باز ؛ يستخدم بازpop ; إزالة عنصر من المكدسmov reg ,[ sp + b ] ; جلب b من معلمة المكدس (sp) إلى سجل مؤقت.mov [ sp + a ], reg ; ضع b في المكان الذي يتوقعه barjmp bar ; يستخدم bar b ويعود فوراً إلى المُستدعي.

هذا الكود أكثر كفاءة من حيث سرعة التنفيذ واستخدام مساحة المكدس.

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

دالة foo ( عدد صحيح x ) { إذا كانت البيانات تساوي 0 ، فأرجع البيانات ؛ } أرجع foo ( البيانات - 1 ) ؛ }

يقوم المترجم غير المُحسَّن بترجمة هذا إلى تسلسل استدعاء قياسي، حيث يدفع إطارًا جديدًا إلى المكدس لكل استدعاء متكرر:

foo: mov reg ,[ sp + x ] ; جلب البيانات من مُعامل المكدس cmp reg , 0 ; التحقق من الحالة الأساسية je end dec reg ; تعديل x push reg ; دفع x الجديد إلى المكدس للاستدعاء التالي call foo ; استدعاء متكرر (يزيد حجم المكدس) pop ; تنظيف المكدس بعد الإرجاع end: ret

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

foo: mov reg ,[ sp + x ] ; جلب x من مُعامل المكدس cmp reg , 0 ; التحقق من الحالة الأساسية je end dec reg ; تعديل x mov [ sp + x ], reg ; تحديث مُعامل المكدس الحالي بشكل مُدمر jmp foo ; القفز مُباشرةً إلى البداية (يبقى المكدس محدودًا) end: ret

هذا الكود المُحسَّن مطابقٌ فعليًا لحلقة تنفيذية حتمية while، حيث يتم تنفيذه بذاكرة محدودة بدقة وبأقصى سرعة.

تعقيد الأجهزة والمساحة

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

العلاقة بالروتينات الفرعية

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

من خلال الترامبولين

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

من الممكن تنفيذ الترامبولين باستخدام وظائف من الدرجة العليا في اللغات التي تدعمها، مثل Groovy و Visual Basic .NET و C# . ^{[ 20 ]}

يُعدّ استخدام الترامبولين لجميع استدعاءات الدوال أكثر تكلفةً من استدعاء دالة C العادية، لذا يستخدم مُصرّف Scheme واحد على الأقل، وهو Chicken ، تقنيةً وصفها هنري بيكر لأول مرة بناءً على اقتراح غير منشور من أندرو أبيل ^{[ 21 ]} ، حيث تُستخدم استدعاءات C العادية، ولكن يتم التحقق من حجم المكدس قبل كل استدعاء. عندما يصل المكدس إلى أقصى حجم مسموح به، تُجمع الكائنات الموجودة عليه باستخدام خوارزمية تشيني عن طريق نقل جميع البيانات النشطة إلى كومة منفصلة. بعد ذلك، يُعاد ترتيب المكدس ("يُسحب منه البيانات")، ويستأنف البرنامج من الحالة المحفوظة قبل عملية جمع البيانات المهملة. يقول بيكر: "تتجنب طريقة أبيل القيام بعدد كبير من القفزات الصغيرة على الترامبولين عن طريق القفز من مبنى إمباير ستيت من حين لآخر." ^{[ 21 ]} يضمن جمع البيانات المهملة استمرار الاستدعاء الذاتي المتبادل إلى أجل غير مسمى. ومع ذلك، يتطلب هذا النهج ألا تعود أي دالة C أبدًا، لأنه لا يوجد ضمان بأن إطار مكدس الدالة المستدعِية لا يزال موجودًا. لذلك، ينطوي الأمر على إعادة كتابة داخلية أكثر جذرية لرمز البرنامج: أسلوب تمرير الاستمرارية .

العلاقة `while`بالبيان

يمكن ربط الاستدعاء الذيل بعبارة while ، وهي تكرار صريح، على سبيل المثال عن طريق التحويل.

الإجراء foo( x ) إذا كان p ( x ) فأرجع bar( x ) وإلا فأرجع foo(baz( x ))

داخل

الإجراء foo( x ) طالما أن p ( x ) صحيح ، أرجع bar( x )، وإلا x ← baz( x )

حيث قد يكون x عبارة عن مجموعة تتضمن أكثر من متغير واحد: في هذه الحالة، يجب توخي الحذر عند تنفيذ عبارة الإسناد x ← baz( x ) لضمان مراعاة التبعيات. قد يلزم إدخال متغيرات مساعدة أو استخدام بنية تبديل .

وبشكل عام،

الإجراء foo( x ) إذا كان p ( x ) يُرجع bar( x ) وإلا إذا كان q ( x ) يُرجع baz( x ) ... وإلا إذا كان r ( x ) فإنك تُرجع foo(qux( x )) ... وإلا، فأرجع foo(quux( x ))

يمكن تحويلها إلى

الإجراء foo( x ) طالما أن p ( x ) صحيح ، أرجع bar( x )، وإلا إذا كان q ( x ) صحيحًا ، أرجع baz( x ). ... وإلا إذا كان r ( x ) x ← qux( x ) ... وإلا x ← quux( x )

على سبيل المثال، يقدم برنامج جوليا هذا تعريفًا تكراريًا غير ذيلي factorialللمضروب:

دالة حساب المضروب ( ن :: عدد صحيح ) :: عدد صحيحإذا كان n == 0إرجاع 1آخرأرجع n * مضروب ( n - 1 )نهايةنهاية

في الواقع، n * factorial(n - 1)يغلف استدعاء الدالة factorial. ولكن يمكن تحويله إلى تعريف تكراري ذيلي عن طريق إضافة وسيط aيسمى المُجمِّع . ^{[ 8 ]}

يقدم برنامج جوليا هذا تعريفًا تكراريًا ذيليًا factorialللمضروب:

دالة حساب المضروب ( n :: عدد صحيح ، a :: عدد صحيح ) :: عدد صحيح إذا كان n == 0 : أرجع a وإلا أرجع المضروب ( n - 1 ، n * a ) نهاية نهايةدالة حساب المضروب ( n :: عدد صحيح ) :: عدد صحيح تُرجع المضروب ( n ، 1 ) نهاية

يقدم برنامج جوليا هذا تعريفًا تكراريًا fact_iterللمضروب:

دالة fact_iter ( n :: عدد صحيح ، a :: عدد صحيح ) :: عدد صحيح طالما n > 0 a = n * a n = n - 1 نهاية إرجاع a نهايةدالة حساب المضروب ( n :: عدد صحيح ) :: عدد صحيح تُرجع fact_iter ( n , one ( n )) نهاية

الدعم اللغوي

كلوجر – لكلوجر recurشكل خاص. ^{[ 22 ]}
لغة Common Lisp – تقوم بعض التطبيقات بتحسين استدعاءات الدوال أثناء عملية الترجمة إذا كان الهدف هو تحسين السرعة
Elixir – Elixir تنفذ تحسين استدعاء الذيل، ^{[ 23 ]} كما تفعل جميع اللغات التي تستهدف حاليًا BEAM VM.
إلم – نعم ^{[ 24 ]}
إرلانغ - نعم
F# – F# تنفذ TCO افتراضيًا حيثما أمكن ^{[ 25 ]}
انطلق – لا يوجد دعم ^{[ 26 ]}
هاسكل – نعم ^{[ 27 ]}
يجب أن تدعم محركات JavaScript المتوافقة مع معيار ECMAScript 6.0 استدعاءات الذيل ^{[ 28 ]} ، وهو ما تم تنفيذه بالفعل في Safari / WebKit ^{[ 29 ]،} ولكنه مرفوض من قبل V8 وSpiderMonkey.
كوتلين – تحتوي على tailrecمُعدِّل للدوال ^{[ 30 ]}
Lua – يتطلب تعريف اللغة التكرار الذيل ^{[ 31 ]}
Objective-C – يقوم المترجم بتحسين استدعاءات الذيل عند تحديد الخيار -O1 (أو أعلى)، ولكن من السهل إزعاجه بالاستدعاءات المضافة بواسطة العد المرجعي التلقائي .
OCaml – نعم. منذ الإصدار 4.03.0، ^[³²^] يمكن استخدام السمة المضمنة للتحقق من تحسين الاستدعاء، مع إصدار تحذير في حال عدم التحسين. ^[³³^]tailcall
بيرل – صريح مع صيغة مختلفة من عبارة "goto" التي تأخذ اسم دالة: goto &NAME;^{[ 34 ]}
برولوج – SWI-Prolog تنفذ تحسين التكرار الذيل. ^{[ 35 ]}
بيور سكريبت - نعم
بايثون – لا تُجري تطبيقات بايثون الافتراضية تحسينًا لاستدعاءات الذيل، على الرغم من توفر وحدة خارجية للقيام بذلك. ^{[ 36 ]} جادل مخترع اللغة، غيدو فان روسوم، بأن حذف استدعاءات الذيل يُغيّر مسارات المكدس ، مما يُصعّب عملية تصحيح الأخطاء، وفضّل أن يستخدم المبرمجون التكرار الصريح بدلاً من ذلك. ^{[ 37 ]} في بايثون 3.14، تم تقديم مُفسّر جديد يستخدم إرسالًا قائمًا على استدعاءات الذيل لرموز بايثون. ^{[ 38 ]} وقد أدى ذلك إلى تحسين الأداء بشكل عام مقارنةً ببايثون 3.13. ^{[ 39 ]}^{[ 40 ]}
R – نعم، tailcall()تم تقديم هذه الوظيفة في R.4.4.0 ^{[ 41 ]}
المضرب – نعم ^{[ 42 ]}
روبي - نعم، ولكنها معطلة افتراضياً ^{[ 43 ]}
Rust – يمكن إجراء تحسين استدعاء الذيل في ظروف محدودة، ولكنه ليس مضمونًا ^{[ 44 ]}
سكالا – يتم تحسين الدوال ذات الاستدعاء الذاتي النهائي تلقائيًا بواسطة المُصرّف. ويمكن أيضًا تمييز هذه الدوال اختياريًا بتعليق @tailrecتوضيحي، مما يجعل عدم كونها ذات استدعاء ذاتي نهائي خطأً في عملية التجميع ^{[ 45 ].}
المخطط – مطلوب بموجب تعريف اللغة ^{[ 46 ]}^{[ 47 ]}
سويفت – في بعض الحالات. ^{[ 48 ]}
Tcl – منذ Tcl 8.6، أصبح لدى Tcl tailcallأمر ^{[ 49 ]}
زيج – نعم ^{[ 50 ]}

انظر أيضاً

ملحوظات

↑ مثل هذا:

إذا كان ( ls ) { head = ( LinkedList * ) malloc ( sizeof ( * head )); head- > value = ls- > value ; head- > next = duplicate ( ls- > next ); }