टेल कॉल: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|Subroutine call performed as final action of a procedure}} कंप्यूटर विज्ञान में, टेल कॉल एक स...")
 
m (Deepak moved page पूँछ बुलाओ to टेल कॉल without leaving a redirect)
(No difference)

Revision as of 14:53, 3 July 2023

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

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

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


विवरण

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

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

उदाहरण कार्यक्रम

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

;; 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 नियंत्रण प्रवाह में स्वयं को अंतिम कहता है। यह एक दुभाषिया (कंप्यूटर सॉफ़्टवेयर) या संकलक को निष्पादन को पुनर्गठित करने की अनुमति देता है जो आमतौर पर इस तरह दिखेगा:[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 उपरोक्त उदाहरण में) फ़ंक्शन के लिए। कुछ मामलों में (जैसे फ़िल्टरिंग सूचियां) और कुछ भाषाओं में, पूर्ण पूंछ रिकर्सन के लिए एक फ़ंक्शन की आवश्यकता हो सकती है जो पहले लिखने के लिए पूरी तरह कार्यात्मक थी ताकि यह अन्य चर में संग्रहीत संदर्भों को बदल सके।[citation needed]


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

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

उदाहरण कोड

% 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 स्टेटमेंट के रूप में माना जा सकता है जो मापदंडों को भी पास करता है, और समान रूप से [मशीन कोड] JUMP निर्देशों के रूप में कोड किया जा सकता है, मशीन कोड स्टैक हेरफेर निर्देशों को एक अनुकूलन माना जाता है (बजाय इसके विपरीत!) ) .[2]स्टील ने सबूतों का हवाला दिया कि लिस्प में अच्छी तरह से अनुकूलित संख्यात्मक एल्गोरिदम तत्कालीन उपलब्ध वाणिज्यिक फोरट्रान कंपाइलरों द्वारा उत्पादित कोड की तुलना में तेजी से निष्पादित हो सकते हैं क्योंकि लिस्प में एक प्रक्रिया कॉल की लागत बहुत कम थी। स्कीम (प्रोग्रामिंग भाषा) में, गेराल्ड जे सुसमैन के साथ स्टील द्वारा विकसित एक लिस्प बोली, टेल-कॉल उन्मूलन को किसी भी दुभाषिया में लागू करने की गारंटी है।[11]


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

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

उदाहरण के लिए, जावा वर्चुअल मशीन (जेवीएम) में, टेल-रिकर्सिव कॉल्स को समाप्त किया जा सकता है (क्योंकि यह मौजूदा कॉल स्टैक का पुन: उपयोग करता है), लेकिन सामान्य टेल कॉल्स नहीं हो सकती हैं (क्योंकि यह कॉल स्टैक को बदल देता है)।[13][14] परिणामस्वरूप, स्काला (प्रोग्रामिंग भाषा) जैसी कार्यात्मक भाषाएं जो जेवीएम को लक्षित करती हैं, प्रत्यक्ष टेल रिकर्सन को कुशलतापूर्वक लागू कर सकती हैं, लेकिन पारस्परिक टेल रिकर्सन को नहीं।

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

असेंबली में

टेल कॉल को अक्सर दुभाषिया (कंप्यूटिंग) और कार्यात्मक प्रोग्रामिंग और तर्क प्रोग्रामिंग भाषाओं के कंपाइलरों द्वारा पुनरावृत्ति के अधिक कुशल रूपों के लिए अनुकूलित किया जाता है। उदाहरण के लिए, स्कीम (प्रोग्रामिंग भाषा) प्रोग्रामर आमतौर पर टेल पोजीशन में प्रक्रियाओं के लिए कॉल के रूप में लूप को व्यक्त करते हैं और टेल कॉल को अधिक कुशल जंप (कंप्यूटर विज्ञान) निर्देशों के साथ प्रतिस्थापित करने के लिए स्कीम कंपाइलर या दुभाषिया पर भरोसा करते हैं।[19] सीधे असेंबली उत्पन्न करने वाले कंपाइलरों के लिए, टेल-कॉल उन्मूलन आसान है: स्टैक पर पैरामीटर्स को ठीक करने के बाद, कॉल ऑपकोड को जंप वन से बदलना पर्याप्त है। एक कंपाइलर के नजरिए से, ऊपर दिए गए पहले उदाहरण को शुरू में छद्म-असेंबली भाषा में अनुवादित किया गया है (वास्तव में, यह वैध x86 असेंबली भाषा है): 

 foo:
  call B
  call A
  ret

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

 foo:
  call B
  jmp  A

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

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

फ़ंक्शन फू (डेटा1, डेटा2)
   बी(डेटा1)
   वापसी ए(डेटा2)

(कहाँ 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.

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

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

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

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

थोड़ी देर के कथन से संबंध

टेल रिकर्सन को while लूप से संबंधित किया जा सकता है, एक स्पष्ट पुनरावृत्ति, उदाहरण के लिए रूपांतरित करके 

'प्रक्रिया' foo(x)
    'अगर' पी(एक्स)
        'वापसी' बार(x)
    'अन्य'
        'वापसी' foo(baz(x))

में 

'प्रक्रिया' foo(x)
    'जबकि' 'सच'
        'अगर' पी(एक्स)
            'वापसी' बार(x)
        'अन्य'
            x ← baz(x)

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

आम तौर पर अधिक, 

'प्रक्रिया' foo(x)
    'अगर' पी(एक्स)
        'वापसी' बार(x)
    'अन्यथा यदि' q(x)
        'वापसी' baz(x)
    ...
    'अन्यथा यदि' r(x)
        'वापसी' foo(qx(x))
    ...
    'अन्य'
        'वापसी' फू(क्वक्स(x))

में परिवर्तित किया जा सकता है 

'प्रक्रिया' foo(x)
    'जबकि' 'सच'
        'अगर' पी(एक्स)
            'वापसी' बार(x)
        'अन्यथा यदि' q(x)
            'वापसी' baz(x)
        ...
        'अन्यथा यदि' r(x)
            x ← qux(x)
        ...
        'अन्य'
            x ← quux(x)

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

<सिंटैक्सहाइलाइट लैंग= जूलिया लाइन= 1 > फ़ंक्शन फैक्टोरियल(एन) 

   यदि एन == 0
       वापसी 1
   अन्य
       रिटर्न एन * फैक्टोरियल (एन - 1)
   अंत

अंत </सिंटैक्सहाइलाइट>

वास्तव में, n * factorial(n - 1) कॉल को लपेटता है factorial. लेकिन इसे एक तर्क जोड़कर टेल-रिकर्सिव परिभाषा में बदला जा सकता है a संचायक कहा जाता है।[8]

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

<सिंटैक्सहाइलाइट लैंग= जूलिया लाइन= 1 > फ़ंक्शन फ़ैक्टोरियल(n::पूर्णांक, a::पूर्णांक) 

   यदि एन == 0:
       वापसी ए
   अन्य
       वापसी भाज्य(एन - 1, एन * ए)
   अंत

अंत

फ़ंक्शन फ़ैक्टोरियल(n::पूर्णांक) 

   वापसी भाज्य(एन, 1)

अंत </सिंटैक्सहाइलाइट>

यह जूलिया प्रोग्राम एक पुनरावृत्तीय परिभाषा देता है 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


भाषा समर्थन


यह भी देखें

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 2.2 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. ↑ "Revised^6 Report on the Algorithmic Language Scheme". R6rs.org. Retrieved 2013-03-21.
  8. ↑ 8.0 8.1 8.2 Sussman, G. J.; Abelson, Hal (1984). कंप्यूटर प्रोग्राम की संरचना और व्याख्या. Cambridge, MA: MIT Press. ISBN 0-262-01077-1.
  9. ↑ D. H. D. Warren, DAI Research Report 141, University of Edinburgh, 1980.
  10. ↑ Daniel P. Friedman and David S. Wise, Technical Report TR19: Unwinding Structured Recursions into Iterations, Indiana University, Dec. 1974. PDF available here (webarchived copy here).
  11. ↑ 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.
  12. ↑ Contact details. "के लिए जाओ". perldoc.perl.org. Retrieved 2013-03-21.
  13. ↑ "What is difference between tail calls and tail recursion?", Stack Overflow
  14. ↑ "What limitations does the JVM impose on tail-call optimization", Programmers Stack Exchange
  15. ↑ 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.
  16. ↑ "Using the GNU Compiler Collection (GCC): Optimize Options". gcc.gnu.org.
  17. ↑ "अनुकूलन-भाई-बहन-कॉल". software.intel.com.
  18. ↑ "Tackling C++ Tail Calls".
  19. ↑ Probst, Mark (20 July 2000). "जीसीसी के लिए उचित पूंछ पुनरावृत्ति". GCC Project. Retrieved 10 March 2015.
  20. ↑ Samuel Jack, Bouncing on your tail. Functional Fun. April 9, 2008.
  21. ↑ 21.0 21.1 Henry Baker, "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A."
  22. ↑ "(पुनरावर्ती व्यय*)". clojure.org.
  23. ↑ "प्रत्यावर्तन". elixir-lang.github.com.
  24. ↑ Czaplicki, Evan. "Functional Programming in Elm: Tail-Call Elimination".
  25. ↑ "F# में टेल कॉल्स". msdn. Microsoft.
  26. ↑ "proposal: Go 2: add become statement to support tail calls". github.com.
  27. ↑ "पूँछ प्रत्यावर्तन - हास्केलविकी". wiki.haskell.org. Retrieved 2019-06-08.
  28. ↑ Beres-Deak, Adam. "Worth watching: Douglas Crockford speaking about the new good parts of JavaScript in 2014". bdadam.com.
  29. ↑ "ECMAScript 6 in WebKit". 13 October 2015.
  30. ↑ "Functions: infix, vararg, tailrec - Kotlin Programming Language". Kotlin.
  31. ↑ "Lua 5.3 Reference Manual". www.lua.org.
  32. ↑ "गोटो - perldoc.perl.org". perldoc.perl.org.
  33. ↑ "baruchel/tco". GitHub. 29 March 2022.
  34. ↑ Rossum, Guido Van (22 April 2009). "Neopythonic: Tail Recursion Elimination".
  35. ↑ "रैकेट संदर्भ". docs.racket-lang.org.
  36. ↑ "जंग अक्सर पूछे जाने वाले प्रश्न". prev.rust-lang.org.
  37. ↑ "Scala Standard Library 2.13.0 - scala.annotation.tailrec". www.scala-lang.org. Retrieved 2019-06-20.
  38. ↑ "Revised^5 Report on the Algorithmic Language Scheme". www.schemers.org.
  39. ↑ "Revised^6 Report on the Algorithmic Language Scheme". www.r6rs.org.
  40. ↑ "टेलकॉल मैनुअल पेज - टीसीएल बिल्ट-इन कमांड्स". www.tcl.tk.
  41. ↑ "Documentation - the Zig Programming Language".
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=टेल_कॉल&oldid=216979’