Combinatory logic

:This article is about a topic in mathematical logic and theoretical computer science, and is not to be confused with combinatorial logic, a topic in electronics.

Combinatory logic in computing

In computer science, combinatory logic is used as a simplified model of computation, used

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

in computability theory (the study of what can be computed) and proof theory (the study of what can be mathematically proven.) The theory, despite its simplicity, captures many essential features of the nature

Related Topics:
Computability theory - Proof theory - Proven

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

of computation.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Combinatory logic can be looked at as a variation of the lambda calculus, in which lambda expressions (used to allow for functional abstraction) are replaced by a limited set of combinators, primitive functions which contain no free variables. It is easy to transform lambda expressions into combinator expressions, and since combinator reduction is much simpler than lambda reduction, it has been used as the basis for the implementation of some non-strict functional programming languages in software and hardware.

Related Topics:
Lambda calculus - Free variable - Non-strict - Functional programming - Hardware

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It can also be looked at in a number of other manners, with many early papers showing the equivalence of various combinators to various logic axioms .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~