Y combinator thảo luận trong "The Little Schemer"

Question

Vì vậy, tôi đã dành rất nhiều thời gian đọc và đọc lại kết thúc của chương 9 trong The Little Schemer, trong đó ứng dụng Y combinator được phát triển cho các chức năng length . Tôi nghĩ rằng sự nhầm lẫn của tôi nắm một tuyên bố duy nhất tương phản hai phiên bản có độ dài (trước khi combinator là yếu tố ra):

A: 
    ((lambda (mk-length) 
    (mk-length mk-length)) 
    (lambda (mk-length) 
    (lambda (l) 
     (cond 
     ((null? l) 0) 
     (else (add1 
       ((mk-length mk-length) 
       (cdr l)))))))) 

B: 
((lambda (mk-length) 
     (mk-length mk-length)) 
    (lambda (mk-length) 
     ((lambda (length) 
     (lambda (l) 
      (cond 
      ((null? l) 0) 
      (else (add1 (length (cdr l))))))) 
     (mk-length mk-length)))) 

Page 170 (4th ed.) bang rằng A

trả về một chức năng khi chúng ta áp dụng nó để một cuộc tranh cãi

trong khi B

không RET urn a function

do đó tạo ra sự hồi quy vô hạn của tự ứng dụng. Tôi bị bối rối bởi điều này. Nếu B bị cản trở bởi vấn đề này, tôi không thấy A tránh nó như thế nào.

Answer 1

Câu hỏi hay. Đối với lợi ích của những người không có một cài đặt DrRacket hoạt động (bản thân tôi bao gồm) Tôi sẽ cố gắng trả lời nó.

Trước tiên, hãy sử dụng tên lành mạnh, dễ dàng theo dõi được bằng một con mắt/tâm trí con người:

((lambda (h)  ; A. 
    (h h))   ; apply h on h 
(lambda (g) 
    (lambda (lst) 
     (if (null? lst) 0 
     (add1 
       ((g g) (cdr lst))))))) 

Thuật ngữ lambda đầu tiên là những gì được gọi là omega combinator. Khi áp dụng vào một cái gì đó, nó gây ra tự ứng dụng của thuật ngữ đó. Do đó, ở trên là tương đương với

(let ((h (lambda (g) 
      (lambda (lst) 
      (if (null? lst) 0 
       (add1 ((g g) (cdr lst)))))))) 
    (h h)) 

Khi h được áp dụng trên h, mới ràng buộc được hình thành:

(let ((h (lambda (g) 
      (lambda (lst) 
      (if (null? lst) 0 
       (add1 ((g g) (cdr lst)))))))) 
    (let ((g h)) 
    (lambda (lst) 
      (if (null? lst) 0 
       (add1 ((g g) (cdr lst))))))) 

Bây giờ không có gì là áp dụng nữa, vì vậy hình thức bên trong lambda được trả lại - cùng với các các mối liên kết ẩn với các khung môi trường (nghĩa là các liên kết cho phép) ở trên nó.

Việc ghép nối biểu thức lambda này với môi trường xác định của nó được gọi là closure. Đối với thế giới bên ngoài, nó chỉ là một hàm khác của một tham số, lst. Không còn nhiều bước giảm nữa để thực hiện tại thời điểm này.

Bây giờ, khi đóng cửa - chức năng list-length - sẽ được gọi, thực hiện cuối cùng sẽ đến điểm (g g) tự bôi, và các bước giảm tương tự như được nêu ở trên sẽ lại được thực hiện. Nhưng không sớm hơn.

---

Bây giờ, các tác giả của cuốn sách mà muốn đến tại combinator Y, vì vậy họ áp dụng một số biến đổi mã trên các biểu hiện đầu tiên, bằng cách nào đó sắp xếp cho rằng tự ứng dụng (g g) được thực hiện tự động - vì vậy chúng tôi có thể viết ứng dụng hàm đệ quy một cách bình thường, (f x), thay vì phải viết nó như ((g g) x) cho tất cả các cuộc gọi đệ quy:

((lambda (h)  ; B. 
    (h h))   ; apply h on h 
(lambda (g) 
    ((lambda (f)   ; 'f' to become bound to '(g g)', 
     (lambda (lst) 
     (if (null? lst) 0 
      (add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x)! 
    (g g))))      ; (this is not quite right) 

Bây giờ sau vài bước giảm chúng đến

(let ((h (lambda (g) 
      ((lambda (f)  
       (lambda (lst) 
       (if (null? lst) 0 
        (add1 (f (cdr lst)))))) 
      (g g))))) 
    (let ((g h)) 
    ((lambda (f) 
     (lambda (lst) 
      (if (null? lst) 0 
       (add1 (f (cdr lst)))))) 
    (g g)))) 

tương đương với

(let ((h (lambda (g) 
      ((lambda (f)  
       (lambda (lst) 
       (if (null? lst) 0 
        (add1 (f (cdr lst)))))) 
      (g g))))) 
    (let ((g h)) 
    (let ((f (g g)))   ; problem! (under applicative-order evaluation) 
     (lambda (lst) 
      (if (null? lst) 0 
       (add1 (f (cdr lst)))))))) 

Và ở đây có vấn đề: tự áp dụng (g g) được thực hiện quá sớm, trước rằng lambda bên trong có thể được thậm chí trở lại, như một đóng cửa, vào run- hệ thống thời gian. Chúng tôi chỉ muốn nó được giảm khi thực hiện đến thời điểm đó bên trong biểu thức lambda, sau khi đóng cửa được gọi. Để giảm nó trước khi việc đóng cửa thậm chí còn được tạo ra là vô lý. A lỗi tinh tế. :)

Tất nhiên, kể từ khi g là ràng buộc để h, (g g) được giảm xuống (h h) và chúng tôi lại một lần nữa, nơi chúng tôi bắt đầu, áp dụng h trên h. Looping.

---

Tất nhiên tác giả nhận thức được điều này. Họ muốn chúng tôi để hiểu điều đó.

Vì vậy, thủ phạm rất đơn giản - đó là applicative order of evaluation: đánh giá lập luận trước các ràng buộc được hình thành thông số chính thức của chức năng và đối số của nó của giá trị.

Chuyển đổi mã đó không hoàn toàn đúng. Nó có thể đã hoạt động dưới normal order nơi các đối số không được đánh giá trước.

này được khắc phục một cách dễ dàng đủ bởi "eta-expansion", mà trì hoãn việc thi công cho đến thời điểm cuộc gọi thực tế: (lambda (x) ((g g) x)) thực sự nói: "sẽ gọi ((g g) x) khi kêu gọi với một cuộc tranh cãi của x".

Và đây thực sự là những gì mà biến dạng mã cần phải có được ở nơi đầu tiên:

((lambda (h)  ; C. 
    (h h))   ; apply h on h 
(lambda (g) 
    ((lambda (f)   ; 'f' to become bound to '(lambda (x) ((g g) x))', 
     (lambda (lst) 
     (if (null? lst) 0 
      (add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x) 
    (lambda (x) ((g g) x))))) 

Bây giờ bước giảm tiếp theo có thể được thực hiện:

(let ((h (lambda (g) 
      ((lambda (f)  
       (lambda (lst) 
       (if (null? lst) 0 
        (add1 (f (cdr lst)))))) 
      (lambda (x) ((g g) x)))))) 
    (let ((g h)) 
    (let ((f (lambda (x) ((g g) x)))) 
     (lambda (lst) 
      (if (null? lst) 0 
       (add1 (f (cdr lst)))))))) 

và việc đóng cửa (lambda (lst) ...) được hình thành và trả lại mà không có vấn đề gì, và khi (f (cdr lst)) được gọi (bên trong đóng) nó được giảm xuống ((g g) (cdr lst)) giống như chúng tôi muốn.

---

Cuối cùng, chúng tôi nhận thấy rằng (lambda (f) (lambda (lst ...)) biểu hiện trong C. không phụ thuộc vào bất kỳ h và g. Vì vậy, chúng ta có thể lấy nó ra, làm cho nó một cuộc tranh cãi, và bị bỏ lại với ... các combinator Y:

(((lambda (rec)   ; D. 
     ((lambda (h) (h h)) 
     (lambda (g) 
      (rec (lambda (x) ((g g) x)))))) ; applicative-order Y combinator 
    (lambda (f)  
     (lambda (lst) 
      (if (null? lst) 0 
      (add1 (f (cdr lst))))))) 
    (list 1 2 3))       ; ==> 3 

Vì vậy, bây giờ, gọi Y trên một chức năng tương đương với việc một định nghĩa đệ quy ra khỏi nó:

(y (lambda (f) (lambda (x) .... (f x) ....))) 
=== define f = (lambda (x) .... (f x) ....) 

... nhưng sử dụng letrec (hoặc tên let) là tốt hơn - hiệu quả hơn, defining the closure in self-referential environment frame. Điều Y toàn bộ là một bài tập lý thuyết cho các hệ thống mà không thể — tức là nơi không thể tên điều này, để tạo các liên kết với tên "trỏ" vào mọi thứ, đề cập đến mọi thứ.

Ngẫu nhiên, khả năng điểm để điều là những gì phân biệt các loài linh trưởng cao hơn từ phần còn lại của thế giới động vật ⁄ sinh vật sống, hoặc vì vậy tôi nghe. :)

Answer 2

Để xem điều gì xảy ra, hãy sử dụng stepper trong DrRacket. Các bước cho phép bạn xem tất cả các bước trung gian (và để đi qua lại).

Dán đoạn mã sau vào DrRacket:

(((lambda (mk-length) 
    (mk-length mk-length)) 
    (lambda (mk-length) 
    (lambda (l) 
     (cond 
     ((null? l) 0) 
     (else (add1 
       ((mk-length mk-length) 
       (cdr l)))))))) 
'(a b c)) 

Sau đó, chọn ngôn ngữ giảng dạy "Intermediate Student với lambda". Sau đó nhấp vào nút stepper (hình tam giác màu xanh lá cây tiếp theo là một thanh).

Đây là những gì bước đầu tiên trông giống như:

Sau đó làm một ví dụ cho các chức năng thứ hai và xem những gì khó khăn.