लेट्रेक के क्या फायदे हैं?

Question

"द सीजनेड शेमर" पढ़ते समय मैंने letrec के बारे में जानना शुरू कर दिया है। मैं समझता हूं कि यह क्या करता है (जिसे वाई-कॉम्बिनेटर के साथ डुप्लिकेट किया जा सकता है) लेकिन पुस्तक पहले से define डी फ़ंक्शन पर आवर्ती होने के तर्कों के आधार पर इसका उपयोग कर रही है जो स्थिर रहती है।

define घ समारोह पर ही आवर्ती (कुछ खास नहीं) का उपयोग कर एक पुराने समारोह का एक उदाहरण: कि एक ही समारोह का एक उदाहरण के लिए

(define (substitute new old l) 
    (cond 
    ((null? l) '()) 
    ((eq? (car l) old) 
     (cons new (substitute new old (cdr l)))) 
    (else 
     (cons (car l) (substitute new old (cdr l)))))) 

अब लेकिन letrec का उपयोग कर:

(define (substitute new old l) 
    (letrec 
    ((replace 
     (lambda (l) 
     (cond 
      ((null? l) '()) 
      ((eq? (car l) old) 
      (cons new (replace (cdr l)))) 
      (else 
      (cons (car l) (replace (cdr l)))))))) 
(replace lat))) 

एक तरफ थोड़ा लंबा होने और पढ़ने के लिए और अधिक कठिन होने से मुझे नहीं पता कि वे लेट्रेक का उपयोग करने के लिए पुस्तक में क्यों काम लिख रहे हैं। क्या एक स्थैतिक चर पर आवर्ती होने पर गति गति बढ़ जाती है क्योंकि आप इसे पास नहीं करते हैं ??

क्या तर्क के साथ कार्यों के लिए यह मानक अभ्यास स्थिर है, लेकिन एक तर्क जो कम हो गया है (जैसे किसी सूची के तत्वों को आवर्ती करना)?

अधिक अनुभवी स्कैमर/लिस्पर्स से कुछ इनपुट मदद करेगा!

Answer 1

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

#lang scheme 

;; original version 
(define (substitute1 new old l) 
    (cond [(null? l) '()] 
     [(eq? (car l) old) (cons new (substitute1 new old (cdr l)))] 
     [else (cons (car l) (substitute1 new old (cdr l)))])) 

;; letrec version (implicitly through a named-let) 
(define (substitute2 new old l) 
    (let loop ([l l]) 
    (cond [(null? l) '()] 
      [(eq? (car l) old) (cons new (loop (cdr l)))] 
      [else (cons (car l) (loop (cdr l)))]))) 

;; making the code a little more compact 
(define (substitute3 new old l) 
    (let loop ([l l]) 
    (if (null? l) 
     '() 
     (cons (let ([fst (car l)]) (if (eq? fst old) new fst)) 
      (loop (cdr l)))))) 

;; a tail recursive version 
(define (substitute4 new old l) 
    (let loop ([l l] [r '()]) 
    (if (null? l) 
     (reverse r) 
     (loop (cdr l) 
      (cons (let ([fst (car l)]) (if (eq? fst old) new fst)) r))))) 

;; tests and timings 

(define (rand-list n) 
    (if (zero? n) '() (cons (random 10) (rand-list (sub1 n))))) 

(for ([i (in-range 5)]) 
    (define l (rand-list 10000000)) 
    (define new (random 10)) 
    (define old (random 10)) 
    (define-syntax-rule (run fun) 
    (begin (printf "~a: " 'fun) 
      (collect-garbage) 
      (time (fun new old l)))) 
    ;; don't time the first one, since it allocates a new list to use later 
    (define new-list (substitute1 new old l)) 
    (unless (and (equal? (run substitute1) new-list) 
       (equal? (run substitute2) new-list) 
       (equal? (run substitute3) new-list) 
       (equal? (run substitute4) new-list)) 
    (error "poof")) 
    (newline)) 

Answer 2

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

यदि कोड संकलित किया गया है, तो प्रत्येक रिकर्सिव फ़ंक्शन कॉल पर स्थिर तर्कों को पार करने से बचने से शायद इस मामले में एक छोटा प्रदर्शन लाभ भी मिलेगा क्योंकि कॉलर नए स्टैक फ्रेम में तर्कों की प्रतिलिपि बनाने से बचाता है। यदि रिकर्सिव फ़ंक्शन कॉल पूंछ की स्थिति में था, तो संकलक स्टैक पर बार-बार तर्कों की प्रतिलिपि बनाने से बचने के लिए पर्याप्त चालाक हो सकता है।

इसी प्रकार यदि कोड का अर्थ है, तो रिकर्सिव कॉल में कम तर्क होने से तेज़ होगा।

अधिक आम तौर पर, letrec के मुख्य लाभों में से एक, जो मुझे नहीं लगता कि आपने उपर्युक्त उल्लेख किया है, यह तथ्य है कि यह पारस्परिक रूप से पुनरावर्ती कार्य परिभाषाओं की अनुमति देता है। मैं योजना के साथ काफी अनुभवहीन हूं, लेकिन जहां तक ​​मैं समझता हूं, यह letrec फ़ॉर्म की मुख्य विशेषताओं में से एक है उदा। define।

Answer 3

एक बात के लिए, letrec संस्करण आपको फ़ंक्शन का उपयोग करने की अनुमति देता है भले ही उसका वैश्विक नाम किसी अन्य चीज़ पर रीसेट हो, उदा।

(define substitute 
    ; stuff involving letrec 
) 

(define sub substitute) 
(set! substitute #f) 

फिर sub अभी भी काम करेगा, जबकि यह होगा गैर letrec संस्करण के साथ नहीं।

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

इसके अलावा, मैं वास्तव में let व्यक्तिगत रूप से नामित उपयोग करेंगे:

(define (substitute new old lat) ; edit: fixed this line 
    (let loop (
      ; whatever iteration variables are needed + initial values 
      ) 
    ; whatever it is that substitute should do at each iteration 
    )) 

मैं इसे अधिक पठनीय इस तरह लगता है। YMMV।