B,C,K,W系统

Haskell Curry 在他的1930年博士论文《Grundlagen der kombinatorischen Logik》中提议了一个組合子邏輯系統。它带有基本组合子 B、C、K 和 W（采用了现在的命名）。

定義

• B x y z = x (y z)
• C x y z = x z y
• K x y = x
• W x y = x y y

直觉上，

• B x y 是函数复合 x o y
• C x y z 交换参数 y 和 z
• K x y 忽略第二个参数 y
• W x y 复制参数 y

在當代，只有兩個基本組合子 K 和 S 的SKI組合子演算成為了組合子邏輯的規范方式。B, C 和 W 可以使用 S 和 K 表達為如下：

• B = S (K S) K
• C = S (S (K (S (K S) K)) S) (K K)
• K = K
• W = S S (K (S K K))

在另一個方向上，SKI 可以依據 B,C,K,W 定義為：

• I = W K
• K = K
• S = B (B (B W) C) (B B) = B (B B B W B) C

参见

• 组合子逻辑
• SKI組合子演算

引用

• Hendrik Pieter Barendregt (1984) The Lambda Calculus, Its Syntax and Semantics, Vol. 103 in Studies in Logic and the Foundations of Mathematics. North-Holland. ISBN 0-444-87508-5
• Haskell Curry (1930) "Grundlagen der kombinatorischen Logik," Amer. J. Math. 52: 509-536; 789-834.
• Curry, Haskell B.; J. Roger Hindley, and Jonathan P. Seldin. Combinatory Logic Vol. II 2. Amsterdam: North Holland. 1972. ISBN 0-7204-2208-6. 
• Raymond Smullyan (1994) Diagonalization and Self-Reference. Oxford Univ. Press.

外部鏈接

• Keenan, David C. (2001) "To Dissect a Mockingbird."
• Rathman, Chris, "Combinator Birds."
• ""Drag 'n' Drop Combinators (Java Applet)."