Làm thế nào để bạn làm letcc trong Clojure?

Question

Trong cuốn sách The Seasoned Schemer - tác giả viết đoạn mã sau:

(define intersectall 
    (lambda (lset) 
    (letcc hop 
     (letrec 
      ((A (lambda (lset) 
       (cond 
        ((null? (car lset)) (hop (quote()))) 
        ((null? (cdr lset)) (car lset)) 
        (else 
        (intersect (car lset) 
           (A (cdr lset)))))))) 
     (cond 
      ((null? lset) (quote())) 
      (else (A lset))))))) 

Đây là tiềm năng như thế nào nó có thể tìm trong Clojure:

(defmacro letcc 
    [name & body] 
    `(letfn [(~name [arg#] 
      (throw (ex-info (str '~name) {:name '~name :value arg#})))] 
    (try ~@body 
      (catch clojure.lang.ExceptionInfo e# 
      (if (= '~name (:name (ex-data e#))) 
       (:value (ex-data e#)) 
       (throw e#)))))) 

(defn intersectall 
    [lset] 
    (letcc hop 
    (letfn [(A [lset] 
      (cond (empty? (first lset)) 
        (hop()) 
        (empty? (rest lset)) 
        (first lset) 
        :else 
        (intersect (first lset) (A (rest lset)))))] 
    (cond (empty? lset) 
      () 
      :else 
      (A lset))))) 

Câu hỏi của tôi là: Làm thế nào để bạn làm letcc trong Clojure ?

Answer 1

nền

Cốt lõi ngôn ngữ Clojure không hỗ trợ continuations hạng nhất. Điều đó, và thực tế là JVM không cung cấp một cách để nắm bắt sự tiếp tục hiện tại, có nghĩa là không có cách nào để thực hiện letcc là thỏa đáng cho mọi tình huống.

Tuy nhiên, có thể triển khai tiếp tục trong một số trường hợp. Cụ thể, nếu bạn sở hữu tất cả các mã (có nghĩa là, mã mà bạn phải nắm bắt liên tục) thì bạn có thể sử dụng kiểu chuyển tiếp (CPS). Về cơ bản, bạn thêm một tham số bổ sung cho mỗi hàm. Tham số này là một hàm đại diện cho sự tiếp tục của cuộc gọi đó. Bạn "trả về" một giá trị bằng cách gọi hàm tiếp tục. Tất nhiên, phong cách này là một nỗi đau để viết của chính nó - nhưng may mắn thay đây là một biến đổi chúng ta có thể dễ dàng áp dụng cho mã cụ thể thông qua các macro.

Bản thân, CPS không phù hợp với các nền tảng không thực hiện tối ưu hóa cuộc gọi đuôi (TCO). Bởi vì bước cuối cùng của bất kỳ hàm nào trong CPS là gọi một hàm khác, mà không có TCO ngăn xếp nhanh chóng tràn ra ngoài trừ các tính toán nhỏ nhất. Vấn đề này có thể được giải quyết bằng cách sử dụng thunking và trampolining.

Giải pháp

Như tôi đã nói ở trên, bạn có thể viết biến đổi CPS của riêng bạn bằng macro. Tuy nhiên, tôi sẽ mời bạn thanh toán thư viện pulley.cps của tôi, thư viện này đã thực hiện việc này cho bạn. Có giải pháp thay thế, nhưng như xa như tôi pulley.cps biết là thư viện Clojure duy nhất cung cấp tất cả các nội dung sau:

• call-cc/let-cc
• cuộc gọi tự động giữa các "bản địa" (không chuyển đổi) và chuyển đổi đang
• Exception (try/catch/finally) hỗ trợ
• binding hình thức (họ đang đúng đuôi-đệ quy quá!)
• cho phép bạn để cung cấp một versio CPS n của một chức năng gốc hiện có (điều này là cần thiết nếu bạn muốn chụp một sự tiếp nối trong phạm vi chức năng đó)

Alternatives bao gồm:

• delimc cung cấp một thư viện cho continuations phân cách. Điều này có vẻ không hoàn chỉnh (ví dụ: binding không thành công vì nó không hiểu khối try/finally) và chưa được xúc động trong 4 năm.
• algo.monads là thư viện đơn lẻ cho Clojure. Có một mối quan hệ mạnh mẽ và thú vị giữa các monads và continuations, và algo.monads cung cấp một đơn nguyên tiếp tục.Mặc dù phong cách monadic không hoàn toàn giống như giao ước, nó có lợi thế là làm cho hiệu ứng rõ ràng hơn, có thể hỗ trợ trong việc gói gọn mã sử dụng hiệu ứng điều khiển từ mã không. Ngoài ra, ký hiệu do (ví dụ: macro domonad) làm mờ các đường thẳng giữa kiểu trực tiếp và đơn sắc.

Answer 2

Việc tiếp tục bị bắt bởi (letcc hop ...) trong ví dụ của bạn được sử dụng làm "tiếp tục tăng lên". Người ta có thể đã sử dụng tên return thay vào đó: (letcc return ... (return() ...). Khi sự tiếp tục có tên là return được gọi, toàn bộ biểu thức letcc đánh giá giá trị được gán cho return - sau đó được trả lại là kết quả của intersectall.

Điều này có nghĩa là 1. sự tiếp tục tăng lên (chúng tôi trả lại) và 2. việc tiếp tục chỉ được sử dụng một lần. Khi các điều kiện này được đáp ứng, người ta có thể thực hiện letcc về mặt số try và catch như bạn đã làm.

Vì vậy, như tôi thấy, bằng cách viết macro letcc của bạn, bạn đã trả lời câu hỏi của riêng bạn.

Bây giờ, Nathan Davis đề cập đến các trường hợp sử dụng khác là tiếp tục, nhưng Clojure không hỗ trợ chúng trực tiếp.

Lưu ý: Có một câu hỏi có liên quan ở đây: The Seasoned Schemer, letcc and guile