Combinatory logic
From Esolang
Combinatory logic is a model by which logical statements can be described as a combination of a small number of primitive elements called combinators. Each combinator is like a function or lambda abstraction, but without any free variables. A "sentence" in combinatory logic is called a combinatory term, and is composed of combinators, free variables, and applications of one combinatory term to another.
Combinatory logic can capture the meaning of any arithmetic or logical statement (and by extension, any non-interactive computer program), making it a Turing-complete computational model. It is often described and/or implemented in terms of rewriting (of graphs, trees, or terms).
Contents |
[edit] Syntax
The syntax commonly used for combinators is like that of the lambda calculus: each combinator only takes one argument (but may yield another combinator which will consume further arguments), application associates to the left, and parentheses are only used for disambiguation, not to delimit an argument list.
[edit] Combinators
In 1924, Moses Schönfinkel devised the three traditional primitive combinators. All other expressions can be formed by application of these combinators to each other:
-
I, the identity combinator. Applied to some combinator x, it simply evaluates to x:
I x = x
-
K, the constant-making combinator. Applied to some combinator x, it yields a combinator that always evaluates to x, no matter what it is applied to:
K x y = x
-
S, the application combinator. Applied to three combinators, it applies each of the first two combinators to the last, then applies the first result of that to the second:
S f g x = f x (g x)
In fact, only two different combinators are strictly necessary; the I combinator can be formed from the S and K combinators:
S K K x = I x = x
[edit] Example
Let's trace through S K K x, both to show that it is equivalent to I x, and just as an example of how combinatory logic works.
First, S applies each of its first two arguments to its last argument, so the expression S K K x can be thought of as reducing to:
K x (K x)
Further, for simplicity's sake, K x can be thought of as yielding a combinator that, when applied to anything, yields x. We'll call this combinator yields-x to demonstrate, even though it wouldn't really be used:
yields-x yields-x
Finally, yields-x is applied to itself. But, no matter what it is applied to, even itself, the result will always be x:
x
So from this we can see that S K K x is equivalent to I x.
