ما هي فوائد letrec؟

Question

وأثناء قراءة "ومحنك مدبر المكائد" لقد بدأت لمعرفة المزيد عن letrec. أنا أفهم ماذا (يمكن أن تتكرر مع Y-Combinator) ولكن الكتاب هو استخدامه بدلا من تكرار على التشغيل وظيفة defined بالفعل على الحجج التي تبقى ثابتة.

ومثال على وظيفة القديمة باستخدام وظيفة defined المتكررة على نفسها (لا شيء خاص):

(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)))

وبصرف النظر عن كونها أطول قليلا وأكثر صعوبة في قراءة لا أعرف لماذا هم إعادة صياغة وظائف في الكتاب لاستخدام letrec. هل هناك زيادة السرعة عند المتكررة على متغير ثابت بهذه الطريقة لأنك لا تبقي تمرير ذلك؟

هل هذه الممارسة القياسية للوظائف مع الحجج التي تبقى ثابتة ولكن وسيطة واحدة أن يتم تخفيض (مثل متكررة أسفل عناصر القائمة)؟

ووبعض مدخلات من المخططين أكثر خبرة / LISPers مساعدة!

Answer 1

وهكذا كان لديك القليل من الاجابات التي تشمل مسألة القراءة، والذي ينبغي أن يكون على ما يرام. ولكن سؤال واحد غير واضح هو ما إذا كان هناك أي مشاكل الأداء. على نظرة سطحية، ويبدو أن النسخة letrec مثل اسمه، let أحد (الذي هو في الحقيقة نفس) يجب أن تكون أسرع لأن هناك أقل الحجج لتمرير حولها في الحلقة. ومع ذلك، من الناحية العملية المجمعين يمكن أن تفعل كل أنواع من التحسينات وراء ظهرك، مثل الرقم إلى أن حلقة في النسخة عادي يمر الحجج الأولين دون تغيير، وتحويله الى حلقة حجة واحدة مع أول واحد. بدلا من أن تظهر لك أرقام على نظام معين، وهنا هو وحدة PLT التي يمكن تشغيلها لآخر أربع صيغ مختلفة، ويمكنك بسهولة إضافة المزيد من الجهود لمحاولة الخروج الاختلافات الأخرى. ملخص قصير هو أن على الجهاز الخاص بي، والنسخة اسمه-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.

وأما عن أداء والقراءة، وهذا الأخير هو على الارجح مسألة ذوق، في حين أن الأول لا تختلف observably (على الرغم من أنني لست مؤهلا حقا أن تصر على هذا الأمر كذلك، وأيضا على أي حال تعتمد على التنفيذ).

وأيضا، فما استقاموا لكم فاستقيموا استخدام اسمه في الواقع 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.