轉換爲CPS（延續傳遞樣式）

Question

如何將Scheme中的這些過程轉換爲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)) 
   

*這不是任何的功課！

Answer 1

請參閱Programming Languages, Application and Interpretation，從第15章開始。第18章討論如何自動完成此操作，但如果您不熟悉如何表達一個執行「接下來要做什麼」的函數，您可能需要先嚐試手指練習。

沒有人爲你做：你真的想了解這個過程，並且能夠獨立於Scheme或其他方式手動完成。特別是在異步JavaScript網頁編程中，你真的別無選擇，只能進行轉換。

---

在CPS變換，所有非基本功能需要消耗現在表示「什麼對DO-未來」的功能。這包括所有的lambda。對稱地，非原始函數的任何應用都需要提供「下一步做什麼」的功能，並在該功能中填充其餘的計算。

所以，如果我們有一個程序來計算一個三角形的hypothenuse：

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

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

，如果我們規定只有原始應用這裏有*，+，並且sqrt，那麼所有其他的函數定義和函數調用需要翻譯，像這樣：

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

最後一個表達式表明，你最終不得不計算「由內向外」，並認爲轉型是很普遍的：所有的lambda表達式在原始源代碼程序中最終需要採取額外的參數，並且所有非原始應用程序都需要填充「下一步做什麼」作爲該參數。

仔細看看引用的書的第17.2節：它涵蓋了這個以及17.5，它講述了爲什麼你需要觸摸源程序中的所有lambda表達式，以便更高階的情況也起作用。

---

作爲另一個例子變換，應用於高階的情況下，讓我們說，我們有：

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

那麼的像這樣的翻譯是：

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

...因爲這個lambda只是一個值，可以傳遞給​​。但是，當然，翻譯也需要貫穿lambda。

我們必須先對f與x進行內部調用（並記住所有非原始函數應用程序都需要傳遞適當的「下一步做什麼！「）：

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

...採取的價值，並再次應用它到f ...

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

...最後該值返回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

你需要選擇你需要的水平/想要CPS轉換。

如果你只想(lambda (x y) ((x x) y)) in continuati傳球（CP）的風格，然後(lambda (k x y) (k ((x x) y)))會做罰款。

如果您希望它的參數也被當作CP樣式，那麼您需要多一點。

首先假設只有第二個參數（y）是CP的形式，因此真的像(lambda (k) (k y0))，因此需要一些延續被調用，以提取其價值，那麼你將需要：

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

最後假設x和y都是CP風格。那麼你就需要這樣的：

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

在這裏，你可以自由地重新排序，以x和y呼叫。或者，也許你只需要撥打x一個電話，因爲你知道它的價值並不取決於它被稱爲的延續。例如：

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

您詢問的其他表達式可以進行類似的轉換。