فطيرة Piper

العودية

تكون الدالة عودية عندما تستدعي نفسها.

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

ونتيجة لذلك، قد تستنفد دالة تواصل استدعاء نفسها كل مساحة المكدس في النهاية. ويُسمى هذا تجاوز سعة المكدس.

ولهذا السبب يجب أن تحتوي كل دالة عودية على حالة أساسية واحدة على الأقل، وهي الحالة التي تُرجع فيها الدالة دون أن تستدعي نفسها. ولا بد أن يصل أي استدعاء عودي في النهاية إلى حالة أساسية.

على سبيل المثال، يمكن تعريف دالة المضروب n! = n * (n - 1) * ... * 1 عوديًّا مع 1 كحالة أساسية:

factorial:
    ; the argument `n` is passed on `rdi`
    ; the factorial will be returned on `rax`

    cmp rdi, 1
    jle .base_case     ; base case -> if rdi <= 1, return 1

    push rdi           ; save n
    dec rdi            ; rdi = n - 1
    call factorial     ; recursive call, rax = (n - 1)!
    pop rdi            ; restore n
    imul rax, rdi      ; rax = n * (n - 1)! = n!
    ret
.base_case:
    mov rax, 1
    ret

لاحظ أن factorial يجب أن تنفذ push rdi قبل الاستدعاء العودي و pop rdi بعده. وذلك لأنها ما زالت تحتاج إلى n بعد إرجاع الاستدعاء العودي كي تحسب n * (n-1)!.

لاحظ أيضًا أن استخدام سجل محفوظ من المُستدعى لن يحل هذه المشكلة.

فرغم أن الدالة العودية مُستدعٍ محتمل لنفسها، فهي نفسها مُستدعاة من دالة أخرى. وهذا يعني أنه يجب على الدالة أيضًا أن تحافظ على السجلات المحفوظة من المُستدعى قبل استخدامها، وأن تستعيد قيمتها بعد استخدامها. ويُفعل هذا عادةً بتسلسل من push/pop، كما رأينا في مفهوم سابق.

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

وهذا يعني أن كل استدعاء عودي يضيف 8 بايت إلى المكدس من أجل عنوان العودة الذي يدفعه call، إضافة إلى 8 بايت لكل متغير محلي يحتاج إلى حفظه. وتظل الدالة تضيف هذه البايتات إلى المكدس مع كل إطار حتى تصل إلى حالتها الأساسية. وعندها فقط تبدأ بالتفكيك بالترتيب العكسي، إذ يستخدم كل استدعاء عودي ما يحتاجه من pop ثم ret.

على سبيل المثال، إذا استُدعيت factorial بالوسيط 10، فإنها ستستدعي نفسها تسع مرات قبل أن تصل إلى الحالة الأساسية 1. وعند تلك النقطة، تكون 144 بايت قد استُخدمت لتخزين n (8 بايت) وعنوان العودة (8 بايت) لكل إطار سابق.

الاستدعاء الذيلِي

في بعض الحالات، لا تؤدي الدالة أي عمل إضافي بعد استدعاء دالة أخرى وقبل أن تُرجع.

تأمّل، على سبيل المثال:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    call times_three
    ret

الدالة triple_of_square:

• تضرب الوسيط المُمرَّر (في rdi) في نفسه، فتحصل على مربعه؛
• ثم تستدعي times_three، التي تُرجع ثلاثة مضروبة في الوسيط المُمرَّر.

ونتيجة لذلك، تُرجع triple_of_square القيمة 3*x²، حيث x هو وسيطها المُمرَّر في rdi.

لاحظ أنه لا يُؤدى أي عمل في triple_of_square بعد استدعاء times_three، فالدالة تُرجع فحسب. في حالة كهذه، قد تستخدم الدالة jmp بدلًا من call، فتنقل التنفيذ إلى الدالة المُستدعاة:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    jmp times_three

ويُسمى هذا الاستدعاء الذيلِي.

تتمثل الميزة الأساسية للاستدعاء الذيلِي في تجنّب الكلفة الإضافية لـ call. فـ call يدفع عنوان عودة إلى المكدس، ولكي تعود السيطرة إلى تلك النقطة لا بد من ret يقابله.

والاستدعاء الذيلِي يتخطى الأمرين معًا: فلا يوجد عنوان عودة يُدفع، ولا ret إضافي يقابله، بل ret الدالة المُستدعاة نفسها فحسب.

العودية الذيلية

يكون الاستدعاء الذيلِي مفيدًا بشكل خاص للدوال العودية التي قد تستدعي نفسها مرات كثيرة قبل أن تُرجع.

غير أن ليس كل استدعاء عودي يمكن تحويله مباشرةً إلى استدعاء ذيلِي. فلأن jmp ينقل السيطرة إلى الدالة المُستدعاة، لا يستطيع المُستدعي أداء أي عمل إضافي بعد الاستدعاء الذيلِي.

على سبيل المثال، الدالة factorial السابقة ليست عودية ذيلية. فبعد الاستدعاء العودي، ما زالت بحاجة إلى ضرب النتيجة في قيمة n الحالية، باستخدام imul rax, rdi.

في حالات كهذه، يمكن أحيانًا استخدام مُراكم يجمع الحسابات الجزئية ويُرجَع في النهاية. على سبيل المثال، يمكننا تعريف factorial_helper التي تؤدي معظم العمل، ثم تُهيّئ factorial مُراكمًا وتنقل السيطرة إلى factorial_helper:

factorial_helper:
    ; the argument `n` is passed on `rdi`
    ; `rax` is used as an accumulator and will be returned at the end

    cmp rdi, 1
    jle .base_case

    imul rax, rdi        ; we accumulate the partial result on `rax`
    dec rdi              ; rdi = n - 1
    jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
    ret                  ; returns the factorial already accumulated on `rax`

factorial:
    mov rax, 1           ; initial value for the accumulator
    jmp factorial_helper ; tail call

ولأنه لم يعد يُؤدى أي عمل بعد الاستدعاء العودي، لم نعد بحاجة إلى حفظ rdi أيضًا. فلا يوجد call ولا push rdi، وبالتالي فإن كل دورة عودية تضيف 0 بايت إلى المكدس: أي أنه لا تُستخدم أي مساحة إضافية على المكدس. ويمكن لهذه النسخة التعامل مع أي قيمة كبيرة لـ n دون أن يتجاوز المكدس سعته. وهي أكثر كفاءة وأكثر أمانًا في آن واحد.

في بعض الحالات، وبإعادة ترتيب الدوال، قد نتفادى حتى jmp إلى الدالة المساعدة. على سبيل المثال، يمكن إعادة كتابة factorial و triple_of_square بالطريقة الآتية:

factorial:
    mov rax, 1
factorial_helper:
    cmp rdi, 1
    jle .base_case

    imul rax, rdi
    dec rdi
    jmp factorial_helper
.base_case:
    ret

triple_of_square:
    imul rdi, rdi
times_three:
    imul rax, rdi, 3
    ret

في المقطع أعلاه، ينساب تنفيذ factorial إلى factorial_helper. ويحدث الأمر نفسه مع triple_of_square و times_three. وفي الحالتين، يستمر التنفيذ بالتتابع، ويبدو أن الدالة الذيلية مجرد علامة محلية داخل الدالة "الرئيسية".

في الواقع، لا يوجد فرق جوهري بين أي علامة محلية ودالة. فلغة تجميع x86-64 لا تمنح أيًّا منها معاملة خاصة، فهي مجرد عناوين في مقطع يحوي كودًا قابلًا للتنفيذ، مثل section .text.

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