Chuyển đổi sang CPS (Kiểu chuyển tiếp tục)

Question

Làm cách nào để chuyển đổi các thủ tục này trong Sơ đồ thành biểu mẫu CPS?

1. (lambda (x y) 
       ((x x) y)) 
   

2. (lambda (x) 
       (lambda (f) 
       (f (lambda (y) 
        (((x x) f) y)))) 
   

3. ((lambda (x) (x x) 
   (lambda (x) (x x)) 
   

* Đây không phải là bất kỳ bài tập về nhà!

Answer 1

Xem Programming Languages, Application and Interpretation, bắt đầu từ Chương 15. Chương 18 nói về cách tự động thực hiện, nhưng nếu bạn không quen với suy nghĩ về cách diễn đạt chức năng "làm gì tiếp theo", có thể bạn sẽ muốn thử các bài tập ngón tay trước.

Không ai đó làm điều đó cho bạn: bạn thực sự muốn hiểu quy trình và có thể làm điều đó bằng tay, độc lập với Đề án hoặc cách khác. Nó xuất hiện đặc biệt trong lập trình web không đồng bộ JavaScript, nơi bạn thực sự không có lựa chọn nào ngoài việc thực hiện phép biến đổi.

---

Trong phép biến đổi CPS, tất cả các chức năng không nguyên thủy cần phải tiêu thụ một hàm đại diện cho "làm gì tiếp theo". Điều đó bao gồm tất cả lambdas. Đối xứng, bất kỳ ứng dụng nào của một hàm không nguyên thủy cần phải cung cấp một hàm "gì-to-do-next", và phần còn lại của tính toán trong hàm đó.

Vì vậy, nếu chúng ta có một chương trình để tính toán hypothenuse của một tam giác:

(define (hypo a b) 
    (define (square x) (* x x)) 
    (define (add x y) (+ x y)) 

    (sqrt (add (square a) 
      (square b)))) 

và nếu chúng ta nói rằng các ứng dụng nguyên thủy duy nhất ở đây là *, +, và sqrt, sau đó tất cả các định nghĩa chức năng khác và các cuộc gọi chức năng cần được dịch, như sau:

(define (hypo/k a b k) 
    (define (square/k x k) 
    (k (* x x))) 

    (define (add/k x y k) 
    (k (+ x y))) 

    (square/k a 
      (lambda (a^2) 
       (square/k b 
         (lambda (b^2) 
         (add/k a^2 b^2 
           (lambda (a^2+b^2) 
            (k (sqrt a^2+b^2))))))))) 

;; a small test of the function. 
(hypo/k 2 3 (lambda (result) (display result) (newline))) 

Biểu thức cuối cùng cho thấy bạn phải tính toán "từ trong ra ngoài" và chuyển đổi phổ biến: tất cả lambdas trong chương trình nguồn gốc kết thúc cần phải có một đối số bổ sung, và tất cả các ứng dụng không nguyên thủy cần phải nhồi nhét "những gì cần làm tiếp theo" làm đối số đó.

Xem kỹ phần 17.2 của sách được trích dẫn: nó bao gồm điều này, cũng như 17.5, nói về lý do tại sao bạn cần chạm vào TẤT CẢ các lambdas trong chương trình nguồn để trường hợp thứ tự cao hơn cũng hoạt động .

---

Như một ví dụ về sự biến đổi, áp dụng cho một trường hợp bậc cao, giả sử rằng chúng ta có:

(define (twice f) 
    (lambda (x) 
    (f (f x)))) 

Sau đó, bản dịch của một cái gì đó như thế này là:

(define (twice/k f k1) 
    (k1 (lambda ...))) 

... bởi vì lambda đó chỉ là một giá trị có thể được chuyển đến k1. Nhưng tất nhiên, bản dịch cũng cần phải chạy qua lambda.

Trước tiên, chúng tôi phải thực hiện cuộc gọi nội bộ tới f với x (và nhớ rằng tất cả các ứng dụng chức năng không nguyên thủy cần phải chuyển "thích hợp làm gì tiếp theo" thích hợp!"):

(define (twice/k f k1) 
    (k1 (lambda (x k2) 
     (f x (lambda (fx-val) 
       ...))))) 

... mất giá trị đó và áp dụng nó một lần nữa để e ...

(define (twice/k f k1) 
    (k1 (lambda (x k2) 
     (f x (lambda (fx-val) 
       (f fx-val ...)))))) 

... và cuối cùng trở về giá trị đó để k2:

(define (twice/k f k1) 
    (k1 (lambda (x k2) 
     (f x (lambda (fx-val) 
       (f fx-val k2)))))) 

;; test. Essentially, ((twice square) 7) 
(define (square/k x k) (k (* x x))) 
(twice/k square/k 
     (lambda (squaresquare) 
      (squaresquare 7 
         (lambda (seven^4) 
          (display seven^4) 
          (newline))))) 

Answer 2

Bạn cần chọn mức độ nào bạn cần/muốn chuyển đổi CPS.

Nếu bạn chỉ muốn (lambda (x y) ((x x) y)) trong liên tục kiểu chuyển động (CP), sau đó (lambda (k x y) (k ((x x) y))) sẽ hoạt động tốt.

Nếu bạn muốn đối số của nó được xử lý theo kiểu CP, thì bạn cần thêm một chút nữa.

Giả sử đầu tiên mà chỉ đối số thứ hai (y) ở dạng CP và do đó thực sự giống như (lambda (k) (k y0)) và do đó cần phải được gọi với một số tiếp tục để trích xuất giá trị của nó, sau đó bạn sẽ cần:

(lambda (k x y) 
    (y (lambda (y0) (k ((x x) y0))))) 

Cuối cùng giả định rằng cả x và y đều theo kiểu CP. Sau đó, bạn sẽ cần một cái gì đó như:

(lambda (k x y) 
    (x (lambda (x0) 
     (x (lambda (x1) 
      (y (lambda (y0) 
       (k ((x0 x1) y0)))))) 

Ở đây bạn có thể tự do sắp xếp lại các cuộc gọi đến và xy. Hoặc có thể bạn chỉ cần một cuộc gọi đến x, bởi vì bạn biết giá trị của nó không phụ thuộc vào việc tiếp tục nó được gọi với. Ví dụ:

(lambda (k x y) 
    (y (lambda (y0) 
     (x (lambda (x0) 
      (k ((x0 x0) y0)))))) 

Các biểu thức khác mà bạn hỏi về có thể được chuyển đổi tương tự.