تحسين الاستدعاء الذيلي (Tail Call Optimization) في Kotlin

بما أن Kotlin لغة متعددة النماذج البرمجية (multi-paradigm)، يمكننا تجنّب استخدام حلقة for واستخدام الاستدعاء الذاتي (recursion) بدلًا منها. في هذه المقالة سأعرض حيلة صغيرة لتطبيق تحسين الاستدعاء الذيلي (TCO) في Kotlin.

تُعرَّف البرمجة الأمرية (Imperative Programming) عادةً بأربعة عناصر:

Sequence, Selection, Iteration, Subroutine

لكن البرمجة الوظيفية (FP) لا تحتوي على مفهومَي Sequence وIteration. فإذا فكّرنا في برنامج لا توجد فيه حلقات تكرار، سنجد أن الأداة الوحيدة المتبقية لنا هي الدالة الاستدعائية. دعوني أكتب دالة استدعائية قصيرة تحسب المضروب (factorial):

fun factorial(num: Double): Double {
        when (num) {
            1.0 ->
                return num
            else ->
                return factorial(num - 1) * num
        }
    }
lang-kotlin

هذا الكود يعمل جيدًا ويعطيكم النتيجة المتوقعة، لكن ماذا لو أخبرتكم أنه قد يسبب لكم مشكلة؟

خطأ StackOverflow

في كل مرة نستدعي فيها دالة، يُنشأ stack frame جديد. لنفترض أنني استدعيت هذه الدالة 50,000 مرة، فسيُنشأ 50,000 frame في الـ stack، وعندما يصل الحجم إلى الحد الأقصى سيظهر هذا الخطأ. إضافة إلى ذلك، فإن أداء هذا الكود سيئ أيضًا.

تحسين الاستدعاء الذيلي

لحل المشكلة، يمكننا تحويل الكود إلى استدعاء ذاتي ذيلي (tail recursion)، أي أن السطر الذي تستدعي فيه الدالة نفسها يجب أن يكون آخر سطر، ويجب ألا تتبعه أي عملية حسابية. على سبيل المثال:

fun myfunc(num : Int = 20): Int {
    if(num == 0){
        return 0
    } else {
        return myfunc()
    }
}
lang-kotlin

الدالة السابقة دالة tail recursion. وإليكم مثالًا آخر ليس tail recursion.

fun notaTailRecursionFunction(num : Int = 20): Int {
        if(num == 0){
            return 0
        } else {
            return notaTailRecursionFunction() + 10
        }
    }
lang-kotlin

الدالة السابقة، رغم أنها تستدعي نفسها في السطر الأخير، ما زالت تجري عملية حسابية (+ 10)، وهذا غير صحيح.

لنحسّن دالة المضروب:

private fun factorial(num: Double): Double {
        return factorial(num, 1.0)
    }

fun factorial(num: Double, result: Double): Double {
        when (num) {
            0.0 ->
                return result
            else ->
                return factorial(num-1, num * result)
        }
    }
lang-kotlin

كل ما فعلته أنني قسمتها إلى دالتين، وتأكدت من أن كلتيهما تتبع مفهوم الـ tail recursion.

هل هذا كل شيء؟ لا. فكما في Scala مع @tailrec، تحتاجون في Kotlin أيضًا إلى تعريف دالة الـ tail recursion باستخدام tailrec syntax، وإلا ستواجهون المشكلة نفسها.

private fun factorial(num: Double): Double {
        return factorial(num, 1.0)
    }

tailrec fun factorial(num: Double, result: Double): Double {
        when (num) {
            0.0 ->
                return result
            else ->
                return factorial(num-1, num * result)
        }
    }
lang-kotlin

لنشغّل البرنامج ونرى الـ stack frame:

إذن، في كل مرة تريدون فيها استخدام الاستدعاء الذاتي، عليكم مراعاة أمرين:

1. اجعلوا الدالة tail recursion
2. ضعوا tailrec قبل تعريف الدالة.

وإذا لم تكن دالتكم tail call ووضعتم tailrec قبلها، فإن Jetbrain IDE ذكي بما يكفي لينبّهكم إلى ذلك. :) المرجع **http://www.hpc-thai.com/?p=172