Combinatory logic

Definition

Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages. It is based on combinators, which were introduced by Schönfinkel in 1920 with the idea of providing an analogous way to build up functions—and to remove any mention of variables—particularly in predicate logic. A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.

Related concepts

APL (programming language)Alonzo Church Applicative computing systems Associative B, C, K, W System B, C, K, W system Belgium Beta normal form Big O notation Cambridge University Press Categorical abstract machine Church encoding Church–Turing thesis Combinational logic Combinatory categorial grammar Computability theory Computable function Computation Computer science Curry–Howard isomorphism Cylindric algebra Dana Scott David Turner (computer scientist)Deduction theorem Elsevier Explicit substitution Expressive power (computer science)Extensional equality First-order logic Fixed point combinator Formal parameter Free variable Free variables and bound variables Function application Function type Functional programming Functional programming languages Graph reduction machine Harvard University Press Haskell Curry Henk Barendregt Higher-order function Hilbert-style deduction system Identity function Inclusion (set theory)Intuitionistic logic Iota and Jot J. Roger Hindley J programming language Jean van Heijenoort Journal of Symbolic Logic Katalin Bimbó Kenneth E. Iverson Kripke semantics Lambda calculus Lawrence Paulson Mathematical logic Model of computation Model theory Moses Schönfinkel Non-strict programming language Normal form (abstract rewriting)North-Holland Publishing Company Oxford University Press Peter G. Harrison Predicate functor logic Predicate logic Princeton University Proof theory Q.E.D.Quantifier (logic)Raymond Smullyan Recursion Rice's theorem Robert Feys SASL programming language SKI combinator calculus Stanford Encyclopedia of Philosophy Stephen Wolfram Supercombinator Tacit programming To Mock a Mockingbird Turing machine Unlambda Up to Willard Van Orman Quine Wolfram Media YouTube

15 concepts already in your glossary