combinatorsa

Combinators are a fundamental concept in theoretical computer science, particularly in lambda calculus. They are functions that take other functions as arguments and return new functions. The key characteristic of combinators is that they do not refer to any arguments explicitly, meaning they are "name-free". This property allows them to be used to build complex computations without needing to bind variables.

The most well-known combinators are the SKI combinator calculus, consisting of three primitive combinators: S, K, and I. The S combinator, or "substitution" combinator, is defined as Sxyz = xz(yz). It takes three arguments, applies the first argument to the third argument, and then applies the result to the application of the second argument to the third argument. The K combinator, or "constant" combinator, is defined as Kxy = x. It takes two arguments and always returns the first argument, discarding the second. The I combinator, or "identity" combinator, is defined as Ix = x. It simply returns its argument unchanged.

These three combinators, S, K, and I, are sufficient to express any computable function. This means that the SKI calculus is a functionally complete system. By combining these basic combinators in various ways, one can construct all possible lambda expressions, and therefore, all possible programs. Combinators have applications in functional programming languages, compiler design, and the study of computability. They provide a way to understand computation in a very abstract and foundational manner, free from the complexities of variable binding and explicit argument manipulation.