CPS以咖喱語言

Question

CPS如何使用lambda微積分或Ocaml等口頭語言更有意義？從技術上講，所有功能都有一個參數。所以說，我們在一個這樣的語言有另外的CPS版本：

cps-add k n m = k ((+) n m) 

我們這樣稱呼它

(cps-add random-continuation 1 2) 

然後，這是一樣的：

(((cps-add random-continuation) 1) 2) 

我已經看到那裏有兩個調用不是尾調用，實際上是一個複雜的嵌套表達式，(cps-add random-continuation)返回一個值，即一個函數，它會消耗一個數字，然後返回一個函數，它會消耗另一個數字，並且然後將兩者的總和遞送到random-continuation。但是我們不能通過簡單地將它翻譯成CPS來解決這個返回值，因爲我們只能給每個函數一個參數。我們需要至少有兩個人爲繼續和「實際」論證騰出空間。

或者我完全錯過了什麼？

Answer 1

是的，從技術上講，所有函數都可以用一種方法分解爲函數，但是當您想使用CPS時，您所做的唯一事情就是在某個計算點運行continuation方法。

用你的例子，讓我們看看。爲了使事情變得容易一點，我們將cps-add解構成它的正常形式，它只是一個只有一個參數的函數。

（CPS-添加K） - > N - > M = K（（+）納米）在這一點上的延續，K，沒有被評估（

注意這會是混亂的點爲你？）。

這裏我們有一個叫做cps-add k的方法，它接收一個函數作爲參數，然後返回一個帶有另一個參數n的函數。

（（CPS-添加k）的N） - > M = K（（+）n×m個）

現在，我們有一個函數，它的參數，米。

所以我想我要指出的是，咖喱沒有得到CPS風格編程的方式。希望在某種程度上有所幫助。

Answer 2

簡短的回答：當然，這是有道理的，你可以申請一個CPS-直接轉化，你只會有大量的冗餘代碼，因爲每個參數都會有，因爲你注意到沒有，自己的附加延續

在你的榜樣，我認爲有一個+(x,y) uncurried原始的，而且你問什麼是

let add x y = +(x,y) 

翻譯（這add忠實代表OCaml中的(+)運營商）

add是syntaxically相當於

let add = fun x -> (fun y -> +(x, y)) 

所以你申請一個CPStransform¹並獲得

let add_cps = fun x kx -> kx (fun y ky -> ky +(x,y)) 

如果你想翻譯的代碼看起來更像是一些你可能會心甘情願地寫，你就可以設計出更細轉換實際上將已知函數看作非curry函數，並將所有參數作爲一個整體進行調整（就像您使用非curry語言以及功能性編譯器已經出於顯而易見的性能原因所做的那樣）。

¹：我寫了「a CPS變換」，因爲沒有「一個真正的CPS翻譯」。已經設計了不同的翻譯，產生或多或少的與連續相關的垃圾。正式的CPS翻譯通常是直接在lambda演算中定義的，所以我想你正在考慮一個不太正式的，更手工的CPS轉換。

CPS的良好屬性（作爲編程方面的風格，而不是對此風格的具體轉換）是評估的順序是完全明確的，並且所有調用都是尾調用。只要你尊重這些，你就可以做到相對自由。因此特別處理curryfied功能非常好。

備註：如果您認爲編譯器檢測並優化cps-add實際上總是帶3個參數，並且不構建中間閉包，那麼您的(cps-add k 1 2)版本也可以被視爲尾遞歸。這看起來似乎有些牽強，但這與我們在使用這些語言推理非CPS程序中的尾部呼叫時使用的假設完全相同。

Answer 3

既然你已經標記此哈斯克爾，我會在這方面的回答：在Haskell，做CPS變換相當於在Cont單子，其轉換價值x成高階函數工作是採用一個參數並將其應用於x。

所以，首先，這裏是1 + 2規則哈斯克爾：(1 + 2)這裏，它是在延續單子：

contAdd x y = do x' <- x 
       y' <- y 
       return $ x' + y' 

...不是非常翔實。爲了看看發生了什麼，讓我們拆開monad。首先，除去do符號：

contAdd x y = x >>= (\x' -> y >>= (\y' -> return $ x' + y')) 

的return函數升降機一個值到單子，並且在這種情況下被實施爲\x k -> k x，或使用中綴運算符截面\x -> ($ x)。

contAdd x y = x >>= (\x' -> y >>= (\y' -> ($ x' + y'))) 

的(>>=)操作（讀「綁定」）鏈一起計算在單子，並且在這種情況下被實現爲\m f k -> m (\x -> f x k)。更改綁定功能，以前綴的形式，並在拉姆達取代，再加上一些重命名爲清楚：

contAdd x y = (\m1 f1 k1 -> m1 (\a1 -> f1 a1 k1)) x (\x' -> (\m2 f2 k2 -> m2 (\a2 -> f2 a2 k2)) y (\y' -> ($ x' + y'))) 

減少一些功能的應用：

contAdd x y = (\k1 -> x (\a1 -> (\x' -> (\k2 -> y (\a2 -> (\y' -> ($ x' + y')) a2 k2))) a1 k1)) 

contAdd x y = (\k1 -> x (\a1 -> y (\a2 -> ($ a1 + a2) k1))) 

，有點最後的清理和重命名：

contAdd x y = \k -> x (\x' -> y (\y' -> k $ x' + y')) 

換句話說：函數的參數已經從數字變成了函數，該函數需要一個數字並返回整個表達式的最終結果，像你所期望的那樣。

編輯：一位評論者指出，contAdd本身仍然採用咖喱風格的兩個參數。這是明智的，因爲它不直接使用延續，但不是必需的。如果不這樣做，你需要先打散參數的函數關係：

contAdd x = x >>= (\x' -> return (\y -> y >>= (\y' -> return $ x' + y'))) 

，然後用它是這樣的：

foo = do f <- contAdd (return 1) 
     r <- f (return 2) 
     return r 

注意，這是從早期版本確實沒有不同;它只是將每個部分應用程序的結果打包爲一個延續，而不僅僅是最終結果。由於函數是第一類值，因此保持數字的CPS表達式與保持函數的CPS表達式之間沒有顯着差異。

請記住，我在這裏以非常冗長的方式寫出所有步驟，以明確所有步驟，其中某些東西是連續傳遞樣式。

---

附錄：您可能會注意到，最終表達式看起來與monadic表達式的脫糖版非常相似。這並不是巧合，因爲單調錶達式的內在嵌套性使得他們根據先前的值改變計算結構與延續傳遞風格密切相關;在這兩種情況下，你都有某種意義上的因果關係的概念。