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 system was discovered by Haskell Curry in his doctoral thesis Grundlagen der kombinatorischen Logik, whose results are set out in Curry (1930).

It has expressive power equivalent to that of S, K, I system. Both systems are fully interchangeable.

When compiling to combinators, an implementation may equally choose one system or the other, or both, as it helps shorten the encodings of functions. For example, the encodings of C exclusively in terms of S,K,I, as well as of S in B,C,W,K are long and complicated, as can be seen below, while their corresponding computational machine implementations are equally trivial. It can be worth it to add additional interpretation rules, allowing for much shorter code which can lead to more efficient execution.


From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by Nelliwinne