B,C,K,W system

The B, C, K, W system is a variant of combinatory logic that takes as primitive the combinators B, C, K, and W. This systems was discovered by Haskell Curry in his doctoral thesis "Grundlagen der kombinatorischen Logik", whose results are set out in Curry (1930).

The combinators are defined as follows:

* B "x y z" = "x" ("y z")

* C "x y z" = "x z y"

* K "x y" = "x"

* W "x y" = "x y y"

Intuitively,
* B "x y" is the composition of "x" and "y";
* C "x y z" interchanges the arguments "y" and "z";
* K "x y" "ignores" the argument "y";
* W "x y" duplicates the argument "y".

In recent decades, the SKI combinator calculus, with only two primitive combinators, K and S, has become the canonical approach to combinatory logic. B, C, and W can be expressed in terms of S and K as follows:
*B = ((S(KS))K);
*C = ((S((S(K((S(KS))K)))S))(KK));
*W = (SS(K(SKK))"').

Going the other direction, SKI can be defined in terms of B,C,K,W as:
* "S" = B(B(BW)C)(BB) [Raymond Smullyan (1994) "Diagonalization and Self-Reference". Oxford Univ. Press: 344, 3.6(d).]

ee also

*combinatory logic
* SKI combinator calculus
* Lambda calculus
* To Mock a Mockingbird

References

*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.
*cite book
last = Curry
first = Haskell B.
coauthors = J. Roger Hindley, and Jonathan P. Seldin
title = Combinatory Logic Vol. II
volume = 2
year = 1972
publisher = North Holland
location = Amsterdam
id = ISBN 0-7204-2208-6
*Raymond Smullyan (1994) "Diagonalization and Self-Reference". Oxford Univ. Press.

Notes

External links

* Keenan, David C. (2001) " [http://users.bigpond.net.au/d.keenan/Lambda/index.htm To Dissect a Mockingbird.] "
* Rathman, Chris, " [http://www.angelfire.com/tx4/cus/combinator/birds.html Combinator Birds.] "
* " [http://cstein.kings.cam.ac.uk/~chris/combinators.html "Drag 'n' Drop Combinators (Java Applet).] "