Кіріспе
Процедураның соңғы әрекеті ретінде орындалатын шақыру Компьютер ғылымында, құйрық шақыру – процедураның соңғы әрекеті ретінде орындалатын кіші бағдарлама шақыруы. Егер құйрықтың мақсаты бірдей кіші бағдарлама болса, онда кіші бағдарлама құйрық рекурсиялық деп аталады, бұл тікелей рекурсияның ерекше жағдайы. Құйрық рекурсиясы (немесе құйрық аяғындағы рекурсия) өте пайдалы және оны жүзеге асыру кезінде оңтайландыру оңай. Құйрық шақырулар шақыру стегіне жаңа стек кадрын қосусыз жүзеге асырылуы мүмкін. Ағымдағы процедураның кадрының көп бөлігі енді қажет емес және оны құйрық шақыруының кадрымен ауыстыруға болады (процестер үшін жабылуға ұқсас, бірақ функция шақырулары үшін). Бағдарлама содан кейін шақырылған кіші бағдарламаға секіреді. Стандартты шақыру тізбегінің орнына мұндай кодты жасау құйрық шақыруын жою немесе құйрық шақыруын оңтайландыру деп аталады. Құйрық шақыруын жою процедуралық шақыруларды құйрық позициясында goto операторлары сияқты тиімді жүзеге асыруға мүмкіндік береді, осылайша тиімді құрылымдалған бағдарламалауға жол ашады. Гай Л. Стилдің сөздерімен айтқанда, "жалпы алғанда, процедуралық шақыруларды параметрлерді беруге мүмкіндік беретін GOTO операторлары ретінде қарастыруға болады және оларды [машиналық код] JUMP нұсқаулары ретінде біркелкі кодтауға болады".
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion (or tail end recursion) is particularly useful, and is often easy to optimize in implementations. Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination or tail call optimization. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements, thus allowing efficient structured programming. In the words of Guy L. Steele, "in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions."
Тарих
1977 жылы Сиэтлде өткен ACM конференциясында Гай Л. Стил GOTO және құрылымдық бағдарламалау туралы пікірталасты сараптап, процедураның соңғы бөлігіндегі процедура шақыруларын шақырылған процедураға тікелей басқаруды беру ретінде қарастырудың тиімді екенін айтты, бұл әдетте қажетсіз стек манипуляцияларын болдырмайды. Мұндай "соңғы шақырулар" Lisp тілінде, процедура шақырулары кең таралғандықтан, процедура шақыруларының құнын басқа іске асырулармен салыстырғанда едәуір төмендететін маңызды оптимизация болып табылады. Стилдің пікірінше, нашар іске асырылған процедура шақырулары GOTO-ның процедура шақыруынан арзан екендігі туралы бұрыс түсінікке әкелді. Сондай-ақ, Стил "жалпы алғанда, процедура шақыруларын параметрлерді беруге мүмкіндік беретін GOTO операторлары ретінде қарастыруға болады және оларды біркелкі түрде [машина коды] JUMP нұсқаулары арқылы кодтауға болады", ал машина кодының стек манипуляциялау нұсқаулары "оптимизация (керісінше емес!)" ретінде қарастырылуы керек деді.
Орындау әдістері
Кейбір жоғары деңгейдегі тілдерде, әсіресе функционалдық және логикалық тілдерде, сондай-ақ Lisp отбасының мүшелерінде құйрық рекурсиясы маңызды. Бұл тілдерде құйрық рекурсиясы итерацияны іске асырудың ең көп қолданылатын (ал кейде жалғыз қолжетімді) тәсілі болып табылады. Scheme тілінің сипаттамасы кезекті шақырулардың стек өлшемін арттырмау үшін оңтайландырылуын талап етеді. Perl тілінде функция атын қабылдайтын "goto" операторының түрі арқылы кезекті шақыруларды тікелей жасауға болады: goto &NAME;
Дегенмен, функция аргументтері мен жергілікті айнымалыларды шақыру стегінде сақтайтын тілдік реализациялар үшін (көптеген тілдер үшін бұл әдепкі реализация, әсіресе аппараттық стекпен жабдықталған жүйелерде, мысалы x86), жалпыланған кезекті шақыруды оңтайландыру (өзара құйрық рекурсияны қоса алғанда) қиындық тудырады: егер шақырылатын функцияның белсендіру жазбасының мөлшері шақырушыдан өзгеше болса, стек кадрын қосымша тазалау немесе қайта өлшеу қажет болуы мүмкін. Мұндай жағдайларда құйрық рекурсиясын оңтайландыру оңай болып қалады, бірақ жалпы кезекті шақыруды тиімді оңтайландыру қиынға түсуі мүмкін. Мысалы, Java виртуалды машинасы (JVM) құйрық рекурсивті шақыруларды жоюға мүмкіндік береді (бұл қолданыстағы шақыру стегін қайта пайдаланады), бірақ жалпы кезекті шақыруларды жоюға болмайды (өйткені бұл шақыру стегін өзгертеді). Осылайша, JVM-ге бағытталған Scala сияқты функционалдық тілдер тікелей құйрық рекурсиясын тиімді іске асыра алады, бірақ өзара құйрық рекурсиясын емес. GCC, LLVM/Clang және Intel компиляторлары C және басқа тілдер үшін жоғары оңтайландыру деңгейлерінде немесе `foptimize sibling calls` опциясы қосылғанда кезекті шақыруды оңтайландырады. Тілдің синтаксисі оны тікелей қолдамаса да, компилятор шақырушы мен шақырылатын функцияның қайтарым түрлерінің сәйкес екенін және екі функцияға берілген аргументтердің түрлері бірдей немесе шақыру стегінде бірдей көлемде сақтау орын алатынын анықтағанда осы оңтайландыруды жасай алады. Оларды іске асырудың әртүрлі әдістері бар.