टेल कॉल

From Vigyanwiki

कंप्यूटर विज्ञान में, टेल कॉल एक कॉल प्रक्रिया है जो किसी प्रक्रिया की अंतिम क्रिया के रूप में की जाती है।[1] यदि किसी टेल कॉल का लक्ष्य एक ही प्रक्रिया है, तो प्रक्रिया को टेल कॉल रिकर्सन कहा जाता है, जो प्रत्यक्ष रिकर्सन (कंप्यूटर विज्ञान) की एक विशेष स्थिति है। टेल रिकर्सन या टेल कॉल रिकर्सन विशेष रूप से उपयोगी है और इससे कार्यान्वयन में अनुकूलन करना प्रायः आसान होता है।

टेल कॉल को कॉल स्टैक में नया स्टैक फ़्रेम जोड़ने के अतिरिक्त प्रयुक्त किया जा सकता है। वर्तमान प्रक्रिया के अधिकांश फ़्रेम की अब आवश्यकता नहीं है और इसे टेल कॉल के फ़्रेम द्वारा प्रतिस्थापित किया जा सकता है, जिसे उपयुक्त के रूप में संशोधित किया जा सकता है प्रक्रियाओं के लिए ओवरले के समान, लेकिन फ़ंक्शन कॉल के लिए पुनः प्रोग्राम को तथाकथित प्रक्रिया पर जा सकता है। मानक कॉल अनुक्रम के अतिरिक्त ऐसे कोड को उत्पादन टेल-कॉल उन्मूलन या टेल-कॉल अनुकूलन कहा जाता है। टेल-कॉल उन्मूलन टेल स्थिति में प्रक्रिया कॉल को GOTO स्टेटमेंट के रूप में कुशलतापूर्वक कार्यान्वित करने की स्वीकृति देता है, इस प्रकार कुशल संरचित प्रोग्रामिंग की स्वीकृति देता है। गाइ एल. स्टील के शब्दों में सामान्यतः प्रक्रिया कॉल को उपयोगी रूप से GOTOस्टेटमेंट के रूप में माना जा सकता है जो पैरामीटर भी पास करते हैं और समान रूप से मशीन कोड JUMP निर्देशों के रूप में कोडित किया जा सकता है।[2]

सभी प्रोग्रामिंग भाषाओं को टेल-कॉल उन्मूलन की आवश्यकता नहीं होती है। हालाँकि, कार्यात्मक प्रोग्रामिंग भाषाओं में टेल-कॉल उन्मूलन का दायित्व प्रायः भाषा मानक द्वारा किया जाता है, जिससे टेल रिकर्सन को समतुल्य लूप (कंप्यूटिंग) की समान मात्रा में मेमोरी का उपयोग करने की स्वीकृति प्राप्त होती है। टेल-रिकर्सिव कॉल की विशेष स्थिति मे जब कोई फ़ंक्शन स्वयं कॉल करता है, तो सामान्य टेल कॉल की तुलना में एलिमिनेशन को कॉल करने के लिए अधिक उत्तरदायी हो सकता है। जब भाषा कोड स्पष्ट रूप से सामान्य टेल कॉल का समर्थन नहीं करता है, तो कंपाइलर प्रायः सिबलिंग कॉल या टेल कॉल को ऐसे फ़ंक्शंन में प्रयुक्त कर सकता है जो कॉल के समान प्रकार के कोड को वापस करते हैं।[3]

विवरण

जब किसी फ़ंक्शन को कॉल किया जाता है, तो कंप्यूटर को उस स्थान और वापसी एड्रेस को "याद" रखना चाहिए, ताकि कॉल पूरा होने के बाद वह परिणाम के साथ उस स्थान पर वापस आ सके। सामान्यतः यह जानकारी कॉल स्टैक पर साझा की जाती है, जो उनके द्वारा वर्णित कॉल स्थानों पर अभिगमन के समय के क्रम में वापसी स्थानों की एक सरल सूची है। टेल कॉल के लिए कॉल को याद रखने की कोई आवश्यकता नहीं होती है। इसके अतिरिक्त टेल-कॉल एलिमिनेशन इसे पास करने से पहले स्टैक फ्रेम में केवल न्यूनतम आवश्यक परिवर्तन करता है[4] और टेल-कॉल फ़ंक्शन प्रत्यक्ष मूल कॉल पर वापस आ जाता है। स्रोत कोड में अन्य सभी स्टेटमेंट के बाद टेल कॉल को शाब्दिक रूप से प्रकट होने की आवश्यकता नहीं होती है। केवल यह महत्वपूर्ण है कि कॉलिंग फ़ंक्शन टेल कॉल के शीघ्र बाद टेल कॉल के परिणाम को वापस कर दे, यदि कोई हो तो, क्योंकि अनुकूलन किए जाने पर कॉलिंग फ़ंक्शन को नष्ट कर दिया जाता है।

गैर-रिकर्सिव कॉल फ़ंक्शन के लिए यह सामान्यतः एक अनुकूलन है जो केवल अपेक्षाकृत समय और स्थान को सुरक्षित करता है क्योंकि कॉल करने के लिए कई अलग-अलग फ़ंक्शन उपलब्ध नहीं हैं। रिकर्सिव या पारस्परिक रूप से रिकर्सिव फ़ंक्शन के समय जहां रिकर्सन टेल कॉल के माध्यम से होता है। हालांकि स्टैक स्पेस और सहेजे गए रिटर्न टेल कॉल की संख्या बहुत महत्वपूर्ण हो सकती है क्योंकि एक फ़ंक्शन स्वयं को प्रत्यक्ष या अप्रत्यक्ष रूप से कॉल कर सकता है, जिससे एक नया कॉल स्टैक फ्रेम बन सकता है। टेल-कॉल उन्मूलन प्रायः अनंतस्पर्शी स्टैक स्पेस आवश्यकताओं को रैखिक O(n) या O(1) तक कम कर देता है। इस प्रकार कुछ प्रोग्रामिंग भाषाओं की मानक परिभाषाओं के लिए टेल-कॉल उन्मूलन की आवश्यकता होती है, जैसे स्कीम[5][6] और एमएल (प्रोग्रामिंग भाषा) समूह की भाषाएं स्कीम भाषा की परिभाषा तर्क की स्थिति की सहज धारणा को शुद्ध रूप से औपचारिक बनाती है। यह निर्दिष्ट करके कि कौन से वाक्यात्मक तर्क के संदर्भ में परिणाम प्राप्त करने की स्वीकृति देते हैं। टेल-कॉल उन्मूलन के कारण एक ही समय में असीमित संख्या में टेल कॉल को सक्रिय करने की स्वीकृति देने वाले कार्यान्वयन को 'उपयुक्त रूप से टेल रिकर्सिव' भी कहा जा सकता है।[5]

एड्रेस और निष्पादन दक्षता के अतिरिक्त टेल-कॉल उन्मूलन कार्यात्मक प्रोग्रामिंग में महत्वपूर्ण है जिसे निरंतरता-पासिंग शैली (सीपीएस) के रूप में जाना जाता है, जो शीघ्र ही स्टैक एड्रेस से बाहर हो जाती है।

वाक्यविन्यास रूप

किसी फ़ंक्शन के वाक्यात्मक अंत से ठीक पहले एक टेल कॉल स्थित हो सकती है: 

function foo(data) {
    a(data);
    return b(data);
}

यहां a(data) और b(data) दोनों कॉल हैं, लेकिन b अंतिम डेटा है जिसे प्रक्रिया लौटने से पहले निष्पादित करती है और इस प्रकार तर्क की स्थिति में होती है। हालाँकि सभी टेल कॉल आवश्यक रूप से प्रक्रिया के वाक्यात्मक अंत में स्थित नहीं होते हैं: 

function bar(data) {
    if ( a(data) ) {
        return b(data);
    }
    return c(data);
}

यहां, b और cदोनों कॉल टेल स्थिति में हैं। ऐसा इसलिए है क्योंकि उनमें से प्रत्येक क्रमशः if-शाखा के अंत में स्थित है, इस कोड में पहला bar एल्गोरिथम के अंत में वाक्यात्मक रूप से नहीं है:

function foo1(data) {
    return a(data) + 1;
}

function foo2(data) {
    var ret = a(data);
    return ret;
}

function foo3(data) {
    var ret = a(data);
    return (ret == 0) ? 1 : ret;
}

यहाँ पर a(data) कॉल foo2 में टेल कॉल स्थिति में है, लेकिन यह foo1 या foo3 में टेल कॉल स्थिति में नहीं है क्योंकि कॉल करने वाले फंक्शन को वापस लौटने से पहले पुनः प्राप्त मान का निरीक्षण या संशोधित करने की स्वीकृति देने के लिए नियंत्रण को वापस लौटना होता है।

उदाहरण: फंक्शन

निम्नलिखित प्रोग्राम स्कीम प्रोग्रामिंग भाषा का एक उदाहरण है:[7] 

;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to n.
(define (factorial n)
 (if (= n 0)
    1
    (* n (factorial (- n 1)))))

यह टेल-रिकर्सिव शैली में नहीं लिखा गया है, क्योंकि गुणन फ़ंक्शन ( * ) टेल की स्थिति में है। इसकी तुलना निम्न से की जा सकती है: 

;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to 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 स्वयं को नियंत्रण डेटा में अंतिम कहता है। यह एक इंटरप्रेटर या संकलक को निष्पादन को पुनर्गठित करने की स्वीकृति देता है जो सामान्यतः इस प्रकार प्रदर्शित होता है:[7] 

call factorial (4)
  call fact-iter (1 4)
  call fact-iter (4 3)
   call fact-iter (12 2)
   call fact-iter (24 1)
   return 24
   return 24
  return 24
  return 24
 return 24

एड्रेस और समय दोनों के संदर्भ में अधिक एल्गोरिथम दक्षता संस्करण: 

 call factorial (4)
call fact-iter (1 4)
  replace arguments with (4 3)
  replace arguments with (12 2)
  replace arguments with (24 1)
  return 24
 return 24

यह पुनर्गठन भंडारण को बचाता है क्योंकि कॉल फ़ंक्शन के एड्रेस को छोड़कर किसी भी स्थिति को स्टैक या हीप पर साझा करने की आवश्यकता नहीं होती है और fact-iter के लिए कॉल स्टैक फ्रेम को मध्यवर्ती परिणाम भंडारण के लिए पुन: उपयोग किया जाता है। इसका तात्पर्य यह भी है कि प्रोग्रामर को अत्यधिक रिकर्सन के लिए स्टैक या हीप भंडारण नष्ट होने के विषय में चिंता करने की आवश्यकता नहीं होती है। विशिष्ट कार्यान्वयन में टेल-रिकर्सिव फ़ंक्शन अन्य फ़ंक्शन की तुलना में एक स्थिर फ़ंक्शन द्वारा अपेक्षाकृत तीव्र होता है।

कार्यात्मक भाषाओं में कार्य करने वाले कुछ प्रोग्रामर रिकर्सिव होने के लिए रिकर्सिव कोड को फिर से लिखेंगे ताकि वे इस सुविधा का लाभ प्राप्त कर सकें। इसके लिए प्रायः एक संचायक तर्क जोड़ने की आवश्यकता होती है (product उपरोक्त उदाहरण में) फ़ंक्शन के लिए कुछ स्थितियों में (जैसे फ़िल्टरिंग सूचियां) और कुछ भाषाओं में पूर्ण तर्क रिकर्सन के लिए एक फ़ंक्शन की आवश्यकता हो सकती है जो पहले लिखने के लिए पूरी तरह कार्यात्मक थी ताकि इनसे अन्य वेरिएबल में संग्रहीत संदर्भों को परिवर्तित किया आ सकता है।[citation needed]

टेल रिकर्सन मॉड्यूल कॉन्स

टेल रिकर्सन मोडुलो कॉन्स प्रोलॉग के संकलन के संदर्भ में डेविड एच. डी. वॉरेन[8] द्वारा प्रारम्भ की गई टेल-रिकर्सन अनुकूलीकरण का एक सामान्यीकरण है, जिसे स्पष्ट रूप से एक बार प्रयुक्त की गई भाषा के रूप में देखा जाता है। इसे 1974 में डैनियल पी. फ्रीडमैन और डेविड एस. वाइज द्वारा एक एलआईएसपी संकलन तकनीक के रूप में वर्णित किया गया था। हालांकि इसका कोई नाम नहीं दिया गया था जैसा कि नाम से पता चलता है, यह तब प्रयुक्त होता है जब रिकर्सिव कॉल के बाद निष्पादित करने के लिए एकमात्र संचालन उससे लौटाई गई सूची के सामने एक ज्ञात मान जोड़ना होता है या सामान्य रूप से सरल डेटा-निर्माण कार्यों की निरंतर संख्या निष्पादित करना होता है। इस प्रकार यह कॉल उक्त कॉन्स संचालन ("मॉड्यूलो") के लिए एक टेल कॉल होती है लेकिन रिकर्सिव कॉल से बाहर निकलने पर किसी सूची के प्रारम्भ में एक मान उपसर्ग लगाना, रिकर्सिव कॉल में प्रवेश पर बढ़ती सूची के अंत में इस मान को जोड़ने के समान है। इस प्रकार सूची को एक अन्य प्रभाव के रूप में बनाना, जैसे कि एक में अंतर्निहित संचायक पैरामीटर निम्नलिखित प्रोलॉग विभाजन इस अवधारणा को दर्शाता है:

उदाहरण कोड

% Prolog, tail recursive 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).

-- In Haskell, guarded recursion:
partition [] _ = ([],[])
partition (x:xs) p 
        | x < p     = (x:a,b)
        | otherwise = (a,x:b)
   where
      (a,b) = partition xs p

% Prolog, with explicit unifications:
%     non-tail recursive translation:
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]
 ).

% Prolog, with explicit unifications:
%     tail-recursive translation:
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 सूची को तर्क के रूप में टेल कॉल करके रिकर्सिव रूप से भरा जाता है। वही प्रभाव तब प्राप्त होता है जब रिकर्सन को एक वास्तविक मूल्यांकन किए गए डेटा निर्माता के अंतर्गत संरक्षित किया जाता है, जो हास्केल जैसी लैज़िली प्रोग्रामिंग भाषाओं में स्वचालित रूप से प्राप्त होता है।

सी प्रोग्रामिंग के उदाहरण

निम्नलिखित खंड सी प्रोग्रामिंग में एक रिकर्सिव फ़ंक्शन को परिभाषित करता है जो तुलना के लिए टिप्पणियों के रूप में कुछ समकक्ष योजना और प्रोलॉग कोड के साथ एक लिंक की गई सूची को प्रतिलिपित करता है: 

typedef struct list {
    void *value;
    struct list *next;
} list;

list *duplicate(const list *ls)
{
    list *head = NULL;

    if (ls != NULL) {
        list *p = duplicate(ls->next);
        head = malloc(sizeof *head);
        head->value = ls->value;
        head->next = p;
    }
    return head;
}

;; in Scheme,
(define (duplicate ls)
  (if (not (null? ls))
    (cons (car ls)
          (duplicate (cdr ls)))
    '()))

%% in Prolog,
duplicate([X|Xs],R):-
  duplicate(Xs,Ys),
  R=[X|Ys].
duplicate([],[]).

इस रूप में फ़ंक्शन टेल रिकर्सिव नहीं है क्योंकि रिकर्सिव कॉल के बाद शेष इनपुट सूची को प्रतिलिपित करने के बाद नियंत्रण कॉलर पर वापस आ जाता है। यद्यपि इसे अन्य को प्रतिलिपित करने से पहले हेड नोड आवंटित करना था, फिर भी इसे कॉल के बाद रिकर्सिव कॉल के परिणाम को next सूची में प्रयुक्त करना होता है।[lower-alpha 1] तो फ़ंक्शन लगभग तर्क रिकर्सिव है। वॉरेन की विधि next सूची को रिकर्सिव कॉल में भरने की आवश्यकता को आगे बढ़ाती है जो इस प्रकार टेल कॉल बन जाती है।[lower-alpha 2] कोड को सरल बनाने के लिए सेंटिनल हेड नोड का उपयोग किया जाता है: 

typedef struct list {
    void *value;
    struct list *next;
} list;
void duplicate_aux(const list *ls, list *end);

list *duplicate(const list *ls)
{  
    list head;

    duplicate_aux(ls, &head);
    return head.next;
}

void duplicate_aux(const list *ls, list *end)
{
    if (ls != NULL) {
        end->next = malloc(sizeof *end);
        end->next->value = ls->value;
        duplicate_aux(ls->next, end->next);
    } else {
        end->next = NULL;
    }
}

;; in 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)))

%% in Prolog,
duplicate([X|Xs],R):-
   R=[X|Ys],
   duplicate(Xs,Ys).
duplicate([],[]).

कॉल प्राप्तकर्ता अब बढ़ती हुई सूची के अंत में जुड़ जाता है, न कि कॉल करने वाले को लौटाई गई सूची की प्रारम्भ में जोड़ा जाता है। कार्य अब सूची के प्रारम्भ से आगे की ओर किया जाता है, रिकर्सिव कॉल से पहले, जो रिकर्सिव कॉल के अपना परिणाम लौटाने के बाद सूची के अंत से पीछे की अतिरिक्त आगे बढ़ता है। इस प्रकार यह संचय पैरामीटर तकनीक के समान है, जो रिकर्सिव गणना को पुनरावृत्त में परिवर्तित कर देता है।इस तकनीक के लिए विशिष्ट रूप से निष्पादन कॉल स्टैक पर एक पैरेंट कॉल फ़्रेम बनाया जाता है, जिसे टेल-रिकर्सिव कैली टेल-कॉल अनुकूलीकरण सम्मिलित होने पर अपने स्वयं के कॉल फ्रेम के रूप में पुन: उपयोग कर सकता है। टेल-रिकर्सिव कार्यान्वयन को अब एक संचित लूप (कंप्यूटिंग) के रूप में स्पष्ट रूप से पुनरावृत्त कार्यान्वयन में परिवर्तित किया जा सकता है: 

typedef struct list {
    void *value;
    struct list *next;
} list;

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

 ;; in 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))))))

%% in Prolog,
%% N/A

इतिहास

1977 में सिएटल में एसीएम सम्मेलन में दिए गए एक पेपर में गाइ एल. स्टील ने जीओटीओ और संरचित प्रोग्रामिंग पर चर्चा का सारांश दिया और देखा कि किसी प्रक्रिया की तर्क स्थिति में प्रक्रिया कॉल को नियंत्रण के सीधे हस्तांतरण के रूप में सबसे अच्छा माना जा सकता है। तथाकथित प्रक्रिया सामान्यतः अनावश्यक स्टैक हस्तांतरण संचालन को समाप्त करती है।[2] चूंकि इस प्रकार की "टेल कॉल" लिस्प में बहुत सामान्य हैं, एक ऐसी भाषा जहां प्रक्रिया कॉल सर्वव्यापी हैं, अनुकूलन का यह रूप अन्य कार्यान्वयन की तुलना में प्रक्रिया कॉल की लागत को अपेक्षाकृत कम कर देता है। स्टील ने तर्क दिया कि अस्पष्ट रूप से कार्यान्वित प्रक्रिया कॉलों ने एक कृत्रिम धारणा को जन्म दिया है कि प्रक्रिया कॉल की तुलना में goto स्टेटमेंट अपेक्षाकृत कम उपयोगी था। स्टील ने आगे तर्क दिया कि "सामान्य प्रक्रिया में कॉल को उपयोगी रूप से goto स्टेटमेंट के रूप में माना जा सकता है जो मापदंडों को भी पारित करता है और समान रूप से मशीन कोड निर्देशों के रूप में कोडित किया जा सकता है", मशीन कोड स्टैक हस्तांतरण निर्देशों के साथ "एक अनुकूलन माना जाता है। इसके विपरीत स्टील ने प्रमाणों को प्रस्तुत किया कि लिस्प में अच्छी तरह से अनुकूलित संख्यात्मक एल्गोरिदम शीघ्र उपलब्ध वाणिज्यिक फोरट्रान कंपाइलरों द्वारा उत्पादित कोड की तुलना में तीव्रता से निष्पादित हो सकते हैं क्योंकि लिस्प में एक प्रक्रिया कॉल की लागत अपेक्षाकृत बहुत कम थी। स्कीम भाषा में गेराल्ड जे सुसमैन के साथ स्टील द्वारा विकसित एक लिस्प भाषा टेल-कॉल उन्मूलन को किसी भी इंटरप्रेटर में प्रयुक्त करने का दायित्व करती है।[9]

कार्यान्वयन विधियाँ

टेल रिकर्सन कुछ उच्च-स्तरीय भाषाओं मे विशेष रूप से कार्यात्मक और तर्क प्रोग्रामिंग भाषाओं, लिस्प प्रोग्रामिंग भाषा समूह के सदस्यों के लिए महत्वपूर्ण है। इन भाषाओं में रिकर्सन को प्रयुक्त करने के लिए टेल रिकर्सन सबसे अधिक उपयोग किया जाने वाला प्रकार (और कभी-कभी उपलब्ध एकमात्र प्रकार) है। स्कीम भाषा विनिर्देश के लिए आवश्यक है कि टेल कॉल को अनुकूलित किया जाए ताकि स्टैक में वृद्धि न हो। टेल कॉल को पर्ल भाषा में स्पष्ट रूप से goto स्टेटमेंट के एक प्रकार के साथ प्रयुक्त किया जा सकता है, जो एक फ़ंक्शन goto &NAME;लेता है।[10] हालाँकि, भाषा कार्यान्वयन के लिए जो फ़ंक्शन तर्क और स्थानीय वेरिएबल को कॉल स्टैक पर संग्रहीत करता है जो कि कई भाषाओं के लिए डिफ़ॉल्ट कार्यान्वयन है कम से कम हार्डवेयर स्टैक वाले सिस्टम पर जैसे कि x86 सामान्यीकृत टेल-कॉल अनुकूलन को प्रयुक्त करना और (पारस्परिक सहित) टेल रिकर्सन की एक समस्या प्रस्तुत करता है। यदि कैली के सक्रियण रिकॉर्ड का आकार कॉल करने वाले से भिन्न है, तो स्टैक फ्रेम की अतिरिक्त सफाई या आकार परिवर्तन की आवश्यकता हो सकती है। इन स्थितियों के लिए टेल रिकर्सन को अनुकूलित करना तुच्छ रहता है, लेकिन सामान्य टेल-कॉल अनुकूलीकरण को कुशलता से प्रयुक्त करना जटिल हो सकता है।

उदाहरण के लिए जावा वर्चुअल मशीन (जेवीएम) में टेल-रिकर्सिव कॉल को समाप्त किया जा सकता है क्योंकि यह सम्मिलित कॉल स्टैक का पुन: उपयोग करती है, लेकिन सामान्य टेल कॉल नहीं हो सकती हैं क्योंकि यह कॉल स्टैक को परिवर्तित कर देती है।[11][12] जिसके परिणामस्वरूप, स्काला (प्रोग्रामिंग भाषा) जैसी कार्यात्मक भाषाएं जो जेवीएम को लक्षित करती हैं, प्रत्यक्ष टेल रिकर्सन को कुशलतापूर्वक प्रयुक्त कर सकती हैं, लेकिन पारस्परिक टेल रिकर्सन को नहीं प्रयुक्त कर सकती है। जीएनयू कंपाइलर संग्रह, एलएलवीएम/क्लैंग और इंटेल सी कंपाइलर सूट सी और अन्य भाषाओं के लिए उच्च अनुकूलन स्तरों पर या जब -foptimize-sibling-calls विकल्प पारित हो जाता है तब टेल-कॉल अनुकूलन करते हैं।[13][14][15] हालाँकि दिया गया भाषा सिंटैक्स स्पष्ट रूप से इसका समर्थन नहीं कर सकता है, लेकिन कंपाइलर यह अनुकूलन कर सकता है जब भी वह यह निर्धारित कर सकता है कि कॉल और कैली के लिए रिटर्न प्रकार समतुल्य हैं और दोनों फ़ंक्शन के लिए पारित तर्क प्रकार या तो समान हैं या समान राशि की आवश्यकता है कॉल स्टैक पर कुल संग्रहण भंडारण अधिकृत करता है।[16] जिसके लिए विभिन्न कार्यान्वयन विधियाँ उपलब्ध हैं।

असेंबली

टेल कॉल को प्रायः कार्यात्मक प्रोग्रामिंग और तर्क प्रोग्रामिंग भाषाओं के इंटरप्रेटर और कंपाइलरों द्वारा रिकर्सन के अधिक कुशल रूपों के लिए अनुकूलित किया जाता है। उदाहरण के लिए, स्कीम प्रोग्रामर सामान्यतः टेल स्थिति में प्रक्रियाओं के लिए कॉल के रूप में लूप को व्यक्त करते हैं और अधिक कुशल जंप निर्देशों के साथ टेल कॉल को प्रतिस्थापित करने के लिए स्कीम कंपाइलर या इंटरप्रेटर पर विश्वास करते हैं।[17]

असेंबली उत्पन्न करने वाले कंपाइलरों के लिए टेल-कॉल उन्मूलन आसान होता है। स्टैक पर पैरामीटर को ठीक करने के बाद कॉल ऑपकोड को जंप वन से परिवर्तित करना पर्याप्त है। एक कंपाइलर के अनुसार ऊपर दिए गए पहले उदाहरण को प्रारम्भ में छद्म-असेंबली भाषा में अनुवादित किया गया है वास्तव में यह एक मान्य एक्स-86 असेंबली भाषा है: 

 foo:
  call B
  call A
  ret

टेल-कॉल एलिमिनेशन अंतिम दो पंक्तियों को एक ही jump निर्देश से परिवर्तित कर देता है: 

 foo:
  call B
  jmp  A

प्रक्रिया A पूरा होने के बाद यह अनावश्यक ret स्टेटमेंट को छोड़कर सीधे foo के रिटर्न एड्रेस पर वापस आ जाता है।

सामान्यतः कॉल किए जाने वाली प्रक्रिया को पैरामीटर प्रदान करने की आवश्यकता होती है। इस प्रकार उत्पन्न कोड को यह सुनिश्चित करने की आवश्यकता है कि टेल-कॉल किए गए प्रक्रिया पर जाने से पहले A के लिए कॉल फ्रेम ठीक से प्रयुक्त किया गया है। उदाहरण के लिए ऐसे प्लेटफ़ॉर्म पर जहां कॉल स्टैक में न केवल रिटर्न एड्रेस होता है, बल्कि प्रक्रिया के पैरामीटर भी होते हैं, कंपाइलर को कॉल स्टैक को समायोजित करने के लिए निर्देश प्रारम्भ करने की आवश्यकता हो सकती है: 

function foo(data1, data2)
  B(data1)
  return A(data2)

जहाँ data1 और data2 पैरामीटर हैं और कंपाइलर इसका अनुवाद इस प्रकार कर सकता है:[lower-alpha 3] 

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   push reg            ; put data2 on stack where A expects it
   call A              ; A uses data2
   pop                 ; remove data2 from stack.
   ret

टेल-कॉल अनुकूलीकरण तब कोड को इसमें परिवर्तित कर सकता है: 

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   mov  [sp+data1],reg ; put data2 where A expects it
   jmp  A              ; A uses data2 and returns immediately to caller.

यह कोड निष्पादन गति और स्टैक स्पेस के उपयोग दोनों की स्थिति में अधिक कुशल है।

ट्रैम्पोलिनिंग के माध्यम से

कई स्कीम कंपाइलर सी प्रोग्रामिंग को एक मध्यवर्ती लक्ष्य कोड के रूप में उपयोग करते हैं, टेल रिकर्सन मे स्टैक को बढ़ाए बिना सी में एन्कोड किया जाना चाहिए, यद्यपि C कंपाइलर टेल कॉल को अनुकूलित न करता हो तब कई कार्यान्वयन ट्रैम्पोलिन (कंप्यूटर) नामक उपकरण का उपयोग करके इसे प्राप्त करते हैं, कोड का एक भाग जो बार-बार फ़ंक्शन को कॉल करता है। सभी फ़ंक्शन को ट्रैम्पोलिन के माध्यम से प्रस्तुत किया जाता है। जब किसी फ़ंक्शन को सीधे कॉल करने और फिर परिणाम लौटाने के अतिरिक्त किसी अन्य को टेल-कॉल करना होता है, तो यह कॉल किए जाने वाले फ़ंक्शन का एड्रेस और कॉल पैरामीटर ट्रैम्पोलिन (जहां से इसे स्वयं कॉल किया गया था) पर वापस लौटाता है और ट्रैम्पोलिन निर्दिष्ट मापदंडों के साथ इस फ़ंक्शन को कॉल करने का ध्यान रखता है। यह सुनिश्चित करता है कि सी स्टैक नहीं बढ़ता है और रिकर्सन अनिश्चित समय तक प्रारम्भ रह सकता है।

उन भाषाओं में उच्च-क्रम के फ़ंक्शंन का उपयोग करके ट्रैम्पोलिन को प्रयुक्त करना संभव है जो उनका समर्थन करते हैं, जैसे कि ग्रूवी (प्रोग्रामिंग भाषा), विज़ुअल बेसिक, डॉटनेट और सी शार्प (प्रोग्रामिंग भाषा) सहित सभी फ़ंक्शन कॉल के लिए ट्रैम्पोलिन का उपयोग करना सामान्य सी फ़ंक्शन कॉल की तुलना में अधिक कीमती है।[18] इसलिए कम से कम एक स्कीम कंपाइलर, एंड्रयू अपेल के एक अप्रकाशित सुझाव से हेनरी बेकर (कंप्यूटर वैज्ञानिक) द्वारा वर्णित तकनीक का उपयोग करता है।[19] जिसमें सामान्य सी कॉल का उपयोग किया जाता है लेकिन प्रत्येक कॉल से पहले स्टैक आकार की जाँच की जाती है। जब स्टैक अपने अधिकतम अनुमत आकार तक अभिगम्य हो जाता है, तो स्टैक पर सम्मिलित वस्तुओं के सभी लाइव डेटा को एक अलग स्टैक में ले जाकर चेनी एल्गोरिदम का उपयोग करके कवेरिएबला स्टैक किया जाता है। इसके बाद स्टैक को मुक्त कर दिया जाता है और प्रोग्राम कवेरिएबला संग्रहण से ठीक पहले साझा की गई स्थिति से फिर से प्रारम्भ हो जाता है। बेकर कहते हैं कि "एपेल की विधि कभी-कभी एम्पायर स्टेट बिल्डिंग से बड़ी संख्या में छोटे ट्रैम्पोलिन को उछालने से बचाती है।"[19] कवेरिएबला संग्रहण यह सुनिश्चित करता है कि पारस्परिक तर्क रिकर्सन अनिश्चित समय तक प्रारम्भ रह सकती है। हालाँकि इस दृष्टिकोण के लिए यह आवश्यक है कि कोई भी C फ़ंक्शन कॉल कभी वापस न आए, क्योंकि इसका कोई महत्व नहीं है कि इसके कॉल का स्टैक फ्रेम अभी भी उपस्थित है। इसलिए इसमें प्रोग्राम कोड निरंतरता-पासिंग शैली का अधिक आकस्मिक आंतरिक पुनर्लेखन सम्मिलित है।

व्हील लूप से संबंध

टेल रिकर्सन को व्हील लूप से संबंधित किया जा सकता है, उदाहरण के लिए रिकर्सन को रूपांतरित करके एक स्पष्ट रिकर्सन मे निम्नलिखित द्वारा प्रदर्शित किया जा सकता है: 

procedure foo(x)
  if p(x)
    return bar(x)
  else
    return foo(baz(x))

procedure foo(x)
  while true
    if p(x)
      return bar(x)
    else
      x ← baz(x)

जहां x एक टपल हो सकता है जिसमें एक से अधिक वेरिएबल सम्मिलित हों सकते है यदि ऐसा है तो असाइनमेंट (कंप्यूटर विज्ञान) x ← baz(x) को प्रयुक्त करने में सावधानी रखनी चाहिए ताकि निर्भरता का सम्मान किया जा सके और किसी फंक्शन को सहायक वेरिएबल प्रस्तुत करने या स्वैप (कंप्यूटर विज्ञान) निर्माण का उपयोग करने की आवश्यकता हो सकती है: 

procedure foo(x)
  if p(x)
    return bar(x)
  else if q(x)
    return baz(x)
  ...
  else if r(x)
    return foo(qux(x))
  ...
  else
    return foo(quux(x))

सामान्यतः उपरोक्त को निम्न एल्गोरिथम में परिवर्तित किया जा सकता है: 

procedure foo(x)
  while true
    if p(x)
      return bar(x)
    else if q(x)
      return baz(x)
    ...
    else if r(x)
      x ← qux(x)
    ...
    else
      x ← quux(x)

उदाहरण के लिए यह जूलिया (प्रोग्रामिंग भाषा) प्रोग्राम एक गैर-तर्क रिकर्सिव परिभाषा factदेता है: 

function factorial(n)
  if n == 0
    return 1
  else
    return n * factorial(n - 1)
  end
end

वास्तव में n * factorial(n - 1) कॉल को factorial में सम्मिलित किया जा सकता है। लेकिन इसे एक एक्युमुलेटर नामक तर्क जोड़कर टेल-रिकर्सिव परिभाषा में परिवर्तित किया जा सकता है।[7] यह जूलिया प्रोग्राम फंक्शन की टेल-रिकर्सिव परिभाषा fact_iter देता है: 

function factorial(n::Integer, a::Integer)
  if n == 0:
    return a
  else
    return factorial(n - 1, n * a)
  end
end

function factorial(n::Integer)
  return factorial(n, 1)
end

यह जूलिया प्रोग्राम एक रिकर्सिव fact_iterपरिभाषा देता है: 

function fact_iter(n::Integer, a::Integer)
    while n > 0
        a = n * a
        n = n - 1
    end
    return a
end

function factorial(n::Integer)
    return fact_iter(n, one(n))
end

भाषा समर्थन

  • क्लोजर (प्रोग्रामिंग भाषा) – क्लोजर का पुनः विशेष रूप recurहोता है।[20]
  • सामान्य लिस्प – कुछ कार्यान्वयन गति के लिए अनुकूलन करते हुए संकलन के समय टेल-कॉल अनुकूलन करते हैं।
  • एलिक्सिर (प्रोग्रामिंग भाषा) – एलिक्सिर टेल-कॉल इष्टमीकरण प्रयुक्त करता है,[21] जैसा कि वर्तमान में बीम वीएम को लक्षित करने वाली सभी भाषाएँ कर रही हैं।
  • एल्म (प्रोग्रामिंग भाषा) – हाँ[22]
  • एर्लांग (प्रोग्रामिंग भाषा) – हाँ
  • एफ शार्प (प्रोग्रामिंग भाषा) – एफ जहां संभव हो वहां डिफ़ॉल्ट रूप से टीसीओ प्रयुक्त करता है। [23]
  • गो (प्रोग्रामिंग भाषा) – कोई सहायता नहीं[24]
  • हास्केल (प्रोग्रामिंग भाषा) – हाँ[25]
  • जावास्क्रिप्ट – ईसीएमएस्क्रिप्ट 6.0 अनुरूप इंजनों में टेल कॉल्स होनी चाहिए[26] जिसे अब सफारी/वेबकिट पर प्रयुक्त किया गया है, लेकिन वी-8 और स्पाइडरमंकी द्वारा निरस्त कर दिया गया है।[27]
  • कोटलिन (प्रोग्रामिंग भाषा) – tailrec के लिए टेलरेक संशोधक है।[28]
  • लुआ (प्रोग्रामिंग भाषा) – भाषा की परिभाषा के अनुसार टेल रिकर्सन आवश्यक है।[29]
  • ऑब्जेक्ट सी – O1 (या उच्चतर) विकल्प निर्दिष्ट होने पर कंपाइलर टेल कॉल को अनुकूलित करता है लेकिन स्वचालित संदर्भ गणना (एआरसी) द्वारा जोड़े गए कॉल से यह आसानी से भ्रमित हो जाता है।
  • ओकैमल – हाँ
  • पर्ल (प्रोग्रामिंग भाषा) – goto स्टेटमेंट के एक प्रकार के साथ स्पष्ट जो एक फ़ंक्शन नाम goto &NAME; लेता है।[30]
  • प्योरस्क्रिप्ट – हाँ
  • पायथन (प्रोग्रामिंग भाषा) – स्टॉक पायथन कार्यान्वयन टेल-कॉल इष्टमीकरण नहीं करता है। हालांकि ऐसा करने के लिए एक तृतीय-पक्ष मॉड्यूल उपलब्ध है।[31] भाषा के आविष्कारक गुइडो वैन रोसुम का तर्क है कि स्टैक ट्रेस को टेल-कॉल उन्मूलन द्वारा परिवर्तित कर दिया जाता है। जिससे डिबगिंग कठिन हो जाती है और पसंद करते हैं कि प्रोग्रामर इसके अतिरिक्त स्पष्ट रिकर्सन का उपयोग करते हैं।[32]
  • रैकेट (प्रोग्रामिंग भाषा) – हाँ[33]
  • जंग (प्रोग्रामिंग भाषा) – टेल-कॉल अनुकूलन सीमित परिस्थितियों में किया जा सकता है, लेकिन इसका कोई दायित्व नहीं है।[34]
  • स्काला (प्रोग्रामिंग भाषा) – टेल-रिकर्सिव फ़ंक्शंन स्वचालित रूप से कंपाइलर द्वारा अनुकूलित होते हैं। ऐसे फ़ंक्शंन को वैकल्पिक रूप से @tailrec से भी चिह्नित किया जा सकता है। एनोटेशन जो इसे एक संकलन त्रुटि बनाता है यदि फ़ंक्शन टेल रिकर्सिव नहीं है।[35]
  • स्कीम (प्रोग्रामिंग भाषा) – भाषा परिभाषा के अनुसार आवश्यक है।[36][37]
  • टी.सी.एल – टीसीएल 8.6 के बाद से टीसीएल के पास टेलकॉल कमांड है।[38]
  • ज़िग (प्रोग्रामिंग भाषा) – हाँ[39]

यह भी देखें

Look up tail recursion in Wiktionary, the free dictionary.

टिप्पणियाँ

  1. ↑ Like this: 
    if (ls != NULL) {
  head = malloc( sizeof *head);
  head->value = ls->value;
  head->next = duplicate( ls->next);
}
  2. ↑ Like this: 
    if (ls != NULL) {
  head = malloc( sizeof *head);
  head->value = ls->value;
  duplicate( ls->next, &(head->next));
}
  3. ↑ The call instruction first pushes the current code location onto the stack and then performs an unconditional jump to the code location indicated by the label. The ret instruction first pops a code location off the stack, then performs an unconditional jump to the retrieved code location.

संदर्भ

  1. ↑ Steven Muchnick; Muchnick and Associates (15 August 1997). उन्नत कंपाइलर डिज़ाइन कार्यान्वयन. Morgan Kaufmann. ISBN 978-1-55860-320-2.
  2. ↑ 2.0 2.1 Steele, Guy Lewis (1977). "Debunking the "expensive procedure call" myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO". Proceedings of the 1977 annual conference on - ACM '77. pp. 153–162. doi:10.1145/800179.810196. hdl:1721.1/5753. ISBN 978-1-4503-2308-6. S2CID 9807843.
  3. ↑ "The LLVM Target-Independent Code Generator — LLVM 7 documentation". llvm.org.
  4. ↑ "रिकर्सन - टेल कॉल के लिए स्टैक मेमोरी उपयोग - सैद्धांतिक कंप्यूटर विज्ञान". Cstheory.stackexchange.com. 2011-07-29. Retrieved 2013-03-21.
  5. ↑ 5.0 5.1 "Revised^6 Report on the Algorithmic Language Scheme". R6rs.org. Retrieved 2013-03-21.
  6. ↑ "Revised^6 Report on the Algorithmic Language Scheme - Rationale". R6rs.org. Retrieved 2013-03-21.
  7. ↑ 7.0 7.1 7.2 Sussman, G. J.; Abelson, Hal (1984). कंप्यूटर प्रोग्राम की संरचना और व्याख्या. Cambridge, MA: MIT Press. ISBN 0-262-01077-1.
  8. ↑ D. H. D. Warren, DAI Research Report 141, University of Edinburgh, 1980.
  9. ↑ R5RS Sec. 3.5, Richard Kelsey; William Clinger; Jonathan Rees; et al. (August 1998). "Revised5 Report on the Algorithmic Language Scheme". Higher-Order and Symbolic Computation. 11 (1): 7–105. doi:10.1023/A:1010051815785. S2CID 14069423.
  10. ↑ Contact details. "के लिए जाओ". perldoc.perl.org. Retrieved 2013-03-21.
  11. ↑ "What is difference between tail calls and tail recursion?", Stack Overflow
  12. ↑ "What limitations does the JVM impose on tail-call optimization", Programmers Stack Exchange
  13. ↑ Lattner, Chris. "LLVM Language Reference Manual, section: The LLVM Target-Independent Code Generator, sub: Tail Call Optimization". The LLVM Compiler Infrastructure. The LLVM Project. Retrieved 24 June 2018.
  14. ↑ "Using the GNU Compiler Collection (GCC): Optimize Options". gcc.gnu.org.
  15. ↑ "अनुकूलन-भाई-बहन-कॉल". software.intel.com.
  16. ↑ "Tackling C++ Tail Calls".
  17. ↑ Probst, Mark (20 July 2000). "जीसीसी के लिए उचित पूंछ पुनरावृत्ति". GCC Project. Retrieved 10 March 2015.
  18. ↑ Samuel Jack, Bouncing on your tail. Functional Fun. April 9, 2008.
  19. ↑ 19.0 19.1 Henry Baker, "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A."
  20. ↑ "(पुनरावर्ती व्यय*)". clojure.org.
  21. ↑ "प्रत्यावर्तन". elixir-lang.github.com.
  22. ↑ Czaplicki, Evan. "Functional Programming in Elm: Tail-Call Elimination".
  23. ↑ "F# में टेल कॉल्स". msdn. Microsoft.
  24. ↑ "proposal: Go 2: add become statement to support tail calls". github.com.
  25. ↑ "पूँछ प्रत्यावर्तन - हास्केलविकी". wiki.haskell.org. Retrieved 2019-06-08.
  26. ↑ Beres-Deak, Adam. "Worth watching: Douglas Crockford speaking about the new good parts of JavaScript in 2014". bdadam.com.
  27. ↑ "ECMAScript 6 in WebKit". 13 October 2015.
  28. ↑ "Functions: infix, vararg, tailrec - Kotlin Programming Language". Kotlin.
  29. ↑ "Lua 5.3 Reference Manual". www.lua.org.
  30. ↑ "गोटो - perldoc.perl.org". perldoc.perl.org.
  31. ↑ "baruchel/tco". GitHub. 29 March 2022.
  32. ↑ Rossum, Guido Van (22 April 2009). "Neopythonic: Tail Recursion Elimination".
  33. ↑ "रैकेट संदर्भ". docs.racket-lang.org.
  34. ↑ "जंग अक्सर पूछे जाने वाले प्रश्न". prev.rust-lang.org.
  35. ↑ "Scala Standard Library 2.13.0 - scala.annotation.tailrec". www.scala-lang.org. Retrieved 2019-06-20.
  36. ↑ "Revised^5 Report on the Algorithmic Language Scheme". www.schemers.org.
  37. ↑ "Revised^6 Report on the Algorithmic Language Scheme". www.r6rs.org.
  38. ↑ "टेलकॉल मैनुअल पेज - टीसीएल बिल्ट-इन कमांड्स". www.tcl.tk.
  39. ↑ "Documentation - the Zig Programming Language".
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=टेल_कॉल&oldid=217608’