The Little âm mưu evens chỉ * & co

Question

Tôi đang gặp khó khăn trong việc hiểu những gì đang xảy ra với evens-only*&co dụ The Little âm mưu của trên trang 145.

Dưới đây là các mã:

(define evens-only*&co 
(lambda (l col) 
    (cond 
    ((null? l) 
    (col '() 1 0)) 
    ((atom? (car l)) 
    (cond 
     ((even? (car l)) 
     (evens-only*&co (cdr l) 
        (lambda (newl product sum) 
         (col (cons (car l) newl) 
          (opx (car l) product) 
          sum)))) 
     (else 
     (evens-only*&co (cdr l) 
        (lambda (newl product sum) 
         (col newl product (op+ (car l) sum))))))) 
    (else 
    (evens-only*&co (car l) 
        (lambda (newl product sum) 
        (evens-only*&co (cdr l) 
            (lambda (dnewl dproduct dsum) 
             (col (cons newl dnewl) 
              (opx product dproduct) 
              (op+ sum dsum)))))))))) 

Các ban đầu col có thể :

(define evens-results 
(lambda (newl product sum) 
    (cons sum (cons product newl)))) 

gì tôi không nhận được là, với l như '((1) 2 3), nó đi ngay lập tức vào trận chung kết else với (car l) là (1) và (cdr l) là (2 3). Tốt, nhưng tâm trí của tôi bị trống khi cố gắng phân loại ra dnewl, dproduct, dsum từ newl, product, sum. Nó cũng sẽ hữu ích nếu ai đó có thể huấn luyện tôi về cách thiết lập DrRacket hoặc Chez Scheme hoặc MIT-Scheme để chạy một stepper.

Nhưng có thể tôi đã quá sớm. Có phải người mới bắt đầu đọc sách này lần đầu tiên thực sự phải hiểu sự tiếp tục hoang dã này không?

Answer 1

Tôi thấy phần này khó hiểu khi đọc lần đầu tiên và chỉ bắt đầu đọc sau khi tôi đọc ở nơi khác về tiếp tục và kiểu chuyển tiếp liên tục (đây là những gì đây).

Có nguy cơ giải thích điều gì đó mà bạn đã nhận được, một cách nhìn vào nó giúp tôi nghĩ đến "người sưu tập" hoặc "tiếp tục" thay thế cách thông thường cho hàm trả về giá trị. Trong phong cách lập trình thông thường, bạn gọi một hàm, nhận một giá trị và làm điều gì đó với nó trong người gọi. Ví dụ, hàm đệ quy tiêu chuẩn length bao gồm cụm từ (+ 1 (length (cdr list))) cho trường hợp không trống. Điều đó có nghĩa là khi một lần (length (cdr list)) trả về một giá trị, có một tính toán đang chờ xảy ra với bất kỳ giá trị nào nó tạo ra, mà chúng ta có thể nghĩ là (+ 1 [returned value]). Trong chương trình bình thường, trình thông dịch theo dõi các tính toán đang chờ xử lý này, có xu hướng "xếp chồng lên nhau", như bạn có thể thấy trong vài chương đầu tiên của cuốn sách. Ví dụ, khi tính toán độ dài của một danh sách đệ quy, chúng ta có một tổ "tính toán chờ đợi" như nhiều cấp độ sâu khi danh sách dài.

Trong kiểu chuyển tiếp liên tục, thay vì gọi hàm và sử dụng kết quả trả về trong hàm gọi, chúng tôi cho biết chức năng cần làm khi tạo giá trị bằng cách cung cấp chức năng "tiếp tục" để gọi. (Điều này tương tự như những gì bạn phải làm với các cuộc gọi lại trong lập trình Javascript không đồng bộ, ví dụ: thay vì viết result = someFunction(); bạn viết someFunction(function (result) { ... }) và tất cả mã sử dụng result đều nằm trong hàm gọi lại).

Đây là length theo kiểu chuyển tiếp liên tục, chỉ để so sánh. Tôi đã gọi tham số tiếp tục return, nên gợi ý cách nó hoạt động ở đây, nhưng hãy nhớ rằng nó chỉ là một biến Scheme bình thường giống như bất kỳ biến nào khác. (Thông thường, tham số tiếp tục được gọi là k theo kiểu này).

(define (length/k lis return) 
    (cond ((null? lis) (return 0)) 
     (else 
     (length/k (cdr lis) 
        (lambda (cdr-len) 
        (return (+ cdr-len 1))))))) 

Có một mẹo hữu ích để đọc loại mã này trong an article on continuations by Little Schemer co-author Dan Friedman. (Xem phần II-5 bắt đầu ở trang 8).Diễn giải, đây là những gì các khoản else trên nói:

tưởng tượng bạn có kết quả của gọi length/k trên (cdr lis), và gọi nó cdr-len, sau đó thêm một và vượt qua các kết quả bổ sung này để tiếp tục của bạn (return) .

Lưu ý rằng đây là gần như chính xác những gì người phiên dịch đã làm trong việc đánh giá (+ 1 (length (cdr lis))) trong phiên bản bình thường của chức năng (ngoại trừ việc nó không nhất thiết phải đặt tên cho kết quả trung gian (length (cdr lis)). Bằng cách vượt qua xung quanh tiếp tục hoặc gọi lại chúng tôi đã thực hiện dòng điều khiển (và tên của các giá trị trung gian) rõ ràng, thay vì yêu cầu thông dịch viên theo dõi nó. thực tế là hàm này tạo ra ba giá trị thay vì một: danh sách lồng nhau với số lẻ đã xóa; sản phẩm của các số chẵn; và tổng các số lẻ. Đây là khoản đầu tiên, nơi (car l) được biết đến là một số chẵn:

(evens-only*&co (cdr l) 
       (lambda (newl product sum) 
        (col (cons (car l) newl) 
         (opx (car l) product) 
         sum))) 

Hãy tưởng tượng rằng bạn có kết quả loại bỏ số lẻ, SỐ CHẴN nhân, và thêm số lẻ từ cdr của danh sách, và gọi cho chúng lần lượt là newl, product và sum. cons số đứng đầu danh sách lên newl (vì đó là số chẵn, nên đi trong kết quả); nhân product bởi người đứng đầu danh sách (kể từ chúng tôi đang tính toán sản phẩm evens); để lại sum một mình; và vượt qua các giá trị ba này để tiếp tục chờ đợi của bạn col.

Đây là trường hợp người đứng đầu danh sách này là một số lẻ:

(evens-only*&co (cdr l) 
       (lambda (newl product sum) 
        (col newl product (op+ (car l) sum)))) 

Như trước đây, nhưng vượt qua cùng các giá trị của newl và product để tiếp tục (tức là "trở lại" họ), cùng với số tiền của sum và người đứng đầu danh sách, vì chúng tôi tổng hợp các số lẻ.

Và đây là người cuối cùng, nơi (car l) là danh sách lồng nhau, và đó là hơi phức tạp do đệ quy kép:

(evens-only*&co (car l) 
       (lambda (newl product sum) 
        (evens-only*&co (cdr l) 
            (lambda (dnewl dproduct dsum) 
            (col (cons newl dnewl) 
             (opx product dproduct) 
             (op+ sum dsum)))))) 

Hãy tưởng tượng bạn có kết quả từ loại bỏ, tổng hợp và thêm các số trong (car l) và gọi những số này newl, product và sum; sau đó hãy tưởng tượng bạn có kết quả từ làm điều tương tự với (cdr l), và gọi cho họ dnewl, dproduct và dsum.Để chờ đợi sự tiếp tục của bạn , hãy cung cấp các giá trị được sản xuất bởi cons ing newl và dnewl (vì chúng tôi đang tạo danh sách danh sách); nhân với nhau product và dproduct; và thêm sum và dsum.

Chú ý: mỗi lần chúng tôi thực hiện cuộc gọi đệ quy, chúng ta xây dựng một sự tiếp nối mới cho cuộc gọi đệ quy, mà "đóng cửa trên" các giá trị hiện tại của các đối số, l, và việc tiếp tục trở lại - col, nói cách khác , bạn có thể nghĩ về chuỗi liên tục mà chúng ta xây dựng trong suốt quá trình đệ quy như mô hình hóa "ngăn xếp cuộc gọi" của một hàm được viết thông thường hơn!

Hy vọng rằng sẽ đưa ra một phần câu trả lời cho câu hỏi của bạn. Nếu tôi đã đi quá ít, chỉ vì tôi nghĩ rằng, sau khi đệ quy chính nó, tiếp tục là ý tưởng thực sự gọn gàng, cởi mở thứ hai trong The Little Schemer và lập trình nói chung.

Answer 2

Tôi đã đọc Chương trình thiết kế (felleisen et.al.). Tôi đang đi qua phần nơi họ xác định các định nghĩa địa phương. Tôi đã viết một mã mà thực hiện các chỉ trên & chỉ sử dụng một định nghĩa địa phương. Đây là những gì tôi đã viết:

(define (evens-only&co l) 
    (local ((define (processing-func sum prod evlst lst) 
      (cond ((null? lst) (cons sum (cons prod evlst))) 
        ((atom? (car lst)) 
        (cond ((even? (car lst)) (processing-func sum (* prod (car lst)) (append evlst (list (car lst))) (cdr lst))) 
         (else 
          (processing-func (+ sum (car lst)) prod evlst (cdr lst))))) 
        (else 
        (local ((define inner-lst (processing-func sum prod '() (car lst)))) 
        (processing-func (car inner-lst) (cadr inner-lst) (append evlst (list (cddr inner-lst))) (cdr lst))))))) 
    (processing-func 0 1 '() l))) 

Để thử nghiệm, khi tôi nhập (evens chỉ & co '((9 1 2 8) 3 10 ((9 9) 7 6) 2)), nó sẽ trả' (38 1920 (2 8) 10 (() 6) 2) như mong đợi trong sơ đồ nhỏ. Tuy nhiên, mã của tôi không thành công trong một điều kiện: khi không có số chẵn, sản phẩm của evens vẫn được hiển thị dưới dạng 1. Ví dụ (chỉ phát sinh & co '((9 1) 3 ((9 9) 7))) trả về '(38 1() (())). Tôi đoán tôi sẽ cần một chức năng bổ sung để khắc phục điều này. @melwasul: Nếu bạn không quen thuộc với định nghĩa địa phương, xin lỗi để đăng bài này ở đây. Tôi đề nghị bạn đọc HTDP quá. Đó là một cuốn sách tuyệt vời cho người mới bắt đầu. Nhưng những người là chuyên gia trong chương trình có thể xin vui lòng gửi ý kiến ​​của họ trên mã của tôi là tốt. Sự hiểu biết của tôi về định nghĩa địa phương có chính xác không?

Answer 3

answer bởi Jon O. là giải thích thực sự tuyệt vời về các khái niệm cơ bản. Mặc dù đối với tôi (và hy vọng, đối với một số người khác nữa), sự hiểu biết về các khái niệm như thế này là dễ dàng hơn nhiều khi họ có một đại diện trực quan.

Vì vậy, tôi đã đặt chuẩn bị hai luồng bảng xếp hạng (tương tự như once I did for multirember&co, bóc tách những gì đang xảy ra trong suốt cuộc gọi của evens-only*&co

khi l là:

'((9 1 2 8) 3 10 ((9 9) 7 6) 2) 

và col là:

(define the-last-friend 
    (lambda (newl product sum) 
     (cons sum (cons product newl)) 
    ) 
) 

Một biểu đồ luồng, phản ánh cách các biến có liên quan trong khác bước erent của đệ quy: Thứ hai dòng chảy biểu đồ, cho thấy sự giá trị thực tế, được thông qua:

Hy vọng của tôi là, câu trả lời này sẽ là một bổ sung khá đến Jon's explanation above.

Answer 4

Trong giả equational (một KRC -like ký hiệu, viết f x y cho cuộc gọi (f x y), nơi nó là rõ ràng), đây là

evens-only*&co l col 
    = col [] 1 0          , IF null? l 
    = evens-only*&co (cdr l) 
        (newl product sum => 
         col (cons (car l) newl) 
          (opx (car l) product) 
          sum)     , IF atom? (car l) && even? (car l) 
    = evens-only*&co (cdr l) 
        (newl product sum => 
         col newl product (op+ (car l) sum))  , IF atom? (car l) 
    = evens-only*&co (car l) 
        (anewl aproduct asum => 
         evens-only*&co (cdr l) 
             (dnewl dproduct dsum => 
              col (cons anewl dnewl) 
               (opx aproduct dproduct) 
               (op+ asum  dsum))) , OTHERWISE 

Đây là một mã CPS thu thập tất cả SỐ CHẴN từ danh sách đầu vào lồng (tức là một cây) trong khi bảo tồn cấu trúc cây, và cũng tìm thấy sản phẩm của tất cả các evens; như đối với phi SỐ CHẴN, nó tổng họ lên:

• nếu l là một danh sách rỗng, ba cơ bản (sắc) giá trị được thông qua như là đối số cho col;

• nếu (car l) là một số chẵn, kết quả xử lý các (cdr l) là newl, product và sum, và sau đó họ được thông qua như các đối số để col trong khi hai đầu được tăng cường bởi consing   ⁄   nhân với (car l) (số chẵn);

• nếu (car l) là một nguyên tử mà không phải là một số chẵn, kết quả xử lý các (cdr l) là newl, product và sum, và sau đó họ được thông qua như các đối số để col với ba một tăng cường bằng cách tổng hợp với (car l) (nguyên tử số chẵn);

• nếu (car l) là một danh sách, kết quả xử lý (car l) là anewl, aproduct và asum, và sau đó kết quả xử lý (cdr l) là dnewl, dproduct và dsum, và sau đó ba kết quả kết hợp là được chuyển làm đối số cho col.

[], 1 và 0 của vụ án cơ sở là những yếu tố bản sắc của monoids danh sách, số dưới nhân, và số dưới Ngoài ra, tương ứng. Điều này chỉ có nghĩa là các giá trị đặc biệt không thay đổi kết quả, khi được kết hợp vào nó.

Là một minh hoạ, cho '((5) 2 3 4) (mà gần như ví dụ trong câu hỏi), nó tạo ra tính

evens-only*&co [[5], 2, 3, 4] col 
= 
col (cons []     ; original structure w only the evens kept in, 
      (cons 2    ; for the car and the cdr parts 
       (cons 4 []))) 
    (opx 1      ; multiply the products of evens in the car and 
      (opx 2 (opx 4 1))) ; in the cdr parts 
    (op+ (op+ 5 0)    ; sum, for the non-evens 
      (op+ 3 0))  

---

Tương tự như my other answer (cho một câu hỏi chị), đây là một cách khác để viết này, với một mã giả phù hợp với patter (với các vệ sĩ):

evens-only*&co = g where 
    g [a, ...xs...] col 
     | pair? a = g a (la pa sa => 
         g xs (ld pd sd => 
             col [la, ...ld...] (* pa pd) (+ sa sd))) 
     | even? a = g xs (l p s => col [ a, ...l... ] (* a p)  s ) 
     | otherwise = g xs (l p s => col   l   p (+ a s) ) 
    g []   col =     col []    1   0 

Nền kinh tế (và đa dạng) của ký hiệu này thực sự làm cho nó rõ ràng hơn, dễ dàng hơn ier to chỉ cần nhìn thấy thay vì bị mất trong từ salad của tên dài cho các hàm và biến, với parens quá tải như dấu tách cú pháp cho dữ liệu danh sách, nhóm khoản (như trong biểu thức cond), tên bindings (trong lambda biểu thức) và các công cụ chỉ định cuộc gọi chức năng tất cả tìm kiếm chính xác giống nhau. Tính đồng nhất của ký hiệu S-biểu thức giúp dễ dàng thao tác bằng máy (ví dụ: read và macro) của lisp là điều bất lợi cho khả năng đọc của con người của nó.