Lợi ích của letrec là gì?

Question

Khi đọc "Schemer dày dặn", tôi đã bắt đầu tìm hiểu về letrec. Tôi hiểu những gì nó làm (có thể được nhân đôi với một Y-Combinator) nhưng cuốn sách đang sử dụng nó thay cho định kỳ trên chức năng đã define d hoạt động trên các đối số vẫn còn tĩnh.

Một ví dụ về một chức năng cũ bằng cách sử dụng define d chức năng định kỳ trên chính nó (không có gì đặc biệt):

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

Bây giờ cho một ví dụ về chức năng tương tự nhưng sử dụng 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))) 

Ngoài từ được hơi lâu hơn và khó đọc hơn Tôi không biết tại sao họ đang viết lại các chức năng trong cuốn sách để sử dụng letrec. Có một tăng cường tốc độ khi định kỳ trên một biến tĩnh theo cách này bởi vì bạn không tiếp tục vượt qua nó ??

Thực hành tiêu chuẩn này cho các hàm có đối số vẫn tĩnh nhưng một đối số được giảm (chẳng hạn như định kỳ lại các phần tử của danh sách)?

Một số đầu vào từ các Schemers/LISPers có kinh nghiệm hơn sẽ hữu ích!

Answer 1

Vì vậy, bạn có một vài câu trả lời bao gồm vấn đề về khả năng đọc, điều này sẽ ổn. Nhưng một câu hỏi không rõ ràng là liệu có bất kỳ vấn đề hiệu suất nào không. Trên một cái nhìn nông, có vẻ như phiên bản letrec, giống như tên let (thực sự giống nhau) nên nhanh hơn vì có ít đối số hơn để truyền xung quanh trong vòng lặp. Tuy nhiên, trong các trình biên dịch thực hành có thể thực hiện tất cả các loại tối ưu sau lưng của bạn, như tìm ra rằng vòng lặp trong phiên bản thuần tuý vượt qua hai đối số đầu tiên không thay đổi, và biến nó thành một vòng lặp đối số đầu tiên. Thay vì hiển thị cho bạn các con số trên một hệ thống cụ thể, đây là một mô-đun PLT mà bạn có thể chạy đến thời gian bốn phiên bản khác nhau và bạn có thể dễ dàng thêm nhiều hơn nữa để thử các biến thể khác. Tóm tắt ngắn gọn là trên máy của tôi, phiên bản có tên let nhanh hơn một chút và làm cho nó có tính đệ quy đuôi có lợi ích tổng thể lớn hơn.

#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

Về ví dụ cụ thể: Cá nhân tôi tìm thấy phiên bản letrec dễ đọc hơn: bạn xác định hàm trợ giúp đệ quy và bạn gọi nó trong phần nội dung của hàm cấp cao nhất. Sự khác biệt chính giữa hai biểu mẫu là ở dạng letrec bạn không phải chỉ định các đối số tĩnh lặp đi lặp lại trong các cuộc gọi đệ quy, mà tôi thấy rõ hơn.

Nếu mã được biên dịch, tránh việc truyền tham số tĩnh trên mỗi cuộc gọi hàm đệ quy cũng có thể cung cấp lợi ích hiệu suất nhỏ trong trường hợp này vì người gọi tránh phải sao chép đối số vào khung ngăn xếp mới. Nếu cuộc gọi hàm đệ quy ở vị trí đuôi, trình biên dịch có thể đủ thông minh để tránh sao chép các đối số trên ngăn xếp lặp đi lặp lại.

Tương tự, nếu mã được giải thích, có ít đối số hơn trong các cuộc gọi đệ quy sẽ nhanh hơn.

Nói chung, một trong những lợi ích chính của letrec, mà tôi không nghĩ rằng bạn đã đề cập ở trên, là thực tế là nó cho phép các định nghĩa hàm đệ quy lẫn nhau. Tôi khá thiếu kinh nghiệm với sơ đồ, nhưng theo như tôi hiểu, đây là một trong những tính năng chính của biểu mẫu letrec so với ví dụ: define.

Answer 3

Vì một điều, phiên bản letrec cho phép bạn sử dụng chức năng ngay cả khi tên chung của nó được đặt lại thành một cái gì đó khác, ví dụ:

(define substitute 
    ; stuff involving letrec 
) 

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

Sau đó sub sẽ vẫn làm việc, trong khi đó nó sẽ không có phiên bản không letrec.

Đối với hiệu suất và khả năng đọc, sau này có thể là một vấn đề của hương vị, trong khi trước đây không nên khác nhau quan sát (mặc dù tôi không thực sự đủ điều kiện để nhấn mạnh điều này như vậy, và cũng có thể thực hiện phụ thuộc anyway).

Ngoài ra, tôi thực sự sử dụng tên let cá nhân:

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

Tôi tìm thấy nó dễ đọc hơn theo cách này. YMMV.